当前位置：文档之家 › 清华大学课程讲义-数据结构答案9[1]电子教案

清华大学课程讲义-数据结构答案9[1]电子教案

  • 格式：doc
  • 大小：179.00 KB
  • 文档页数：8

9-1 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的? 【解答】

9-2 设待排序的关键码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次关键码比较。 (1) 直接插入排序 (2) 希尔排序(增量为5,2,1) (3) 起泡排序 (4) 快速排序 (5) 直接选择排序 (6) 锦标赛排序 (7) 堆排序 (8) 二路归并排序 (9) 基数排序 【解答】

9-3 在起泡排序过程中，什么情况下关键码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？ 【解答】 如果在待排序序列的后面的若干关键码比前面的关键码小，则在起泡排序的过程中，关键码可能向与最终它应移向的位置相反的方向移动。例如， 57 40 38 11 13 34 48 75 6 19 9 7 如9向相反方向移动 6 57 40 38 11 13 34 48 75 7 19 9 如19向相反方向移动 6 7 57 40 38 11 13 34 48 75 9 19 如9向最终方向移动 6 7 9 57 40 38 11 13 34 48 75 19 如13向相反方向移动 6 7 9 11 57 40 38 13 19 34 48 75 如13向最终方向移动 6 7 9 11 13 57 40 38 19 34 48 75 如34向相反方向移动 6 7 9 11 13 19 57 40 38 34 48 75 6 7 9 11 13 19 34 57 40 38 48 75 6 7 9 11 13 19 34

9-4 试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把关键码最大的对象放到序列的最后，第二趟把关键码最小的对象放到序列的最前面。如此反复进行。 【解答】

