数据结构考试复习题库.doc

单项选择题
1. 向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动〔 〕个元素。
C　
【答案】A
2. 线性表是具有n个〔 〕的有限序列〔n≠0〕。
　
【答案】C
3. 以下哪种排序方法在最坏的情况下的时间复杂度是O〔n*log2n〕〔 〕。
A .直接插入排序 B. 堆排序 C. 简单项选择择排序 D. 快速排序
【答案】B
4. 数组A[5][6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，那么元素A[4][4]的地址为〔 〕。
C
【答案】A
5. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，那么执行〔 〕。
=HS;HS=HS->next;
=HS->data;
=HS->next;x=HS->data;
=HS->data;HS=HS->next;
【答案】D
6. 含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如下图，那么从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为〔 〕。
A.(v0，v1，v2，v5，v4，v3) B.(v0，v1，v2，v3，v4，v5)
C.(v0，v1，v5，v2，v3，v4) D.(v0，v1，v4，v5，v2，v3)
【答案】A
7. 如下陈述中正确的选项是〔 〕。
A．串是一种特殊的线性表 B．串的长度必须大于零
C．串中元素只能是字母 D．空串就是空白串
【答案】A
8. 在一个长度为n的顺序表中插入一个元素时,等概率情况下的平均移动元素的次数是〔 〕。
A．n/2 B．〔n-1〕/2 C．n*(n-1)/2 D． (n+1)/2
【答案】A
9. 数据的存储结构包括顺序、链接、散列和〔 〕4种根本类型。

【答案】D
10. 在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为〔 〕。
A．e B．2e C．n2－e D．n2－2e
【答案】D
11. 引入二叉线索树的目的是〔 〕。




【答案】A
12. 对一棵m阶B-树，以下选项错误的选项是〔　〕。
，每个结点至少有[m/2]棵子树
〔k<=m〕
【答案】C
13. 循环队列用数组A[M]存放元素，其头尾指针分别为front和rear，那么当前队列中的元素个数是〔　〕。
A．rear-front+1 B．rear-front-1
C．rear-front D．(rear-front+M) % M
【答案】D
14. 判断两个串大小的根本准那么是〔 〕。


【答案】D
15. 在线性表的以下运算中，不改变数据元素之间结构关系的运算是〔 〕。
A．插入 B．删除 C．排序 D．定位
【答案】D
16. 对用邻接矩阵表示的连通图进行深度或广度优先遍历时的时间复杂度为〔 〕。
A．O(n2) B．O(n) C． O(e2) D． O(e+n)
【答案】A
17. 对用邻接表表示的连通图进行深度或广度优先遍历时的时间复杂度为〔 〕。
A. O(n2) B. O(e2) C. O(n+e ) D. O(n2)
【答案】C
18. 一棵有124个叶子结点的完全二叉树，至多有〔 〕个结点。
A．251 B．250 C．248 D．247
【答案】D
19. 如果最常用的操作是提取第i个结点及其前驱，那么采用〔 〕存储方式最节