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

2013春第二次在线作业
试卷总分：100
单选题
判断题
一、单选题（共 20 道试题，共 60 分。）
V
1. 对关键码序列 28 , 16 , 32, 12, 60, 2, 5, 72 快速排序 ( 从小到大序 ) , 一次划分的结果为 ()。
A. ( 2 , 5 , 12 , 16 ) 28 ( 60 , 32 , 72 )
B. ( 5 , 16 , 2 , 12 ) 28 ( 60 , 32 , 72 )
C. ( 2 , 16 , 12 , 5 ) 28 ( 60 , 32 , 72 )
D. ( 5 , 16 , 2 , 12 ) 28 ( 32 , 60 , 72 )
满分：3 分
2. 一个有n个结点的图，连通分量的个数最少为 ()。
A. 0
B. 1
C. n-1
D. n
满分：3 分
3. 广义表运算式tail ( ( ( a , b ) , ( c , d ) ) ) 的操作结果是 ()。
A. ( c , d )
B. c , d
C. ( ( c , d ) )
D. d
满分：3 分
4. 设有n个结点的二叉排序树，对于成功的查找，最少的比较次数为()。
A. Ο( 1 )
B. Ο(log2n)
C. Ο(n)
D. Ο(nlog2n)
满分：3 分
5. 内排序方法的稳定性是指 ()。
A. 该排序算法不允许有相同的关键字记录
B. 该排序算法允许有相同的关键字记录
C. 平均时间为O(nlog2n ) 的排序方法
D. 以上都不对
此题选: D 满分：3 分
6. 快速排序算法在下述哪种情况下效率最高 ()。
A. 被排序的数据已完全有序
B. 被排序的数据中含有多个相同的排序码
C. 被排序的数据已基本有序
D. 被排序的数据完全无序
此题选: D 满分：3 分
7. 设二维数组A[0..m-1][0..n-1]按行优先顺序存储且每个元素占c个单元，则元素A[j]的地址为 ()。
A. LOC(A[0][0]) + (j*m+i)*c
B. LOC(A[0][0]) + (i*n+j)*c
C. LOC(A[0][0]) + [(j-1)*m+i-1]*c
D. LOC(A[0][0]) + [(i-1)*n+j-1]*c
满分：3 分
8. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是 ()。
A. 逆拓扑有序
B. 拓扑有序
C. 无序的
D. 部分有序的
满分：3 分
9. 分块查找要求表中的结点 ()。
A. 全部无序
B. 块之间无序
C. 全部有序
D. 块之间有序
此题选: D 满分：3 分
10. ISAM文件和VSAM文件属于 ()。
A. 索引非顺序文件
B. 索引顺序文件
C. 顺序文件
D. 散列文件
满分：3 分
11. 设有100个关键字，用折半查找法进行查找时，最小比较次数为 ()。
A. 7
B. 4
C. 2
D. 1
此题选: D 满分：3 分
12. 平衡的二叉排序树(AVL树)属于()的数据结构。
A. 动态
B. 静态
C. 线性
D. 无结构
满分：3 分
13. 最佳二叉排序树属于()的数据结构。
A. 动态
B. 静态
C. 线性
D. 无结构
满分：3 分
14. 对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是 ()。
A. 直接插入排序
B. 冒泡排序
C. 快速排序
D. 归并排序
此题选: D 满分：3 分
15. 有n个顶点的有向图的边数最多为 ()。
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
满分：3 分
16. 排序趟数与序列的原始状态有关的排序方法是 () 排序法。
A. 直接插入
B. 直接选择
C. 冒泡
D. 归并
满分：3 分
17. 在索引顺序文件中， ()。
A. 主文件是无序的
B. 主文件是有序的
C. 不适宜随机查找
D. 索引是稠密索引
满分：3 分
18. 顺序查找法适合于存储结构为下列哪一种方式的线性表 ()。
A. 散列存储
B. 顺序存储或链接存储
C. 压缩存储
D. 索引存储
满分：3 分
19. 存放在外存中的数据的组织结构是 ()。
A. 数组
B. 表
C. 文件
D. 链表
满分：3 分
20. 折半查找要求结点 ()。
A. 无序、顺序存储
B. 无序、链接存储
C. 有序、顺序存储
D. 有序、链接存储
满分：3 分
2013春第二次在线作业
试卷总分：100
单选题
判断题
二、判断题（共 20 道试题，共 40 分。）
V
1. 存放在磁盘、磁带上的文件，既可以是顺序文件，也可以是索引结构或其他结构类型的文件。
A. 错误
B. 正确
满分：2 分
2. 对无环有向图进行拓扑排序一定能够得到完整的拓扑序列。
A. 错误
B. 正确
满分：2 分
3. 快速排序总比简单的排序方法快。
A. 错误
B. 正确
满分：2 分
4. 折半查找法的查找速度一定比顺序查找法快。
A. 错误
B. 正确
满分：2 分
5. 对一棵二叉排序树按前序方法遍历得到的结点序列是从小到大的序列。
A. 错误
B. 正确
满分：2 分
6. 在有向图中，度为0的顶点称为终端顶点(或叶子)。
A. 错误
B. 正确
满分：2 分
7. 对一棵二叉排序树按中序方法遍历得到的结点序列是从小到大的序列。
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. 倒排文件与多重表文件的次关键字索引结构是不同的。
A. 错误
B. 正确
满分：2 分
15. 归并排序的辅助存储空间代价为O(1 )。
A. 错误
B. 正确
满分：2 分
16. N个结点的二叉排序树有多种，其中树的高度为最小的二叉排序树是最佳的。
A. 错误
B. 正确
满分：2 分
17. 二维以上的数组其实是一种特殊的广义表。
A. 错误
B. 正确
满分：2 分
18. 需要借助于一个栈来实现DFS算法。
A. 错误
B. 正确
满分：2 分
19. 快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。
A. 错误
B. 正确
满分：2 分
20. 在待排数据基本有序的情况下，快速排序效果最好。
A. 错误
B. 正确
满分：2 分