计算机软件基础习题及参考答案

习题一1.什么是数据结构，数据的逻辑结构，数据的存储结构？数据结构对算法有什么影响？请举例说明。2数据结构的存储方式主要有哪两种？它们之间的本质区别是什么?3.设〃为正整数，分析下列各程序段中加下划线的语句的执行次数。(1)for(inti=1;iV="i-H)for(intj=1;jV=弭j-H){c[i]田=0.Qfor(intk=1;k<=rxk-H)c「i[「i[=c「i]IT+a「i]k*bkIT;}0x=Qy=Qfor(inti=1;i"i-H)for(intj=1;ji;j-H)for(intk=1;k<=j;leH)x=x+y;③inti=1,j=1;砒ile 8&.j<=n){i=i+1；j=j+i；}④*inti=1;do{for(intj=1;j<=店j-H)i=i+i；}vdiile(i<100+ri);4试编写一个函数计算n!*7的值，结果存放于数组A区rraySiz句的第n个数组元素中，OWn<arraySize,若设计算机中允许的整数的最大值为maxlnt,则当n>arraySize或者对于某一个kQWk<rj),使得k!*7>maxlnt时，应按出错处理。可有如下三种不同的出错处理方式：(1)用printf显示错误信息及exit。)语句来终止执行并报告错误；0用返回整数函数值0,1来实现算法，以区别是正常返回还是错误返回；(3)在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。5.设有一个线性表 即…，aQ存放在一个一维数组A|arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为Qt,八，…，a,&)。最后分析此算法的时间复杂度及空间复杂度。6顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有127个元素的顺序表进行插入，平均需要移动多少个元素？删除一个元素,又平均需要移动多少个元素？7.利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度，并分析②与③的时间复杂度出现差异的原因。(1)从顺序表中删除具有给定值x的所有元素。②从顺序表中删除其值在给定值s与t之间(要求s小于t)的所有元素。⑤从有序顺序表中删除其值在给定值s与t之间(要求s小于t)的所有元素。④将两个有序顺序表la,1b合并成一个新的有序顺序表k(5)从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。&线性表可用顺序表或链表存储。试问：(D两种存储表示各有哪些主要优缺点?0如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3)若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？9.试写出计算线性链表长度的算法。设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。pr=0P Pr hPiQaniQHZQHZHrmVTnhrViIL设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表，其中一链表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。12设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。.设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。.在一个循环链表中寻找值为x的结点，并将该结点移到第一个结点之前。.对于下面的每一步，画出栈元素和栈顶指针的示意图:(1)栈初始化；(2)元素x入栈;(3元素y入栈;(④出栈(5)栈初始化(6)元素z入栈16铁路进行列车调度时，常把站台设计成栈式结构的展人.，以皿站台，如右图所示。试问：(1)设有编号为L23,45,6的六辆列车，顺序开户入栈式结构的站台，则可能的出栈序列有多少种？0若进站的六辆列车顺序如上所述，那么是否能够得到435612,325641,154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到即写出।进栈域'出栈得序列)。17.试证明：若借助栈可由输入序列L2,3,…，n得到一个输出序列p,R,P,…，P它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况,即存在ivjvk,使得pvrvp。提示：用反证法)1&将编号为0和1的两个栈存放于一个数组空间V项中，栈底分别处于数组的两端。当第0号栈的栈顶指针top也等于T时该栈为空，当第1号栈的栈顶指针topD□等于m时该栈为空。两个栈均从两端向中间增长。当向第0号栈插入一个新元素时，使top⑻增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top口］减1得到新的栈顶位置。当top⑼+1=top口］时或top⑻=top口］—1时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈(DoubleStacD结构的类定义，并实现判栈空、判栈满、插入、删除算法。.改写顺序栈的进栈成员函数Push3,要求当栈满时执行一个stackFull()操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前gxSize位置。.根据教案中给出的优先级，回答以下问题：(1)在表达式求值的过程中，如果表达式e含有n个运算符和分界符，问操作数栈〜中最多可存入多少个元素？②如果表达式e含有n个运算符，且括号嵌套的最大深度为6层，问栈中最多可存入多少个元素？.表达式的中缀表示为a*x-b/xA2,试利用栈将它改为后缀表示ax*bx2y一写出转换过程中栈的变化。藻示乘方运算)22设循环队列的容量为70(序号从1到7Q),经过一系列入队和退队运算后，有：front=15,realgfront=45,reai^lO问在上述两种情况下，循环队列中各有多少个元素？23.设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结构的队列的插入tnqueuH和删除(dequeue)算法，并给出队列空和队列满的条件。习题21.列出右图所示二叉树的叶结点、分支结点和每个结点的层次。2使用(1)顺序表示和②二叉链表表示法，分别画出上图所示二叉树的存储表示。.在结点个数为n(h>D的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。.如果一棵树有A个度为1的结点，有垃个度为2的结点，…，ri个度为m的结点，试问有多少个度为0的结点？试推导之。6若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：(1)统计二叉树中叶结点的个数。0以二叉树为参数，交换每个结点的左子女和右子女。0)求二叉树的深度。.一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：(1)各层的结点个数是多少？0编号为i的结点的父结点若存在)的编号是多少？0)编号为i的结点的第g孩子结点若存在)的编号是多少？④编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？(5)若结点个数为n,则高度h是n的什么函数关系？&请画出下图所示的树所对应的二叉树。.已知一棵二叉树的前序遍历的结果是ABKEFCHIJ,中序遍历的结果是EBOMFHIGJ,试画出这棵二叉树。.给定权值集合(15,03,1402,06,09,16,171,构造相应的霍夫曼树，并计算它的带权路径长度。习题三1.设有序顺序表中的元素依次为017,094154170,275,503,509,512,553,612,677,765,897,908,试画出对其进行折半查找时的二叉查找树，并计算查找成功的平均查找长度和查找不成功的平均查找长度。2若对有n个元素的有序顺序表和无序顺序表进行顺序查找，试就下列三种情况分别讨论两者在等查找概率时的平均查找长度是否相同？(1)查找失败；0查找成功，且表中只有一个关键码等于给定值k的对象；0)查找成功，且表中有若干个关键码等于给定值皿对象，要求一次查找找出所有对象。.设有10000个记录对象，通过分块划分为若干子表并建立索引，那么为了提高查找效率，每一个子表的大小应设计为多大？.设散列表为HT口引，散列函数为H伏朗=key^\用闭散列法解决冲突，对下列关键码序列1Z23,45,57,20,03,7&31,15,36造表。(1)采用线性探测法寻找下一个空位，画出相应的散列表，并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。②采用随机探测法寻找下一个空位，随机数序列为：5,4Z7,3,6,-o画出相应的散列表，并计算等概率下查找成功的平均查找长度。.设有150个记录要存储到散列表中，要求利用线性探查法解决冲突，同时要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？设a是散列表的装载因子，则有ASLsucc=-(l+—)2 \-a6设有15000个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连结，每个页块可存放30个记录。若采用按桶散列，且要求查找到一个已有记录的平均读盘时间不超过1,5次，则该文件应设置多少个桶？已知，链地址法的平均查找长度网尸1女/2.设待排序的排序码序列为｛12,2,16,3Q2&10,16*20,&试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。(1)直接插入排序 0希尔排序增量为5,2,1) 6)冒泡排序⑷快速排序 (5)直接选择排序 ⑥堆排序⑦二路归并排序&在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？.试设计一个算法，使得在。⑪的时间内重排数组，将所有取负值的排序码排在所有取正值昨负值)的排序码之前。提示：对比快速排序的第一趟排序，此处，以0为控制关键字。.手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个排序码后堆的变化。(1)按字母顺序排序：TirqDot,Eva,RaqKirqGuy,Ann,Jin;Kay,Ron,Jan0按数值递增顺序排序：26,33,35,29,19,12,22(3)同样7个数字，换一个初始排列，再按数值的递增顺序排序：12,19,33,26,29,35,22.希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法，试举例说明。12在已排好序的序列中，一个对象所处的位置取决于具有更小排序码的对象的个数。基于这个思想，可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域count,用于存放在已排好序的序列中该对象前面的对象数目，最后依count域的值，将序列重新排列，就可完成排序。试编写一个算法，实现计数排序。并说明对于一个有n个对象的序列，为确定所有对象的count值，最多需要做n知1)/2次排序码比较。习题解答3.设〃为正整数，分析下列各程序段中加下划线的语句的执行次数。(1)for(inti=1;iV=店i-H)for(intj=1;jrxj-H){cH□=0.Qfor(intk=1;kqleH)

cmm=c用m+a用k*bkm；for(inti=1;i"i-H)for(intj=1;j<=i;j-H)for(intk=1;k<=j;leH)x=x+y③inti=1,j=1;while {=i+1；j=j+i；}④*inti=1;do{for(intj=1;j<=j-H)i=i+i；}vdiile(i<100+q);【解答】(1)【解答】(1)nnni=lj=lk=l0金心白="竽卜疝+5=i=lj=lk=li=lj=li=l\ /J乙i=l乙i=ln(n+l)(2n+l)1n(n+l)n(n+l)(n+2)= 1 = TOC\o"1-5"\h\z6 2 2 60)i=1时，i= 2,j=j+i =l+2=2+_l,i=2时，i=3, j=j+i= (2+1)+3=3 +1+ 2,i=3时，i=4 j=j+i= (3+1+2)+4 =4+ 1+ 2 +3,i=4时，i=5, j=j+i= (4+1+2+3)+5=5 + 1 + 2+3+vj=(k+l)+^i<ni=l,(k+1)+k(k1l)=k^3k13,n2 2i=k时，i=k+1,j=j+i=(k+1)+(1+2+3+4+…+k),解出满足上述不等式的k值，即为语句i=i+l的程序步数。④for语句每执行一次，语句i=i+j将执行n次，而i的值会增加普D因此，当for语句执行k次后，i的值将变为2故最终for语句的执行次数k为满足1+&迎2100+〃2的最小整数k,语句i=i+j的程序步数为n*k4试编写一个函数计算n!*7的值，结果存放于数组A^rraySiz日的第n个数组元素中，0<n<arraySize5若设计算机中允许的整数的最大值为maxlnt,则当n>arraySize或者对于某一个k(0<k<rj),使得k!*7>maxlnt时，应按出错处理。可有如下三种不同的出错处理方式：(1)用printf显示错误信息及exit(1)语句来终止执行并报告错误；Q)用返回整数函数值。1来实现算法，以区别是正常返回还是错误返回；(3)在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。【解答】#include<stdiah>constintarraySize=10QconstintNhxlnt=0x7fffffff;intcalc(intT口，intn){inti,value=1;if(n!=0){intedge=Nhxlnt/n/金for(i=1;iV弭i+F){value』i*2;if(value>edge)return。value』n*2;T[h]=valu0printfCAE%!]= ,n,T[n]);return1;voidmain(){intA[arraySize];inti;for(i=。i<arraySiz^i4+)if(!calc(Ai)){printf("failedat%i.\pn,i);break;个 顺序表结构的定义.为简化起见，表元素我们使用整型数据数据元素从data⑪处开始存储typedefstruct /注意typedef的使用(intdataMXXSIZE]；/数据域。intlength}1isttyp^5.设有一个线性表(3),%…，*,a-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为Qt,ar,…，a,&)。最后分析此算法的时间复杂度及空间复杂度。【解答】voidinverse(1isttype{inttupintn=A->lengtl^for(inti=。i<=(n-1)/&i-H-){tnp=Ae>data[i1;AeMata[i] =A->data[n—i—1];A^data|n—i—1]=tup时间复杂度：需进行次循环，因此时间复杂度为。倒；空间复杂度：使用一个整形辅助存储单元tm®因此空间复杂度为0(1)。6顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有127个元素的顺序表进行插入，平均需要移动多少个元素？删除一个元素,又平均需要移动多少个元素？【解答】若设顺序表中已有n个元素。又设插入或删除表中各个元素的概率相等，则在插入时因有肝1个插入位置可以在表中最后一个表项后面追加)，每个元素位置插入的概率为1/34),但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为插入时平均移动元素个数AvNragyMovingNumber)为t1S 1 , , ，八、1n(n+1)n,,,AMN= >(n—i)= (n+(n-1)+…+1+0)= =—=63.5n4-17^) n+1 n4-1 2 2删除时平均移动元素个数为N为AMN=-¥(n-i-l)=-((n-l)+(n-2)+---+l+0)=-^^-=^^-=63

nj=() n n2 27.利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度,并分析②与6)的时间复杂度出现差异的原因。(1)从顺序表中删除具有给定值X的所有元素。0从顺序表中删除其值在给定值S与t之间(要求S小于t)的所有元素。(3)从有序顺序表中删除其值在给定值s与t之间(要求s小于t)的所有兀素O④将两个有序顺序表U1b合并成一个新的有序顺序表Io,(5)从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。【解答】(1)从顺序表中删除具有给定值x的所有元素。voidDelValue(1isttype*L,intx){inti=0,j;while(i<^length) /盾环，寻找具有值x的元素并删除它*/if—data[i]=x){ /删除具有值x的元素，后续元素前移for(j=i；j<L->length—1;j-H-)LH>data田=LH>data[j+1];L-length—长减上}elsei-H;)②实现删除其值在给定值s与t之间(要求s小于t)的所有元素的函数如下：voidDelValuestot(1isttype*L,ints,intt){inti,j;if(L->length=0||s>=t){printfCListisenptyorparametersarei1legal!5);exit(1);}i=awhile(iV—length) /循环，寻找具有值x的元素并删除它*/if(fHxlata 品dQdata[i]V=t){f除满足条件的元素，后续元素前移沙for(j=i;j<L->length—1;j-H-)L->data[j]=L->data|j+l];L->length—; /表长减]之}elsei-H;}(3)实现从有序顺序表中删除其值在给定值s与t之间的所有元素的函数如下：voidEtelValuestot1(1isttype*Lintsintt){inti,j,k;if(L->length=0||s>=t){printfCListisenptyorparametersarei1legal!Xo));exit(1);}for(i=«i<LH>lengthi-H-)/循环，寻找值>s的第一个元素*/if(L-^data[i]>=s)break; 出循环时，i指向该元素if(i<L->length){for(j=1;i+jV—lengthj+F)/f盾环，寻找值>t的第一个元素*/if-data[i+j[>t)break; /退出循环时，i+j指向该元素*/for(k=i+j;k<LH>length;k4+)/删除满足条件的元素，后续元素前移之L-^>datak-j]=LH>data因;Lr^>length-=j; 长减}}④实现将两个有序顺序表合并成一个新的有序顺序表的函数如下：1isttype*Nferge(1isttype*L\1isttype*LB){/合并有序顺序表IA与LB成为一个新的有序顺序表并由函数返回listtype*LQintvaluel,valuedinti,j,kinitiatelist(J_0;ifOA>length+LB^>length>M^XSIZ0{printf("表上溢/f;exit(1);}i=0,j=0,k=。valuel=LAS>data[i];value2=LB-^>data[j];Wiile(i<IA>lengthj<LB-^>length){/循环，两两比较，小者存入结果表if(valuel<=value2){LG'data[k]=valuel;i-H;valuel=LA^>data[i];}else{LCfdata冈=valuedj"value2=43-^>data[j];}k4-H}while(i<LA^lengtli){/当LA表未检测完，继续向结果表传送^LG->data[k]=valuel;i+f^k+4^valuel=LAH>data[i];}while(j<LB^>lengtFj){/当LB表未检测完，继续向结果表传送^LG->data[k]=valuedj-H;k-H;value2=LB-^>data[j];}LG->length=k;returnLQ(5)实现从表中删除所有其值重复的元素的函数如下：voidDelDouble(listtype*D{inti,j,k;inttiTRif5^length=0){printf("表空Zf;exit(1);}0while(i<alength){/循环检测*/j=i+1；tnp=LH>data[i];\\hile(j<LH>length){/对于每一个i,重复检测一遍后续元蒸*/if(tmp=!H>data□) 如果相等，删除此结点，后续元素前移Vfor(k=j+l;kVL-i>lengthk+4-)L-i^data[k-1]=L->data[k];L^>length-; 最后元素位置减11y!elsej44t}i+h /佥测完—data□,检测下一个*/&线性表可用顺序表或链表存储。试问：(1)两种存储表示各有哪些主要优缺点？②如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化,表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？0)若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么?【解答】（1）顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或按下标）直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半或近一半）元素，修改效率不高。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放,且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。0如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示。如果采用顺序存储表示，必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现,释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于n个表包括表的总数可能变化）共存的情形，处理十分简便和快捷。所以选用链接存储表示较好。0）应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。链表结构的定义.为简化起见，表元素我们使用整型数据 此链表带头结点 Vtypedefstructmynode{intdata; /数据域：整型structmynode*next;旨针域V'}node,1inklisttype;9•试写出计算线性链表长度的算法。intlengths1(1inklisttype*D{1inklisttype*pintlen;if(L=NULL){return1;}P= p指向链表L的头结点*/1cn—■。while3!=MU){leirH;p=pH>next;}returnlen;}10.设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。

【解答】voidLinkListInverse(1inklisttype*D{1inklisttype*p>*pre>*next;ifC=NULL||LH^iext=NULL)return;未初始化，或为空表57p=L->next;pre=L;研ile(p!=ZIL){ /循环修改链表中所有结点的后继指针的指向next=pH>next;E当前结点的后继指针*/pH>next=pre;/当前结点的后继改为指向其原来的前next=pH>next;E当前结点的后继指针*/pH>next=pre;/当前结点的后继改为指向其原来的前pre=p,p=Hiext;川旨针后移*/L->:next->next=NULL;/原第一个结点改为最后一个结点*/LH>next=pre;/链表的头结点指向原最后一个结点*/1L设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表,其中一链表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。【解答】voidLinkListDispose(linklisttype*L1inklisttype* 1inklisttype将链表L分解为IALB两个链表，其中LA中结点值均为正，LB中结点值均为并删除结点值为零的结点，最后释放L的头结点。

1inklisttype*p,*pt,*p&*pb;LA=initiatesl(;pa=IA /指向IA中的最后一个结点*/LB=initiateslJ;pb=13 旨向LB中的最后一个结点*/If(L=NCLL||!H>next=niI)return /"L为空指针或L为空表*/p=Ij-^next;Wiile(p!p=Ij-^next;Wiile(p!=NLU)ifg>data>Q){paH>next=ppa=Rp=p-^next;}elseif^H>data<Q){ptHxiext=p5Pb=Rp=pH>next;ielse(pt=pH>next;结点^free@;p=pt;}par->next=NULL;ptH>next=NULL;Z*P指向链表L的第一个结点V/遍历链表LV/各P链入链表LA的pa后*/P链入链表LB的pb后表//删除值为0的结点*/己录当前结点的后继，以便删除当前12设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。【解答】void1inklistNferge(1inklisttype*L/\1inklisttype*LB){/合并有序链表IA与当结果存入IA中，并释放LB的头结点*/1inklisttype*pa,*pb,*pre,*p、if0A=N_LL11LB=NULL||)returnif(LAOnext=NLU){ 为空表，则直接将LB链入IA即可^LA->next=LB^next;free;retr叫}if(LB-^=next=NJLI)return /*LB为空表，则直接返回即可/pa=LA-^=next,pb=IB-^next,pre=iz\while(pa!=NULLpb!=NJI) /盾环，两两比较，小者存入结果表之if02data>p2next){不各pb链入L\然后pb指针后移pre^>next=pb;pn=pb~〉next;pb-^next=pa;pb=p店pre=pre->nextelse{kpa指针后移else{pa=paH>next;pre=pre-^>next;}ifQb!=NJ!) 不等pb剩余结点链入LA*/pre-^>next=pb;freeC3;}13.设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。【解答】Linklisttype*1inklistJvfergeinverse(1inklisttype 1inklisttype*LB){/合并有序链表IA与四结果存入LC中，并释放IALB的头结点，函数返回1inklisttype*pa,*pb,*口ifOA=NULL||LB=NULL||)return;LC=initiatesljj;pa=LA^>next,pb=LB-^>next;while(pa!=NULLpb!=NULL) 循环，两两比较，大者存入I£Vifg-data>pb-^iext){ pa链为LC的第一个结点沙p=pa-^>next;paH>next=LGv>next;LG^next=pa;

else(p=ptH>next;ptH>next=IXH>next;else(p=ptH>next;ptH>next=IXH>next;LG->next=phpb=R}砒ile0a!=NULQ{p=paH>next;par>next=LC->next;LG->next=pa;pa=B}while(pb!=NLU){p=pb->next;ptH>next=LG-^next;LG-^>next=pb;Pb=B}free@;freeC9；/Wpa链为LC的第一个结点*/pa剩余结点链入IXVpb剩余结点链入LC*/14在一个循环链表中寻找值为x的结点，并将该结点移到第一个结点之前。【解答】设此循环链表为单链表，则其类型定义与一般单链表相同typedefstructmynodecyclelisttype;voidsearchjpovefirstCyclelisttype*€1,int力{cyclelisttype*p,*pre;

ifCL=NULL)return;p=dj->next;pre=CL;while0!=Q)G找％注意与普通单链表在判断是否到表尾上的不同Vif^H>data='break;else{pre=Rp=pH>next;/喳找成功夫//喳找成功夫//在原来位置删除pVZ*p插入到CL后女/ifg!=o){peiHxiext=p->next;pH>next=CL->next;Q_H>next=g16铁路进行列车调度时，常把站台设计成栈式结构的站台，如右图所示。试问：(1)设有编号为LZ3,4,5,6的六辆列车，顺序开入栈式结构的站台，则可能的出栈序列有多少种？②若进站的六辆列车顺序如上所述，那么是否能够得到435612,325641,154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到即写出得栈域得栈得序列)。种。廨答】 Q/(6+D)*号32种。(1)可能的不同出栈序列 有0不能得到435612和154623这样的出栈序列。因为若在43,5,6之后再将1,2出栈，则1,2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面,不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。17.试证明：若借助栈可由输入序列L2,3,…，n得到一个输出序列p,R,P,…，R它是输入序列的某一种排列），则在输出序列中不可能出现以下情况，即存在ivjvk,使得pvrVp。提示：用反证法）【解答】因为借助栈由输入序列L2,3,…，n,可得到输出序列p,出出…，R,如果存在下标i,j,k,满足ivjvk,那么在输出序列中，可能出现如下5种情况：①i进栈，i出栈，j进栈，j出栈，k进栈，k出栈。此时具有最小值的排在最前面p位置，具有中间值的排在其后p位置，具有最大值的排在R位置，有pVRV%不可能出现RvRvp的情形；②i进栈，i出栈，j进栈，k进栈，k出栈，j出栈。此时具有最小值的排在最前面p位置，具有最大值的排在p位置，具有中间值的排在最后R位置，有pVRVp,不可能出现pVRVP的情形；

③i进栈，j进栈，j出栈，i出栈，k进栈，k出栈。此时具有中间值的排在最前面p位置，具有最小值的排在其后p位置，有pVp<“不可能出现pVRVR的情形；④i进栈，j进栈，j出栈，k进栈，k出栈，i出栈。此时具有中间值的排在最前面p位置，具有最大值的排在其后p位置，具有最小值的排在R位置，有RVpVp,也不可能出现RVRVp的情形；⑤i进栈，j进栈，k进栈，k出栈，j出栈，i出栈。此时具有最大值的排在最前面P位置，具有中间值的排在其后P位置，具有最小值的排在R位置，有RVRVP,也不可能出现RVRVP的情形；1&将编号为0和1的两个栈存放于一个数组空间V项中，栈底分别处于数组的两端。当第0号栈的栈顶指针top⑻等于T时该栈为空，当第1号栈的栈顶指针top口］等于m时该栈为空。两个栈均从两端向中间增长。当向第0号栈插入一个新元素时，使top⑻增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top口］减1得到新的栈顶位置。当top位］+1=top□□时或top⑻=topQQT时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈DoubleStac已结构的类定义，并实现判栈空、判栈满、插入、删除算法。【解答】bot(0|top[0]topi1bot(0|top[0]topi1Ibot|1]双栈的类型定义如下：typedefstruct{inttopO,topi;elemtypedata^KXSIZE];}DoubleStack;判栈空intDoubleStackRnpty(DoubleStack*intStackNcj){指向双栈的指针，Stacks0或1,指定要判断的是第。栈，还是第一栈if($tackNo=Q)return(DS-^>topO<0;elseretrun(pS-^>topl>=MKXSIZ0;}判栈满intDoubleStackFul1(poubleStack*DQ{return(D&^>topHDS-^>topO=l);}入栈intPopDoubleStack(poubleStack*intStackNo,elemtype田{不殍数据元素x插入到栈StackNo中Vif(DoubleStackFul1小)return您LSa 满溢出去/if($tackNo=q)Q(寸第0栈插入D6r>top(H4;D&tdata[top(J]==x;}else/对第1栈插入D&->>topl—;ES->data[topl]=x;)return(IK®;删除算法elemtypePushEbubleStack(poubleStack*历intStackNc^{/从StackNo栈中删除并返回一个元素，若栈空，则返回NWZifdDoubleStackBnpty比StackNc^)returnNW；ifStackNgQ(寸0号栈进行操作D8^>top0—;return(pS-^>dataJj6-^>top0+l]);}else{DS->topl-H5return(DBfdatapS-^>topl—1]);.改写顺序栈的进栈成员函数Push⑨，要求当栈满时执行一个stackFull()操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组,代替原来的栈数组，原来栈数组中的元素占据新数组的前NfexSize位置。【解答】voidpush(stack*Selemtype力{if(StackBnpty0)stackFul10; /栈满，做溢出处理S-^>top44;S-^>datatS->top]=x; 栈voidstackFull(stack*9{elemtype*temptenp=calloc6为gXSIZE；sizeof©lemtyp。)；/创建体积大二倍的数组for(inti=QiV=2topi+F) /传送原数组的数据temp[i]=S-^>data[i];/删去原数组

MXXSIZE』MXXSIZE』3;S-^>data=temp/数组最大体积增长二倍/新数组成为栈的数组空间.根据教案中给出的优先级，回答以下问题：(1)在表达式求值的过程中，如果表达式e含有n个运算符和分界符，问操作数栈网中最多可存入多少个元素？0如果表达式e含有n个运算符，且括号嵌套的最大深度为6层，问栈中最多可存入多少个元素？【解答】(1)如果表达式e含有n个运算符和分界符，则可能的运算对象有什1个。因此在利用后缀表达式求值时所用到的运算对象栈中最多可存入计1个元素。0同上。.表达式的中缀表示为a*x-b/xA2,试利用栈将它改为后缀表示ax*bx2V-写出转换过程中栈的变化。诔示乘方运算)【解答】若设当前扫描到的运算符ch的优先级为icpUi),该运算符进栈后的优先级为ispdi),则可规定各个算术运算符的优先级如下表所示。运算符(A*，/%3十一■)isp017538icp086421isp也叫做栈内(instackpriorit力优先数,icp也叫做栈外(incaningpriority优先数。当刚扫描到的运算符ch的icp9W大于isp(stac用时，则ch进栈;当刚扫描到的运算符ch的icp四小于isp(stack)时，则位于栈顶的运算符退栈并输出。从表中可知，icp(“《)最高，但当“《进栈后，isp(“《)变得极低。其它运算符进入栈中后优先数都升L这样可体现在中缀表达式中相同优先级的运算符自左向右计算的要求。运算符优先数相等的情况只出现在括号

配对")”或栈底的号与输入流最后的号配对时。前者将连续退出位于栈顶的运算符，直到遇到“【为止。然后将“【退栈以对消括号，后者将结束算法。步序扫描项项类型动 作栈的变化输出0b 进栈，读下一符号1a操作数b直接输出，读下一符号A2*操作符bisp('；')VicpC*'栈，读下一符号),进・*A3X操作数b直接输出，读下一符号,*aX4—操作符bisp('*')>icpC-栈输出),退aX*▼isp(z;z)<icp('栈，读下一符号),进. *aX*5b操作数b直接输出，读下一符号•aX*b6/操作符bisp )vicp('/),栈，读下一符号进；KaX*b7X操作数▼直接输出，读下一符号；aX火bx8操作符bisp('/')<icp('2栈，读下一符号),进aX*bx92操作数b直接输出，读下一符号aX*bx210操作符bisp('T')>icp('；'栈输出),退;-/aX*1bx2Abisp('/')>icp('；'栈输出),退• ax*bx2"/▽isp('-')>icp '栈输出),退ax*b।x2入/22设循环队列的容;止为70(序号从1到70,经过一系列入队和退队运算后,(1)front==15,rear=46;(4front=45,rear=10问在上述两种情况下，循环队列中各有多少个元素？【解答】(D队列中元素的个数为WSIZE^rear-front)%mxSIZE=(70+46-15)%70=^1②队列中元素的个数为MSXSIZBHear—front)%mxSIZE=(70+10-45)%7CM523.设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结构的队列的插入Rnqueu®和删除(dequeue)算法，并给出队列空和队列满的条件。设此队列含头结点，队头指针front指向头结点，限定在表头端删除队列空：队尾指针指向头结点，即rea-front时，队空队列满：因为是链表，所以，只有内存空间不足时才会有队满的问题。voidinsertqueueQueuetype七intlocation,elemtype3{/Q指向队列的指针；location:插入位置，0表示队头，1表示队尾；x数据元素*/node*口p=(node ma11oc(sizeof(node));pH>data=苏if(location=Q/在队头处插入pH>next=Q->front->next;Q^>front->next=口ifQ>reap=Q>front)Q>rear=口/仅寸空表插入*/else，在队尾处插入p->next=NULL;Q^>rear-^>next=rQ^>rear=pelemtypedeletequeue^jueuetype{elemtypex;node*bifQ^>rear=Q^>front)returnMU);队列*/p=6>front—>next;x=p->data;Q4>front-^next=pH>next;ifO>rear=p)Q>rear=Q->front /*X寸只有一个元素的队列进行删除*/free©;return®;.所谓回文，是指从前向后顺读和从后向前倒读都一样的不含空白字符的串。例如did,madamimadainpop即是回文。试编写一个算法，以判断一个串是否是回文。【解答1]将字符串中全部字符进栈，然后将栈中的字符逐个与原字符串中的字符进行比较。算法如下：intpalindrcme(string9{stacktype*st;intyes=1,i=QMile6[i]!= ){push(st,S[i])；i+H /扫描字符串，所有字符进栈1yi=awhile6[i]!="U) /t匕较字符串。/if6DO==st.GetTop())fop(st);i+h}else{yes=Qbreak;}returnfyes);【解答a采用递归算法，判断从s到e中的字符串是否回文，通过函数返回是或不是。intpalindromefcharA[],intstart,inten(${if[start]!=A[end])returnQelseif(s>e)return1;elsepalindrcme(Astart+1,end—1);.设AW⑹为一个上三角矩阵，将A中所有非零元素按列序顺次存入一维数组B中，则A与B元素的对应关系是什么？【解答】上三角矩阵如下所示a\\ 〃12 〃13•一a\n° 。22 。23 …0 0 «33…a3n0 0 0••"其数据元素满足Aij=Q对所有的i>j上三角矩阵正好是一个下三角矩阵的转秩，我们知道，一个下三角矩阵按行压缩存储时，矩阵元素与一维数组的对应关系为AH 对所有的i>j;因此，下三角矩阵按列序存储在一维数组中的元素对应关系为

ahDl^BD*G+l)/2+i],对所有的i<j.26编写串的替换函数Replace(str,strl,str2),将主串str中所有子串strl替换为str2【解答】见书p581.列出右图所示二叉树的叶结点、分支结点和每个结点的层次。【解答】二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。结点①的层次为Q结点②、③的层次为1;结点④⑧的层次为点①的层次为Q结点②、③的层次为1;结点④⑧的层次为3;结点⑨的层次为42使用(1)顺序表示和②二叉链表表示法，储表示。【解答】0123456789①②③④⑤⑥⑦、⑤、⑥的层次为&结点⑦、分别画出上图所示二叉树的存/②A ③1011 121314151617 ⑧ 11⑨顺序表示3.在结点个数为n3*1)的各棵树中,//\A④|八⑤IA⑥A.⑦八 八⑧A/♦⑨a| 二叉链表表示高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？【解答】结点个数为n时，高度最小的树的高度为1,有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1,有n层；它有1个叶结点，n-1个分支结点。.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。【解答】具有3个结点的树 具有3个结点的二叉树.如果一棵树有讣个度为1的结点，有m个度为2的结点，…，4个度为m的结点，试问有多少个度为0的结点？试推导之。【解答】总结点数n=n,+n+rt+…+%总分支数e=n—1=n)+ni+@H—+/一1=m*n>+(n-1) +•••+2*n+n则有+l6若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：(1)统计二叉树中叶结点的个数。0以二叉树为参数，交换每个结点的左子女和右子女。0)求二叉树的深度。【解答】(1)统计二叉树中叶结点个数intleaf(BINode*pti){ifQtr=NULL)return©;elseif^)tr-^>lchiId=MILLptr->rchiId=NULL)return1;elsereturnleaf^)tr->lchiId)+leaf(pti^->rchiId);0交换每个结点的左子女和右子女voidexchange(BINode*ptr){BINode*tempif^)tr->lchild!=NULL||ptr->rchild!=NULL){temp=ptr->lchiletptr->lchiId=ptr-^>rchi14ptiH>rchiId=tempexchange r-^>lchiId);exchange r->rchiId);③求二叉树的深度voiddepth阚Mode*pti){ifr=NULL)return。;returnfnaxfclepthr->lchiId),depthQtr->rchi1(J)));}7.一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：(1)各层的结点个数是多少？②编号为i的结点的父结点若存在)的编号是多少？0)编号为i的结点的第崎孩子结点若存在)的编号是多少？④编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？(5)若结点个数为n,则高度h是n的什么函数关系？【解答】

(1)k1(i=0,1,……，h)②i+k-2_k_③(i-1)*k+m+1④ (i—1)%kw0或i<一二*k时有右兄弟，右兄弟为i+lo_k_0)h=logg*好i)+i)—ig=o时h=—i)&请画出下图所示的树所对应的二叉树。&请画出下图所示的树所对应的二叉树。9.已知一棵二叉树的前序遍历的结果是ABBTKHIJ,中序遍历的结果是EBCLAFHIQJ,试画出这棵二叉树。【解答】当前序序列为ABHERHIJ,中序序列为EBCIXFHI⑷时，逐步形成二叉树的过程如下图所示:过程如下图所示:10.给定权值集合(15,03,14,02,06,09,16,17},构造相应的霍夫曼树，并计算它的带权路径长度。【解答】F：(I)10.给定权值集合(15,03,14,02,06,09,16,17},构造相应的霍夫曼树，并计算它的带权路径长度。【解答】F：(I)(111)@@@@@/\(II)⑲®⑥⑯⑪Q此树的带权路径长度WPL=22幺1.设有序顺序表中的元素依次为017,094154170,275,503,509,512,553,612,677,765,897,90&试画出对其进行折半查找时的二叉查找树，并计算查找成功的平均查找长度和查找不成功的平均查找长度。【解答】1Ji,1 45ASLsucc=—£g=—(1+2*2+3*4+4*7)=—

succ '14 142若对有n个元素的有序顺序表和无序顺序表进行顺序查找，试就下列三种情1s,i 59ASLunsucc-—VC=—(3*1+4*14)=ASLunsucc-15£'15 15况分别讨论两者在等查找概率时的平均查找长度是否相同?(1)查找失败；0查找成功，且表中只有一个关键码等于给定值k的对象；0)查找成功，且表中有若干个关键码等于给定值k的对象，要求一次查找找出所有对象。【解答】(1)不同。因为有序顺序表查找到其关键码比要查找值大的对象时就停止查找，报告失败信息，不必查找到表尾；而无序顺序表必须查找到表尾才能断定查找失败。0相同。查找到表中对象的关键码等于给定值时就停止查找，报告成功信息。0)不同。有序顺序表中关键码相等的对象相继排列在一起，只要查找到第一个就可以连续查找到其它关键码相同的对象。而无序顺序表必须查找全部表中对象才能确定相同关键码的对象都找了出来，所需时间就不相同了。前两间可做定量分析。第三问推导出的公式比较复杂，不再进一步讨论。3.设有10000个记录对象，通过分块划分为若干子表并建立索引，那么为了提高查找效率，每一个子表的大小应设计为多大？【解答】每个子表的大小4=J10000=100个记录对象。4设散列表为HT口引，散列函数为H长勺)用闭散列法解决冲突,对下列关键码序列12,23,45,57,20,03,7&31,15,36造表。(1)采用线性探测法寻找下一个空位，画出相应的散列表，并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。②采用随机探测法寻找下一个空位，随机数序列为：5,42,7,3,6画出相应的散列表，并计算等概率下查找成功的平均查找长度。【解答】使用散列函数H3吻=keyxvod13,有H(12)==12,H(23)=10,H3)=6, H(57)=5,H(2Q)==%HQ3)=3,H(7S)=0, H01)=5,H(15);H0O=10.(1)利用线性探测法造表:012345678910111278150357452031233612(1)(1)(1)(1)(1)(1)④(1)②(1)查找成功的平均查找长度为他口"=_L(1+1+1+1+1+1+4+1+2+1)=li10 10查找不成功的平均查找长度为■ASLnsucc=—(2+1+3+2+1+5+4+3+2+1+5+4+5=133613②利用随机探测法造表:H=Ht+REi-13)%13,H=H(key)TOC\o"1-5"\h\z0 1 2 3 4 5 6 7 8 9 10 11 1278311503574520362312TOC\o"1-5"\h\z(1)0) (1)(1) (1)(1)(1)④ (1) (1)查找成功的平均查找长度为ASLm=，(1+1+1+1+1+1+4+1+3+1)=受10 10查找不成功的平均查找长度为AS—”0+6+3+6+1+7+2+9+3+1+7+1+2)=13

51135.设有150个记录要存储到散列表中，要求利用线性探查法解决冲突，同时要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？设a是散列表的装载因子，则有2 \-a【解答】已知要存储的记录数为n=150,查找成功的平均查找长度为ASLu“<2,则有ASLu” 2,解得a42。又有a=4=空42,则m>22工2\ 1-a/ 3 mm3.设有15000个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连结，每个页块可存放30个记录。若采用按桶散列，且要求查找到一个已有记录的平均读盘时间不超过1.5次，则该文件应设置多少个桶？已知，链地址法的平均查找长度ASIaHx/2【解答】已知用链地址法(开散列)解决冲突，查找成功的平均查找长度为1治/2<1.5,解出a<1,又a=n/m=15000/30/m=500/m<1,2500,由此可知，该文件至少应设置500个桶。.设待排序的排序码序列为｛12,2,16,3Q2&10,16*20,01金,试分(1)直接插入排序排序(1)直接插入排序排序④快速排序(7)二路归并排序【解答】(1)直接插入排序②希尔排序增量为5,2,1) 6)冒泡©直接选择排序 ⑥堆排序初始排0123456789排序码比较次数i=l[<2]i=2]2i=3E2i=4[2i=5[2i=6[2i=7L2216302812163028]12163028]12163、28]入k2、30、]10121628、、10121616*10 16 20 610 16 20 610 16* 20 610 1G 20 610 1G 20 630、 16 20 6]2、30、20 6i=8[ %入％1七2、2、30、62 ]1818181818181818i=9[2[26101216610121616*2、2、30、18]16*18202830]1112533380希尔排序增量为5,2,1)初始排01234 5 6 7列12 2163028 1016*208 9排序码比较次数61814-1+1+1+1=10 216 6 18 12 16* 20 30 28 (1+1+2+1)+(1+1d=2 1 1——1 1 1 1 +1+1)=910 216 6 16* 12 18 20 30 28 1+1-F3+1-H+1+1.1IIIIIIIIII「s1Xd=l +1+2=142 6101216 16*18202830希尔(shell)本人采取的增量序列为L30, 止30/21/21,…，L一般地，增量序列可采用LmJ,11nxJaJ,LLnxJaJaJ,…，L大量实验表明，取a=0.45454的增量序列比取其他的增量序列的优越性更显著。计算L0.45454d的一个简单方法是用整数算术计算0*nT)/llo需要注意，当avl/2时，增量序列可能不以1结束，需要加以判断和调整。6)冒泡排序初始排012345初始排0123456789排序码比较2i=22i=22i=32i=4212< >< ><6[一1016126 10 [ 16126 10 [1216列 次数TOC\o"1-5"\h\zi=0[_2U3Q_»2 1J2J618 912 ]i=l[ 6163028 10162018 8< >< >3J2J16182016*3J2j182016* 183£U2J20]i=5 610i=5 61016L118203O_>282 12 6*i=6610 1616*2028302i=6610 1616*2028302 12610 1616*18 1182028302 12④快速排序PivPvtpo01 2PivPvtpo01 23 4 56789排序码比较ots120,1,2r16302810ots120,1,2r163028101620IposIposIposIpos,3 122次数618] 960,112L1616*203018360,112L1616*203018328284,5,6[,7,8284,5,6[,7,8 216E112L161^203018]|P0SIpos|POSIPospos01 28t184,5,6 261012E16,62028[3IposIposIpos18 ] 0]416*1012^pos416*1012^pos1616*118E22300]8101216E1182028306 * 6]左子序列递归深度为L右子序列递归深度为3b

