2011年12月考试数据结构第二次作业
一、单项选择题（本大题共100分，共 25 小题，每小题 4 分）
1. 树型结构是数据元素之间存在一种：( )
A. 一对多关系
B. 多对多关系
C. 多对一关系
D. 一对一关系
2. 以下的排序算法属于稳定排序算法的是（）
A. 基数排序
B. 快速排序
C. 希尔排序
D. 堆排序
3. 适于对动态查找表进行高效率查找的组织结构是（）
A. 有序表
B. 分块有序表
C. 二叉排序树
D. 线性链表
4. 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（）
A. 选择排序
B. 希尔排序
C. 归并排序
D. 快速排序
5. 在一棵二叉树中，度为2的结点有2个，那么，该树有（）个叶结点。
A. 3
B. 4
C. 5
D. 6
6. 图中有n个顶点，e条边，如果用邻接矩阵表示图，则深度优先搜索遍历图的时间复杂性为（）。
A. O(n)
B. O(e)
C. O(n2)
D. O(n+e)
7. 分块查找中块内的查找采用的查找方法是（）
A. 顺序查找
B. 折半查找
C. 顺序查找、折半查找都可以
D. 顺序查找、折半查找都不可以
8. 假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi 相关的所有弧的时间复杂度是( )
A. O(n)
B. O(e)
C. O(n+e)
D. O(n*e)
9. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。
A. 2
B. 1
C. 0
D. –1
10. 若n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵为一个什么矩阵？（）
A. 对称矩阵
B. 一般矩阵
C. 稀疏矩阵
D. 对角矩阵
11. 平衡二叉树的平衡因子的取值不可能是（）
A. 1
B. -1
C. 0
D. 2
12. 在二叉树的中序遍历递归算法中，顺着搜索路径，在第( )次经过结点时作访问操作。
A. 1
B. 2
C. 3
D. 4
13. VSAM文件中的记录均存放在（）。
A. 数据集
B. 索引集
C. 顺序集
D. 以上都不是
14. 关键路径是AOE网络中（）
A. 从源点到汇点的最长路径
B. 最短的回路
C. 从源点到汇点的最短路径
D. 最长的回路
15. 对数据元素序列（49，72，68，13，38，50，97，27）进行排序，如果采用起泡排序方法，则第二趟排序结果是（）
A. 49，68，13，38，50，72，27，97
B. 13，38，49，50，27，68，72，97
C. 49，13，38，50，68，27，72，97
D. 13，38，49，27，50，68，72，97
16. 如果只想得到1024个元素组成的序列中的前6个最小元素，那么用（）方法最快。
A. 起泡排序
C. 堆排序
D. 直接选择排序
17. 哈希表表长为m，k为关键字，哈希地址H(k)=k MOD p。
为了减少发生冲突的频率，一般取p为（）
A. 小于m的最大奇数
B. 小于m的最大合数
C. 小于m的最大素数
D. 大于m的最小素数
18. 处理溢出可以采用哈希表中处理冲突的各种方法，但对散列文件，主要采用（）
A. 开放地址法
B. 再哈希法
C. 链地址法
D. 建立一个公共溢出区
19. 设图G采用邻接表存储，则拓扑排序算法的时间复杂度为（）
A. O（n）
B. O(n+e)
C. O(n2)
D. O(n×e)
20. 一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（）。
A. {38，46，79，56，40，84}
B. {38，79，56，46，40，84}
C. {40，38，46，56，79，84}
D. {38，46，56，79，40，84}
21. 把一棵树转换为二叉树后，这棵二叉树的形态是（）。
A. 唯一的
B. 有多种
C. 有多种，但根结点都没有左孩子
D. 有多种，但根结点都没有右孩子
22. 在一个图中，所有顶点的度数之和等于所有边数的多少倍？（）
A. 1/2
B. 1
C. 2
D. 4。
23. 在对应于序列(12，5，8，15，25，10，30，7)的二叉排序树中查找30需要进行多少次比较。
（）
A. 1
B. 2
C. 3
D. 4
24. 在基于关键字比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O(nlog2n)。
B. 希尔排序
C. 归并排序
D. 快速排序
25. 下列哪项属于顺序文件的优点？（）
A. 顺序存取速度快
B. 适合随机存取
C. 适合按关键字存取
D. 以上都不是
答案：
一、单项选择题（100分，共 25 题，每小题 4 分）
1. A
2. A
3. C
4. B
5. A
6. C
7. A
8. C
9. A 10. A 11. D 12. B 13. A
14. A 15. C 16. D 17. C 18. C 19. B 20. C 21. A 22. C 23. D 24. C 25.
A。