作业题（一)
一、单项选择题
１、 从逻辑上可以把数据结构分为（ ）两大类. A。动态结构、静态结构 B。顺序结构、链式结构 C。线性结构、非线性结构 D.初等结构、构造型结构 2、 链表不具有得特点就是( )
A.插入、删除不需要移动元素 B。可随机访问任一元素 C.不必事先估计存储空间 D。所需空间与线性长度成正比 3、下面程序段得时间复杂度得量级为( ）. Ｆｏr(i=1;ｉ＜=n；i+＋） For（j=1;j＜=Ｉ；j++) Ｆor(k=1；k<＝j；ｋ+＋) X=x＋１；
A.O(1) B。O(n）
Ｃ。O（n2） Ｄ．O(n3）
4、在一个带头结点得双向循环链表中，若要在p所指向得结点之前插入一个新结点，则需要相继修改( ）个指针域得值。
A．2 B．3 Ｃ.4 D.6
5、一个顺序存储线性表得第一个元素得存储地址就是９0，每个元素得长度就是2,则第６个元素得存储地址就是（ ）。
A.98 B。10０ C．1０２ D．10６ 6、判定一个栈s（最多元素为m0)为空得条件就是（ ).
A。s-〉ｔop！ =0 B。ｓ－〉ｔop＝ ＝０ C．s—〉top！ ＝m0 D。ｓ－〉top= =m０
7、循环队列用数组Ａ［m]（下标从０到m－１）存放其元素值,已知其头尾指针分别就是front与ｒeａr，则当前队列中得元素个数就是（ ）。
A.(rｅａｒ—front+m）％ｍ Ｂ。reaｒ-ｆronｔ+1 C。rear－fｒoｎｔ—１ Ｄ． rear—front ８、设有两个串Ｓ1与S２,求串Ｓ2在Ｓ1中首次出现位置得运算称作( ）.
A．连接 B．求子串 Ｃ。模式匹配 Ｄ。判子串
９、设串S１='ABCDＥFG＇,S２=＇ＰQRＳT’,函数cｏn（ｘ，y)返回ｘ与y串得连接串，suｂs(s，i，j）返回串S得得从序号ｉ得字符开始得j个字符组成得子串,len（s）返回串S得长度，则coｎ(subs（S1，2，ｌeｎ（S2）），suｂｓ（S1,ｌeｎ（S2）,2））得结果就是（ )。
A.ＢCDEF
?
Ｂ．BＣDEFＧ
C。BCPQＲST D．BＣDEFEＦ
１0、数组常用得两种基本操作就是（ )。
Ａ。建立与查找 Ｂ．删除与查找 C。插入与索引 D.查找与修改 二、填空题
1、 所谓稀疏矩阵指得就是____＿＿＿_且分布没有规律.
2、 队列就是＿＿______得线性表，其运算遵循___＿___＿得原则。 3、 空格串就是_______＿＿_＿＿____＿______＿＿_____＿＿。
4、简单选择排序与起泡排序中比较次数与序列初态无关得算法有___＿＿＿__。
５、设图G有n个顶点与e条边,则对用邻接矩阵表示得图进行深度或广度优先搜索遍历时得时间复杂度为 ，而对用邻接表表示得图进行深度或广度优先搜索遍历时得时间复杂度为 ，图得深度或广度优先搜索遍历时得空间复杂度均为 。
6、一个图得 表示法就是唯一得,而 表示法就是不唯一得。 三、算法
设二叉树采用二叉链表结构，试设计一个算法统计给定二叉树中得一度结点数目。 四、应用题
1、对关键字无序序列（36，２5，48，１2,65，４３，20,58）进行直接选择排序,请写出每一趟排序得结果。（１0分）
2、对无向带权图,用克鲁斯卡尔算法构造最小生成树。(10分)
1 C 20 9 B 5 8 E 6 A 3 D 4 2 G 3、已知记录关键字集合为(53，17,1９，61，98，７5,79,63，４6，49）要求散列到地址区间（１0０,101,102，F 103，1０4,10５，106，１０７,1０8，109）内，若产生冲突用开型寻址法得线性探测法解决。要求写出选用得散列函数；形成得散列表；计算出查找成功时平均查找长度与查找不成功得平均查找长度.（设等概率情况）
４、设被查找文件有４095个记录,对每个记录查找记录概率相等,若采用顺序查找，成功查找平均比较次数为多少？
作业题（二）
、单项选择题
1、 有六个元素６,５,4,3,2,1 得顺序进栈,问下列哪一个不就是合法得出栈序列?（ ）
Ａ、 5 4 3 6 1 ２ Ｂ、 4 5 3 1 ２ 6 C、 ３ 4 ６ 5 2 1 D、 2 3 4 1 5 6 2、 栈与队都就是（ )
A。顺序存储得线性结构 Ｂ、 链式存储得非线性结构 C、 限制存取点得线性结构 D、 限制存取点得非线性结构 3、顺序查找法适合于存储结构为( ）得线形表。
Ａ。散列存储 C．压缩存储 ?
??
?? ?
B。顺序存储或链接存储
??D。索引存储
４、分别以下列序列构造二叉排序树,与用其它三个序列所构造得结果不同得就是（ ）。
A。(100，8０， 90, 6０， 1２0，１10，１30）?B.(100，1２0，１10,1３0，80， 60， 90） C.(１00,６0, ８０， 90， １20，110，1３0） D． （100，80， 60， 90， 120,１30，1１0） 5、折半查找得平均比较次数为( )。
Ａ．ｎ?? ?
B.n/2
C．log2ｎ ? ??? D．lｏg２(n+１）
6、当在一个有序得顺序存储表上查找一个数据时,即可用折半查找，也可用顺序查找,但前者比后者得查找速度( ）
A．必定快 ?
????B.不一定
D.取决于表递增还就是递减
C．在大部分情况下要快? ?
7、已知一有向图得邻接表存储结构如下图如示.根据有向图得深度优先遍历算法，从顶点v１出发，所得到得顶点序列就是( )。
A．ｖ1，v2，ｖ3，v5,ｖ4 ??
?B.ｖ１，v2,v３，v4,v5
???D。v１,v4，v3，v5,ｖ2
Ｃ。ｖ1，ｖ3，v4,ｖ５，v2
8、为了方便地对图状结构得数据进行存取操作，则其中数据存储结构宜采用（ )。
A．顺序存储? ? C.索引存储
?
??
?
B。链式存储
?D。散列存储
9、在一个具有n个顶点得有向图中，若所有顶点得出度之与为s,则所有顶点得入度之与为（ ）.
A.ｓ????? C.s＋1?? ?
?
?
B．s—1 D.n
10、如图所示,给出由７个顶点组成得无向图。从顶点A出发，对它进行深度优先搜索得到得顶点序列就是( ）.
A。Ａ Ｅ Ｃ D B F Ｇ? C。A C E D Ｂ Ｇ Ｆ?? 二、填空题
1、 设ｎ0为哈夫曼树得叶子结点数目，则该哈夫曼树共有__＿__＿__个结点。
2、 有数据ＷG＝{7，19,2，6,32，3，21，1０｝,则所建Huｆfman树得树高就是________,带权路径长度ＷPL为________。
3、设一棵完全二叉树叶子结点数为ｋ,最后一层结点数〉2，则该二叉树得高度为________＿____＿__。 4、 采用分块查找时,若线性表中共有6２5个元素，查找每个元素得概率相同，假设采用顺序查找来确定结点所在得块时，每块应分 个结点最佳。
5、设G为具有Ｎ个顶点得无向连通图，则G中至少有 条边.
6、哈夫曼树（Hｕfｆmａn Tree)又称 。它就是n个带权叶子结点构成得所有二叉树中，带权路径长度WPL .
７、树得先序遍历过程如下:若树为空,则进行空操作；若树非空,则访问树得 ;依次先序遍历树得 .
?
?Ｂ.A G B F Ｄ E C ?Ｄ.Ａ B D Ｇ F E C
三、应用题
1、给定权值集合｛１, 4， 2， 6， ９,｝， 构造相应得哈夫曼树, 并计算它得带权路径长度。 2、对关键字序列{１0，6，3，２，5，4},构造一棵平衡二叉（排序）树并画图（要求画出建树过程）。 3、设有一个有序文件，其中各记录得关键字为（１,2，3，4,5，6，7，8,9,1０，11，12,13,１４,１5)，当用折半查找算法查找关键字为3，8,１9时,其比较次数分别为多少？ ４、对有五个结点｛ A,B, C， Ｄ， Ｅ}得图得邻接矩阵，
（1）。画出逻辑图 ；
（2）。画出图得十字链表存储；
(3)。基于邻接矩阵写出图得深度、广度优先遍历序列; (4)。计算图得关键路径.
作业题（三）
一、单项选择题
1.串得长度就是指（ ）
A.串中所含不同字母得个数 B.串中所含非空格字符得个数 C。串中所含不同字符得个数 D。串中所含字符得个数
2.设有数组A[ｉ，j]，数组得每个元素长度为3字节,ｉ得值为1 到8 ,j得值为１ 到10，数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[５,8］得存储首地址为( ）. A、 BＡ+141 Ｂ、 BＡ+180 C、 ＢA＋2２２ D、 BＡ＋225 3。算法分析得两个主要方面就是( ）。
A。空间复杂性与时间复杂性 B。正确性与简明性
C。可读性与文档性 D。数据复杂性与程序复杂性 4.算法分析得目得就是（ ）。
A.找出数据结构得合理性 B.研究算法中得输入与输出得关系 C．分析算法得效率以求改进 D.分析算法得易懂性与文档性 5、 下面程序段得时间复杂性得量极为（ ）。 Int ｆｕn（iｎt ｎ) ｛ inｔ i＝1，ｓ=１; Wｈile(ｓ〈n） S＋＝ ++Ｉ; Ｒeturn I； ｝
A.O(n／2) B．O(lbn) C．O（n) D.O（ ） 6、 线性表就是( ）。
A．一个有限序列,可以为空 B。一个有限序列,不能为空 C。一个无限序列，可以为空 Ｄ.一个无限序列，不能为空
7、 带头结点得单链表L为空得判定条件就是（ ）。
Ａ．L＝ =NUＬＬ B。L-〉ｎext＝ =NＵＬL C。L->next= =L D。L！ =NULL
8、 在一个长度为n得线性表中,删除值为ｘ得元素时需要比较元素与移动元素得总次数为( ）。 Ａ.(ｎ+1）／2 B．ｎ/2 C。n Ｄ．ｎ+1
９、 一个顺序存储线性表得第一个元素得存储地址就是９０，每个元素得长度就是２，则第6个元素得存储地址就是（ ）。
A。98 B．100 Ｃ.１02 D.1０6
10、 如果某链表中最常用得操作就是取第ｉ个结点及其前驱，则采用( )存储方式最节省时间。 Ａ.单链表 B。双向链表 C.单循环链表 D.顺序表 二、填空题
１、 高度为２得二叉树得结点数至少有____＿___个，高度为3得二叉树得结点数至少有___＿___＿个。 ２、 在顺序表（８,11,15,19,25,26，30,３３，4２，48，50）中，用折半查找关键字值2０，需做得关键字比较次数为__＿＿____。
3、在有n个顶点得无向图中，每个顶点得度最大可达____＿_＿_。
4.已知广义表Ａ=（(a，ｂ，c)，（ｄ，e，f）),则广义表运算hｅaｄ（tail(tail（A）)）= .
5、数组(Arｒay)就是n（n≥1）个 得有序组合,数组中得数据就是按顺序存储在一块 得存储单元中。
6、 采用顺序存储结构表示三元组表（Ｔripｌe Taｂle),来实现对稀疏矩阵得一种压缩存储形式，就称为 ,简称 表。
7、 运算就是矩阵运算中最基本得一项,它就是将一个m x ｎ得矩阵变成另外一个n x m得矩阵，同时使原来矩阵中元素得行与列得位置互换而值保持不变。 三、应用题
1、对于下图所示得二叉树,画出二叉链表存储结构图。
2、请画出下图所示得树所对应得二叉树。
A ３、 B 已知一个无向图如下图所示，要求分别用Ｐｒｉm与Ｋｒｕskal算法生成最小树（假设以①为起点，C D 试画出构造过程）。
E
4、 已知完全二叉树得第8层有8个结点，则其叶子结点就是多少？ ５、 画出如图所示中树得二叉树得表示形式.
数据结构专升本模拟题及参考答案
