发布时间 : 星期六 文章数据结构总复习更新完毕开始阅读
一、 单选题 1.
数据结构研究( )。
A.数据的逻辑结构、存储结构及操作的实现 B. 数据的物理结构 C. 数据的逻辑结构与存储结构 D. 数据的逻辑结构。
数据的存储结构包括顺序;链式;散列和( )4 种基本类型。 A. Vector B. Index C. Sets D. Array 若某线性表最常用的操作是取第 i 个元素，则采用( )存储方式最节省运算时间。 A．双链表 B． 单链表 C．顺序表 D． 单循环链表
一个单链表中，已知*q 结点是*p 结点的前趋结点，若在*q 和*p 之间插入*s 结点， 则必须执行( )操作。
A．q->next=p ->next; p ->next=s; B． p ->next=s; s->next=q C．p ->next=s->next; s->next=p D．q->next=s; s->next= p ;
在一个具有n个结点的有序单链表中，若插入一个新结点，单链表仍然有序，则算法的 时间复杂度为（ ）。 A．O(n) B．O(1) C．O(n2) D．O(nlog2n) 队列与一般线性表的区别在于( )。
A. 数据元素的类型不同 B. 插入或删除操作的位置受限制 C. 数据元素的个数不同 D. 逻辑结构不同
设进栈的顺序为 a b c d，则不可能得到的出栈序列是( )。 A.a b c d B.d c b a C. d a b c D. a c d b 用链接方式存储的队列，在进行插入运算时( ).
A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改
循环队列的队满条件为（在牺牲一个存储空间的情况下） ( )
A. rear % maxsize ==(front+1) % maxsize; B. (rear+1)% maxsize == front+1 C. (rear+1)% maxsize == front D. rear == front 下面关于串的叙述中，哪一个是不正确的( )
A.串是字符的有限序列 B. 模式匹配是串的一种重要运算
C. 空串是由空格构成的串 D.串既可以采用顺序存储，也可以采用链式存储 稀疏矩阵一般的压缩存储方法有( )两种。
A．三元组表和十字链表 B．三元组表和哈希表 C．二维数组和三维数组 D．哈希表和十字链表
中序遍历一颗二叉排序树所得到的结点访问序列是结点值的( )序列。 A.递增或递减 B.递增 C. 递减 D. 无序
在树中，若结点A 有四个兄弟，而且B 是A 的双亲，则B 的度为( )。 A.3 B.4 C.5 D.6
若一棵二叉树具有 10 个度为 2 的结点，则该二叉树的度为 0 的结点个数是( ) A．9 B．11 C．12 D、不确定 n 个顶点的连通图至少有( )条边 A. 0 B. n C. n+1 D. n-1
若采用邻接矩阵法存储一个n 个顶点的无向图，则该邻接矩阵是一个 ( ) 。 A ．上三角矩阵 B ．稀疏矩阵 C．对角矩阵 D. 对称矩阵
- 0 -
2. 3. 4.
5.
6.
7. 8.
9.
10.
11.
12. 13. 14. 15. 16.
17. AOV网是一种( )。
A．有向图 B．无向图 C．有向无环图 D．无向无环图 18. 采用折半查找方法进行查找，数据文件应为( )。
A．有序表和链式存储结构 B ．有序表和顺序存储结构 C． 随机表和顺序存储结构 D ．随机表和链式存储结构
19. 在顺序表{2、5、7、10、14、15、18}中，用二分法查找关键码 12需做( )次关键码
比较。 A．2 B．3 C．1 D．5
20. 下面的排序算法中，时间复杂度不是O(n2）的是( )。
A.直接插入排序 B.冒泡排序 C.二路归并排序 D.直接选择排序 21. 算法指的是（ ）
A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列
22. 下列数据结构中，（ ）是线性结构。
A．树 B ．队列 C．图 D ．A 和B 23. 下面程序的时间复杂为（ ）
for（i=1，s=0； i<=n； i++） { t=1；
for(j=1；j<=i；j++) t=t*j； s=s+t； } A. O(n) B. O(n2) C. O(n3) D.O(n4) 24. 用链表表示线性表的优点是 ( )。
A. 便于随机存取 B. 花费的存储空间比顺序表少
C. 便于插入与删除 D. 数据元素的物理顺序与逻辑顺序相同
25. 从一个具有n 个结点的单链表中查找其值等于x 的结点时，在查找成功的情况下，需
平均比较( )个结点。
A．n B．n/2 C．（n-1 ）/2 D．(n+1)/2
26. 在一个单链表中，已知 q 所指节点是 p 所指节点的前驱节点，若在 q 和 p 之间插
入 s 节点，则执行( )。
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; 27. 栈的插入和删除操作在（ ）进行。
A 栈顶 B 栈底 C 任意位置 D 指定位置 28. 设栈的输入序列是 1 2 3 4,则( )是不可能的出栈序列。
A.1 2 4 3 B. 2 1 3 4 C. 1 4 3 2 D. 4 3 1 2 29. 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，
则执行出队操作后其头指针front值为（ ）
A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m 30. 如下陈述中正确的是（ ）
A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串
- 1 -
31. 树型结构中元素间存在( )的关系。
A. 一对一 B. 多对多 C. 一对多 D. 随机 32. 一棵深度为 5 的满二叉树中,结点的总数为 ( )。
A.31 B.32 C.33 D.16 33. 一棵二叉树有 67 个结点，这些结点的度或者是 0，或者是 2。这棵二叉树中度为 2 的
结点有( )个。
A. 33 B.34 C.32 D.30 34. 下面关于图的存储的叙述中正确的是（ ）
A.邻接矩阵占用的存储空间只与图中结点个数有关，而与边数无关； B.邻接矩阵占用的存储空间只与图中边数有关，而与结点个数无关； C.邻接表占用的存储空间只与图中结点个数有关，而与边数无关； D.邻接表占用的存储空间只与图中边数有关，而与结点个数无关。
35. n 个顶点的连通图至少有( )条边。
A．n-1 B．n C．n+1 D ．0 36. AOV网是一种（ ）。
A．有向图 B．无向图 C．无向无环图 D．有向无环图
37. 若采用邻接矩阵法存储一个n 个顶点的无向图，则该邻接矩阵是一个 ( ) 。
A ．上三角矩阵 B ．稀疏矩阵 C．对角矩阵 D. 对称矩阵 38. 对二叉排序树进行( )遍历，可以得到该二叉树所有结点构成的有序序列
A. 前序 B. 中序 C.后序 D.按层序
39. 有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}, 如果采用二分查找法, 查
值为 82 的结点时，（ ）次比较后查找成功。 A. 1 B. 2 C. 4 D. 8
40. 假定有 K 个关键字互为同义词,若用线性探测法把这 K 个关键字存入散列表中,至少
要进行( )次探测。
A.K-1 次 B. K(K-1)/2 次 C.K+1 次 D.K(K+1)/2 次 41. 对一个算法的评价，不包括如下（ ）方面的内容。
A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度
42. 对线性表，在下列哪种情况下应当采用链表表示？( )
A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变
43. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。
A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL;
44. 栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素 C.都是先进先出 A. 2 3 1 C. 3 1 2
B.都是先进后出 D.没有共同点
- 2 -
45. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( )
B. 3 2 1 D. 1 2 3
46. 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，
则执行出队操作后其头指针front值为（ ）
A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m
47. 用链接方式存储的队列，在进行插入运算时( ).
A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改
48. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在
676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
A．688 B．678 C．692 D．696
49. 树最适合用来表示( )。
A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据
50. 二叉树的第k层的结点数最多为( ).
A．2k-1 B.2K+1 C.2K-1 D. 2k+1
51. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分
查找，则查找A［3］的比较序列的下标依次为( )
A. 1，2，3 C. 9，5，3
B. 9，5，2，3 D. 9，4，2，3
52. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为
A. O（1） B. O（n） C. O（1og2n） D. O（n2）
53. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）
=K %9作为散列函数，则散列地址为1的元素有（ ）个，
A．1 B．2 C．3 D．4
54. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5 B.6 C.7 D.8
55. AOV网是一种（ ）。
A．有向图 B．无向图 C．无向无环图 D．有向无环图
56. 时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ）。
A. 堆排序
B. 冒泡排序 C. 希尔排序 D. 快速排序
57. 快速排序在最坏情况下的时间复杂度为（ ）。
A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)
58. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A. O(n) B. O(1) C. O(log2n) D. O(n2)
59. 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序
时，序列的变化情况如下：
20，15，21，25，47，27，68，35，84
- 3 -