2024年4月30日发(作者：)

数据结构_中国人民解放军陆军工程大学中国大学mooc课后章节答案

期末考试题库2023年

1. 排序的时间复杂度不受数据初始状态影响而恒为O(nlogn)的是（ ）。

参考答案:

堆排序

2. 设栈S和队列Q的初始状态都为空，元素A,B,C,D,E,F依次通过栈S,一个元

素出栈后即进入队列Q，若6个元素出队的序列是BDCFEA，则栈的容量至

少应该存 元素？

参考答案:

3

3. 将元素“42，30，74，56，15，60”依次插入开始为空的检索树，那么不成

功查找的平均查找长度为____。

参考答案:

3

4. 设有正文AADBAACACCDACACAAD，字符集为A、B、C、D，设计一套二进

制编码，使得上述正文的编码最短，其总码长为。

参考答案:

31

5. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时

间性能受数据初始特性影响的是。

参考答案:

快速排序

6. 一组记录的排序码为{79，46，84，38，40，56}，则利用堆排序（建立小

根堆）的方法建立的初始堆为 ____。

参考答案:

38,40,56,46,79,84

7. 在对一组记录{54，38，96，23，15，72，60，45，83}进行直接插入排序

时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 次。

参考答案:

3

8. 对于下图中的加权图，其最小生成树的边长之和等于______。【图片】

参考答案:

15

9. G是一个非连通无向图，共有28条边，则该图至少有 个顶点。

参考答案:

8

10. 在一棵二叉树中，度为2的结点有5个，度为1的结点有6个，则叶子结

点数有_________个。

参考答案:

6

11. 在下图中，A到F的最短路径为：_______。【图片】

参考答案:

AD、DF

12. 用下图求得的最小生成树中，A到F的路径为：_______。【图片】

参考答案:

AC、CD、DF

13. 使用普里姆算法构造出如图所示的图G的一棵最小生成树，从顶点1出发

依次得到的最小生成树的序列为 。【图片】

参考答案:

(1,3)1,(3,6)4,(6,4)2,(3,2)5,(2,5)3

14. 一个有n个顶点的无向图最多有 条边。

参考答案:

n(n-1)/2

15. 对n个记录的数组元素进行简单选择排序，所需进行的元素间的比较次数

为 。

参考答案:

n(n-1)/2

16. 正则二叉树的先序序列为ABCDE，后序序列为BDECA，则其中序序列是

__________。

参考答案:

BADCE

17. 在对n个元素进行改进的冒泡排序的过程中，最好情况下的时间复杂度为

____。

参考答案:

O(n)

18. _____可以满足稳定性要求。

参考答案:

直接插入排序和冒泡排序

19. 在对n个元素进行快速排序的过程中，若每次划分得到的两个数据段的长

度相等或只差一个元素，则排序的时间复杂度为 。

参考答案:

O(nlogn)

20. 对n个元素进行快速排序，第一次划分最多需要移动 次元素，假定包括基

准和临时量之间的移动。

参考答案:

n+1

21. 若某线性表中最常用的操作是在最后一个元素之后插入新元素，或删除第一

个元素，则采用 存储方式最节省时间。

参考答案:

仅有尾指针的单循环链表

22. 对一个具有n个元素的线性表，建立其有序单链表的时间复杂度为_____。

参考答案:

O(n^2)

23. 稳定的排序方法是 。

参考答案:

直接插入排序

24. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是 。

参考答案:

选择排序

25. 已知一棵二叉树的先序序列是A,B,C,D,E,F,G，和整数序列2,0,0,1,0,1,0。其

中，整数序列中的第i个数，表示先序序列第i个结点的左子树上结点个数。

则该二叉树的后序序列是 。

参考答案:

CBEGFDA

26. 用二分法对数组a[13]进行查找，在等概率的情况下，查找不成功的平均查

找长度为 。

参考答案:

27/7

27. 带头结点的单链表L为空的判定条件是 。

参考答案:

L->next==NULL

28. 将如图所示的单向链表中A段和B段交换位置（将B段调到A段的前面，

其余结点次序不变），正确的程序段为_______。【图片】

参考答案:

t=q->next; q->next=r->next; r->next=p->next; p->next=t；

29. 对初始状态为递增序列的表按递增顺序排序，最省时间的是 算法，最费时

间的是算法。

参考答案:

直接插入排序、快速排序

30. 设环形队列中数组的下标是0～N-1，其头尾指针分别为f和r，则其元素个

数为 。

参考答案:

