《人武学院数据结构课后习题答案及期末综合练习.doc》由会员分享，可在线阅读，更多相关《人武学院数据结构课后习题答案及期末综合练习.doc（84页珍藏版）》请在金锄头文库上搜索。
1、资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。第十章内部排序一、 基本知识题答案1. 排序: 将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序。 内部排序: 数据存储在内存中, 并在内存中加以处理的排序方法叫内部排序。 堆: 堆是一个完全二叉树, 它的每个结点对应于原始数据的一个元素, 且规定如果一个结点有儿子结点, 此结点数据必须大于或等于其儿子结点数据。稳定排序: 一种排序方法, 若排序后具有相同关键字的记录仍维持原来的相对次序, 则称之为稳定的, 否则称为不稳定的。2. 回答下面问题 (1) 5000个无序的数据, 希望用最快速度挑选出其中前10个最大的元素, 在快速
2、排序、 堆排序、 归并排序和基数排序中采用哪种方法最好? 为什么? (2) 大多数排序算法都有哪两个基本操作? 答: (1)采用堆排序最好。 因为以上几种算法中, 快速排序、 归并排序和基数排序都是在排序结束后才能确定数据元素的全部顺序, 而无法知道排序过程中部分元素的有序性。堆排序则每次输出一个最大( 或最小) 的元素, 然后对堆进行调整, 保证堆顶的元素总是余下元素中最大( 或最小) 的。根据题意, 只要选取前10个最大的元素, 故采用堆排序方法是合适的。 (2)两个基本操作: 比较两个关键字的大小、 改变指向记录的指针或移动记录本身。3. 3. 已知序列17, 25, 55, 43, 3
3、, 32, 78, 67, 91, 请给出采用冒泡排序法对该序列作递增排序时每一趟的结果。 答: 采用冒泡排序法排序时的各趟结果如下: 初始: 17, 25, 55, 43, 3, 32, 78, 67, 91第1趟: 17, 25, 43, 3, 32, 55, 67, 78, 91第2趟: 17, 25, 3, 32, 43, 55, 67, 78, 91第3趟: 17, 3, 25, 32, 43, 55, 67, 78, 91第4趟: 3, 17, 25, 32, 43, 55, 67, 78, 91第5趟: 3, 17, 25, 32, 43, 55, 67, 78, 91第5趟无元
4、素交换, 排序结束。 4. 已知序列491, 77, 572, 16, 996, 101, 863, 258, 689, 325, 请分别给出采用快速排序、 堆排序和基数排序法对该序列作递增排序时每一趟的结果。答: 采用快速排序法排序时的各趟结果如下: 初始: 491, 77, 572, 16, 996, 101, 863, 258, 689, 325第1趟: 325, 77, 258, 16, 101 491 863, 996, 689, 572第2趟: 101, 77, 258, 16 325, 491 863, 996, 689, 572第3趟: 16, 77 101 258 325,
5、491 863, 996, 689, 572第4趟: 16 77 101 258 325, 491 863, 996, 689, 572第5趟: 16, 77, 101 258 325, 491 863, 996, 689, 572第6趟: 16, 77, 101, 258, 325, 491 863, 996, 689, 572第7趟: 16, 77, 101, 258, 325, 491 572, 689 863 996第8趟: 16, 77, 101, 258, 325, 491, 572 689 863 996第9趟: 16, 77, 101, 258, 325, 491, 572,
6、689, 863 996第10趟: 16, 77, 101, 258, 325, 491, 572, 689, 863, 996采用堆排序法排序时各趟的结果如下图所示: (a) 初始堆 (b) 建堆 (c) 交换996和77, 输出996 (d) 筛选调整采用基数排序法排序时各趟的结果如下: 初始: 491, 77, 572, 16, 996, 101, 863, 258, 689, 325第1趟( 按个位排序) : 491, 101, 572, 863, 352, 16, 996, 77, 258, 689第2趟( 按十位排序) : 101, 16, 352, 258, 863, 572,
7、77, 689, 491, 996第3趟( 按百位排序) : 16, 77, 101, 258, 352, 491, 572, 689, 863, 9965. 已知序列86, 94, 138, 62, 41, 54, 18, 32, 请给出采用插入排序法对该序列作递增排序时, 每一趟的结果。答: 采用插入排序法排序时各趟的结果如下: 初始: (86), 94, 138, 62, 41, 54, 18, 32第1趟: (86, 94), 138, 62, 41, 54, 18, 32第2趟: (86, 94, 138), 62, 41, 54, 18, 32第3趟: (62, 86, 94, 1
8、38), 41, 54, 18, 32第4趟: (41, 62, 86, 94, 138), 54, 18, 32第5趟: (41, 54, 62, 86, 94, 138), 18, 32第6趟: (18, 41, 54, 62, 86, 94, 138), 32第7趟: (18, 32, 41, 54, 62, 86, 94, 138) 6. 已知序列27, 35, 11, 9, 18, 30, 3, 23, 35, 20, 请给出采用归并排序法对该序列作递增排序时的每一趟的结果。答: 采用归并排序法排序时各趟的结果如下: 初始: 27, 35, 11, 9, 18, 30, 3, 23,
9、 35, 20第1趟: 27, 35 9, 11 18, 30 3, 23 20, 35第2趟: 9, 11, 27, 35 3, 18, 23, 30 20, 35第3趟: 9, 11, 27, 35 3, 18, 20, 23, 30, 35第4趟: 3, 9, 11, 18, 20, 23, 27, 30, 35, 35 二、 算法设计题答案1. 二、 算法设计题1. 一个线性表中的元素为全部为正或者负整数, 试设计一算法, 在尽可能少的时间内重排该表, 将正、 负整数分开, 使线性表中所有负整数在正整数前面。解: 本题的算法思想是: 设置两个变量分别指向表的首尾, 它们分别向中间移动,
10、 指向表首的如果遇到正整数, 指向表尾的如果遇到负整数则互相交换, 然后继续移动直至两者相遇。实现本题功能的算法如下: void part(int array,int n) int i,j; i=1; j=n;while(ij) while(ij & arrayi0) i+; while(i=0) j-; if(inext; /*p指向待插入的元素*/ while(p!=NULL) q=head; if(p-keykey) /*插到表首*/ pre-next =p-next; p-next =head; head=p; else while(q-next!=p & q-next -keykey
11、) q=q-next;if(q-next =p) pre=p;p=p-next; else pre-next =p-next; p-next =q-next; q-next =p; p=pre-next; 3. 试设计一个算法实现双向冒泡排序。( 双向冒泡排序就是在排序的过程中交替改变扫描方向。) 解: 实现本题功能的算法如下: void dbubblesort(sqlist r,int n) int i,j,flag; flag=1; i=1; while(flag!=0) flag=0; for(j=i;jrj+1)flag=1;r0=rj;rj=rj+1;rj+1=r0; for(j=n
12、-i;ji;j-) if(rjrj-1) flag=1;r0=rj;rj=rj-1;rj-1=r0; i+; 4.设一个一维数组An中存储了n个互不相同的整数, 且这些整数的值都在0到n-1之间, 即A中存储了从0到n-1这n个整数。试编写一算法将A排序, 结果存放在数组Bn中, 要求算法的时间复杂性为O(n)。 解: 实现本题功能的算法如下: void sort(int An,int Bn) int i; for(i=0;in;i+) BAi=Ai; 第九章一、 基础知识题1.(1)查找: 查找又称为查询或检索, 是在一批记录中依照某个域的指定域值, 找出相应的记录的操作。 (2)树型查找: 将原始数据表示成二叉排序树, 树的每个结点对应一个记录, 利用此二叉排序树进行类似于二分查找思想的数据查找, 这种查找方法称为树型查找。 (3)平衡因子: 二叉树中每一结点的左子树高度减右子树高度为该结点的平衡因子。 (4)散列函数: 根据关键字求存储地址的函数称为散列函数。 (5)两个不同的关键字,
