1.数据结构复习(5)

选择 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。 （①A ②B）

① A．操作对象 Ｂ．计算方法 Ｃ．逻辑存储 Ｄ．数据映象 ② A．结构 Ｂ．关系 Ｃ．运算 Ｄ．算法 2. 数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②有限集合。（①B ②D）

① A．算法 Ｂ．数据元素 Ｃ．数据操作 Ｄ．逻辑结构 ② A．操作 Ｂ．映象 Ｃ．存储 Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成①。（C）

A．动态结构和静态结构 Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构 Ｄ．内部结构和外部结构

4. 线性表的顺序存储结构是一种①A的存储结构，线性表的链式存储结构是一种②B的存储结构。

A．随机存取 B．顺序存取 C．索引存取 D．散列存取 5. 算法分析的两个主要方面是（A）。

A. 空间复杂性和时间复杂性 B. 正确性和简明性

C. 可读性和文档性 D. 数据复杂性和程序复杂性 6. 计算机算法指的是①，它必具备输入、输出和②等五个特性。（①C ②B） ① A. 计算方法 B. 排序方法

C. 解决问题的有限运算序列 D. 调度方法

② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 7. 线性表的逻辑顺序与存储顺序总是一致的，这种说法①。（B） A. 正确 B. 不正确

8. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址①。（D） A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以 9. 在以下的叙述中，正确的是①。（B）

A.线性表的线性存储结构优于链表存储结构 B.二维数组是其数据元素为线性表的线性表

C.栈的操作方式是先进先出 D.队列的操作方式和先进后出 10. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法①。（A） A. 正确 B. 不正确

11. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是_(B) A. 110 B. 108 C. 100 D. 120

12. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是_( C ) A. edcba B. decba C. dceab D. abcde

13. 若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为__( C )_。

A. i B. n - i C. n-i+1 D. 不确定 14. 栈结构通常采用的两种存储结构是__(A)

A. 顺序存储结构和链式存储结构 B. 散列方式和索引方式

C. 链表存储结构和数组 D. 线性存储结构和非线性存储结构 15. 判定一个栈ST（最多元素为m0）为空的条件是__(B) A. ST—> top !=0 B. ST—> top= =0 C. ST—> top !=m0 D. ST—> top= =m0

1

16. 判定一个栈ST（最多元素为m0）为栈满的条件是__(D)

A. ST—> top！=0 B. ST—> top= =0 C. ST—> top！=m0 D. ST—> top= =m0 17. 栈的特点是__(B)__，队列的特点是__(A)__。 A. 先进先出 B. 先进后出

18. 一个队列的入列序列是1，2，3，4，则队列的输出序列是__(B)_ 。 A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，1

19. 判定一个循环队列QU（最多元素为m0）为空的条件是__(A)

A. QU—>front= =QU—>rear B. QU—>front！=QU—>rear

C. QU—>front= =（QU—>rear+1）%m0 D. QU—>front！=（QU—>rear+1）%m0 20. 判定一个循环队列QU（最多元素为m0）为满队列的条件是__(C)

A. QU—>front= =QU—>rear B. QU—>front！=QU—>rear

C. QU—>front= =（QU—>rear+1）%m0 D. QU—>front！=（QU—>rear+1）%m0 21. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是__(A)

A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 22. 栈和队列的共同点是___(C)

A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 23. 不带头结点的单链表head为空的判定条件是____。(A) A. head= =NULL B. head—＞next= =NULL C. head—＞next= =head D. head!=NULL 24. 带头结点的单链表head为空的判定条件是____。(B)

A. head= =NULL B. head—＞next= =NULL C. head—＞next= =head D. head!=NULL

25. 非空的循环单链表head的尾结点（由p所指向）满足____。(C) A. p—＞next= =NULL B. p= =NULL C. p—＞next= =head D. p= =head

26. 在循环双链表的p所指结点之后插入s所指结点的操作是____。(D) A. p—＞right=s; s—＞left=p; p—＞right—＞left=s; s—＞right=p—＞right; B. p—＞right=s; p—＞right—＞left=s; s—＞left=p; s—＞right=p—＞right; C. s—＞left=p; s—＞right=p—＞right; p—＞right=s; p—＞right—＞left=s; D. s—＞left=p; s—＞right=p—＞right; p—＞right—＞left=s; p—＞right=s; 27. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_(C)_。

A. s—＞next=p—＞next; p—＞next=s; B. p—＞next=s—＞next; s—＞next=p; C. q—＞next=s; s—＞next=p; D. p—＞next=s; s—＞next=q;

28. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行__(B) A. s—＞next=p; p—＞next=s; B. s—＞next=p—＞next; p—＞next=s; C. s—＞next=p—＞next; p=s; D. p—＞next=s; s—＞next=p; 29. 在一个单链表中，若删除p所指结点的后续结点，则执行____。(A)

A. p—＞next= p—＞next—＞next； B. p= p—＞next; p—＞next= p—＞next—＞next； C. p—＞next= p—＞next; D. p= p—＞next—＞next；

2

30. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比

较____个结点。

