《数据结构》期末复习题及参考答案

《数据结构》复习资料

一 单选题 (共48题 ，总分值0分 )

1. 设用链表作为栈的存储结构，则退栈操作 （0 分）

A. 必须判别栈是否为满

B. 必须判别栈是否为空

C. 判别栈元素的类型

D. 对栈不作任何判别

2. 下面关于m阶B树说法正确的是（ ）。

①每个结点至少有两棵非空子树； ②树中每个结点至多有m-1个关键字；

③所有叶子在同一层上； ④当插入一个数据项引起B树结点分裂后，树长高一

层。 （0 分）

A. ①②③

B. ②③

C. ②③④

D. ③

3. 下列关于文件的说法，错误的是（ ）。 （0 分）

A. 选择文件的组织方式时应考虑外存的性质和容量

B. 不定长文件指的是总长度可变的文件

C. 对文件的操作主要是维护和检索

D. 文件的存储结构指的是文件在外存上的组织方式

4. 设无向图的顶点个数为n，则该图最多有（ ）条边。 （0 分）

A. n-1

B. n(n-1)/2

C. n(n+1)/2

D. n

2

5. 设广义表L=((a,()),b,(c,d,e))，则Head(Tail(Tail(L)))的值为（ ）。 （0 分）

A. b

B. c

C. (c)

D. (c,d,e)

6. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644

(10)

，A[2][2]存放位置在676

(10)

，每

个元素占一个空间，问A[3][3]

(10)

存放在什么位置？脚注

(10)

表示用10进制表示。 （0 分）

A. 688

B. 678

C. 692

D. 696

7. 设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为 （0 分）

A. n

B. e

C. 2n

D. 2e

8. 广义表(a,(b,(),c))的深度为（ ）。 （0 分）

A. 1

B. 2

C. 3

D. 4

9. 设有向图G中有五个顶点，各顶点的度分别为3、2、2、1、2，则G中弧数为（ ）。 （0 分）

A. 4条

B. 5条

C. 6条

D. 无法确定

10. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，

则查找A[3]的比较序列的下标依次为 （0 分）

A. 1，2，3

B. 9，5，2，3

C. 9，5，3

D. 9，4，2，3

11. 具有n个顶点的有向强连通图最少有（ ）条弧。 （0 分）

A. n-1

B. n

C. n(n-1)

D. n(n-1)/2

12. 将两个各有n个元素的有序表归并成一个有序表，最少进行（ ）次比较。 （0 分）

A. n

B. 2n-1

C. 2n

D. n-1