(5)直接选择排序初始排列0 1i=0]122初始排列0 1i=0]122i=l [2 12ti=22 6i=32 6i=42 6i=52 6i=62 6i=72 6i=82 3 4 5 616 30 28 10 16* 20 616 30 28 10 16* 20 6[16 30 28 10 16* 20 12[ t10 30 28 16 16* 20 12t [1012281616*2030

t__t[1012162816*2030

t__t[10 12 16 16 28 20 30.9排序码比较次数18 9]18 8]189排序码比较次数18 9]18 8]18 7：18 6]18 518 4]18 3：28 2]28 12 6 10121616*162030]tt[32 6 10121616*1620280]⑥堆排序第一步，形成初始的最大堆略），第二步，做堆排序。初始排列，不是最大堆形成初始最大堆从0#到8#重新形成堆交换初始排列，不是最大堆形成初始最大堆从0#到8#重新形成堆交换时与甜对象从0到7#重新形成堆成堆28282828交换0#与7#对象交换0#与7#对象从州到6#重新形成堆交换附与6#对象从用到5#重新形成堆交换0#与5#对象从0#到4#重新形成堆交换0#与4#对象从0#到交换0#与4#对象从0#到3#重新形成堆交换明与3#对从0#到2#重新形成堆 交换0#与2#对象从0#到1#重新形成堆排序码比较5排序码比较5次排序码比较6次排序码比较7次排序码比较9次交换0#与1#对象从州到1#重新形成堆，得到结果⑦二路归并排序采用迭代的方法进行归并排序。设待排序的数据对象有n个。首先把每一个待排序的数据对象看作是长度为的初始归并项，然后进行两两归并，形成长度为2的归并项，再对它们两两归并，形成长度为4的归并项，如此一趟一趟做下去,最后得到长度为n的归并结果。&在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？r解答】如果在待排序序列的后面的若干排序码比前面的排序码小，则在起泡排序的过程中，排序码可能向与最终它应移向的位置相反的方向移动。例如，&4Q.、（14A75 619 9 7如9向相反方向移动6 RK 邓 Q173、3\44 75 yl9 9 如19向相反方向移动6 70 @13st34纥弋9 19 如9向最终方向移动6 7 9、5人怨3811y3、34、487519如13向相反方向移动6 7 9 11 <7 V0、3813 19 34 48 75 如 13向最终方向移动6 7 9 11 13、57、4人38 19 34 48 75 如 34向相反方向移动6 7 9 11 13 19、5K4Q 38 34 48 756 7 9 11 13 193457 40 38 48 75.试设计一个算法，使得在O®的时间内重排数组，将所有取负值的排序码排在所有取正值昨负值)的排序码之前。【解答】voidreArrange(RB32KEKTEa□,intn){个寸数组a位n-1]执行此操作*/inti=0,j=n—1;加le(i!=j){while(a[i].key<0)i-H;while(a[j].key>=0)j—swap(a[i],a□);i+hj-t

.手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个排序码后堆的变化。(1)按字母顺序排序：TirnDot,Eva,RorqKiniGuy,Ann,Jin)Kay,Ron,Jan0按数值递增顺序排序：26,33,35,29,19,12,220)同样7个数字，换一个初始排列，再按数值的递增顺序排序：12,19,33,26,29,35,22【解答】为节省篇幅，将用数组方式给出形成初始堆和进行堆排序的变化结果。阴影部分表示参与比较的排序码。请大家按照完全二叉树的顺序存储表示画出堆的树形表示。(1)按字母顺序排序形成初始堆(按最大堆)01201234DotEvaRonKimTimi=