数据结构练习题2021——参考答案

1. 计算机处理数据的基本单位是 ( )。

A．元素 B．结点 C．数据类型 D．数据项

2. 计算机处理数据的最小单位是（ ）。

A．元素 B．结点 C．数据类型 D．数据项

3. 数据表示是指数据（ ）。

A．书写在纸上 B．从机外转为机内

C． 磁盘中的数据 D．光盘中的数据

4. 以下关于数据结构的说法中，正确的是（ ）。

A．数据的逻辑结构独立于其存储结构

B．数据的存储结构独立于其逻辑结构

C．数据的逻辑结构唯一决定了其存储结构

D．数据结构仅由其逻辑结构和存储结构决定

5. 在存储数据时，不仅要存储各数据元素的值，还要存储 ( )。

A．数据的处理方法

C． 数据元素的类型

B．数据元素之间的关系

D．数据的存储方法

6. 算法是指 ( )。

A．计算方法 B．排序方法

C．解决问题的有限运算步骤 D．查找方法

7. 数据的算法（ ）。

A．效率与采用何种存储结构有关 B．是根据存储结构来定义的

C．有算术运算和关系运算两大类 D．必须用程序设计语言来描述

8. 下列关于算法的说法中，正确的是（ ）。

A．算法等于程序 B．算法可以直接在计算机上运行

C．算法可以描述解题思想和基本框架 D．算法可以没有输出

9. 算法分析的两个主要方面是( )。

A．空间性能和时间性能

C．可读性和文档性

B．正确性和简明性

D．数据复杂性和程序复杂性

10. 如果算法的时间复杂度为O(n)，表明该算法的（ ）。

A．问题规模是n B．执行时间等于n

C．执行时间与n成正比 D．问题规模与n成正比

11. 算法能正确地实现预定功能的特性称为（ ）。

A．正确性 B．易读性

12. 算法指的是（ ）。

A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序

C 解决问题的计算方法 D 数据处理

13. 算法分析的目的是( )。

A．找出数据结构的合理性 B．研究算法中输入和输出的关系

C．分析算法的效率以求改进 D．分析算法的易读性和文档性

14. 顺序存储结构要求存储地址 ( )。

A．必须连续 B．必须不连续

C．健壮 D．高效率

C．连续与否均可 D．看情况

15. 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的

A 线性结构 B 非线性结构 C 存储位置 D 指针

16. 单循环链表的主要优点是（ ）。

A 不再需要头指针了 B 从表中任一结点出发都能扫描到整个链表；

C 已知某个结点的位置后，能够容易找到它的直接前趋；

D 在进行插入、删除操作时，能更好地保证链表不断开。

17. 一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是( )。

A 54321 B 45321 C 43512 D 12345

18. 常对数组进行的两种基本操作是( )

A．建立和删除 B． 索引和修改 C．插入和修改 D．插入和索引

19. 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲

区， 该缓冲区应该是一个（ ）结构。

A 栈 B 队列 C 数组 D 线性表

20. 二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下

标的范围是从0~9，则存放A至少需要（ ）个字节。

A 90 B 180 C 240 D 540

21. 算法在发生非法操作时可以作出处理的特性称为（ ）。

A 健壮性 B 确定性 C 可行性 D 正确性

22. 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用

（ ）存储方法最节省时间。

A 顺序表 B 单链表 C 双链表 D 单循环链表

23. 元素A, B, C, D依次进入顺序栈后，栈顶元素是（ D ），顶底元素是

（ A ）。

A．A B．B C．C D．D

24. 元素A, B, C, D依次进入队列后，队头元素是（ A ），队尾元素是

（ D ）。

A．A B．B C．C D．D

25. 将数组称为随机存取结构是因为（ ）。

A 数组元素是随机的 B 对数组任一元素的存取时间是相等的

C 随时可以对数组进行访问 D 数组的存储结构是不定的

26. 一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（ ）

成立。

A n=h+m B h+m=2n C m=h-1 D n=2m-1

27. 队列的操作原则是（ ）。

A． 先进后出 B． 先进先出 C． 只能进行插入 D． 只能进行删除

28. 在栈中，栈顶指针top指示 ( )。

A．栈底元素的位置

B．栈顶元素的位置

D．以上均不对

C．栈中任何元素的位置

29. 下面（ ）不是算法所必须具备的特性。

A 有穷性 B 确切性 C 高效性 D 可行性

30. 在一棵树中，（ ）没有后继结点。

A． 根结点 B． 叶子结点 C． 分支结点 D． 所有结点

31. 串是（ ）。

A．不少于一个字母的序列 B．任意个字母的序列

C．不少于一个字符的序列 D．有限个字符的序列

32. 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个

结点，

则采用（ ）存储方法最节省时间。

A 单链表 B 带头指针的单循环链表 C 双链表 D 带尾指针的单循环链表

33. 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过

栈S， 一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、

e6、e5、e1，则栈S的容量至少应该是（ ）。

A 6 B 4 C 3 D 2

34. 二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下

