《数据结构》期末复习题答案
1.以下与数据的存储结构⽆关的术语是（ c ）
C、哈希表
2.⼀个向量第⼀个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ）
B、108
3.假设带头结点的单向循环链表的头指针为head，则该链表为空的判定条件是（ C ）
C、head–>next= =head
4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进⾏，则不可能出现的出栈序列是（ D ）
D、2，3，5，1，6，4
5.下列关键字序列中，构成⼩根堆的是（ A ）
A、{12，21，49，33，81，56，69，41}
6.下列数据结构中，不属于⼆叉树的是（ A ）
A、B树
7.⽤顺序存储的⽅法来存储⼀棵⼆叉树，存放在⼀维数组A[1..N]中，若结点A[i]有右孩⼦，则其右孩⼦是（ C ）。
C、A[2i+1]
8.设树T的⾼度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶⼦数为（ D ）
D、 8
9.有数据{53，30，37，12，45，24，96}，从空⼆叉树开始逐个插⼊数据来形成⼆叉排序树，若希望⾼度最⼩，则应选择下⾯哪个序列输⼊（ B ）
B、37，24，12，30，53，45，96
10.对下⾯有向图给出了四种可能的拓扑序列，其中错误的是（ C ）
C、5，1，6，3，4，2
11.m阶B-树中所有⾮终端（除根之外）结点中的关键字个数必须⼤于或等于( B )
B、[m/2]-1
12.散列⽂件也称为( C )
B 、索引⽂件
13.数据结构是（ D ）
D、相互之间存在⼀种或多种特定关系的数据元素的集合
14.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（ C ）
C、线性结构和树型结构
15.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别⽤p→llink和p→rlink表⽰，则同样表⽰
p指针所指向结点的表达式是（ D ）
D、p→llink→rlink
16.若栈采⽤顺序存储⽅式存储，现两栈共享空间]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的
底在V[m]，则栈满的条件是（ B ）
B、 top[1]+1=top[2]
17.若⼀棵⼆叉树有11个叶⼦结点，则该⼆叉树中度为2的结点个数是（ A ）
A、10
18.树的先根序列等同于与该树对应的⼆叉树的（ A ）
A、先序序列
19.下⾯关于哈希(Hash，杂凑)查的说法正确的是( C )
C、不存在特别好与坏的哈希函数，要视情况⽽定
20.下列序列中，（ D ）是执⾏第⼀趟快速排序后所得的序列。
D、 [68，11，69，23，18] [93，73]
21.下列关键字序列中，构成⼩根堆的是( D )
D、 (15，28，46，37，84，58，62，41)
22.ISAM⽂件和VASM⽂件属于( C )
C、索引顺序⽂件
23.下⾯程序段的时间复杂度为（ C ）
for (i=0; i
for (j=0; j
A[i][j]=i*j;
C、O(m*n)
24.已知指针p和q分别指向某单链表中第⼀个结点和最后⼀个结点。假设指针s指向另⼀个单链表中某个结点，则在s所指结点之后插⼊上述链表应执⾏的语句为（ A ）
A、q->next=s->next；s->next=p；
25.为便于判别有向图中是否存在回路，可借助于（ D ）
D、拓扑排序算法
26.若以S和X分别表⽰进栈和退栈操作，则对初始状态为空的栈可以进⾏的栈操作系列是（ D ）
D、SSSXXSXX
27.设有⼀顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量⾄少应
B、3
28.假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下⼀个存储位置，则队头元素所在的存储位置为（ B ）。
B、(rear-length+m)%m
29.在⼀个链队列中，front和rear分别为头指针和尾指针，则插⼊⼀个结点s的操作为（ D ）。
D、rear->next=s;rear=s;
30.对于哈希函数H(key)=key%13，被称为同义词的关键字是（ D ）
D、25和51
31.采⽤⼆叉链表存储的n个结点的⼆叉树，共有空指针（ A ）个。
A、n+1
32.连通⽹的最⼩⽣成树是其所有⽣成树中（ D ）
D、边的权值之和最⼩的⽣成树
33.对记录序列(314，298，508，123，486，145)依次按个位和⼗位进⾏两趟基数排序之后所得结果为（ B ）
B、508，314，123，145，486，298
34.任何⼀个⽆向连通图的最⼩⽣成树( C )。
C、⼀棵或多棵
35.⽆向图的邻接矩阵是⼀个( C )
C、对称矩阵
36.设⽆向图G-=(V,E)和G’=(V’,E’)，如G’为G的⽣成树，则下列说法中不正确的是( B )。B、G’为G 连通分量
37.以v1为起始结点对下图进⾏深度优先遍历，正确的遍历序列是（ D ）
D、v1，v2，v5，v6，v7，v3，v4
38.下⾯⼏个符号串编码集合中，不是前缀编码的是（ B ）
B、{0,1,00,11}
39.希尔排序的增量序列必须是（B ）。
B、递减的
40.采⽤起泡排序法对n个关键字进⾏升序排序，若要使排序过程中⽐较关键字的次数最多，则初始时的序列应满⾜条件
（ D ）
D、关键字从⼤到⼩排列
41.在下列内部排序中( A )是不稳定的。
42.
分别以下列序列构造⼆叉排序树，与⽤其它三个序列所构造的结果不同的是( C )。 A 、（100，80， 90， 60，
120，110，130） 43.
在查过程中，冲突指的是（ C ）。 C 、不同键值对应相同的存储地址 44.
对有14个元素的有序表A[1..14]作⼆分查，查元素A[4]时的被⽐较元素依次为（ D ）。 D 、A[7]，A[3]，A[5]，A[4] 45.
以v1为起始结点对下图进⾏⼴度度优先遍历，正确的遍历序列是（ A ） A 、 v1，v2，v3，v4，v5，v6，v7
⼆、填空题(本⼤题共10⼩题，每⼩题2分，若有两个空格，每个空格1分，共20分) 1. 数据的物理结构包括数据元素的存储和数据之间关系的存储。
2. 若⼀个算法中的语句频度之和为T(n)=1921n+4nlogn，则算法的时间复杂度为 nlogn 。
3.
下⾯程序段的时间复杂度是
n log 3 。
i=1；
while (i<=n) i=i*3； 4.
循环队列⽤数组-1]存放其元素值，已知其头尾指针分别是front 和rear ，则当前队列的元素个数是（ rear-front+m ）% m 5. 主要是使插⼊和删除等操作统⼀ 6. （n-1）/2 。
7. 在单链表中设置头结点的作⽤是深度优先。
线性表L=（a1,a2,…,an ）⽤数组表⽰，假定删除表中任⼀元素的概率相同，则删除⼀个元素平均需要移动元素的个数是相同值关键字。 9.
已知⼀⽆向图G=（V ，E ），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现⽤某⼀种图遍历⽅法
从顶点a 开始遍历图，得到的序列为abecd ，则采⽤的是前移遍历⽅法。 10. 如果排序过程不改变时间复杂度之间的相对次序，则称该排序⽅法是稳定的。 11. 从顺序表中删除⼀个元素时，表中所有在被删元素之后的元素均需出度⼀个位置。 12. 当问题的规模n 趋向⽆穷⼤时，算法执⾏时间T(n)的数量级被称为算法的 10 。
13.
若以邻接矩阵表⽰有向图，则邻接矩阵上第i ⾏中⾮零元素的个数即为顶点vi 的 sxssxxssxssxxx 。
14.⼀棵含999个结点的完全⼆叉树的深度为12 。
15.假设S和X分别表⽰进栈和出栈操作，由输⼊序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”
得到“ab*cd/+”的操作序列为 4 。
16..如图所⽰的有向⽆环图可以排出L->next->next==L
17.边种不同的拓扑序列。
18.从空树起，依次插⼊关键字1l，27，35，48，52，66和73构造所得的⼆叉排序树，在等概率查的假设下，查成功时的平均查长度为384 。
19.带头结点的双循环链表L中只有⼀个元素结点的条件是队列。
20.求最⼩⽣成树的克鲁斯卡尔(Kruskal)算法耗⽤的时间与图中边稠密、边稀疏的数⽬正相关。
先序中序后序遍历二叉树
21.已知⼀棵完全⼆叉树中共有768结点，则该树中共有 5 个叶⼦结点。
22.实现图的⼴度优先搜索，除了⼀个标志数组标志已访问的图的结点外，还需要8、64 存放被访问的结点以实现遍历。
23.Prim（普⾥姆）算法适⽤于求2h-1的⽹的最⼩⽣成树；kruskal（克鲁斯卡尔）算法适⽤于求2h-1 的⽹的最⼩⽣成树。
24.对长度为20的有序表进⾏⼆分查的判定树的⾼度为n-1 。
25.设⼀棵完全⼆叉树有128个结点，则该完全⼆叉树的深度为n ，有_ 个叶⼦结点。
26.⾼度为h的完全⼆叉树中最少有栈个结点，最多有个结点。
27.设连通图G中有n个顶点e条边，则对应的最⼩⽣成树上有 3 条边。
28.构造n个结点的强连通图，⾄少有O(n2)条弧。
29.表达式求值是（42,13,94,55,05,46,17）应⽤的⼀个典型例⼦。
30.设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，⼀个元素出栈后即进⼊队列Q，若6个元素出
队的序列是e2,e4,e3,e6,e5,e1，则栈的容量⾄少应该是。
31.快速排序算法在最差的情况下其时间复杂度是。
32.对序列{55，46，13，05，94，17，42}进⾏基数排序，第⼀趟排序后的结果是。
三、应⽤题（本⼤题共5⼩题，每⼩题6分，共30分）
1.已知⼆叉树的先序遍历序列ABCDEFGH，中序遍历序列为CBEDFAGH，画出⼆叉树。
答案：⼆叉树形态
A
F
G
D
E
C
B
2.
如图请给出邻接表、邻接矩阵及逆邻接表。
参考答案如下：
（1
）
邻接表：(注意边表中邻接点域的值是顶点的序号，这⾥顶点的序号是顶点的下标值-1) vertex firstedge next
（2）逆邻接表：
（3
）
V1 V3
V2 V4
3.由字符集{s，t，a，e，I}及其在电⽂中出现的频度构建的哈夫曼树如图所⽰。已知某段电⽂的哈夫曼编码为111000010100，
请根据该哈夫曼树进⾏译码，写出原来的电⽂。
答案：原来的电⽂为：eatst
4.请画出下图所⽰的树所对应的⼆叉树，并写出对应⼆叉树的先序遍历和中序遍历。
答案：
先序遍历为：12345687 中序遍历为：34867521
5.设散列表为HT[13], 散列函数为H (key) = key %13。⽤闭散列法解决冲突, 对下列关键码序列12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采⽤线性探查法寻下⼀个空位, 画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。
答案：
使⽤散列函数H(key) = key mod 13，有
H(12) = 12, H(23) = 10, H(45) = 6, H(57) = 5,
H(20) = 7, H(03) = 3, H(78) = 0, H(31) = 5,

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。