13. 若需在O(nlog

2

n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是

（ ）。 （0 分）

A. 快速排序

B. 堆排序

C. 归并排序

D. 直接插入排序

14. 下列说法中错误的是（ ）。 （0 分）

A. 栈是一种非线性结构

B. 一个数据元素由一或多个数据项构成

C. 在顺序存储结构中，结点间的逻辑关系由存储单元的邻接关系来体现

D. 语句的频度就是语句的执行次数

15. 对稀疏矩阵进行压缩存储的目的是（ ）。 （0 分）

A. 便于进行矩阵运算

B. 便于输入和输出

C. 节省存储空间

D. 降低运算的时间复杂度

16. 二叉树的第k层的结点数最多为 （0 分）

A. 2

k

-1

B. 2K+1

C. 2K-1

D. 2

k-1

17. 下面给出的四种排序法中（ ）排序法是不稳定的排序法。 （0 分）

A. 插入

B. 冒泡

C. 二路归并

D. 堆

18. 外部排序是指（ ）。 （0 分）

A. 在外存上进行的排序方法

B. 不需要使用内存的排序方法

C. 数据量很大，需要人工干预的排序方法

D. 排序前后数据在外存，排序时数据调入内存的排序方法

19. 下述文件中适合于磁带存储的是（ ）。 （0 分）

A. 顺序文件

B. 索引文件

C. 散列文件

D. 多关键字文件

20. 栈和队列的共同特点是 （0 分）

A. 只允许在端点处插入和删除元素

B. 都是先进后出

C. 都是先进先出

D. 没有共同点

21. 下列说法中错误的是（ ）。 （0 分）

A. 数据对象是数据的子集

B. 数据元素间关系在计算机中的映象即为数据的存储结构

C. 非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系

D. 抽象数据类型指一个数学模型及定义在该模型上的一组操作

22. 设有一组关键字值（46,79,56,38,40,84），则用快速排序的方法，以第一个记录为基准得到

的一次划分结果为（ ）。 （0 分）

A. 38,40,46,56,79,84

B. 40,38,46,79,56,84

C. 40,38,46,56,79,84

D. 40,38,46,84,56,79

23. 在树形结构中，数据元素间存在（ ）的关系。 （0 分）

A. 一对一

B. 一对多

C. 多对多

D. 除同属一个集合外别无关系

24. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为 （0 分）

A. O(n)

B. O(nlog

2

n)

C. O(1)

D. O(n

2

)

25. 用链接方式存储的队列，在进行插入运算时 （0 分）

A. 仅修改头指针

B. 头、尾指针都要修改

C. 仅修改尾指针

D. 头、尾指针可能都要修改

26. 下列叙述中错误的是（ ）。 （0 分）

A. 由树的先序遍历序列和后序遍历序列可以惟一确定一棵树

B. 二叉树不同于度为2的有序树

C. 深度为k的二叉树上最少有k个结点

D. 在结点数目相同的二叉树中，最优二叉树的路径长度最短

27. 若查找每个元素的概率均相等，则在具有n个元素的静态查找表中采用顺序查找法查找一个

记录，其平均查找长度ASL为（ ）。 （0 分）

A. (n-1)/2

B. n/2

C. (n+1)/2

D. n

28. 判定一个栈顶指针为S且不带头结点的链栈为空栈的条件是（ ）。 （0 分）

A. S

B. S->next

C. S->next==NULL

D. !S

29. 设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则删除一个结点的

操作是（ ）。 （0 分）

A. rear=front->next

B. rear=rear->next

C. front=front->next

D. front=rear->next

30. 设表中含100个数据元素，用折半查找法进行查找，则所需最大比较次数为（ ）。 （0 分）

A. 50

B. 25

C. 10

D. 7

31. 串的长度是指（ ）。 （0 分）

A. 串中所含不同字母的个数

B. 串中所含字符的个数

C. 串中所含不同字符的个数

D. 串中所含非空格字符的个数

32. ISAM文件和VSAM文件属于（ ）。 （0 分）

A. 索引非顺序文件

B. 索引顺序文件

C. 顺序文件

D. 散列文件

33. 设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。 （0 分）

A. n

B. n-1

C. m

D. m-1

34. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟

的分配和回收才能使得初始关键字序列变成有序序列。 （0 分）

A. 3

B. 4

C. 5

D. 8

35. 对二叉排序树进行（ ）遍历所得的遍历序列中，关键字值是按升序排列的。 （0 分）

A. 前序

B. 中序

C. 后序

D. 层序

36. 下列叙述中错误的是（ ）。 （0 分）

A. 树的度与该树中结点的度的最大值相等

B. 二叉树就是度为2的有序树

C. 有5个叶子结点的二叉树中必有4个度为2的结点

D. 满二叉树一定是完全二叉树

37. 顺序表中数据元素的存取方式为（ ）。 （0 分）

A. 随机存取

B. 顺序存取

C. 索引存取

D. 连续存取

38. （ ）是数据的不可分割的最小单位。 （0 分）

A. 数据元素

B. 数据对象

C. 数据项

D. 数据结构

39. 含n个顶点的有向图最多有（ ）条弧。 （0 分）

A. n

B. n(n-1)

C. n(n+1)

D. n2

40. 设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则判定该队中只有

一个结点的条件是（ ）。 （0 分）

A. front->next

B. rear->next

C. front==rear

D. front!=rear

41. 设有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表，至少要进行（ ）

次探测。 （0 分）

A. k-1

B. k

C. k+1

D. k(k-1)/2

42. 树最适合用来表示 （0 分）

A. 有序数据元素

B. 无序数据元素

C. 元素之间具有分支层次关系的数据

D. 元素之间无联系的数据

43. 下列叙述中错误的是（ ）。 （0 分）

A. 对数组一般不做插入和删除操作

B. 顺序存储的数组是一个随机存取结构

C. 空的广义表没有表头和表尾

D. 广义表的表尾可能是原子也可能是子表

44. 设图Ｇ的邻接矩阵A=

，则图Ｇ中共有（ ）个顶点。 （0 分）

A. 1

B. 3

C. 4

D. 9

45. 以下数据结构中哪一个是非线性结构？ （0 分）

A. 队列

B. 栈

C. 线性表

D. 二叉树

46. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作

为散列函数，则散列地址为1的元素有( )个 （0 分）

A. 1

B. 2

C. 3

D. 4

47. 一棵高为k的二叉树最少有（ ）个结点。 （0 分）

A. k-1

B. k

C. k+1

D. 2

k-1

E.

2

k

-1

48. 已知二叉树T的先序序列为abdegcfh，中序序列为dbgeachf，则T的后序序列为（ ）。 （0

分）

A. gedhfbca

B. dgebhfca

C. abcdefgh

D. acbfedhg

二 填空题 (共10题 ，总分值100分 )

49. 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为（ _________ ）。 （10

分）

50. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为

（ _________ ），树的深度为（ _________ ），树的度为（ _________ ）。 （10 分）

51. 假定一个线性表为(12,23,74,55,63,40)，若按Key % 4的条件进行划分，使得同一余数的元素

成为一个子表，则得到的四个子表分别为（ _________ ）、（ _________ ）、（ _________ ）

和（ _________ ）。 （10 分）

52. AOV网是一种（ _________ ）的图。 （10 分）

53. 设有n个无序的记录关键字，则直接插入排序的时间复杂度为（ _________ ），快速排序的

平均时间复杂度为（ _________ ）。 （10 分）

54. 一个算法的时间复杂度为(n

3

+n

2

log

2

n+14n)/n

2

，其数量级表示为（ _________ ） （10 分）

55. 设一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储（ _________ ）个队

列元素；当前实际存储（ _________ ）个队列元素（设头指针F指向当前队头元素的前一个

位置，尾指针指向当前队尾元素的位置）。 （10 分）

56. 通常从四个方面评价算法的质量：（ _________ ）、（ _________ ）、（ _________ ）和

（ _________ ）。 （10 分）

57. 设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中

（ _________ ）个数据元素；删除第i个位置上的数据元素需要移动表中（ _________ ）个

元素。 （10 分）

58. 设初始记录关键字序列为(K

1

，K

2

，…，K

n

)，则用筛选法思想建堆必须从第（ _________ ）

个元素开始进行筛选。 （10 分）

三 问答题 (共24题 ，总分值0分 )

59. 设有向网如下，试用迪杰斯特拉算法求从顶点Ａ出发到其余各顶点的最短路径。

（0 分）

60. 设内存有大小为５个记录的区域可供内部排序之用，文件的关键字序列为：（18，32，56，

40，23，11，8，99，58，36，21，7，4，15，19，87，73，52，82，63），要求用置换－选

择排序求初始归并段。 （0 分）

61. 设有AOE网如下，要求：

⑴

求图中各顶点代表的事件的最早发生时间和最晚发生时间；

⑵

求图中各弧代表的活动的最早开始时间和最晚开始时间；

⑶

列出各条关键路径。

（0 分）

62. 试将下图中的树转化为二叉树。

（0 分）

63. 设ｎ为正整数，试确定如下程序段中语句“x++;”的频度。

for (i=1;i<=n;i++)

for (j=1;j<=i;j++)

for (k=1;k<=n;k++)

x++;

（0 分）

64. 设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。 （0 分）

65. 试设计算法，对以邻接矩阵存储的无向图进行深度优先遍历。 （0 分）

66. 假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内

含元素的个数，试写出其入队和出队算法（在出队算法中要返回队头元素）。 （0 分）

67. 设有上三角矩阵(a

ij

)

n×n

，将其上三角元素逐行存于数组B[m]中（m充分大），使得B[k]=a

ij

，

求用i和j表示k的下标变换公式。 （0 分）

68. 试写出对如下无向图从顶点Ａ出发进行广度优先遍历可能得到的所有遍历序列。

（0 分）

69. 已知单链表L中含有三类字符的数据元素，即字母字符、数字字符和其他字符，试编写算法

将L分割为三个循环链表，其中每个循环链表只含一类字符。 （0 分）

70. 设哈希函数H(key)=key%13，用公共溢出区法处理冲突，试在长度为18的散列地址空间中对

关键字序列（71，28，46，14，2，20，85，58）构造哈希表，要求画出哈希表存储结构示意

图，并求等概率下查找成功时的平均查找长度。 （0 分）

71. 设计递归算法，从大到小输出给定二叉排序树中所有关键字值不小于ｘ的数据元素。

（0 分）

72. 有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先

出栈（即C第一个且D第二个出栈）的次序有哪几个？ （0 分）

73. 设有关键字序列（87,43,28,91,12,62,55,26），用快速排序法进行排序，要求写出每趟排序

结束时的关键字序列。 （0 分）

74. 设a='colomn'，b='How are you!'，c='please'，试求：

⑴

StrLength(b)的返回值；

⑵

Index(a,'o',5)的返回值；

⑶

执行StrInsert(a,3,c)后串a的值；

⑷

执行Replace(c,'e','x')后串c的值；

⑸

执行SubString(s,b,5,3)后串s的值。

（0 分）

75. 设单链表Ｌ如图所示：

画出执行如下程序段后，各指针变量及单链表Ｌ的示意图。

p=L;

for(i=1;i<=3;i++){

q=(LinkList)malloc(sizeof(LNode));

q->data=i*3;

q->next=p->next;

p->next=q;

}

（0 分）

76. 设以带头结点的单链表为存储结构，设计算法，实现简单选择排序。 （0 分）

77. 设给定关键字序列（68, 55, 27, 43, 58, 12），试构造平衡的二叉查找树。 （0 分）

78. 设有3阶B-树如下，试画出对其依次执行下列操作后的结果。

(1)插入52；(2)删除11；(3)删除74。

（0 分）

79. 设元素的入栈次序为a、b、c、d，且在入栈的过程中允许出栈，试写出所有不可能得到的出

栈序列。 （0 分）

80. 画出对长度为１７的有序表进行折半查找的判定树，并求等概率下查找成功时的平均查找长

度。 （0 分）

81. 设n为正整数，则在下面的程序段中，语句“a+=2;”的频度为多少？

for(x=0;x

for(y=0;y

a+=2;

（0 分）

82. 设a='data structure'，b='computer'，c='demo'，试求：

⑴

StrLength(a)的返回值；

⑵

执行StrInsert(b,4,c)后串b的值；

⑶

Index(a,'u',10)的返回值；

⑷

执行Replace(a,'structure',b)后串a的值；

⑸

执行SubString(s,b,3,3)后串s的值。

（0 分）

一 单选题 (共48题 ，总分值0分 )

1. 答案：B

解析过程：

2. 答案：B

解析过程：

3. 答案：B

解析过程：

4. 答案：B

解析过程：

5. 答案：D

解析过程：

6. 答案：C

解析过程：

7. 答案：D

解析过程：

8. 答案：C

解析过程：

9. 答案：B

解析过程：

10. 答案：D

解析过程：

11. 答案：B

解析过程：

12. 答案：A

解析过程：

13. 答案：C

解析过程：

14. 答案：A

解析过程：

15. 答案：C

解析过程：

16. 答案：D

解析过程：

17. 答案：D

解析过程：

18. 答案：B

解析过程：

19. 答案：C

解析过程：

20. 答案：A

解析过程：

21. 答案：B

解析过程：

22. 答案：D

解析过程：

23. 答案：B

解析过程：

24. 答案：C

解析过程：

25. 答案：D

解析过程：

26. 答案：D

解析过程：

27. 答案：C

解析过程：

28. 答案：D

解析过程：

29. 答案：C

解析过程：

30. 答案：A

解析过程：

31. 答案：B

解析过程：

32. 答案：A

解析过程：

33. 答案：C

解析过程：

34. 答案：A

解析过程：

35. 答案：B

解析过程：

36. 答案：B

解析过程：

37. 答案：A

解析过程：

38. 答案：C

解析过程：

39. 答案：B

解析过程：

40. 答案：C

解析过程：

41. 答案：B

解析过程：

42. 答案：C

解析过程：

43. 答案：D

解析过程：

44. 答案：B

解析过程：

45. 答案：D

解析过程：

46. 答案：D

解析过程：

47. 答案：B

解析过程：

48. 答案：B

解析过程：

二 填空题 (共10题 ，总分值100分 )

49. 答案：3

解析过程：

50. 答案：9,3,3

解析过程：

51. 答案：（12，40）,（ ）,（74）,（23，55，63）

解析过程：

52. 答案：有向无回路

解析过程：

53. 答案：O(n

2

),O(nlog

2

n)

解析过程：

54. 答案：O(n)

解析过程：

55. 答案：m-1,(R-F+M)%M

解析过程：

56. 答案：正确性,易读性,强壮性,高效率

解析过程：

57. 答案：n+1-i,n-i

解析过程：

58. 答案：n/2

解析过程：

三 问答题 (共24题 ，总分值0分 )

59. 答案：

解析过程：

60. 答案：初始归并段１：18,23,32,40,56,58,99；

初始归并段２：7,8,11,15,19,21,36,52,63,73,82,87

初始归并段３：4

解析过程：

61. 答案：

关键路径１：v

1

→v

2

→v

5

→v

7

关键路径２：v

1

→v

3

→v

6

→v

7

解析过程：

62. 答案：答：

解析过程：

63. 答案：

解析过程：

64. 答案：Status LevelOrderTraverse(Bitree T,Status (*visit)(TElemType e)){

if (!T) return OK; //空二叉树

InitQueue(Q); //初始化辅助队列

if (!visit(T->data)) return ERROR; //访问根结点

EnQueue(Q,T); //指向结点的指针入队

while (!QueueEmpty(Q)){ //若队列非空

DeQueue(Q,p); //队头指针出队

if (p->lchild){//先访问p所指结点的左孩子，再访问其右孩子

if (!visit(p->lchild->data)) return ERROR;

EnQueue(Q,p->lchild);

}//if

if (p->rchild){

if (!visit(p->rchild->data)) return ERROR;

EnQueue(Q,p->rchild);

}//if

}//while

return OK;

}//LevelOrderTraverse

解析过程：

65. 答案：int depth(BiTree t){

if (!t) return 0;

if(t->lchild)//有左子树

if (t->rchild){ //左、右子树均有

hl=depth(t->lchild); //求左子树高度

hr=depth(t->rchild); //求右子树高度

return hl>hr?hl+1:hr+1;

}

else //只有左子树

return depth(t->lchild)+1;

else //无左子树

return depth(t->rchild)+1;

//有右子树，则返回右子树高度加1

//无右子树，即右子树高度为0，则返回1

}//depth

解析过程：

66. 答案：#define MAXQSIZE 100

typedef struct{

ElemType base[MAXQSIZE];

int rear;

int length;

}Queue;

Status EnQueue(Queue &Q,ElemType e){

if(==MAXQSIZE) return ERROR;

=(+1)%MAXQSIZE;

[]=e;

++;

return OK;

}//EnQueue

Status DeQueue(Queue &Q,ElemType &e){

if(!) return ERROR;

front=(+1)%MAXQSIZE;

e=[head];

--;

}//DeQueue

解析过程：

67. 答案：答：

解析过程：

68. 答案：ABCEGHFD

ABCEHGFD

ACBGHEDF

ACBHGEDF

解析过程：

69. 答案：void partition(LinkList &L,LinkList &LC,LinkList &LN,LinkList &LO){

//L带头结点，LC为含字母字符的循环链表，LN为含数字字符的循环链表，

//LO为含其他字符的循环链表

InitCL(LC);

InitCL(LN);

InitCL(LO); //对三个循环链表进行初始化

p=L->next; //p指向第一个结点

while (p){

q=p;

p=p->next; //q指向当前待处理结点，p指向剩余链表

if (q->data>=’A’ && q->data<=’Z’|| q->data>=’a’ && q->data<=’z’){

q->next=LC->next;

LC->next=q;

} //字母字符入循环链表LC

else if (q->data>=’0’ && q->data<=’9’){

q->next=LN->next;

LN->next=q;

} //数字字符入循环链表LN

else {

q->next=LO->next;

LO->next=q;

} //其他字符入循环链表LO

}//while

free(L); //释放单链表L的头结点

}//partition

void InitCL(LinkList &L){

//对循环链表进行初始化

L=(LinkList)malloc(sizeof(LNode));

if (!L) exit(OVERFLOW);

L->next=L;

}

解析过程：

70. 答案：H(71)=6 H(28)=2 H(46)=7 H(14)=1 H(2)=2 H(20)=7 H(85)=7 H(58)=6

ASL=(1+1+1+1+2+3+4+5)/8=9/4

解析过程：

71. 答案：void OutputNLT(BiTree T,KeyType x){

if (!T) return;

if (!LT(T->,x)){ //根结点及右子树中所有结点的关键字值均不小于x

Output(T->rchild); //按关键字值从大到小的顺序输出右子树中所有结点

printf(T->data); //输出p所指结点

OutputNLT(T->lchild,x); //处理左子树

}

else OutputNLT(T->rchild,x);

}//OutputNLT

void Output(BiTree T){

Output(T->rchild);

printf(T->data);

Output(T->lchild);

}

解析过程：

72. 答案：答：CDEBA CDBEA CDBAE

解析过程：

73. 答案：第一趟：26,43,28,55,12,62,87,91

第二趟：12,26,28,55,43,62,87,91

第三趟：12,26,28,55,43,62,87,91

第四趟：12,26,28,43,55,62,87,91

解析过程：

74. 答案：（1）12

（2）0

（3）’copleaselomn’

（4）’plxasx’

（5）’are’

解析过程：

75. 答案：

解析过程：

76. 答案：void SelectSort(LinkList &L){

//单链表Ｌ带头结点

p=L;

while(p->next){

min=p->next; //min用以指向本趟排序中关键字值最小的结点

q=min->next;

while(q){

if LT(q->,min->) min=q; //q所指结点关键字值更小

q=q->next;

}//while

p=p->next;

if (min!=p) min->data←→p->data; //当前关键字值最小的记录到位

}//while

}//SelectSort

解析过程：

77. 答案：

解析过程：

78. 答案：

⑸

'mpu'

解析过程：

解析过程：

79. 答案：dabc dacb dbac dbca dcab cadb cabd cdab bdac adbc

解析过程：

80. 答案：

平均查找长度：

解析过程：

81. 答案：答：n

2

。

解析过程：

82. 答案：⑴14

⑵

'comdemoputer'

⑶

12

⑷

'data computer'