法表示出查找过程。
第十章 排序
一、名词解释
1.排序 2.内部排序 3.外部排序 4.堆 5.堆排序 二、填空
1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。
2.按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。
3.按排序过程中依据的不同原则对内部排序方法进行分类，主要有：________、________、________、________等四类。
4.在排序算法中，分析算法的时间复杂性时，通常以________和________为标准操作。评价排序的另一个主要标准是执行算法所需要的________。
5.常用的插入排序方法有________插入排序、________插入排序、________插入排序和________插入排序。 6.以下为直接插入排序的算法。请分析算法，并在________上填充适当的语句。 void straightsort(list r); {for(i=___________;i<=n;i++)
{r[0]=r[i];j=i-1;
while(r[0].key r[j+1]=_______; } } 7.直接插入排序是稳定的，它的时间复杂性为________，空间复杂度为________。 8.以下为冒泡排序的算法。请分析算法，并在________上填充适当的语句。 void bulbblesort(int n,list r) /*flag为特征位，定义为布尔型*/ {for(i=1;i<=________;i++) {_______________; for(j=1;j<=_________;j++) if(r[j+1].key 9.对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是________。 10.以下对r[h],r[h+1],??r[p]子序列进行一趟忆速排序。请分析算法，并在________上填充适当的语句。 int quickpass(list r,int h,int p) {i=h;j=p;x=r[i];/*置初值，以第一个记录的键值为标准*/ while(i {while((r[j].key>=x.key)&&(i {________;i++;/* 将r[j].kiy while((r[i].key<=x.key)&&(i r[i]=________;return(i);/*一趟快速 排序结束，将x移至正确的位置*/ } 11.对快速排序来讲，其最好情况下的时间复杂度是________，其最坏情况下的时间复杂度是________。 12.以下是直接选择排序的算法。请分析算法，并在横线上填充适当的语句。 void select(list r,int n) {for(i=1;i<=________;i++)/*每次循环，选择出一个最小键值*/ {k=i; for(j=i+1;j<=n;j++)if(r[j].key if(______)swap(r[k],r[i]）;/*函数swap(r[k],r[i]）交换r[k]和r[i]的位置*/ } } 13.直接选择排序是不稳定的，其时间复杂性为________。 14.树形选择排序要增加________个结点以保存前面比较的结果。另外，排序的结果还需要另外开辟________. 15.树形选择排序可用一棵树来表示这一排序过程，树中的n个叶子代表待排序记录的键值，叶子上面一层是________两两比较的结果，依次类推。________表示最后选择出来的最小关键字。在选择次最小键值时，只需将叶结点中最小键值改成________，重新进行比较。依次类推。 16.若树形选择排序的叶子数为n，除第一次需执行________次比较就选择出一个最小的键值外，以后的每次都只经过________次比较就选择出一个最小的键值。所以树形选择排序总的时间开销为________。 17.从一个无序序列建立一个堆的方法是：首先将要排序的所有键值分放到一棵________的各个结点中，然后从i=________的结点ki开始，逐步把以kn/2,kn/2-1,kn/2-2,??为根的子树排成堆，直到以k1为根的树排成堆，就完成了建堆的过程。 18.堆排序是不稳定，空间复杂度为________。在最坏情况下，其时间复杂性也为________。 19.以下将ah,?,am和am+1,?,an两个有序序列（它们相应的关键字值满足Kh<=?<=Km,Km+1<=?<=Kn）合并成一个有序序列Rh，?,Rn（使其关键字值满足Kh<=?<=Kn）。请分析算法，并在________上填充适当的语句。 void merge(list a,list R,int h,int m,int n) {i=h;k=h;j=m+1; while((i<=m)&&(j<=n)) {if(a[i].key<=a[j].key){R[k]=________;________;} else{R[k]=________;________;} k++; } while(i<=________){R[k]=a[i];i++;k++;} while(j<=________){R[k]=a[j];j++;k++;} 21 } 此算法的执行时间为________. 20．归并排序要求待排序列由若干个___________的子序列组成。 21．二路归并排序的时间复杂度是___________。 22．对于n个记录的集合进行归并排序，所需的附加空间消耗是___________。 23.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则___________最省时间，___________最费时间。 24．分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递增顺序进行排序，最省时间的是___________算法，最费时间的是___________算法。 三、单项选择 1． 以下说法错误的是 （ ） ①直接插入排序的空间复杂度为O(1)。 ②快速排序附加存储开销为O(log2n)。 ③堆排序的空间复杂度为O(n)。 ④二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。 2． 以下不稳定的排序方法是 （ ） ①直接插入排序 ②冒泡排序 ③直接选择排序 ④二路归并排序 3． 以下稳定的排序方法是 （ ） ①快速排序 ②冒泡排序 ③直接选择排序 ④ 堆排序 2 4． 以下时间复杂性不是O(n)的排序方法是 （ ） ①直接插入排序 ②二路归并排序 ③冒泡排序 ④直接选择排序 5． 以下时间复杂性不是O(nlog2n)的排序方法是 （ ） ①堆排序 ② 直接插入排序 ③二路归并排序 ④快速排序 6． 在文件局部有序或文件长度较小的情况下，最佳的排序方法是 （ ） ①直接插入排序 ② 冒泡排序 ③ 直接选择排序 ④归并排序 7． 对于大文件的排序要研究在外设上的排序技术，即 （ ） ①快速排序法 ② 内排序法 ③外排序法 ④ 交叉排序法 8．排序的目的是为了以后对已排序的数据元数进行（ ）操作。 ①打印输出 ②分类 ③ 合并 ④查找 9．当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（ ） 2 ①n-1 ②log2n ③ 2log2n ④n 10.快速排序在最坏的情况下的时间复杂度是 （ ） 23 ①O(log2n) ②O(nlog2n) ③ O(n) ④O(n) 11.具有24个记录的序列，采用冒泡排序至少的比较次数是 （ ） ①1 ②23 ③ 24 ④ 529 12．用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下： 25 84 21 47 15 27 68 35 20 15 20 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 则采取的排序方法是 （ ） ①直接选择排序 ②冒泡排序 ③快速排序 ④二路归并排序 13．在排序过程中，健值比较的次数与初始序列的排列顺序无关的是 （ ） ①直接插入排序和快速排序 ②直接插入排序和归并排序 ③直接选择排序和归并排序 ④快速排序和归并排序 14．（ ）方法是从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。 ①归并排序 ② 插入排序 ③快速排序 ④选择排序 15（ ）方法是从未排序序列中挑选元素，并将其依次放入已排序序列的一端。 ①归并排序 ②插入排序 ③ 快速排序 ④选择排序 16．（ ）方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。 ①归并排序 ②插入排序 ③快速排序 ④选择排序 17．将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用（ ）方法能够最快地找出其中最大的正整数。 ①快速排序 ②插入排序 ③ 选择排序 ④ 归并排序 18一般情况下，以下四种排序方法中，平均查找长度最小的是 （ ） ①归并排序 ②快速排序 ③选择排序 ④插入排序 19．以下四种排序方法中，要求附加的内存容量最大的是 （ ） ①插入排序 ②选择排序 ③快速排序 ④归并排序 20已知一个链表中有3000个结点，每个结点存放一个整数，（ ）可用于解决这3000个整数的排序问题且不需要对算法作大的变动。 ①直接插入排序法 ②简单选择排序方法 ③快速排序方法 ④堆排序方法 21．若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行（ ）次比较。 ①33 ②45 ③70 ④91 22．在任何情况下，快速排序方法的时间性能总是最优的。这种说法 ①正确 ②错误 23．对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（ ）方法。 ①归并排序 ②直接插入排序 ③直接选择排序 ④快速排序。 四、简答及应用 1．对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行排序中各趟的结果。 2．举例说明本章介绍的各排序方法中那些是不稳定的？ 3．相对于树形选择排序，直接选择排序和堆排序有何优点？ 4．试比较直接插入排序、直接选择排序、快速排序、堆排序、归并排序的时、空性能。 5．判断下列两序列是否为堆？如不是，按照建堆的思想把它调整为堆，并用图表示建堆的过程。 （1）（3，10，12，22，36，18，28，40）； 22 （2）（5，8，11，15，23，20，32，7）。 6．对于下列一组关键字46，58，15，45，90，18，10，62，试写出快速排序每一趟的排序结果，并标出每一趟中各元素的移动方向。 7．已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。 第二章 线性表参考答案 一、 名词解释 （略） 二、 填空题 1、结点 起始 终端 序号 位置 前趋 后趋 2、（） ф 3、前趋 前趋 后趋 后趋 4、线性 5、线性 长度 表长 6、空表 7、初始化INITLATE（L） 求表长LENGTH（L） 读表长GET（L，i） 定位LOCATE （L，X） 插入INSERT（L，X，i） 删除DELETE（L，i） 8、逻辑结构中相邻的结点在存储结构中仍相邻 9、b+（i-1）x k 10、L．data[j]=L．data[j-1] 11、n O(n) n/2 O(n) 12、L.data[j-2]=l.data[j-1] 13、n-1 o(n) (n-1)/2 O(n) 14、i=1 i≦L.last 15、O(n) O(1) 16、L.last L.data[i-1] 17、单链表 循环链表 双链表 18、指针 19，单链表 20、头结点 表结点 21、首结点 尾结点 任何信息、特殊标志 表长 22、头结点 头结点 23、t=malloc(size) t->next=NULL 24、p=haed p=p->next 25、(p->next!=NULL)&&(j 26、(p->next!=NULL)&&(p->data!=x) 27、(p!=NULL)&&(p->next!=NULL) p->next 28、mailloc(size) p->next 29、insert_lklist(head,x,I) I++ n(n-1)/2 O(n2) 30、p=q p->next=NULL O(n) 31、单向循环链表（简称循环链表） 双向循环链表（简称双链表） 32、NULL 头结点 33、双链表 34、字符数组 赋值 35、空 ф 非空 字符 36、长度 相同 子 主 37、非紧缩 紧缩 38、结点大小 不属于字符集的特殊符号 三、 单项选择题 1、②2、①3、①4、②5、①6、②7、③8、③9、④ 10、②11、④12、③13、⑤14、④15、③16、①17、②18、③ 19、④20、④21、④22、223、②24、③25、④26、②27、③ 28、④29、①30、④31、②32、②33、④34、④35、③36、③ 37、②38、③39、②40、①41、④ 第三、四章答案 3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)? (2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 (3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 答： (1)出栈序列为：1324 (2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。 (3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是： 1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 3.2 链栈中为何不设置头结点? 答： 链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 3.3 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 答： 当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队 23 操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 3.4答： (1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。 (2)程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。 (3)程序段的功能是利用栈T，将一个非空栈S中值等于m的元素全部删去。 (4)程序段的功能是将一个循环队列Q经过S栈的处理，反向排列，原来的队头变成队尾，原来的队尾变成队头。 (5)这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。 4.1 (1)strcpy函数功能是串拷贝，concatt函数的功能是串联接。所以: 在执行strcpy(s3,s1); 后，s3的值是\ 在执行concatt(s3,\后，s3的值变成\ 在执行完concat(s3,s2);后，s3的值就成了\ (2)函数strcmp(串1，串2)的功能是串比较，按串的大小进行比较，返回大于0，等于0或小于0的值以表示串1比串2 大，串1等于串2 ，串1小于串2。因此在调用函数strcmp(s1,s2)后，返回值是大于0的数(字符比较是以ascii码值相比的) (3)首先，我们要知道&s1[5]是一个地址，当放在函数strcmp中时，它就表示指向以它为首地址的一个字符串，所以在strcmp( &s1[5],\中，前一个字符串值是\用它和\比较，应该是后者更大，所以返回值是小于0的数。 (4)strlen是求串长的函数，我们先将s1,s2联接起来，值是\数一数有几个字符?是不是23个(空格也是一个)? 所以返回值是23。 4.2解： 算法如下： void StrInsert(char *S, char *T, int i) {//将串T插入到串S的第i个位置上 char *Temp; if(i<=strlen(S)) { Temp=(char *)malloc(sizeof(char[Maxsize]));// 设置一个临时串 strcpy(Temp,&S[i]);//将第i位起以后的字符拷贝到临时串中 strcpy(&S[i], T);//将串T拷贝到串S的第i个位置处，覆盖后面的字符 strcat(S,Temp);//把临时串中的字符联接到串S后面 free( Temp ); } } 第六章 树和二叉树参考答案 一、名词解释（略） 二、填空题 1、 分支层次、根、直接前趋 2、 子孙、祖先 3、 空、只含根、非空左子树、非空右子树、非空左右子树 4、 2i-1 5、 2k-1 6、 n2+1 7、 最大值、完全 8、 floor(log2n)+1 9、 根、floor(i/2)、左孩子、右孩子、2i、右孩子、2i+1 10、顺序、链式 11、根 12、根、root 13、指向该结点的一个孩子、空指针NULL 14、2n、n-1、n+1 15、二叉链表、三叉链表 16、虚结点 17、*count++,countleaf(l->rchile,count) 18、访问根结点、遍历左子树、遍历右子树 19、DLR、LDR、LRD、先根（或前序）遍历、中根（或中序）遍历、后根（或后序）遍历 20、先根遍历、后根遍历、层次遍历 21、非终端结点、终端结点 22、WPL（T）＝ 23、i 26、floor(n/2),l,n,floor(n/2)+1 27、后面 28、相同 29、左子树、右子树、左子树、右子树 30、树 24 31、最短、较近 32、2m-1 33、（A），（E、G、I、J、K、L、N、O、P、Q、R），（3），（4），（5），（J、K）（C） 34、1、0 35、树、二叉树 36、只有一个根结点的树、空二叉树 37、n-1 38、n-2m+1 39、5、答案见图 A B A C C B A C C B A C B A B 40、WPL＝165 62 37 25 19 18 13 12 10 9 7 6 5 4 41、m-1 42、本题有一定的难度，其求解方法如下：设总结点数为n度为0、1、2、3的结点数分别为n0,n1,n3,则有下面两个等式成立： n=n0+n1+n2+n3 /*结点数*/ n-1=n1+2n2+3n3 /*分支数*/ 两式相减得 n0=1+n2+2n3=1+3+2x4=12 (12) 三、单项选择 1、①2、③3、④4、④5、②6、④7、③8、④9、③10、① 11、④12、②13、④14、①15、②16、①17、②18、④19、①20、② 21、④22、③23、①24、②25、②26、③27、③28、①29、②30、④ 31、④32、②33、②34、③35、①36、③37、③ 四、简答及应用题 4．就图简答题4.1（a）中的二叉树 ⑴根结点是A； ⑵叶结点是：D，F，J； ⑶G的双亲是：E； ⑷G的祖先是：A； ⑸G的孩子是：H； ⑹E的子孙是：F，G，H，I，J； ⑺E的兄弟是：B；C的兄弟是：C无兄弟；⑻结点B和I的层数分别是2，5； ⑼树的深度是：6； ⑽以结点G为根的子树的深度是：4； ⑾树的度数是：2。 就图简答题4.1(b)中的树 ⑴根结点是A； ⑵叶结点是：D，F，G，H，I，J； ⑶G的双亲是：C； ⑷G的祖先是：A； ⑸G的孩子是：G无孩子； ⑹E的子孙是：H，I，J； ⑺E的兄弟是：D；C的兄弟是：B； ⑻结点B和I的层数分别是2，4； ⑼树的深度是：4； ⑽以结点G为根的子树的深度是：1； ⑾树的度数是：3。 5．(a)因为该图所示结构，有两个结点没有直接前趋，即有两个根结点，而树只能有一个根结点。 (b)因为找不到树的根结点，所以不满足树的定义。 (c)因为最上面一个结点的后继结点分不出两个不相交的子集，不满足树的定义。 6．答案见图简答题6所示。 7．答案见图简答题7-2所示。 8．先根序列：A B C D E F G H I J; 中根序列：B C D A F E H J I G; 后根序列：D C B F J I H G E A。 9．⑴二叉树中任意一个结点都无左孩子； ⑵二叉树中任意一个结点都无右孩子； ⑶至多只有一个结点的二叉树。 10．由后根遍历序列得到二叉树的根结点A（后根序列中最后一个结点）；在中序序列中，A的左力是A的左子树上的结点，A的右边是A的右子树上的结点；再到后根序列中找左子树和右子树的根结点，依次类推，直到画出该二叉树，如图简答题10所示。 11．答案见图简答题11-2所示。 12．先根序列：A B E F K L C G D H I J； 后根序列：E K L F B G C H I J D A； 层次序列：A B C D E F G H I J K L。 13．答案见图简答题13-2所示。 14．答案见图简答题14-2所示。 (a)(b)(c)(d)(e) 15.答案见图简答题15-1所示。 25