标的范围是从0~9, A的第8列和第5行共占（ ）个字节。

A 114 B 54 C 108 D 540

35. 在一棵树中，每个结点最多有 ( ) 个前驱结点。

A．0 B．1 C．2 D．任意多个

36. 一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（ ）。

A 4321 B 1234 C 1432 D 3241

37. 下面的说法中，不正确的是（ ）。

A 数组是一种线性结构 B 数组是一种定长的线性结构

C 除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等

D 数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作

38. 如果结点A有3个兄弟，B是A的双亲，则结点B的度是（ ）。

A 1 B 2 C 3 D 4

39. 静态查找与动态查找的根本区别在于（ ）。

A 它们的逻辑结构不一样 B 施加在其上的操作不同

C 所包含的数据元素的类型不一样 D 存储实现不一样

40. 线性表的顺序存储结构是一种（ ）的存储结构。

A 随机存取 B 顺序存取 C 索引存取 D 散列存取

41. 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产； 子女可以继承

父亲或母亲的遗产；子女间不能相互继承。 则表示该遗产继承关系的最合

适的数据结构应该是（ ）。

A 树 B 图 C 线性表 D 集合

42. 线性表采用链式存储结构时，其地址（ ）。

A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 连续与否均

可以

43. 线性表的第一个元素叫做（ ）。

A．表头元素 B．表尾元素 C．前驱元素 D．后继元素

44. 线性表的最后一个元素叫做（ ）。

A．表头元素 B．表尾元素 C．前驱元素 D．后继元素

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

A 6 B 7 C 8 D 9

46. 在以下哪种情况下，不能执行出栈操作？（ ）

A．栈满 B．栈空 C．任何情况均可 D．任何情况均不可

47. 下列数据结构中，（ ）不是线性结构。

A．栈 B．队列 C．数组 D．树

48. 栈又称为（ ）表。

A． 先进先出 B． 后进先出 D． 不进不出 D． 以上均不对

49. 在以下哪种情况下，不能执行入栈操作？（ ）

A．栈满 B．栈空 C．任何情况均可 D．任何情况均不可

50. 在以下哪种情况下，不能执行出栈操作？（ ）

A．栈满 B．栈空 C．任何情况均可 D．任何情况均不可

51. 栈和队列的共同点是（ ）。

A．都是先进后出

C．都是线性结构

B．都是先进先出

D．没有共同点

52. 在一棵树中，每个结点最多有（ ）个双亲结点。

A． 0 B． 1 C． 2 D． 任意多个

53. 在一棵树中，每个结点最多有（ ）个孩子结点。

A． 0 B． 1 C． 2 D． 任意多个

54. 非空树有（ ）个根结点。

A． 0 B．1 C．2 D． 任意多个

55. 串是一种特殊的线性表，其特殊性体现在 ( )

A．可以顺序存储

C．可以链接存储

B．数据元素是一个字符

D．数据元素可以是多个字符

56. 数组中的数据元素的类型（ ）。

A．必须相同 B．不必相同 C．一定不能相同 D．以上都不对

57. 下列数据结构中，( )不都是线性结构。

A．栈和队列 B．队列和数组 C．数组和串 D．树和队列

58. 关于空串与空格串，下面说法正确的是( )。

A．空串与空格串是相同的

C．空格串中存放的都是空格

B．空串与空格串长度是相同的

D．空串中存放的都是NULL

59. 递归可采用下面哪种结构实现（ ）

A．队列 B．栈 C．树 D．图

60. 栈操作的原则是( )

A．先进先出 B．后进先出 C．只能进行插入 D．只能进行删除

61. 在关键字序列(4, 12, 23, 55, 56，67，88)中，使用折半查找法查找56，

需要比较多少次（ ）

A. 1 B.2 C.3 D.4

62. 二叉树有（ ）种基本形态。

A．0 B．1 C．3 D．5

）的结点数最多。 63. 在具有相同高度的二叉树里，（

A．完全二叉树

C．斜树

B．满二叉树

D．普通二叉树

64. 折半查找法适合于存储结构为（ ）的线性表。

A． 顺序存储，排序与否均可 B．链式存储，排序与否均可

C． 顺序存储，已排序 D．链式存储，已排序

）的结点数最少。 65. 在具有相同高度的二叉树里，（

A．完全二叉树

C．斜树

B．满二叉树

D．普通二叉树

66. 具有8个叶子结点的二叉树中，有（ ）个度为2的结点。

A．6 B．7 C．8 D．9

67. 二叉树第i层上最多有（ ）个结点。

A．i B．i-1 C．2

i

-1 D．2

i-1

68. 以下关于二叉树的说法中哪个是正确的（ ）。

A．二叉树的度一定为2

C．二叉树是无序树

B．满二叉树是一种特殊的完全二叉树

D．二叉树就是度为2的有序树

69. 如果一个函数在其函数体中调用自己本身，则该函数叫做 ( )。

A．重载函数 B．递归函数 C．普通函数 D．成员函数

70. 以下的说法中，错误的是（ ）。

A．完全二叉树是满二叉树的特例

