江南大学网络教育第三阶段练习题
考试科目:《数据结构》第章至第章（总分100分）
__________学习中心（教学点）批次：层次：
专业：学号：身份证号：
身份证号一键查询姓名姓名：得分：
一单选题 (共10题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。)
A. m-1
B. m
C. [m/2]
D. [m/2]+1
2. 设有一组关键字值（46,79,56,38,40,84），则用快速排序的方法，以第一个记录为基准得
到的一次划分结果为（）。（2 分）
A. 38,40,46,56,79,84
B. 40,38,46,79,56,84
C. 40,38,46,56,79,84
D. 40,38,46,84,56,79
3. 直接插入排序在最好情况下的时间复杂度为（）。（2 分）
A. O(logn)
B. O(n)
C. O(n*logn)
D. O(n2)
4. 设有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表，至少要进行（）
次探测。（2 分）
A. k-1
B. k
C. k+1
D. k(k-1)/2
5. 外部排序是指（）。（2 分）
A. 在外存上进行的排序方法
B. 不需要使用内存的排序方法
C. 数据量很大，需要人工干预的排序方法
D. 排序前后数据在外存，排序时数据调入内存的排序方法
6. 下述文件中适合于磁带存储的是（）。（2 分）
A. 顺序文件
B. 索引文件
C. 散列文件
D. 多关键字文件
7. 设表中含100个数据元素，用折半查法进行查，则所需最大比较次数为（）。（2 分）
A. 50
B. 25
C. 10
D. 7
8. 设哈希表地址范围为0~19，哈希函数H(key)=key%17，使用二次探测再散列法处理冲突。若
表中已存放有关键字值为6、22、38、55的记录，则再放入关键字值为72的记录时，其存放地址应为（）。（2 分）
A. 2
B. 3
C. 7
D. 8
9. 将两个各有n个元素的有序表归并成一个有序表，最少进行（）次比较。（2 分）
A. n
B. 2n-1
C. 2n
D. n-1
10. ISAM文件和VSAM文件属于（）。（2 分）
A. 索引非顺序文件
B. 索引顺序文件
C. 顺序文件
D. 散列文件
二多选题 (共4题，总分值8分，下列选项中至少有2个或2个以上选项符合题目要求，请在答题卡上正确填涂。)
11. 下列说法中正确的是（）。（2 分）
A. 衡量查算法效率的主要标准是平均查长度;
B. 静态查是在查过程中不做增加、删除或修改的查;
C. 选择好的哈希函数就可以避免冲突的发生;
D. 在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针
域置空即可
12. 在下列排序方法中，每趟排序结束后都能选出一个元素放在其最终位置上的是（）。（2
分）
A. 简单选择排序;
B. 起泡排序;
C. 快速排序;
D. 直接插入排序;
E. 堆排序
13. 下列算法中，时间复杂度为的是（）。（2 分）
A. 希尔排序;
B. 堆排序;
C. 快速排序;
D. 简单选择排序;
E. 直接插入排序
14. 下列排序方法中，（）是稳定的排序方法。（2 分）
A. 简单选择排序;
B. 起泡排序;
C. 快速排序;
D. 直接插入排序;
E. 折半插入排序
三判断题 (共10题，总分值10分正确的填涂“A”，错误的填涂“B”。)
15. 理想情况下哈希查的等概率查成功的平均查长度是O(1)。（1 分）（对）
16. 进行折半查的表必须是顺序存储的有序表。（1 分）（对）
17. 对于两棵具有相同记录集合而具有不同形态的二叉查树，按中序遍历得到的结点序列是
相同的。（1 分）（对）
18. 堆是完全二叉树，完全二叉树不一定是堆。（1 分）（对）
19. 当待排序序列初始有序时，快速排序的时间复杂度为O(n)。（1 分）（错）
20. 散列函数值应当以同等概率取其值域的每个值。（1 分）（对）
21. 链式存储的有序表上也可以进行折半查，其时间复杂度与在顺序存储的有序表上相同。
（1 分）（错）
22. 对平衡二叉树进行中根遍历，可得到结点的有序序列。（1 分）（对）
23. 在插入排序、选择排序、快速排序和归并排序这四种排序方法中，快速排序所需要使用的
内存空间最大。（1 分）（错）
24. 折半查所对应的判定树，既是一棵二叉查树，又是一棵理想平衡二叉树。（1 分）
（对）
四简答题 (共2题，总分值20分 )
25. 画出对长度为１７的有序表进行折半查的判定树，并求等概率下查成功时的平均查
长度。（10 分）
平均查长度：。
26. 设用堆排序法对给定关键字序列（８５，６１，１５，３３，２４，９６，７６，４３）
按升序进行排序，试画出初始堆。（10 分）
９６，６１，８５，４３，２４，１５，７６，３３
五综合题 (共3题，总分值42分 )
27. 设内存有大小为５个记录的区域可供内部排序之用，文件的关键字序列为：（18，32，56，
40，23，11，8，99，58，36，21，7，4，15，19，87，73，52，82，63），要求用置换－选择排序求初始归并段。（14 分）
初始归并段１：18,23,32,40,56,58,99；
初始归并段２：7,8,11,15,19,21,36,52,63,73,82,87
初始归并段３：4
28. 设哈希函数H(key)=(3*key)%11，用开放定址法处理冲突，d i=i*((7*key)%10+1)，
i=1,2,3…。试在０～１0的散列地址空间中对关键字序列（２２，４１，５３，４６，３０，１３，０１，６７）造哈希表，并求等概率下查成功时的平均查长度。（14 分）
H(71)=6 H(28)=2 H(46)=7 H(14)=1
H(2)=2 H(20)=7 H(85)=7 H(58)=6
ASL=(1+1+1+1+2+3+4+5)/8=9/4
29. 设计递归算法，从大到小输出给定二叉排序树中所有关键字值不小于ｘ的数据元素。（14 分）
void OutputNLT(BiTree T,KeyType x){
if (!T) return;
if (!LT(T->data.key,x)){ //根结
点及右子树中所有结点的关键字值均不
小于x
Output(T->rchild); //按关键字
值从大到小的顺序输出右子树中所有结
点
发布评论