(r-f+N)％N

31. 设有两个长度为n的单链表，结点类型相同，若以hl为首结点的链表是非

循环的，以h2为首结点指针的链表是循环的，则 。

参考答案:

对于两个链表来说，删除最后一个结点的操作，其时间复杂度都是O(n)

32. 非空的循环单链表L的尾结点(由p所指向)满足 。

参考答案:

p->next==L

33. 对于下图所示的无向图，若从顶点A开始进行先深搜索，可得到的顶点序

列可能为________。【图片】

参考答案:

ADECHBFG

34. 对于下图所存储的有向图，从顶点A开始进行先广搜索，不能得到的顶点

序列是______。【图片】

参考答案:

ADCEB

35. 数组a[m]存储的散列表，散列函数为hash(x)=x mod p，一般情况下，p取

（ ）时，散列结果可能比较平均。

参考答案:

小于m的最大素数

36. 以head为头指针的非空单向循环链表的尾结点（由p所指向）满足_____。

参考答案:

p->next==head

37. 二分查找最适合用于下面的那种线性表？

参考答案:

有序顺序表

38. 假定有k个元素的散列函数值相等（称为同义词），若用线性探测法把这k

个元素逐一插入散列表中，至少要进行（ ）次探测。

参考答案:

K(k+1)/2

39. 算法的有效性指的是（ ）。

参考答案:

时间复杂度与空间复杂度

40. 一个长度为n（n>1）的单向链表设有头和尾两个指针，执行_____操作所用

时间与表长有关。

参考答案:

删除单链表中的最后一个元素

41. 如果对非空线性表的运算只有如下4种：（1）删除第一个元素；（2）删

除最后一个元素；（3）在第一个元素左边插入新元素；（4）在最后一个

元素的右边插入新元素。那么，最合适的存储形式是_____。

参考答案:

仅有表头指针的双向循环链表

42. 设有两个长度都为n的单向链表，结点类型相同。若以h1为表头指针的链

表是非循环的，以h2为表头指针的链表是循环的，则_____。

参考答案:

对于两个链表来说，删除最后一个结点的操作，其时间复杂性都是O（n）

43. 在长度为n的_____上，删除第一个元素，如果不允许移动结点的值，其算法

的时间复杂性为O（n）。

参考答案:

只有表头指针的简单循环链表

44. 判定以head为头指针的单向加头(加监督元)循环链表为空的条件是 。

参考答案:

head->next= =head

45. 一个数据节点集合，以及集合中（ ），组成一个数据结构。

参考答案:

各节点之间的关系

46. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列

变为{15，-1，4，8，20，9，7}则该次采用的增量是 ( ) 。

参考答案:

4

47. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（ ）算法。

参考答案:

直接插入排序

48. 双向循环链表中，在p所指结点的右侧插入指针s所指结点，其操作是____。

参考答案:

s->Llink=p; s->Rlink=p->Rlink; p->Rlink->Llink=s; p->Rlink=s;

49. 在双向链表中，删除p所指结点（不考虑回收结点）不正确的操作是_____。

参考答案:

p->Llink= p->Rlink, p->Rlink=p->Llink;

50. 通过 遍历可以删除二叉树中所有的叶子结点。

参考答案:

先序

51. 图中由3棵树组成的森林所转换成的二叉树有 片叶子。【图片】

参考答案:

5

52. 具有n片叶子的完全二叉树共有 个。

参考答案:

2

53. 一组记录的关键字为{25，50，15，35，80，85，20，40，36，70}，其中

含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的

结果为（ ）。

参考答案:

15,25,35,50,20,40,80,85,36,70

54. 图中，_____都是完全二叉树。【图片】

参考答案:

1、2、4

55. 若二叉树中，2度结点数为m，则叶子数为____。

参考答案:

m+1

56. 具有50个结点的三元树，其高度的最小值为____。

参考答案:

5

57. 含3个结点的普通树的树形共有___ _种。

参考答案:

2

58. 若三元树中，度数为1，2，3的结点数分别是2，1，3。叶子数必为____个。

参考答案:

8

59. 对于顺序存储的长度为n的线性表，插入、删除一个元素的平均时间复杂

度分别是 。

参考答案:

O(n) O(n)

60. 二叉树按层遍历算法实现时采用了数据结构 。

参考答案:

队

61. 设二叉树的结点个数为n，采用双链法存储，其递归先序遍历算法如下：

void suorder(Bptr p){0. if(!p)return;1. visit(p);2. suorder(p->Lson);3.

suorder(p->Rson);4.}主调语句为：suorder(root);递归遍历算法执行时，要

