东师《数据结构》2012秋第二次在线作业(随机)第1份

2012秋第二次在线作业
试卷总分：100
单选题
判断题
一、单选题（共 20 道试题，共 60 分。）
V
1. 下列哪项不是利用查找表中数据元素的关系进行查找的方法 ()。
A. 有序表的查找
B. 二叉排序树的查找
C. AVL树
D. 散列查找
此题选: D 满分：3 分
2. 有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是 () 。
A. 60
B. 66
C. 18000
D. 33
满分：3 分
3. 排序趟数与序列的原始状态有关的排序方法是 () 排序法。
A. 直接插入
B. 直接选择
C. 冒泡
D. 归并
满分：3 分
4. 求图的最小(代价)生成树问题，考虑的是下面的哪一种图 ()。
A. 无向图
B. 有向图
C. 带权的无向图
D. 带权的有向图
满分：3 分
5. 分块查找要求表中的结点 ()。
A. 全部无序
B. 块之间无序
C. 全部有序
D. 块之间有序
此题选: D 满分：3 分
6. 倒排文件中倒排表是指 ()。
A. 主关键字索引
B. 次关键字索引
C. 物理顺序与逻辑顺序不一致
D. 多关键字索引
满分：3 分
7. ISAM文件和VSAM文件属于 ()。
A. 索引非顺序文件
B. 索引顺序文件
C. 顺序文件
D. 散列文件
满分：3 分
8. 对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是 ()。
A. 直接插入排序
B. 冒泡排序
C. 快速排序
D. 归并排序
此题选: D 满分：3 分
9. B+ 树应用在 () 文件系统中。
A. ISAM
B. VSAM
C. 顺序
D. 散列
满分：3 分
10. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是 ()。
A. 直接插入排序
B. 快速排序
C. 直接选择排序
D. 堆排序
满分：3 分
11. 顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
A. 附加文件
B. 按关键字大小排序
C. 按记录输入先后排序
D. 连续排序
满分：3 分
12. 有n个顶点的无向图的边数最多为 ()。
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
满分：3 分
13. 如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是 ()。
A. 顺序查找
B. 折半查找
C. 分块查找
D. 基于属性的查找
满分：3 分
14. 假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测？（）
A. k-1次
B. k次
C. k+1次
D. k(k+1)/2次
此题选: D 满分：3 分
15. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是 ()。
A. 直接插入排序
B. 快速排序
C. 直接选择排序
D. 归并排序
满分：3 分
16. 下面的排序方法中，辅助空间为O( n ) 的是 ()。
A. 希尔排序
B. 堆排序
C. 选择排序
D. 归并排序
此题选: D 满分：3 分
17. 设有2500个无序的记录，希望以最快的速度挑选出其中前10个排序码最大的记录，最好选用的排序方法是 ()。
A. 直接插入排序
B. 堆排序
C. 冒泡排序
D. 快速排序
满分：3 分
18. 广义表运算式tail ( ( ( a , b ) , ( c , d ) ) ) 的操作结果是 ()。
A. ( c , d )
B. c , d
C. ( ( c , d ) )
D. d
满分：3 分
19. 快速排序算法在下述哪种情况下效率最高 ()。
A. 被排序的数据已完全有序
B. 被排序的数据中含有多个相同的排序码
C. 被排序的数据已基本有序
D. 被排序的数据完全无序
此题选: D 满分：3 分
20. 数据序列 ( 8 , 9 , l0 , 4 , 5 , 6 , 20 , 1 , 2 ) 只能是下列排序算法中的 () 的两趟排序后的结果。
A. 直接选择排序
B. 冒泡排序
C. 直接插入排序
D. 堆排序
满分：3 分
2012秋第二次在线作业
试卷总分：100
单选题
判断题
二、判断题（共 20 道试题，共 40 分。）
V
1. 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。
A. 错误
B. 正确
满分：2 分
2. 对无序表用折半查找比顺序查找快。
A. 错误
B. 正确
满分：2 分
3. ( 101, 88, 46, 70, 34, 39, 45, 58, 66, 10）是堆。
A. 错误
B. 正确
满分：2 分
4. 对一棵二叉排序树按前序方法遍历得到的结点序列是从小到大的序列。
A. 错误
B. 正确
满分：2 分
5. 拓扑排序算法仅适用于有向无环图。
A. 错误
B. 正确
满分：2 分
6. 有向图的邻接矩阵是对称的。
A. 错误
B. 正确
满分：2 分
7. N个结点的二叉排序树有多种，其中树的高度为最小的二叉排序树是最佳的。
A. 错误
B. 正确
满分：2 分
8. 有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素个数的一半。
A. 错误
B. 正确
满分：2 分
9. 堆是完全二叉树。
A. 错误
B. 正确
满分：2 分
10. 折半查找法的查找速度一定比顺序查找法快。
A. 错误
B. 正确
满分：2 分
11. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
A. 错误
B. 正确
满分：2 分
12. 当广义表中的每个元素都是原子时，广义表便成了线性表。
A. 错误
B. 正确
满分：2 分
13. 无向图的邻接矩阵是对称的。
A. 错误
B. 正确
满分：2 分
14. 哈希表(散列表)的结点中只包含数据元素自身的信息，不包含任何指针。
A. 错误
B. 正确
满分：2 分
15. 最佳二叉排序树是AVL树 ( 平衡二叉排序树 ) 。
A. 错误
B. 正确
满分：2 分
16. 虽然关键字序列的顺序不一样，但依此生成的二叉排序树却是一样的。
A. 错误
B. 正确
满分：2 分
17. 二叉排序树删除一个结点后，仍是二叉排序树。
A. 错误
B. 正确
满分：2 分
18. 折半插入排序所需比较次数与待排序记录的初始排列状态无关。
A. 错误
B. 正确
满分：2 分
19. 归并排序在任何情况下都比所有简单的排序方法速度快。
A. 错误
B. 正确
满分：2 分
20. 用邻接矩阵法存储一个图所需的存储单元数目与图的边数无关。
A. 错误
B. 正确
满分：2 分