B．满二叉树中没有度为1的结点

C．在相同高度的二叉树中，满二叉树的结点数最多

D．在相同高度的二叉树中，斜树的结点数最少

71. 线性表若采用顺序存储结构时，要求内存中可用存储单元的地址 ( )

A．必须是连续的 B．部分地址必须是连续的

C．一定是不连续的 D．连续或不连续都可以

72. 有n个顶点的无向完全图，其边数等于（ ）。

A．n B．n

2

C．n(n-1)/2 D．n(n-1)

73. 有n个顶点的有向完全图，其边数等于（ ）。

A．n B．n

2

C．n(n-1)/2 D．n(n-1)

74. 无向图的邻接矩阵是一个（ ）。

A．对称矩阵 B．零矩阵 C．上三角矩阵 D．对角矩阵

75. 设计一个判别表达式中左右括号是否配对的算法，采用（ ）数据结构最佳。

A 顺序表 B 栈 C 队列 D 链表

76. 在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。

A．1/2 B．1 C．2 D．4

77. 在有向图中，所有顶点的出度之和等于入度之和的（ ）倍。

A．1/2 B．1 C．2 D．4

78. 下面的说法中，不正确的是（ ）。

A 对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可。

B 对角矩阵只须存放非零元素即可。

C 稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。

D 稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储。

二．应用题

1. 计算下列式子的时间复杂度。

(1) 2n

3

+100log

2

n+12 ：O（n3）

(2) 5+n

2

+n

3

：O（n3）

(3) 10+20n+2

n

：O（2n）

2. 某数据结构DS=(D,R)，其中D={a,b,c,d,e,f},R={(a,b),(a,c),

(a,d),(b,d),(b,e),(b,f),(c,d),(d,f),(e,f)},画出其逻辑结构图并说明

其属于哪种逻辑结构。

逻辑结构图略。

属于图形结构。

3. 有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，列出

所有可能的出栈序列。

abc

acb

bac

bca

cba

4. 栈S=(a，b，c)，在栈中插入1个元素d，再从栈中删除一个元素，请写出S

的变化过程。

S=(a,b,c)—>S=(a,b,c,d)—>S=(a,b,c)

5. 队列Q=(a，b，c)，在队列中插入1个元素d，再从队列中删除一个元素，

请写出Q的变化过程。

Q=(a,b,c)—>Q=(a,b,c,d)—>Q=(b,c,d)

6. 已知二维数组A[10][8]，每个元素占4个字节，且数组在内存中的起始地

址为3000。请计算：数组A共占用多少字节？数组A第一个数据元素的存

储地址是多少？数组A最后一个元素的存储地址是多少？采用行优先顺序

存储该数组，元素A[6][5]的地址是多少？采用列优先顺序存储该数组，元

素A[6][5]的地址是多少？

（1） 数组A共占用多少字节：10*8*4=320 B

（2） 数组A第一个数据元素的存储地址是多少：3000

（3） 数组A最后一个元素的存储地址是多少：3000+320-4=3316

3000+79*4=3316

（4） 采用行优先顺序存储该数组，元素A[6][5]的地址：

（6*8+5）*4+3000=3212

（5） 采用列优先顺序存储该数组，元素A[6][5]的地址是：

（5*10+6）*4+3000=3224

7. 假设在一棵树中，以有序对表示从双亲结点到孩子结点的一条边，若已

知树中边的集合为 {,,,,,,},请画

出该树，并回答下列问题：

① 哪个是根结点? A

② 哪些是叶子结点? BFGHE

③ 哪个是结点C的双亲结点? A

④ 哪些是结点C的孩子结点? DE

⑤ C的兄弟是哪个结点？B

⑥ 哪些是D的祖先结点？AC

⑦ 哪些结点是C的子孙结点？DEFGH

⑧ 结点C的度等于多少？2

⑨ 树的深度是多少? 4

⑩ 树的度是多少？3

8. 一棵二叉树如图所示，请写出该树的先根遍历序列、中根序列、后根序列、

层次遍历序列。

先根遍历序列: ABDCEFG

中根序列: BDAECGF

后根序列: DBEGFCA

层次遍历序列: ABCDEFG

9. 写出下图的邻接矩阵，深度优先遍历序列、广度优先遍历序列，并分别用prim

算法和kruskal算法构造下图的最小生成树，并计算其代价。

G

D

E

F

B C

A

邻接矩阵：



0452810





4501221





281201726







101701513





212615011









13110





深度优先遍历序列: ABCDEF

广度优先遍历序列: A BCD E F

代价=63

10. 若对序列(56，23，67，4，88，12，55)采用直接插入排序法和冒泡排序法

进行排序，请写出每一趟的结果。

直接插入排序法：

（56），[23，67，4，88，12，55]

（23，56），[67，4，88，12，55]

（23，56, 67），[4，88，12，55]

（4，23，56，67），[88,12,55]

(4, 23, 56, 67, 88),[12,55]

(4, 12, 23, 56, 67, 88),[55]

(4,12,23,55,56,67,88)