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

习题一L什么是数据结构，数据的逻辑结构，数据的存储结构？数据结构对算法有什么影响？请举例说明。2.数据结构的存储方式主要有哪两种？它们之间的本质区别是什么？3.设为正整数，分析下列各程序段中加下划线的语句的执行次数。(1)for(int i =1;i =n;i-H)for(int j =1；j 9 l j-H)c i D I=0.。for(int k=1;k =n;leH)cif=ci 口 +ai R *;x =a y =afor(int i =1;i =n;i-H)for(int j =1;j =i;j-H)for(int k 1;k =j;k-H)x =x +y;int i =1,j =1;whi le&:j i)i =i +1；j =j +i；*int i =1;do for(int j =1;j j-H)i =i +j；while(i 1 00+rj);4试编写一个函数计算n!*2,的值，结果存放于数组A,rray Siz e的 第n个数组元素中，OW n array Siz e或者对于某一个k(p k max lnt时，应按出错处理。可有如下三种不同的出错处理方式：(1)用printf显示错误信息及ex it(1)语句来终止执行并报告错误；(2)用返回整数函数值Q 1来实现算法，以区别是正常返回还是错误返回；(3)在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。5.设 有 一 个 线 性 表(劭 加2,a i)存放在一个一维数组A ar ray Siz e中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个 原 址 内 容 置 换 为a r,，a 幻。最后分析此算法的时间复杂度及空间复杂度。6.顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对 有1 2 7个元素的顺序表进行插入，平均需要移动多少个元素？删除一个元素,又平均需要移动多少个元素？7.利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度，并 分 析 与6)的时间复杂度出现差异的原因。(1)从顺序表中删除具有给定值x的所有元素。(2)从顺序表中删除其值在给定值s与t之间(要求s小 于t)的所有元素。(3)从有序顺序表中删除其值在给定值s与t之 间(要 求s小 于t)的所有元素。将两个有序顺序表l a,1 b合并成一个新的有序顺序表1 G(5)从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。&线性表可用顺序表或链表存储。试问：(1)两种存储表示各有哪些主要优缺点?如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3)若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？9.试写出计算线性链表长度的算法。10.设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。pr=Q P pr h PjnW rkrnprm 1kl dsIL设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表，其中一链表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。1 2设h a和h b分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。13.设h a和h b分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。14在一个循环链表中寻找值为x的结点，并将该结点移到第一个结点之前。15.对于下面的每一步，画出栈元素和栈顶指针的示意图:(1)栈初始化；(2)元 素 x入栈;(3)元 素 y入栈;(出栈(5)栈初始化(。元 素 z入栈16.铁路进行列车调度时，常把站台设计成栈式结构的五陵,皿站台，如右图所示。试问：(1)设有编号为L 2,3,4,5,6的六辆列车，顺序开 P入栈式结构的站台，则可能的出栈序列有多少种？若进站的六辆列车顺序如上所述，那么是否能够得到435612,325641,154623和 135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到即写出得栈域得栈的序列)。17.试证明：若借助栈可由输入序列1,2,3,，n得到一个输出序列p,R,R,，R 它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况,即存在i j k,使 得 p p;二写出转换过程中栈的变化。诔示乘方运算）22.设循环队列的容量为7 0（序 号 从1到7Q）,经过一系列入队和退队运算后，有：（1）front=15,reap=46（2）front=45,reai=10问在上述两种情况下，循环队列中各有多少个元素？23.设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结构的队列的插入Qnqueu和删除（dequeue）算法，并给出队列空和队列满的条件。习 题21.列出右图所示二叉树的叶结点、分支结点和每个结点的层次。2.使 用（1）顺 序 表 示 和Q）二叉链表表示法，分别画出上图所示二叉树的存储表示。3.在 结 点 个 数 为 n 3 D 的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？4.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。5.如果一棵 树 有 n 个 度 为 1的结点，有 力 个 度 为 2 的结点，瓜 个 度 为 m的结点，试问有多少个度为0的结点？试推导之。6.若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：(1)统计二叉树中叶结点的个数。(2)以二叉树为参数，交换每个结点的左子女和右子女。求二叉树的深度。7.一棵高度为h 的 满 k叉树有如下性质：第 h 层上的结点都是叶结点，其余各层上每个结点都有k 棵非空子树，如果按层次自顶向下，同一层自左向右，顺序 从 1开始对全部结点进行编号，试问：(1)各层的结点个数是多少？编 号 为 i的结点的父结点若存在)的编号是多少？(3)编 号 为 i 的结点的第m个孩子结点若存在)的编号是多少？编 号 为 i 的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？(5)若 结 点 个 数 为 n,则 高 度 h 是 n 的什么函数关系？&请画出下图所示的树所对应的二叉树、9.已 知 一 棵 二 叉 树 的 前 序 遍 历 的 结 果 是 ABBOEKHIJ,中序遍历的结果是EBONFHiqj,试画出这棵二叉树。10.给定权值集合 15,03,14,02,06,09,16,171,构造相应的霍夫曼树，并计算它的带权路径长度。习题三1.设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,765,897,9 0&试画出对其进行折半查找时的二叉查找树，并计算查找成功的平均查找长度和查找不成功的平均查找长度。2.若对有n个元素的有序顺序表和无序顺序表进行顺序查找，试就下列三种情况分别讨论两者在等查找概率时的平均查找长度是否相同？(1)查找失败；查找成功，且表中只有一个关键码等于给定值k的对象；(3)查找成功，且表中有若干个关键码等于给定值k的对象，要求一次查找找出所有对象。3.设 有1 0 0 0 0个记录对象，通过分块划分为若干子表并建立索引，那么为了提高查找效率，每一个子表的大小应设计为多大？4.设散列表为H T 口 引，散列函数为H=丘工用闭散列法解决冲突，对下列关键码序列12,23,45,57,20,03,7&31,15,3 6造表。(1)采用线性探测法寻找下一个空位，画出相应的散列表，并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。Q)采用随机探测法寻找下一个空位，随机数序列为：5,4,2,7,3,6,。画出相应的散列表，并计算等概率下查找成功的平均查找长度。5.设 有1 5 0个记录要存储到散列表中，要求利用线性探查法解决冲突，同时要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？设a是散列表的装载因子，则有ASLsucc=l(l+-l-)2-a6.设 有15000个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连结，每个页块可存放30个记录。若采用按桶散列，且要求查找到一个已有记录的平均读盘时间不超过1.5次，则该文件应设置多少个桶？已知，链地址法的 平 均 查 找 长 度/I7.设待排序的排序码序列为 12,2,16,3Q 28,10,16*20,0 1&,试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。(1)直接插入排序 希尔排序增量为5,2,1)(3)冒泡排序快速排序(3直接选择排序 堆排序二路归并排序&在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？9.试设计一个算法，使 得 在O 的时间内重排数组，将所有取负值的排序码排在所有取正值祚负值)的排序码之前。提示：对比快速排序的第一趟排序，此处，以0为控制关键字。10.手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个排序码后堆的变化。(1)按字母顺序排序：Tin)Dot,Eva,Rai)Kin)Guy,Ann,J in;Kay,Ron,JanQ)按数值递增顺序排序：26,33,35,29,19,12,22(3)同 样7个数字，换一个初始排列，再按数值的递增顺序排序：12,19,33,26,29,35,2211.希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法，试举例说明。1 2.在已排好序的序列中，一个对象所处的位置取决于具有更小排序码的对象的个数。基于这个思想，可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域co u n t,用于存放在已排好序的序列中该对象前面的对象数目，最后依count域的值，将序列重新排列，就可完成排序。试编写一个算法，实现计数排序。并说明对于一个有n个对象的序列，为确定所有对象的count值，最多需要 做n g 1）二次排序码比较。习题解答3.设为正整数，分析下列各程序段中加下划线的语句的执行次数。(1)for(int i 1;i Q n;i-H)for(int j=1;j=n;j-H)c ffl 0=0.0;for(int k 1;k =耳 kH)ci 皿=ci +ai k*bk 叱 x =a y =af o r (i n t i =1;i =n;i-H)f o r (i n t j =1；j Q i；j-H)f o r (i n t k 1;k =j;k-H)x =x +y;i n t i =1,j =1;w h i l e (i =i j =j)i =i +1；j =j +i；*i n t i =1;d o f o r (i n t j =1;j j-H)i =i +j；汕i l e (i 1 0 0 +r j);【解 答】(1)n n ni=l j=l k=li=l j=l k=l i=l j=l i=l 乙)乙 i=l 乙 i=l1 n(n+l)(2n+1)1 n(n+1)n(n+l)(n+2)=-1-=-2 6 2 2 6(3)i =1时，i=2,j=j+i =l +2 =2+，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 +v j=(k+l)+i 100+n2的最小整数k,语 句 i=i+j 的程序步数为n*k4 试编写一个函数计算n!*2的值，结果存放于数组A 区 rraySize的 第 n个数组元素中，04 nW arraySiza若设计算机中允许的整数的最大值为maxlnt,则当 n arraySize或者对于某一个k(J)k maxlnt时，应按出错处理。可有如下三种不同的出错处理方式：(1)用 printf显示错误信息及exit(1)语句来终止执行并报告错误；(2)用返回整数函数值0,1来实现算法，以区别是正常返回还是错误返回；(3)在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。【解答】#include const int arraySize=10Qconst int IVhxInt 0 x7fffffff;int calc(int T 口，int n)int i,value=1;if(n!=0)int edge=VhxInt/n/2;for(i 1;i(耳 i-H-)value*=i*2;i f(value edge)return Qv al u e*n *2;Tn =v al u ep r in t f C A：%=,n,Tn);r et u r n 1;v o id m ain ()in t Aar r ay Siz e;in t i;fo r (i =。i length;for(int i=。i data i;Adata i=Ardata n i-1;Ardata|n i 1=tn时间复杂度：需进行P，次循环，因此时间复杂度为O G；空间复杂度：使用一个整形辅助存储单元W因此空间复杂度为。6.顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对 有127个元素的顺序表进行插入，平均需要移动多少个元素？删除一个元素,又平均需要移动多少个元素？【解答】若设顺序表中已有n个元素。又设插入或删除表中各个元素的概率相等，则在插入时因有 叶1个插入位置 可以在表中最后一个表项后面追加)，每个元素位置插入的概率为U 3 4),但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为人插入时平均移动元素个数AvN(Averagy Moving Number)为AANMANT =-1 -。(n i)=-1-(/n +(/n -1八)+1 +0()=-1-n-(-n-+-1-)=n=6n+l )n +1 n +1 2 2删除时平均移动元素个数的 为AMN=一(n i 1)(n-l)+(n-2)+1 +0)=-63n M n n 2 27.利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度,并 分 析 与(3)的时间复杂度出现差异的原因。(1)从顺序表中删除具有给定值X的所有元素。从顺序表中删除其值在给定值S与 t之间(要求S小 于 t)的所有元素。(3)从有序顺序表中删除其值在给定值s与 t之 间(要 求 s小 于 t)的所有元素。将两个有序顺序表la,1b合并成一个新的有序顺 序 表 Ie,(5)从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。【解答】(1)从顺序表中删除具有给定值x的所有元素。void DelValue(listtype int x)int i=0,j；wh ile(i V length)/循 环，寻找具有值x的元素并删除它Vif(Hxiata i=x)/删除具有值x的元素，后续元素前移for(j=i;j length 1;j-H-)LHdata|j=L-data j+1;L-length;长减 1Velse)Q)实现删除其值在给定值s与 t之 间(要 求 s小 于 t)的所有元素的函数如下：void DelValue s to t(1 i st type*L int s,int t)int i,j;i f(LHlength =0|s=t)printf C List is enpty or parameters are i 1 legal!5);exit(1);i=a毗 ile(i dataiXs 幽 lHdata i=t)T J 除满足条件的元素，后续元素前移for(j=i;j length 1;j-H-)L4data j=LHdata j+1;le n g th-i 长减else i-H;)6)实现从有序顺序表中删除其值在给定值s与 t之间的所有元素的函数如下：void DelValue s to t 1 (1 i st type int s int t)int i,j,k;i f(LHlength =0|s=t)printf C List is errpty or parameters are i 1 legal!p);exit(1);for(i=Q i lengt4 i-H-)/为 循环，寻 找 值 s 的第一个元素”i f(LHdata i X s)break;/退出循环时，i指向该元素i f(i length )for(j=l;i+j t 的第一个元素沙if(Hdata Q+j t)break;/3 退出循环时，i+j指向该元素*/for&=i+j;k v length;k+)/删除满足条件的元素，后续元素前移9L-5data k j=L-data R;Llength-=j;长减”)实现将两个有序顺序表合并成一个新的有序顺序表的函数如下：1 i st type*Nferge(listtype*IA 1 i st type*LB)/哈并有序顺序表LA与 LB成为一个新的有序顺序表并由函数返回1 isttype*L Qint va luel,va luedint i,j,k;ini t ia tel ist(L O;i f C A length+L B-length M X X S I Z printf(表上溢;exit(1);i =0,j=0,k=。va luel=I A da ta i;va lue2 =L B-da ta j;while(i length 8&c j length)/循 环，两两比较，小者存入结果表”i f(ya luel da ta k =va luel;iH 4；va 1 uel=L A da ta i;else I X H da ta k =va lued j H va lue2=L B-da ta j;while(i lengtli)/当L A表未检测完，继续向结果表传送*/L G-da ta I X =va luel;i-H;k+;va luel=I A da ta i;while(j V L&lengtH)/当L B表未检测完，继续向结果表传送L G-da ta k =va lued j-H;va lue2 =L B da ta j;)L G-length=k;return L Q(5)实现从表中删除所有其值重复的元素的函数如下:void D elD oub le(listtype*D int i,j,k;int trqi f Clength =0)printf(表空5 ;exit(1);i=Qwh ile(i length )Y 环 检 测/j=i+1；tnp=LHdata i;i l e(j le n g th)/对 于 每 一 个 i,重复检测一遍后续元素*/if(tmp=I d a ta m)/像口果相等，删除此结点，后续元素前移*/for(k j+1;k lengtFg leH-)L-data L-data 冈;LHlength 5 /表最后元素位置减1/)else j+Hi+H/检测完 data DQ,检测下一个“&线性表可用顺序表或链表存储。试问：(1)两种存储表示各有哪些主要优缺点？(2)如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化,表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3)若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么?【解答】（1）顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或按下标）直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时；由于在插入或删除时，为保持原有次序，平均需要移动一半或近一半）元素，修改效率不高。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。（2）如 果 有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示。如果采用顺序存储表示，必须在一个连续的可用空间中为这n 个表分配空间。初始时因不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对 于 n 个表包括表的总数可能变化）共存的情形，处理十分简便和快捷。所以选用链接存储表示较好。6）应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。链 表 结 构 的 定 义.为 简 化 起 见，表元素我们使用整型数据此 链 表 带 头 结 点-Vtypedef struct mynode int data;据域：整型“struct mynode*next;/旨针域 夕 node,1 inkl isttyp9试写出计算线性链表长度的算法。int length s 1 (1 inkl isttype*D 1inklisttype*gint lergi f=NULI)return 1;P=Inext;广p指向链表L的头结点*/len=。wh i le 3!=NULI)len-Hp=p-next;return len;10.设有一个表头指针为h 的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。pr=O P pr h Prm1rzprr=prm rTffTF1kl ES【解答】void LinkListlnverse(linklisttype*D 1 inkl isttype*p,*pre,*next;i f t =N IL|L4next=MLL)return;未初始化，或为空表*/p=L-next;pre=Lwh ile(p!=NIIL)指 向 next=p-next;pHnext=pre;驱 tzpre=p,p=next;LHnext-next=NULL;LHnext=pre/循环修改链表中所有结点的后继指针的E当前结点的后继指针/当前结点的后继改为指向其原来的前针后移女/小 第 一个结点改为最后一个结点*/链表的头结点指向原最后一个结点*/11.设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表，其中一链表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。【解答】void LinkListDispose(1 inklisttype*L,1 inklisttype*LA 1inklisttype*13 将链表L分解为IA LB两个链表，其 中 IA中结点值均为正，LB中结点值均为负，并删除结点值为零的结点，最后释放L的头结点。*/1 inkl isttype*p,*pt,*ptLA=initiatesl 0;pa=IA 川旨向LA中的最后一个结点*/LB=initiates1pb=邙 向 中 的 最后一个结点*/If(L=NLL|I ie x t=NLII)return 为空指针或 L为空表/p=LHnext;wh ile(p!=i f-data Q pa-next=居pa=Dp=fHxiext;elsei f(pHxiata next=RPb=Bp=p-next;else pt=p-next;结 点/free ;P=Pt；pa-next=NULL;pb-next=NULL;尸 P指向链表L的第一个结点*/遍 历 链 表 LV个 各P链入链表LA的 pa后/P链入链表LB的 pb后火/删 除 值 为 0的结点*/d己录当前结点的后继，以便删除当前f ree Q;12.设 h a和 h b分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。【解答】void 1inklistNferge(linklisttype*IA 1inklisttype*LB)/哈并有序链表IA与 13结果存入IA中，并释放 的 头 结 点 V1 inkl isttype*pa,*pb,*pre,*prgi f(LA 7 NULL|I LB=NULL|)return;i f OAnext=N U)/I A 为空表，则直接将LB链 入 IA即 可 D-iext=LB-iext;f ree CB;ret run;if C3next=NLLD return;/1 fLB为空表，则直接返回即可“pa=IAnext,pb=LB-next,pre=4A汕 ile 0a!=N IL pb!=N II)I5循环，两两比较，小者存入结果表i f)a-data ptHnext)4各pb链 入 L A 然 后 pb指针后移*/pre-next=pb;pn=pkHnext;pbnext=pa;pb=pn;pre=pre4nextelse/tp a指 针 后 移/pa=pa-next;pre=pre-next;i f(pb!=N II)pre-next=pb;f ree(JJ3;不 各pb剩余结点链入LAV13.设h a和h b分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。【解答】Linkl i st type*1 inkl istlferge_inverse(1 inkl isttype 1 inkl isttype*LB)/哈 并 有 序 链 表LA与13结 果 存 入LC中，并 释 放IA LB的 头 结 点，函数返回LCVlinklisttype*pa,*pb,*口if(LA=MIL|LB=N IL|)return;LC=initiates!0;pa=LA-next,pb=LB-next;wh ile(pa!=NULL pb!=NULL)f 环，两两比较，大者存入LCVi f(pa-data pb-next)/各 pa链为 LC的 第 一 个 结 点/p=pa-next;pa-next=LG-next;LG-next pa;pa=居else p=pb-next;pb-next=LG-next;LGnext=pb;pb=Rwh i le 9a!=N II)p=pa-next;paHnext=LGfnext;LG-next=pa;pa=Bwh ile(pb!=NM)p=pb-next;ptHnext=LG-next;LG-next=pb;Pb=R个 各pa链 为 DC的第一个结点*/个 各 pa剩余结点链入LC*/各 pb剩余结点链入LCVf ree 口;f ree C3；14在一个循环链表中寻找值为x的结点，并将该结点移到第一个结点之前。【解答】设此循环链表为单链表，则其类型定义与一般单链表相同typedef struct mynode cyclelisttypvoid search jnovef i rst Cyclel isttype*_ int 力 cyclelisttype*p,i f CL=NULL)returnp=CLHnext;pre=CL;wh i le 3!=CI)小 找x,注意与普通单链表在判断是否到表尾上的不同文/i f Hdata=%break;else pre=Rp=p-next;if(p!=CI)per-next=pHnext;p-4next=CL-next;CLHnext=p/蜜 找 成 功/在原来位置删除p V/p插入到CL后*/16.铁路进行列车调度时，常把站台设计成栈式结构的站台，如右图所示。试问：(1)设有编号为1,2,3,4,5,6的六辆列车，顺序开入栈式结构的站台，则可能的出栈序列有多少种？(2)若进站的六辆列车顺序如上所述，那么是否能够得到435612,325641,154623和135426的出站序列,如果不能，说明为什么不能；如果能,说明如何得到即写出得栈域性栈的序列)。【解答】(1)可能的不同出栈序列(l/(6+l)*Cp=132有种。不能得到435612和154623这样的出栈序列。因为若在4,3,5,6之后再将1,2出栈，则L 2必须一直在栈中，此 时1先进栈，2后进栈，2应压在1上面,不可能1先于2出栈。1 5 4 6 2 3也是这种情况。出栈序列3 2 5 6 4 1和1 3 5 4 2 6可以得到。1 7.试证明：若借助栈可由输入序列1,2,3,，n得到一个输出序列p,R,访，P它是输入序列的某一种排列），则在输出序列中不可能出现以下情况，即存在i v j v k,使 得P v R P。提示：用反证法）【解答】因为借助栈由输入序列1,2,3,，0,可得到输出序列P,必 出 ,P，,如果存在下标i,j,k,满 足i j Vk,那么在输出序列中，可能出现如下5种情况：i进栈，i出栈，j进栈，j出栈，k进栈，k出栈。此时具有最小值的排在最前面p位置，具有中间值的排在其后p位置，具有最大值的排在R位置，有p v p v 时 不可能出现R n p的情形；i进栈，i出栈，j进栈，k进栈，k出栈，j出栈。此时具有最小值的排在最前面R位置，具有最大值的排在p位置，具有中间值的排在最后R位置，有P i R p ,不 可 能 出 现R P i的情形；i进栈，j进栈，j出栈，i出栈，k进栈，k出栈。此时具有中间值的排在最前面R位置，具有最小值的排在其后P位置，有D V p,时 不可能出现D R R的情形；i进栈，j进栈，j出栈，k进栈，k出栈，i出栈。此时具有中间值的排在最前面P位置，具有最大值的排在其后P位置，具有最小值的排在R位置，有R V R R,也不可能出现pj V R P的情形；i进栈，j进栈，k进栈，k出栈，j出栈，i出栈。此时具有最大值的排在最前面R位置，具有中间值的排在其后P位置，具有最小值的排在R位置，有R topO Q;elseret run topl xNKXSI;判栈满int DoubleStackFul 1 (DoubleStack*D Q)return C6topl-4DStopO=l);入栈int PopDoubl eStack(poubl eSt ack*int StackNQ elentype 力 个等数据元素x插入到栈StackNo中*/if(poubleStackFull(ffi)return(FALSE 满溢出沙i f(StackN D Q 寸第0栈插入 VD6top0-H;D6Hdata top(J=x;)e ls e Q(寸第1栈插入DS-5topl;D6Hdata topl=return(E R L 旧;删除算法elemtype Push DoubleStack(poubleStack*int StackNq)/以 StackNo栈中删除并返回一个元素，若栈空，则返回N IL Vi f Cbub 1 eStackBnpty(DS,StackNo)return H W ；if S ta c k N g 依 寸 0号栈进行操作”DSHtopOjreturn(pS-data|DSHtopCH-l);else DSHtopl-H3return(p&-data 0DS-topl 1);)19.改写顺序栈的进栈成员函数P u s h3,要求当栈满时执行一个stackFull()操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组,代替原来的栈数组，原来栈数组中的元素占据新数组的前皿xSize位置。【解答】void push (stack*S elontype 力 i f(StackBrpty stackFul 1 ；栈满，做溢出处理S-topSHdata S-tof)=/f f i 栈void stackFul 1 (stack*9 elemtypetOTp=cal loc(3/KXSIZE；sizeof(plemtypq);/创建体积大二倍的数组for(in t i=Q i data i;free(5dat);/删去原数组MXSIZE 3;SHdata=taip5/数组最大体积增长二倍/新数组成为栈的数组空间20.根据教案中给出的优先级，回答以下问题：（1）在表达式求值的过程中，如果表达式e含 有 n个运算符和分界符，问操作数栈M 中最多可存入多少个元素？如果表达式e含 有 n个运算符，且括号嵌套的最大深度为6层，问栈中最多可存入多少个元素？【解答】（1）如果表达式e含 有 n个运算符和分界符，则可能的运算对象有叶1个。因此在利用后缀表达式求值时所用到的运算对象栈中最多可存入计1个元素。同上。21.表达式的中缀表示为a*x-b/xA2,试利用栈将它改为后缀表示ax*bx2-3 写出转换过程中栈的变化。诔示乘方运算）【解答】若设当前扫描到的运算符Ch 的优先级为icp（c*该运算符进栈后的优先级为 isp th）,则可规定各个算术运算符的优先级如下表所示。运 算符(A3十_)isp017538icp086421isp 也叫做栈内（in stack p rio rit。优 先 数,icp也叫做栈外（in caningp riori3 优先数。当刚扫描到的运算符ch 的 icptH）大 于 isp（stacb时，则ch 进栈；当刚扫描到的运算符ch 的 icp四 小 于 isp（stac2时，则位于栈顶的运算符退栈并输出。从表中可知，icp（“）最高，但当“（进栈后，isp（“）变得极低。其它运算符进入栈中后优先数都升1,这样可体现在中缀表达式中相同优先级的运算符自左向右计算的要求。运算符优先数相等的情况只出现在括号配 对 )”或栈底的“丁 号 与 输 入 流 最 后 的 号 配 对 时。前者将连续退出位于栈顶的运算符，直到遇到“(为止。然后将“退栈以对消括号，后者将结束算法。步序扫描项项类型动 作栈的变化输出0年进栈，读下一符号1a 操作数k 直接输出，读下一符号A2*操作符 isp(；)icp C-栈输出),退a X *b isp C；)icp C栈，读下一符号),进 _a X *5b 操作数它直接输出，读下一符号 _a X *b6/操作符k isp(-)icp(;栈输出),退；-za X *1 3 7 icp C;栈输出),退 _a x*b Xr yb isp(-)icp C;