计算机软件基础习题及答案.docx

习题一L什么是数据结构，数据的逻辑结构，数据的存储结构？数据结构对算法有什么影响？请举例说明。2 .数据结构的存储方式主要有哪两种？它们之间的本质区别是什么？3 .设刀为正整数，分析以下各程序段中加下划线的语句的执行次数。(1) for(inti=1;i<=n;i+)for(intj=1;j<=n;j+)cij=0.0;for(intk=1;k<=n;k+)cij=cij+aik*bkj;)(2) x=0;y=0;for(inti=1;i<=n;i+)for(intj=1;j<=i;j+)for(intk=1;k<=j;k+)=+y;(3) inti=1,j=1;while(i<=n&&j<=n)1 =i+1；J=J+i；)(4)*inti=1;dofor(intj=1;j<=n;j+)while(i<100+n);4 .试编写一个函数计算n!*2r的值，结果存放于数组AarraySize的第n个数组元素中，0narraySizeo假设设计算机中允许的整数的最大值为maxlnt,那么当QarraySize或者对于某一个k(0kn),使得k!*2k>maxlnt时，应按出错处理。可有如下三种不同的出错处理方式：(1)用Printf显示错误信息及exit(1)语句来终止执行并报告错误；(2)用返回整数函数值0,1来实现算法，以区别是正常返回还是错误返回；(3)在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。5 .设有一个线性表(ao,a,an-2,an-)存放在一个一维数组AarraySize中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为(an-1,an-2,a1,a。)。最后分析此算法的时间复杂度及空间复杂度。6 .顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下，对有127个元素的顺序表进行插入，平均需要移动多少个元素？删除一个元素，又平均需要移动多少个元素？7 .利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度，并分析(2)与(3)的时间复杂度出现差异的原因。(1)从顺序表中删除具有给定值X的所有元素。(2)从顺序表中删除其值在给定值S与t之间要求S小于t)的所有元素。(3)从有序顺序表中删除其值在给定值S与t之间要求S小于t的所有元素。(4)将两个有序顺序表la,Ib合并成一个新的有序顺序表Ico(5)从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。8 .线性表可用顺序表或链表存储。试问：(1)两种存储表示各有哪些主要优缺点？(2)如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3)假设表的总数根本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时,应采用哪种存储表示？为什么？9 .试写出计算线性链表长度的算法。10设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如以下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。W=OPPrh11 .设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表，其中一链表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。12 .设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。13 .设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。14 .在一个循环链表中寻找值为X的结点，并将该结点移到第一个结点之前。15 .对于下面的每一步，画出栈元素和栈顶指针的示意图:1栈初始化；元素X入栈；元素y入栈；出栈栈初始化6)元素Z入栈右图所示。结构的站台,到435612,16 .铁路进行列车调度时，常把站台设计成栈式结构的站台，如试问：(1)设有编号为1,2,3,4,5,6的六辆列车，顺序开入栈式那么可能的出栈序列有多少种？(2)假设进站的六辆列车顺序如上所述，那么是否能够得325641,154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出进栈或出栈的序列)。17 .试证明：假设借助栈可由输入序列1,2,3,n得到一个输出序列pi,p2,p3,，小(它是输入序列的某一种排列)，那么在输出序列中不可能出现以下情况，即存在i<j<k,使得Pj<Pk<Pi0(提示：用反证法)18 .将编号为O和1的两个栈存放于一个数组空间Vm中，栈底分别处于数组的两端。当第O号栈的栈顶指针top0等于T时该栈为空，当第1号栈的栈顶指针topl等于m时该栈为空。两个栈均从两端向中间增长。当向第0号栈插入一个新元素时，使top0增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使topl减1得到新的栈顶位置。当top0+l=topl时或top0=toplT时，栈空间满，此时不能再向任一栈参加新的元素。试定义这种双栈(DoUbIeStaCk)结构的类定义，并实现判栈空、判栈满、插入、删除算法。19 .改写顺序栈的进栈成员函数PUSh(x),要求当栈满时执行一个StaCkFUI1()操作进行栈满处理。其功能是：动态创立一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前MaxSize位置。20 .根据教案中给出的优先级，答复以下问题：(1)在表达式求值的过程中，如果表达式e含有n个运算符和分界符，问操作数栈(NS)中最多可存入多少个元素？(2)如果表达式e含有n个运算符,且括号嵌套的最大深度为6层，问栈中最多可存入多少个元素？21 .表达式的中缀表示为a*X-b/x2,试利用栈将它改为后缀表示ax*bx27-。写出转换过程中栈的变化。表示乘方运算)22 .设循环队列的容量为701序号从1到70，经过一系列入队和退队运算后，有：1)front=15,rear=46;front=45,rear=10问在上述两种情况下，循环队列中各有多少个元素？23.设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结构的队列的插入(enqueue)和删除(dequeue)算法，并给出队列空和队列满的条件。习题21 .列出右图所示二叉树的叶结点、分支结点和每个结点的层次。2 .使用(1)顺序表示和(2)二叉链表表示法，分别画出上图所示二叉树的存储表示。3 .在结点个数为n(n>l)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？4 .试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。5 .如果一棵树有m个度为1的结点，有112个度为2的结点，个度为m的结点，试问有多少个度为O的结点？试推导之。6 .假设用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：(1)统计二叉树中叶结点的个数。(2)以二叉树为参数，交换每个结点的左子女和右子女。(3)求二叉树的深度。7 .一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：(1)各层的结点个数是多少？(2)编号为i的结点的父结点(假设存在)的编号是多少？(3)编号为i的结点的第m个孩子结点(假设存在)的编号是多少？(4)编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？(5)假设结点个数为n,那么高度h是n的什么函数关系？8 .请画出以下图所示的树所对应的二叉树。9 .一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树。10 .给定权值集合15,03,14,02,06,09,16,17),构造相应的霍夫曼树，并计算它的带权路径长度。习题三11 设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,765,897,908o试画出对其进行折半查找时的二叉查找树，并计算查找成功的平均查找长度和查找不成功的平均查找长度。12 假设对有n个元素的有序顺序表和无序顺序表进行顺序查找，试就以下三种情况分别讨论两者在等查找概率时的平均查找长度是否相同？(1)查找失败；(2)查找成功，且表中只有一个关键码等于给定值k的对象；(3)查找成功，且表中有假设干个关键码等于给定值k的对象，要求一次查找找出所有对象。13 设有100oO个记录对象，通过分块划分为假设干子表并建立索引，那么为了提高查找效率，每一个子表的大小应设计为多大？14 设散列表为HT13,散列函数为H(左”)=Aey%130用闭散列法解决冲突，对以下关键码序列12,23, 45,57,20,03,78,31,15,36造表。(1)采用线性探测法寻找下一个空位，画出相应的散列表，并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。(2)采用随机探测法寻找下一个空位，随机数序列为：5,4,2,7,3,6,。画出相应的散列表,并计算等概率下查找成功的平均查找长度。5 .设有150个记录要存储到散列表中，要求利用线性探查法解决冲突，同时要求找到所需记录的平均比拟次数不超过2次。试问散列表需要设计多大？设是散列表的装载因子，那么有ASLSUCC=(1+；-)21-a6 .设有15000个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连结，每个页块可存放30个记录。假设采用按桶散列，且要求查找到一个已有记录的平均读盘时间不超过次，那么该文件应设置多少个桶？，链地址法的平均查找长度ASL=1+27 .设待排序的排序码序列为12,2,16,30,28,10,16*,20,6,18),试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比拟。(1)直接插入排序(2)希尔排序(增量为5,2,1)(3)冒泡排序(4)快速排序(5)直接选择排序(6)堆排序(7)二路归并排序8 .在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？9 .试设计一个算法，使得在0(n)的时间内重排数组，将所有取负值的排序码排在所有取正值(非负值)的排序码之前。提示：比照快速排序的第一趟排序，此处，以0为控制关键字。10 .手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个排序码后堆的变化。(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,2211 .希尔排序、简单项选择择排序、快速排序和堆排序是不稳定的排序方法，试举例说明。12 .在已排好序的序列中，一个对象所处的位置取决于具有更小排序码的对象的个数。基于这个思想，可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域COUnt,用于存放在已排好序的序列中该对象前面的对象数目，最后依c。Unt域的值，将序列重新排列，就可完成排序。试编写一个算法,实现计数排序。并说明对于一个有n个对象的序列，为确定所有对象的CoUnt值，最多需要做n(n-1)/2次排序码比拟。习题解答3.设刀为正整数，分析以下各程序段中加下划线的语句的执行次数。(1) for(inti=1;i<=n;i+)for(intj=1;j<=n;j+)cij=0.0;for(intk=1;k<=n;k+)cij=cij+aik*bkj;(2) x=0;y=0;for(inti=1;i<=n;i+)for(intj=1;j<=i;j+)for(intk=1;k<=j;k+)x=x+y;(3) inti=1,j=1;while(i<=n&&j<=n)1 =i+1；j=j+i；)(4)*inti=1;dofor(intj=1;j<=n;j+)i=i+j;while(i<100+n);【解答】/、nnn(1)1-113i=lj=lk=lnijni=ji=lj=lk=li=lj=l1n(n+l)(2n+l)1n(n+l)_n(n+l)(n+2)26+226(3) i=1时，i=2,j=j+i=l+2=2+l,i=2时，i=3,j=j+i=(2+l)+3=3+1+2,i=3时，i=4,j=j+i=(3+l+2)+4=4+1+2+3,i=4时，i=5,j=j+i=(4+l+2+3)+5=5+1+2+3+4,i=k时，i=k+l,j=j+i=(k+1)+(1+2+3+4+k),kVj=(k+l)+ini=l.(k÷l)÷±l)=k2÷3k÷3nv722解出满足上述不等式的k值，即为语句i=i+1的程序步数。(4) for语句每执行一次，语句i=i+j将执行n次，而i的值会增加MD2因此，当for语句执行k次后，i的值将变为+心生2故最终for语句的执行次数k为满足i+*"+oo+72的最小整数k,语句i=i+j的程序步数为n*k。4 .试编写一个函数计算ri!*2”的值，结果存放于数组AErraySize的第n个数组元素中，0narraySizeo假设设计算机中允许的整数的最大值为maxlnt,那么当n>araySize或者对于某一个k(0kn),使得卜!*2卜>maxlnt时，应按出错处理。可有如下三种不同的出错处理方式：(1)用Printf显示错误信息及exit(1)语句来终止执行并报告错误；(2)用返回整数函数值0,1来实现算法，以区别是正常返回还是错误返回；(3)在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。【解答】ttinclude<stdio.h>constintarraySize=100;constintMaxInt=0x7fffffff;intcalc(intT,intn)inti,value=1;if(n!=0)intedge=MaxInt/n/2;for(i=1;i<n;i+)value*=i*2;if(value>edge)return0;)value*=n*2;)Tn=value;printf(zzA%d=%dn?,n,Tn);return1;)voidmain()intAarraySize;inti;for(i=0;i<arraySize;i+)if(!calc(A,i)printf(zzfailedat%d.r,i);break;)*顺序表结构的定义.为简化起见，表元素我们使用整型数据数据元素从data0处开始存储*/typedefstruct*注意typedef的使用*/(intdataMAXSIZE;*数据域*/intlength;*表长*/listtype;5 .设有一个线性表(ao,a,，an-2,an-)存放在一个一维数组AarraySize中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为(an-1,an-2,-,a1,a。)。最后分析此算法的时间复杂度及空间复杂度。【解答】voidinverse(listtype*A)inttmp;intn=A->length;for(inti=0;i<=(n-l)/2;i+)tmp=A->datai;A->datai=A->datan-i-l;A->datan-i-l=tmp;)时间复杂度：需进行n/2次循环，因此时间复杂度为0(n)；空间复杂度：使用一个整形辅助存储单元tmp,因此空间复杂度为0(1)。6 .顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下，对有127个元素的顺序表进行插入，平均需要移动多少个元素？删除一个元素，又平均需要移动多少个元素？【解答】假设设顺序表中已有n个元素。又设插入或删除表中各个元素的概率相等，那么在插入时因有n+1个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为1/(n+1),但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为l11o插入时平均移动元素个数AMN(AVeragyMovingNumber)为AMN=V(n-i)=(n+(n-1)+1+0)=-J-n+D=三=63.5n+l£11+111+122删除时平均移动元素个数AMN为AMN=-Y(n-i-l)=-(n-l)+(n-2)+l+0)=-i=63IlMnn227 .利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度，并分析与(3)的时间复杂度出现差异的原因。(1)从顺序表中删除具有给定值X的所有元素。(2)从顺序表中删除其值在给定值S与t之间要求S小于t的所有元素。(3)从有序顺序表中删除其值在给定值S与t之间要求S小于t的所有元素。(4)将两个有序顺序表la,Ib合并成一个新的有序顺序表Ico(5)从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。【解答】(1)从顺序表中删除具有给定值X的所有元素。voidDelValue(listtype*L,intX)inti=0,j;while(i<L->length)*循环，寻找具有值X的元素并删除它*/if(L->datai=x)/*删除具有值X的元素，后续元素前移*/for(j=i;j<L->length-l;j+)L->dataj=L->dataj+l;L-Iength一;*表长减1*/elsei+;)(2)实现删除其值在给定值S与t之间要求S小于t的所有元素的函数如下：voidDelValuestot(listtype*L,ints,intt)inti,j;if(L->length=0s>=t)printf("Listisemptyorparametersareillegal!n");exit(1);)i=O;while(i<L->length)*循环，寻找具有值X的元素并删除它*/if(L->datai>=s&&L->datai<=t)/*删除满足条件的元素，后续元素前移*/for(j=i;j<L->length-l;j+)L->dataj=L->dataj+l;L->length-;/*表长减1*/elsei+;(3)实现从有序顺序表中删除其值在给定值s与t之间的所有元素的函数如下:voidDelValuestotl(listtype*L,intsintt)inti,j,k;if(L->length=Os>=t)printf("Listisemptyorparametersareillegal!n");exit(1);)for(i=O;i<L->length;i+)if(L->datai>=s)break;*循环，寻找值s的第一个元素*/*退出循环时，i指向该元素*/if(i<L->length)for(j=1;i+j<L->length;j+)*循环，寻找值t的第一个元素*/if(L->datai+j>t)break;for(k=i+j;k<L->length;k+/*退出循环时，i+j指向该元素*/*删除满足条件的元素，后续元素前移*/L->datak-j=L->datak;L->length-=j;*表长减j*/(4)实现将两个有序顺序表合并成一个新的有序顺序表的函数如下:listtype*Merge(listtypeA,Iisttype*LB)*合并有序顺序表LA与LB成为一个新的有序顺序表并由函数返回listtype*LC;intvaluel,value2;inti,j,k;initiatelist(LC);if(LA->length+LB->length>MAXSIZE)Printf("表上溢/n”；exit(1);i=O,j=O,k=O;valuel=LA->datai;value2=LB->dataj;while(i<LA->length&&jLB->length)*循环，两两比拟，小者存入结果表*/if(valuel<=value2)LC->datak=valuel;i+;valuel=LA->datai;elseLC->datak=value2;j+;value2=LB->dataj;k+;)while(i<LA->length)*当LA表未检测完，继续向结果表传送*/LC->datak=valuel;i+;k+;valuel=LA->datai;)while(j<LB->length)*当LB表未检测完，继续向结果表传送*/LC->datak=value2;j+;k+;value2=LB->dataj;LC->length=k;returnLC;)(5)实现从表中删除所有其值重复的元素的函数如下:voidDelDouble(listtype*L)inti,j,k;inttmp;if(L->length=O)Printf(“表空n"；exit(1);)i=0;while(i<L->length)*循环检测*/j=i+1;tmp=L->datai;while(j<L->length)*对于每一个i,重复检测一遍后续元素*/if(tmp=L->dataj)/*如果相等,删除此结点，后续元素前移*/for(k=j+1;k<L->length;k+)L->datak-l=L->datak;L->length-;/*表最后元素位置减1*/)elsej+;)i+;/*检测完L->datai,检测下一个*/8 .线性表可用顺序表或链表存储。试问：(1)两种存储表示各有哪些主要优缺点？(2)如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3)假设表的总数根本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时,应采用哪种存储表示？为什么？【解答】(1)顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不fo链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。(2)如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示。如果采用顺序存储表示，必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于11个表(包括表的总数可能变化)共存的情形,处理十分简便和快捷。所以选用链接存储表示较好。(3)应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。假设表的总数根本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。/*链表结构的定义.为简化起见，表元素我们使用整型数据此链表带头结点*/typedefstructmynodeintdata;/*数据域：整型*/structmynode*next;/*指针域*/node,Iinklisttype;9 .试写出计算线性链表长度的算法。intIengthsl(linklisttype*L)Iinklisttype*p;intIen;if(LP=Ien,=NULL)return-1;L->next;*p指向链表L的头结点*/=0;while(p!=NULL)Ien+;p=p->next;)returnlen;10设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如以下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。PFKIreturn;*表未初始化，或为空表*/*循环修改链表中所有结点的后继指针的指向*/*取当前结点的后继指针*/*当前结点的后继改为指向其原来的前驱*/*指针后移*/*原第一个结点改为最后一个结点*/*链表的头结点指向原最后一个结点*/【解答】voidLinkListInverse(linklisttype*L)Iinklisttype*p,*pre,*next;if(L=NULLIIL->next=NULL)p=L->next;pre=L;while(p!=NULL)next=p->next;p->next=pre;pre=p,p=next;)L->next->next=NULL;L->next=pre;11 .设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表，其中一链表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。【解答】voidLinkListDispose(linklisttype*L,Iinklisttype*LA,Iinklisttype*LB)*将链表L分解为LA、LB两个链表，其中LA中结点值均为正，LB中结点值均为负，并删除结点值为零的结点,最后释放L的头结点。*/Iinklisttype*p,*pt,*pa,*pb;LA=initiatesl();pa=LA;/*指向LA中的最后一个结点*/LB=initiatesl();pb=LB;/*指向LB中的最后一个结点*/If(L=NULLIIL->next=NUUL)return;*L为空指针或L为空表*/p=L->next;while(p!=NULL)if(p->data>0)pa->next:p;pa=p;p=p->next;)elseif(p->data<O)pb->next:p;pb=p;p=p->next;)elsept=p->next;free(p);P=pt；)pa->next=NULL;pb->next=NULL;free(L);*P指向链表L的第一个结点*/*遍历链表L*/*将p链入链表LA的pa后*/*将p链入链表LB的pb后*/*删除值为O的结点*/*记录当前结点的后继，以便删除当前结点*/12 .设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。【解答】voidIinklistMerge(linklisttypeA,Iinklisttype*LB)/*合并有序链表LA与LB,结果存入LA中，并释放LB的头结点*/Iinklisttype*pa,*pb,re,*pn;if(LA=NULLIILB=NULL)return;if(LA->next=NULL)*LA为空表，那么直接将LB链入LA即可*/LA->next=LB->next;free(LB);retrun;if(LB->next=NULL)return;pa=LA->next,pb=LB->next,pre=LA;while(pa!=NULL&&pb!=NULL)if(pa->data>pb->next)pre->next:pb;pn=pb->next;pb->next:pa;pb=pn;pre=pre->next)elsepa=pa->next;pre=pre->next;)if(pb!=NULL)pre->next=pb;free(LB);*LB为空表，那么直接返回即可*/*循环，两两比拟，小者存入结果表*/*将Pb链入LA,然后Pb指针后移*/*pa指针后移*/*将Pb剩余结点链入LA*/13 .设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。【解答】Linklisttype*IinklIstMergeinverse(linklisttypeA,Iinklisttype*LB)/*合并有序链表LA与LB,结果存入LC中，并释放LA、LB的头结点，函数返回LC*/Iinklisttype*pa,*pb,*p;if(LA=NULLIILB=NULL)return;LC=initiatesl();pa=LA->next,pb=LB->next;while(pa!=NULL&&pb!=NULL)if(pa->data>pb->next)p=pa->next;pa->next:LC->next;LC->next:pa;pa=p;)elsep=pb->next;pb->next:LC->next;LC->next:pb;Pb=p；)while(pa!=NULL)p=pa->next;pa->next=LC->next;*循环，两两比拟，大者存入LC*/*将pa链为LC的第一个结点*/*将Pa链为LC的第一个结点*/*将pa剩余结点链入LC*/LC->next=pa;pa=p;)*将pb剩余结点链入LC*/while(pb!=NULL)p=pb->next;pb->next=LC->next;LC->next=pb;pb=p；)free(LA);free(LB);14 .在一个循环链表中寻找值为X的结点，并将该结点移到第一个结点之前。【解答】设此循环链表为单链表，那么其类型定义与一般单链表相同typedefstructmynodecyclelisttype;voidSearchmovefirst(cyclelisttype*CL,intx)cyclelisttype*p,*pre;if(CL=NULL)return;p=CL->next;pre:CL;while(p!=CL)*查找x,注意与普通单链表在判断是否到表尾上的不同*/if(p->data=x)break;elsepre=p;p=p->next;)*查找成功*/*在原来位置删除p*/*P插入到CL后*/if(p!=CL)per->next=p->next;p->next=CL->next;CL->next=p;右图所不。结构的站台,到435612,16.铁路进行列车调度时，常把站台设计成栈式结构的站台，如试问：(1)设有编号为1,2,3,4,5,6的六辆列车，顺序开入栈式那么可能的出栈序列有多少种？(2)假设进站的六辆列车顺序如上所述，那么是否能够得325641,154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出进栈或出栈的序列)。【解答】可能的不同出栈序列有(1/(6+1)*=132种。(2)不能得到435612和154623这样的出栈序列。因为假设在4,3,5,6之后再将1,2出栈，那么1,2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。17.试证明：假设借助栈可由输入序列1,2,3,n得到一个输出序列pi,p2,p3,6（它是输入序列的某一种排列），那么在输出序列中不可能出现以下情况