进行 次空调用。

参考答案:

n+1

62. 如图所示：二叉树1的先序序列为_____________，二叉树2的中序序列分别

为_____________。【图片】

参考答案:

ABDGCEFH，DFEBAGC

63. 对普通树先根遍历的规则是：先访问根结点，再依次先根遍历根的各个子树；

后根遍历的规则是：先依次后根遍历根的各个子树，再访问根结点。对普通

树T先根遍历和后根遍历得到先根序列和后根序列，与将T转换成二叉树

B的先序序列、中序序列、后序序列之间的关系是_____。

参考答案:

T的先根序列与B的先序序列相同

64. 有序数组a[18]进行二分查找时，查找到a[5]的查找路径（下标序列）为

_____。

参考答案:

8，3，5

65. 对a[12]进行二分查找，在等概率情况下，查找成功的平均查找长度为___。

参考答案:

37/12

66. 已知h是指向单向加头链表的头指针，删除首元结点（第1个元素结点）

的操作是_____。

参考答案:

p=h->next,h->next=p->next;free(p);

67. 已知hs为首指针的简单单向链表存储一个栈，使指针s所指结点进栈的操

作是____。

参考答案:

s->next=hs;hs=s;

68. 数组q[M]（M等于6）存储一个循环队，first和last分别是首尾指针。已

知first和last的当前值分别等于2和5，且q[5]存放的是队尾元素。当从

队列中删除两个元素，再插入一个元素后，first和last的值分别等于_____。

参考答案:

4和0

69. 若某线性表中最常用的操作是在最后一个元素之后插入新元素，或删除第一

个元素，则采用 存储方式最节省时间。

参考答案:

仅有尾指针的单循环链表

70. 下面哪种说法是不正确的 。

参考答案:

正则二叉树，可由其先序序列唯一确定。

71. 二叉树的后序序列为DBKHFEGCA，中序序列为DBAKHEFCG，则其先序序

列是__________。

参考答案:

ABDCEHKFG

72. 设进栈序列是1，2，3，…，n，输出序列为p1，p2，p3，…，pn。若

p1=3，则p2为_____。

参考答案:

可能是2

73. 下面给出的四种排序法中，（ ）排序是不稳定排序法。

参考答案:

堆排序

74. 设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，

则按字母升序排序的第一趟冒泡排序结束后的结果是（ ）。

参考答案:

H，C，Q，P，A，M，S，R，D，F，X，Y

75. 利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（ ）。

参考答案:

O(n^2)

76. 一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ ）。

参考答案:

希尔排序

77. 数组S[M]存储一个栈，top为栈顶指针。如果条件top= =-1表示栈空，在

栈不空的情况下，栈顶元素为_____。

参考答案:

S[top]

78. 插入排序和选择排序是都不稳定。

参考答案:

错误

79. 已知检索树的后序序列是12，21，19，67，45，23，那么，它的先序序列

是________________。

参考答案:

23，19，12，21，45，67

80. 若检索树中序序列是从小到大的序列，下列说法正确的是 。

参考答案:

检索树中，每个结点的关键字都比其左子树中所有结点关键字大或相等，

比其右子树中所有结点关键字小。

81. 如图所示检索树，其不成功查找的平均查找长度为_ ___。【图片】

参考答案:

3

82. 在关键字随机分布的情况下，用检索树的方法进行查找，其查找长度与 数

量级相当。

参考答案:

折半查找

83. 由输入序列46，70，25，15，28，10，36，78，55所构造的检索树，其

后序序列是___________。

参考答案:

10，15，36，28，25，55，78，70，46

84. 若检索树中，每个结点，其左子树中所有结点值都比其小或相等，其右子树

中所有结点值都比其大，删除结点时，若被删除结点有二个儿子，则真正删

除的是 。

参考答案:

该结点的中序前驱结点

85. 如图所示的4棵二叉树， 是平衡二叉树。【图片】

参考答案:

B

86. 含有15个结点的平衡二叉树的最大高度为 。

参考答案:

5

87. 在一棵AVL树中，每个结点的平衡因子（整数）的取值范围是 。

参考答案:

-l～1

88. 若树的结点个数相同，则下面 是查找效率最高的树。

参考答案:

平衡二叉树

89. 按照授课视频中“平衡因子”的定义，平衡树插入时，若进行LL旋转，则插

入前失衡结点的左儿子的平衡因子是 。

参考答案:

0