template void dataList :: shake_Sort ( ) { //奇数趟对表Vector从前向后, 比较相邻的关键码, 遇到逆序即交换, 直到把参加比较关键码序列 //中最大的关键码移到序列尾部。偶数趟从后向前, 比较相邻的关键码, 遇到逆序即交换, 直到把 //参加比较关键码序列中最小的关键码移到序列前端。 int i = 1, j; int exchange; while ( i < CurrentSize ) { //起泡排序趟数不超过n-1

exchange = 0; //假定元素未交换 for ( j = CurrentSize-i; j >= i; j-- ) //逆向起泡 if ( Vector[j-1] > Vector[j] ) { //发生逆序 Swap ( Vector[j-1], Vector[j] ); //交换, 最小关键码放在Vector[i-1]处 exchange = 1; //做“发生了交换”标志 } if ( exchange == 0 ) break; ////当exchange为0则停止排序 for ( j = i; j <= CurrentSize-i-1; j++ ) //正向起泡 if ( Vector[j] > Vector[j+1] ) { //发生逆序 Swap ( Vector[j], Vector[j+1] ); //交换, 最大关键码放在Vector[n-i]处 exchange = 1; //做“发生了交换”标志 } if ( exchange == 0 ) break; ////当exchange为0则停止排序 i++; } }

9-5 如果待排序的关键码序列已经按非递减次序有序排列，试证明函数QuickSort( )的计算时间将下降到O(n2)。 9-6 在实现快速排序的非递归算法时，可根据基准对象，将待排序关键码序列划分为两个子序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的深度为O(log2n)。

9-7 在实现快速排序算法时，可先检查位于两端及中点的关键码，取三者之中的数值不是最大也不是最小的关键码作为基准对象。试编写基于这种思想的快速排序算法，并证明对于已排序的关键码序列，该算法的计算时间为O(nlog2n)。

9-8在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端点。那么能否用队列来代替这个栈? 为什么? 【解答】 可以用队列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分为两个子区间，然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时，保存另一个子区间的上界和下界，待该区间处理完成后再从栈中取出另一子区间的边界，对其进行处理。这个功能利用队列也可以实现，只不过是处理子区间的顺序有所变动而已。

9-9 试设计一个算法, 使得在O(n)的时间内重排数组, 将所有取负值的关键码排在所有取正值(非负值)的关键码之前。 【解答】

9-10 奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i扫描，第二趟对序列中的所有偶数项i扫描。若A[i] > A[i+1]，则交换它们。第三趟有对所有的奇数项，第四趟对所有的偶数项，…，如此反复，直到整个序列全部排好序为止。 (1) 这种排序方法结束的条件是什么？ (2) 写出奇偶交换排序的算法。 (3) 当待排序关键码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换排序过程中的关键码比较次数是多少？ 【解答】

9-11 请编写一个算法，在基于单链表表示的待排序关键码序列上进行简单选择排序。 【解答】

9-12 若参加锦标赛排序的关键码有11个，为了完成排序，至少需要多少次关键码比较？ 【解答】

9-13 试给出适用于锦标赛排序的胜者树的类型声明。并写一个函数，对n个参加排序的对象，构造胜者树。设n是2的幂。 【解答】

9-14 手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个关键码后堆的变化。 (1) 按字母顺序排序：Tim, Dot, Eva, Rom, Kim, guy, Ann, Jim, Kay, Ron, Jan (2) 按数值递增顺序排序：26, 33, 35, 29, 19, 12, 22 (3) 同样7个数字，换一个初始排列，再按数值的递增 顺序排序：12, 19, 33, 26, 29, 35, 22 【解答】

9-15 如果只想在一个有n个元素的任意序列中得到其中最小的第k (k<分排序序列, 那么最好采用什么排序方法? 为什么? 例如有这样一个序列: {503, 017, 512, 908, 170, 897, 275, 653, 612, 154, 509, 612*, 677, 765, 094}, 要得到其第4个元素之前的部分有序序列: {017, 094, 154, 170}, 用所选择的算法实现时, 要执行多少次比较? 【解答】 一般来讲，当n比较大且要选的数据k << n时, 采用堆排序方法中的筛选(调整)算法最好。但当n比较小时，采用锦标赛排序方法更好。 例如，对于序列{ 57, 40, 38, 11, 13, 34, 48, 75, 6, 19, 9, 7 }，选最小的数据6，需形成初始堆，进行18次数据比较；选次小数据7时，需进行4次数据比较；再选数据9时，需进行6次数据比较；选数据11时，需进行4次数据比较。

但如果选用锦标赛排序，对于有n个数据的序列，选最小数据需进行n -1次数据比较，以后每选一个数据，进行数据比较的次数，均需 log2n 次。例如，同样12个数据，第一次选最小的数据6，需进行11次数据比较，以后选7、9、11时，都是 log212 = 3次数据比较。

9-16 希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法, 试举例说明。 【解答】 (1) 希尔排序 { 512 275 275* 061 } 增量为2 { 275* 061 512 275 } 增量为1 { 061 275* 275 512 }

(2) 直接选择排序 { 275 275* 512 061 } i = 1 { 061 275* 512 275 } i = 2 { 061 275* 512 275 } i = 3 { 061 275* 275 512 }

(3) 快速排序 { 512 275 275* } { 275* 275 512 }

(4) 堆排序 { 275 275* 061 170 } 已经是最大堆，交换275与170 { 170 275* 061 275 } 对前3个调整 { 275* 170 061 275 } 前3个最大堆，交换275*与061 { 061 170 275* 275 } 对前2个调整 { 170 061 275* 275 } 前2个最大堆，交换170与061 { 061 170 275* 275 } 9-17 设有n个待排序元素存放在一个不带表头结点的单链表中, 每个链表结点只存放一个元素, 头指针为r。试设计一个算法, 对其进行二路归并排序, 要求不移动结点中的元素, 只改各链结点中的指针, 排序后r仍指示结果链表的第一个结点。（提示：先对待排序的单链表进行一次扫描, 将它划分为若干有序的子链表, 其表头指针存放在一个指针队列中。当队列不空时重复执行, 从队列中退出两个有序子链表, 对它们进行二路归并, 结果链表的表头指针存放到队列中。如果队列中退出一个有序子链表后变成空队列, 则算法结束。这个有序子链表即为所求。) 【解答】

(1) 两路归并算法 procedure merge ( ha, hb : pointer; var hc : pointer ); var pa, pb, pc : pointer; begin

if ha↑.data <= hb↑.data then begin hc := ha; pa := ha↑.next; pb := hb; end else begin hc := hb; pb := hb↑.next; pa := ha; end; pc := hc; while ( pa <> nil ) and ( pb <> nil ) do

if pa↑.data <= pb↑.data then begin pc↑.next := pa; pc := pa; pa := pa↑.next; end else begin pc↑.next := pb; pc := pb; pb := pb↑.next; end; if pa <> nil then pc↑.next := pa else pc↑.next := pb; end; (2) 归并排序主程序 procedure mergesort( var r : pointer ); var s, t : pointer; var Q : Queue; begin if r = nil then return; SetEmpty ( Q ); s := r; Enqueue( Q, r ); while s <> nil do begin t := s↑.next; while ( t <> nil ) and ( s↑.data <= t↑.data ) do begin s := t; t := t↑.next; end; if t <> nil then begin s↑.next := nil; s := t; EnQueue( Q, s ); end; end; while not IsEmpty( Q ) do begin r := DlQueue( Q ); if IsEmpty( Q ) then break; s := DlQueue( Q );

合集下载

数据结构(C语言版清华大学出版社)-章课后部分答案

数据结构(C语言版清华大学出版社)-章课后部分答案

第八章选择题1. C2.A3.B4.C5.D6.B7.B8.A9.D 10.D 11.C 12.C填空题1.n、n+12. 43.8.25( 折半查找所在块 )4.左子树、右子树5.266.顺序、(n+1)/2、O(log2n)7.m-1、[m/2]-18.直接定址应用题1.进行折半查找时，判定树是唯一的，折半查找过程是走了一条从根节点到末端节点的路径，所以其最大查找长度为判定树深度[log2n]+1.其平均查找长度约为[log2n+1]-1.在二叉排序树上查找时，其最大查找长度也是与二叉树的深度相关，但是含有n个节点的二叉排序树不是唯一的，当对n个元素的有序序列构造一棵二叉排序树时，得到的二叉排序树的深度也为n，在该二叉树上查找就演变成顺序查找，此时的最大查找长度为n；在随机情况下二叉排序树的平均查找长度为1+4log2n。

因此就查找效率而言，二分查找的效率优于二叉排序树查找，但是二叉排序树便于插入和删除，在该方面性能更优。

3. 评价哈希函数优劣的因素有：能否将关键字均匀的映射到哈希表中，有无好的处理冲突的方法，哈希函数的计算是否简单等。

冲突的概念：若两个不同的关键字Ki和Kj，其对应的哈希地址Hash(Ki) =Hash(Kj)，则称为地址冲突，称Ki和K,j为同义词。

（1）开放定址法（2）重哈希法（3）链接地址法4.（1）构造的二叉排序树，如图（2）中序遍历结果如下：10 12 15 20 24 28 30 35 46 50 55 68（4）平均查找长度如下：ASLsucc = （1x1+2x2+3x3+4x3+5x3）/12 = 41/128.哈希地址如下：H(35) = 35%11 = 2H(67) = 67%11 = 1H(42) = 42%11 = 9H(21) = 21%11 = 10H(29) = 29%11 = 7H(86) = 86%11 = 9H(95) = 95%11 = 7H(47) = 47%11 = 3H(50) = 50%11 = 6H(36) = 36%11 = 3H(91) = 91%11 = 3第九章选择题1. D2.C3.B4.D5.C6.B7.A8.A9.D 10.D填空题1.插入排序、交换排序、选择排序、归并排序2.移动（或者交换）3.归并排序、快速排序、堆排序4.保存当前要插入的记录，可以省去在查找插入位置时的对是否出界的判断5.O(n)、O(log2n)6.直接插入排序或者改进了的冒泡排序、快速排序7.Log2n、n8.完全二叉树、n/29.1510.{12 38 25 35 50 74 63 90}应用题11.（1）Shell排序(步长为5 3 1)每趟的排序结果初始序列为100 87 52 61 27 170 37 45 61 118 14 88 32步长为5的排序14 37 32 61 27 100 87 45 61 118 170 88 52步长为3的排序结果14 27 32 52 37 61 61 45 88 87 170 100 118步长为1的排序结果14 27 32 37 45 52 61 61 87 88 100 118最后结果14 27 32 37 45 52 61 61 87 88 100 118 170（2）快速排序每趟的排序结果如图初始序列100 87 52 61 27 170 37 45 61 118 14 88 32第一趟排序[32 87 52 61 27 88 37 45 61 14]100[118 170]第二趟排序[14 27]32[61 52 88 37 45 61 87]100 118[170]第三趟排序14[27]32[45 52 37]61[88 61 87]100 118[170]第四趟排序14[27]32[37]45[52]61[87 61]88 100 118[170]第五趟排序14[27]32[37]45[52]61[87 61]88 100 118[170]最后结果14[27]32[37]45[52]61[61]87 88 100 118[170]（3）二路归并排序每趟的排序结果初始序列[100][87][52][61][27][170][37][45][61][118][14][88][32]第一趟归并[87 100][52 61][27 170][37 45][61 118][14 88][32]第二趟归并[52 61 87 100][27 37 45 170][14 61 88 118][32]第三趟归并排序[27 37 45 52 61 87 100 170][14 32 61 88 118]第四趟归并排序[14 27 32 37 45 52 61 61 87 88 100 118 170]最后结果14 27 32 37 45 52 61 61 87 88 100 118 17012.采用快速排序时，第一趟排序过程中的数据移动如图：算法设计题1.分析：为讨论方便，待排序记录的定义为（后面各算法都采用此定义）：#define MAXSIZE 100 /* 顺序表的最大长度，假定顺序表的长度为100 */ typedef int KeyType; /* 假定关键字类型为整数类型 */typedef struct {KeyType key; /* 关键字项 */OtherType other; /* 其他项 */}DataType; /* 数据元素类型 */typedef struct {DataType R[MAXSIZE+1]; /* R[0]闲置或者充当哨站 */int length; /* 顺序表长度 */}sqList; /* 顺序表类型 */设n个整数存储在R[1..n]中，因为前n-2个元素有序，若采用直接插入算法，共要比较和移动n-2次，如果最后两个元素做一个批处理，那么比较次数和移动次数将大大减小。

数据结构 第9章答案

数据结构 第9章答案

第9章 查找参考答案一、填空题（每空1分，共10分）1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。

2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。

设有100个结点，用二分法查找时，最大比较次数是 7 。

3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。

解：显然，平均查找长度＝O （log 2n ）<5次（25）。

但具体是多少次，则不应当按照公式)1(log 12++=n nn ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。

因为这是在假设n ＝2m -1的情况下推导出来的公式。

应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！4．【计研题2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。

6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。

7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。

如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。

(而任一元素查找次数 ≤n-1)二、单项选择题（每小题1分，共27分）（ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;Ｃ. ＡＳＬ＝n ＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（ A ）2．【计研题2001】折半查找有序表（4，6，10，12，20，30，50，70，88，100）。

清华大学出版社数据结构C++版第2版课后习题答案最全整理精编版

清华大学出版社数据结构C++版第2版课后习题答案最全整理精编版

第1章绪论课后习题讲解1.填空（1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素3（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构, 都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺ 在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻ 设待处理问题的规模为n,若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

【解答】0（1），0（nlog2n）【分析】用大0记号表示算法的时间复杂度，需要将低次幕去掉，将最高次幕的系数去掉。

2. 选择题⑴ 顺序存储结构中数据兀素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A线性结构B非线性结构C存储位置D指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

数据结构(C语言版)9-12章练习 答案 清华大学出版社

数据结构(C语言版)9-12章练习 答案 清华大学出版社

9-12章数据结构作业答案第九章查找选择题1、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )A．（n+1）/2 B. n/2 C. n D. [（1+n）*n ]/22. 下面关于二分查找的叙述正确的是 ( D )A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序且表中数据必须是整型，实型或字符型C. 表必须有序，而且只能从小到大排列D. 表必须有序，且表只能以顺序方式存储3. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2)C ）时其查找效率最低(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A) 个链表。

这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C) （1） A．17 B. 13 C. 16 D. 任意（2） A．0至17 B. 1至17 C. 0至16 D. 1至16判断题1．Hash表的平均查找长度与处理冲突的方法无关。

(错)2. 若散列表的负载因子α<1，则可避免碰撞的产生。

（错）3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。

（错）填空题1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为 4 .算法应用题1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。

要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

2. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲突。