A. n B. n/2 C. (n-1)/2 D. (n+1)/2

31. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是____。(B) A. O（1） B.O（n） C. O (n2) D.O (nlog2n)

11. 11. 若线性表最常用的操作是存取第i个元素及其前趋的值，则采用__D__存储方式最节省时间。

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

32. 向一个栈顶指针为HS的链栈(不带空的头结点)中插入一个s所指结点时，执行_(C)_。 A. HS—＞next=s; B.s—＞next= HS—＞next; HS—＞next=s; C.s—＞next= HS; HS=s; D.s—＞next= HS; HS= HS—＞next; 33. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行____。(不带空的头结点) (D)

A.x=HS; HS= HS—＞next; B. x=HS—＞data;

C. HS= HS—＞next; x=HS—＞data; D. x=HS—＞data; HS= HS—＞next; 34. 空串与空格串是相同的，这种说法___B A. 正确 B. 不正确

35. 串是一种特殊的线性表，其特殊性体现在____。D A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符

36. 设有两个串p和q，求q在p中首次出现的位置的运算称作___B A. 连接 B. 模式匹配 C. 求子串 D. 求串长

37. 设串s1=’ABCDEFG’，s2=’PQRST’，函数con (x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，con (subs (s1,2,len (s2)), subs (s1,len (s2),2))的结果串是____。D A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 38. 常对数组进行的两种基本操作是____。C A. 建立与删除 B. 索引和修改 C. 查找和修改 D. 查找与索引

39. 二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M 至少需要__①D__个字节；M的第8列和第5行共占__②B__个字节。 ① A. 90 B. 180 C. 240 D. 540 ② A. 108 B. 114 C. 54 D. 60

40. 数组A中，A的每个元素长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是____。C A. 80 B. 100 C.240 D. 270

41. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为__ C __。 A. SA+141 B. SA+144 C. SA+222 D. SA+225

42. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为__B__。 A. SA+141 B. SA+180 C. SA+222 D. SA+225

43. 1. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法__A__。 A. 正确 B. 错误

3

44. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_B___。

A. 正确 B. 错误

45. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。 (参考：2^(h-1)+1 )

A. 2^h B. 2^(h-1) C. 2^(h+1) D. h+1

46. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是__D__。

A. acbed B. decab C. deabc D. cedba

47. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 B 。 A．a在b的右方 B．a在b的左方 C．a是b的祖先 D．a是b的子孙

48. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 B 个。 A．15 B．16 C．17 D．47

49. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_A___。

A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca

50. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法__B__。 A. 正确 B. 错误

51. 按照二叉树的定义，具有3个结点的二叉树有__C__种。 A. 3 B. 4 C. 5 D. 6

52. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论__A__是正确的。

A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上都不对

53. 在一非空二叉树的中序遍历序列中，根结点的右边__A__。

A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 54. 树最适合用来表示__C__。

A. 有序数据元素 B. 无序数据元素

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

55. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序__A__。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 56. 对一个满二叉树，m个树叶，n个结点，深度为h，则____ 。(无答案) A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-1

57. 如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序为__C__。 A. uwvts B. vwuts C. wuvts D. wutsv

58. 设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是__C__。 A. n在m右方 B. n是m祖先 C. n在m左方 D. n是m子孙 59. 深度为5的二叉树至多有__C__个结点。 A. 16 B. 32 C. 31 D. 10

60. 在一个图中，所有顶点的度数之和等于所有边数的_C___倍。 A. 1/2 B. 1 C. 2 D. 4

4

61. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的__B__倍。

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

62. 带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中____。 A. 第i行非∞的元素之和 B. 第i行非∞且非0的元素个数 C. 第i列非∞的元素之和 D. 第i列非∞且非0的元素个数 63. 一个有n个顶点的无向图最多有__C__条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 64. 具有4个顶点的无向完全图有_A___条边。 A. 6 B. 12 C. 16 D. 20

65. 具有6个顶点的无向图至少应有_A___条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8

66. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要__C__条边。 A. n B. n+1 C. n-1 D. n/2

67. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是__n*n__。 A. n B. (n-1)^2 C. n-1 D. n^2

68. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①_A__；所有邻接表中的接点总数是_②_C__。 ① A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e C.2e D. n+e

69. 已知一个图如图9.5所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。 ① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b

70. ⑴ 根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。 A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2

⑵ 根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。 A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2

71. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的__A__。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历

72. 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的__D__。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历

73. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用__B__。 A. 求关键路径的方法 B. 求最短路径的Dijkstra方法 C. 宽度优先遍历算法 D. 深度优先遍历算法 74. 顺序查找法适合于存储结构为_B___的线性表。 A. 散列存储 B. 顺序存储或链接存储 C. 压缩存储 D. 索引存储

75. 对线性表进行二分查找时，要求线性表必须__C__。 A. 以顺序方式存储 B. 以链接方式存储 C. 以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序

76. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为__C__. A. n B. n/2 C. (n+1)/2 D. (n-1)/2

77. 有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，__C__次比较后查找成功。

5

本文来源：https://www.bwwdw.com/article/xy0f.html