90. 依次插入20，8，17，25，30，18来构造开始为空的平衡二叉树，其构造

过程中经过的旋转方式依次为 。

参考答案:

LR，RR，RL

91. 若有一个整数序列，把这些整数依次插入开始为空的平衡树，使四种旋转

LL，RR，LR，RL各至少一次，则此整数序列至少有 个数。

参考答案:

7

92. 依次删除如图所示的AVL树中的结点47、17、22、9、39，则删除过程进

行的旋转方式依次为 。【图片】

参考答案:

LL，RL，RR，LR

93. 以序列2，3，23，9，12，14，6，8，15，17作为叶之权的三元Huffman

树，其W(T)=___ _。

参考答案:

219

94. 插入排序时间复杂度大于选择排序时间复杂度。

参考答案:

错误

95. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排

序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较

____次。

参考答案:

3

96. 设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有 个结点。

参考答案:

25

97. 学生成绩分布情况如表所示，现有10000个学员成绩数据，利用哈夫曼树，

设计最好的比较判断逻辑结构，最少需要 次比较分数段

0~5960~6970~7980~8990~100比例0.050.150.400.300.10五分制不及格

及格中良优

参考答案:

20500

98. 设有正文AADBAACACCDACACAAD，字符集为A、B、C、D，设计一套二进

制编码，使得上述正文的编码最短，其总码长为 。

参考答案:

31

99. 对于无向图的邻接矩阵，说法正确的是_____。

参考答案:

第i行上的非零元素个数和第i列的非零元素个数一定相等

100. 图的先广搜索是二叉树_____的推广。

参考答案:

按层遍历

101. 以下说法正确的是____。

参考答案:

对有向图也能进行先广搜索_实现先广搜索通常要用到队_实现先深搜索通常

要用到栈

102. 无向图G的连通分量是G的极大连通子图。

参考答案:

正确

103. 通过对无向图进行先深搜索，一定可以判断该图是否是连通图，或找出图的

连通分量及先深生成树。

参考答案:

正确

104. n个顶点的有向图中，顶点的最大度数等于______。

参考答案:

2(n-1)

105. 对含有k个连通分量的无向图进行先深搜索时，主控函数中需要调用递归

的搜索函数dfs_____次。

参考答案:

k

106. 用Prim算法，以G为初始生长点，求下图的最小生成树时，依次得到的树

边为：_____。【图片】

参考答案:

GB4、BC2、AB3、CD5、ED10、EF9

107. 用Dijkstra算法求下图顶点A到其余各顶点的最短路径时，将按照__________

的次序，依次求出A到它们的最短路径。【图片】

参考答案:

BEDCF

108. 下面不正确的说法是_____。（1）边的权不能为负的主要原因是无实际意义。

（2）Dijkstra算法经修改后可以用于含负长度的边（但不含负回路）的加

权图。（3）用Dijkstra算法求每一对顶点之间最短路径的时间复杂性为

O(n*n*n)。（4）用Kruskal算法与用Prim算法求同一个无向连通加权图

的最小生成树，所得结果必然是一样的。

参考答案:

（1）（4）

109. 对于n个顶点，m条边的无向图G，说法正确的是______。

参考答案:

若m≥n，则G中必含回路

110. 在下面的排序方法中，辅助空间为O（n）的是 。

参考答案:

合并排序

111. 数组q[M]存储一个循环队，first和last分别是首尾指针。如果使元素x出

队操作的语句为“first=(first+1)%m, x=q[first];”。那么元素x进队的语句是

_____。

参考答案:

last=(last+1)%m,q[last]=x;

112. 首尾指针分别是f和r的单向加头链表存储一个队，元素x出队的语句为

“f=f->next, x=f->data;”，那么判断队空否的条件是_____。

参考答案:

f= =r

113. 数组q[M]存储一个循环队，first和last分别是首尾指针。当前队中元素个

数为_____。

参考答案:

(last- first+M)%M

114. 高度为h的正则二叉树至少有_____结点。

参考答案:

2h-1

115. 设散列表长m=14，散列函数Hash(x)=x mod 11。表中已有4个结点：

addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空。若用

平方探测法处理冲突，插入元素49时，其地址是_____。

参考答案:

9

116. 数组a[m]存储的散列表，散列函数为：hash(x)=x mod p,一般情况下，p取

（）时，散列结果可能比较平均。

参考答案:

小于m的最大素数

117. 平均情况下，查找速度最快，而且又能适应插入、删除的数据结构是（）。

参考答案:

散列表