一、单选题（共 30 道试题，共 60 分。）V
1. 下列程序段的时间复杂度为（）。i=0，s=0；while(s<n){s=s+i；i++；}
A. O(n)
B. O(n)
C. O(n)
D. O(n)
满分：2 分
2. 设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（）。
A. 6
B. 11
C. 5
D. 6.5
满分：2 分
3. 用链表表示线性表的优点是（）
A. 便于随机存取
B. 花费的存储空间比顺序表少
C. 便于插入与删除
D. 数据元素的物理顺序与逻辑顺序相同
满分：2 分
4. 对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较。
A. 8
B. 10
C. 15
D. 25
满分：2 分
5. 设完全无向图中有n个顶点，则该完全无向图中有（）条边。
A. n(n-1)/2
B. n(n-1)
C. n(n+1)/2
D. (n-1)/2
满分：2 分
6. 在二叉排序树中插入一个结点的时间复杂度为（）。
A. O(1)
B. O(n)
C. O(log2n)
D. O(n)
满分：2 分
7. 程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的时间复杂度为（）。
A. O(n)
B. O(nlog2n)
C. O(n)
D. O(n/2)
满分：2 分
8. 以下数据结构中哪一个是非线性结构？（）
A. 队列
B. 栈
C. 线性表
D. 二叉树
满分：2 分
9. 设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。
A. 1
B. 2
C. 3
D. 4
满分：2 分
10. 时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（）。
A. 堆排序
B. 冒泡排序
C. 希尔排序
D. 快速排序
满分：2 分
11. 设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图
A. 5
B. 6
C. 7
D. 8
满分：2 分
12. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）
A. 存储结构
B. 逻辑结构
C. 算法
D. 操作
满分：2 分
13. 树最适合用来表示（）。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
满分：2 分
14. 设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。
A. 5
B. 6
C. 7
D. 8
满分：2 分
15. 二叉排序树中左子树上所有结点的值均（）根结点的值。
A. <
B. >
C. =
D. !=
满分：2 分
16. 设有一个二维数组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
满分：2 分
17. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。
A. 8
B. 7
C. 6
D. 5
满分：2 分
18. 树最适合用来表示（）
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
满分：2 分
19. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。
A. 9
B. 10
C. 11
D. 12
满分：2 分
20. 设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（）个度数为0的结点。
A. 5
B. 6
C. 7
D. 8
满分：2 分
21. 设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为（）。
A. 10，15，14，18，20，36，40，21
B. 10，15，14，18，20，40，36，21
C. 10，15，14，20，18，40，36，2l
D. 15，10，14，18，20，36，40，21
满分：2 分
22. 设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。
A. n-i
B. n-1-i
C. n+l-i
D. 不能确定
满分：2 分
23. 若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个（）
A. 上三角矩阵
B. 稀疏矩阵
C. 对角矩阵
D. 对称矩阵
满分：2 分
24. 链式栈与顺序栈相比，一个比较明显的优点是（）
A. 插入操作更加方便
B. 通常不会出现栈满的情况
C. 不会出现栈空的情况
D. 删除操作更加方便
满分：2 分
25. 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为（）。
A. n
B. n/2
C. (n+1)/2
D. (n-1)/2
满分：2 分
26. 设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。
A. n
B. e
C. 2n
D. 2e
满分：2 分
27. 栈和队列的共同特点是（）。
A. 只允许在端点处插入和删除元素
B. 都是先进后出
C. 都是先进先出
D. 没有共同点
满分：2 分
28. 栈的插入和删除操作在（）进行。
A. 栈顶
B. 栈底
C. 任意位置
D. 指定位置
满分：2 分
29. 在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为（）
A. e
B. 2e
C. n2－e
D. n2－2e
满分：2 分
30. 设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（）个。
A. 4
B. 5
C. 6
D. 7
满分：2 分
二、判断题（共 20 道试题，共 40 分。）V
1. 用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。
A. 错误
B. 正确
满分：2 分
2. 如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。
A. 错误
B. 正确
满分：2 分
3. 闭散列法通常比开散列法时间效率更高。
A. 错误
B. 正确
满分：2 分
4. 希尔排序算法的时间复杂度为O(n2)。
A. 错误
B. 正确
满分：2 分
5. 如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。
A. 错误
B. 正确
满分：2 分
6. 有向图的邻接表和逆邻接表中表结点的个数不一定相等。
A. 错误
B. 正确
满分：2 分
7. 子串“ABC”在主串“AABCABCD”中的位置为3。
A. 错误
B. 正确
满分：2 分
8. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。
A. 错误
B. 正确
满分：2 分
9. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
A. 错误
B. 正确
满分：2 分
10. 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。
A. 错误
B. 正确
满分：2 分
11. 堆是完全二叉树，完全二叉树不一定是堆。
A. 错误
B. 正确
满分：2 分
12. 中序遍历二叉排序树可以得到一个有序的序列。
A. 错误
B. 正确
满分：2 分
13. 二维数组和多维数组均不是特殊的线性结构。
A. 错误
B. 正确
满分：2 分
14. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。
A. 错误
B. 正确
满分：2 分
15. 先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。
A. 错误
B. 正确
满分：2 分
16. 二维数组是数组元素为一维数组的线性表，因此它是线性结构。
A. 错误
B. 正确
满分：2 分
17. 层次遍历初始堆可以得到一个有序的序列。
A. 错误
B. 正确
满分：2 分
18. 由树转化成二叉树，该二叉树的右子树不一定为空。
A. 错误
B. 正确
满分：2 分
19. 顺序表用一维数组作为存储结构，因此顺序表是一维数组。
A. 错误
B. 正确
满分：2 分
20. 设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。
A. 错误
B. 正确
满分：2 分