计算机软件基础习题及其参考-答案~.doc

《计算机软件基础习题及其参考-答案~.doc》由会员分享，可在线阅读，更多相关《计算机软件基础习题及其参考-答案~.doc（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-_习题一习题一1.什么是数据结构，数据的逻辑结构，数据的存储结构？数据结构对算法有什么影响？请 举例说明。2.数据结构的存储方式主要有哪两种？它们之间的本质区别是什么？3.设n为正整数, 分析下列各程序段中加下划线的语句的执行次数。(1) for (int i = 1; i arraySize 或者 对于某一个 k (0 k n)，使得 k!*2k maxInt 时，应按出错处理。可有如下三种不同 的出错处理方式： (1) 用 printfprintf 显示错误信息显示错误信息及 exitexit(1)语句来终止执行并报告错误； (2) 用返回整数函数值 0, 1 来实现算法，以区别是正常返

2、回还是错误返回； (3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。5.设有一个线性表 (a0, a1, , an-2, an-1) 存放在一个一维数组 AarraySize中的前 n 个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前 n 个原址内容置 换为 (an-1, an-2, , a1, a0)。最后分析此算法的时间复杂度及空间复杂度。6.顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有 127-_个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一

3、个元素, 又平均需要移动多 少个元素?7.利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度，并分析(2) 与(3)的时间复杂度出现差异的原因。 (1) 从顺序表中删除具有给定值 x 的所有元素。 (2) 从顺序表中删除其值在给定值 s 与 t 之间（要求 s 小于 t）的所有元素。 (3) 从有序顺序表中删除其值在给定值 s 与 t 之间（要求 s 小于 t）的所有元素。 (4) 将两个有序顺序表 la,lb 合并成一个新的有序顺序表 lc。 (5) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。8.线性表可用顺序表或链表存储。试问： (1) 两种存储表示各有

4、哪些主要优缺点? (2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总 数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？ (3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的 元素，这时，应采用哪种存储表示？为什么？9.试写出计算线性链表长度的算法。10.设有一个表头指针为 h 的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有 结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针 h 指向原链表的最后一 个结点。11.设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表，其中一链 表中的结点值均为负整

5、数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。12设 ha 和 hb 分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的 存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。13设 ha 和 hb 分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的 存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。14.在一个循环链表中寻找值为 x 的结点，并将该结点移到第一个结点之前

6、。15.对于下面的每一步，画出栈元素和栈顶指针的示意图： （1）栈初始化； （2）元素 x 入栈；-_（3）元素 y 入栈； （4）出栈 （5）栈初始化 （6）元素 z 入栈16.铁路进行列车调度时, 常把站台设计成栈式结构的站台， 如右图所示。试问： (1) 设有编号为 1,2,3,4,5,6 的六辆列车, 顺序开入栈式 结构的站台, 则可能的出栈序列有多少种? (2) 若进站的六辆列车顺序如上所述, 那么是否能够得到 435612, 325641, 154623 和 135426 的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出“进栈“或“出栈“的序列)。17.试

7、证明：若借助栈可由输入序列 1, 2, 3, , n 得到一个输出序列 p1, p2, p3, , pn (它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在 i 1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？ 多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 4试分别画出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态。 5如果一棵树有 n1个度为 1 的结点, 有 n2个度为 2 的结点, , nm个度为 m 的结点, 试 问有多少个度为 0 的结点? 试推导之。 6若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归

8、算法： (1) 统计二叉树中叶结点的个数。 (2) 以二叉树为参数，交换每个结点的左子女和右子女。 (3) 求二叉树的深度。 7一棵高度为 h 的满 k 叉树有如下性质: 第 h 层上的结点都是叶结点, 其余各层上每个结 点都有 k 棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从 1 开始对全部结点 进行编号, 试问: (1) 各层的结点个数是多少? (2) 编号为 i 的结点的父结点(若存在)的编号是多少? (3) 编号为 i 的结点的第 m 个孩子结点(若存在)的编号是多少? (4) 编号为 i 的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为

9、n, 则高度 h 是 n 的什么函数关系? 8请画出下图所示的树所对应的二叉树。9已知一棵二叉树的前序遍历的结果是 ABECDFGHIJ, 中序遍历的结果是 EBCDAFHIGJ, 试 画出这棵二叉树。 10给定权值集合 15, 03, 14, 02, 06, 09, 16, 17 , 构造相应的霍夫曼树, 并计算它 的带权路径长度。12345678-_习题三1. 设有序顺序表中的元素依次为 017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半查找时的二叉查找树, 并计算查找成功的平均 查找

10、长度和查找不成功的平均查找长度。2. 若对有 n 个元素的有序顺序表和无序顺序表进行顺序查找, 试就下列三种情况分别讨论 两者在等查找概率时的平均查找长度是否相同? (1) 查找失败; (2) 查找成功, 且表中只有一个关键码等于给定值 k 的对象; (3) 查找成功, 且表中有若干个关键码等于给定值 k 的对象, 要求一次查找找出所有 对象。3. 设有 10000 个记录对象, 通过分块划分为若干子表并建立索引, 那么为了提高查找效率, 每一个子表的大小应设计为多大? 4. 设散列表为 HT13, 散列函数为 H (key) = key %13。用闭散列法解决冲突, 对下列 关键码序列 12

11、, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。 (1) 采用线性探测法寻找下一个空位, 画出相应的散列表, 并计算等概率下查找成功 的平均查找长度和查找不成功的平均查找长度。 (2) 采用随机探测法寻找下一个空位, 随机数序列为：5，4，2，7，3，6，。画出 相应的散列表, 并计算等概率下查找成功的平均查找长度。5. 设有 150 个记录要存储到散列表中, 要求利用线性探查法解决冲突, 同时要求找到所需 记录的平均比较次数不超过 2 次。试问散列表需要设计多大？ 设是散列表的装载因子， 则有)111 (21ASLsucc6. 设有 15000 个记录需放在散

12、列文件中，文件中每个桶内各页块采用链接方式连结，每个 页块可存放 30 个记录。若采用按桶散列，且要求查找到一个已有记录的平均读盘时间不超 过 1.5 次，则该文件应设置多少个桶？ 已知，链地址法的平均查找长度 ASL=1+/27. 设待排序的排序码序列为12, 2, 16, 30, 28, 10, 16*, 20, 6, 18, 试分别写出使 用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。 (1) 直接插入排序(2) 希尔排序(增量为 5,2,1)(3) 冒泡排序 (4) 快速排序(5) 直接选择排序(6) 堆排序 (7) 二路归并排序8. 在起泡排序过程中，什么情况下排序码会

13、朝向与排序相反的方向移动，试举例说明。在 快速排序过程中有这种现象吗？-_9. 试设计一个算法, 使得在 O(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 个数字，换一个初

14、始排列，再按数值的递增顺序排序：12, 19, 33, 26, 29, 35, 2211. 希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法, 试举例说明。12. 在已排好序的序列中，一个对象所处的位置取决于具有更小排序码的对象的个数。基 于这个思想，可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域 count，用于存放在已排好序的序列中该对象前面的对象数目，最后依 count 域的值，将序 列重新排列，就可完成排序。试编写一个算法，实现计数排序。并说明对于一个有 n 个对 象的序列，为确定所有对象的 count 值，最多需要做 n(n-1)/2 次排序码比较。-_ n1

15、in1j3n1kn162)1)(nn(n 21)n(n 21 61)1)(2nn(n 21i21i21 21)i(ij1n1in1in1i2n1ii1jn1ii1jj1k 习题解答 3.设n为正整数, 分析下列各程序段中加下划线的语句的执行次数。(1) for (int i = 1; i arraySize 或者 对于某一个 k (0 k n)，使得 k!*2k maxInt 时，应按出错处理。可有如下三种不同 的出错处理方式： (1) 用 printf 显示错误信息及 exit(1)语句来终止执行并报告错误； (2) 用返回整数函数值 0, 1 来实现算法，以区别是正常返回还是错误返回； (

16、3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。 【解答】#include const int arraySize = 100; const int MaxInt = 0x7fffffff; int calc( int T , int n ) int i, value = 1; if ( n != 0 ) int edge = MaxInt / n / 2; for ( i = 1; i edge ) return 0; value *= n * 2; Tn = value; printf(“A %d =

17、 %dn”,n,Tn); return 1; void main ( ) int AarraySize; int i; for ( i = 0; i length; for( int i = 0; i datai; A-datai = A-datan-i-1; A-datan-i-1 = tmp; 时间复杂度：需进行 n/2 次循环，因此时间复杂度为 O(n)； 空间复杂度：使用一个整形辅助存储单元 tmp，因此空间复杂度为 O(1)。6.顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有 127 个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平

18、均需要移动多 少个元素?【解答】 若设顺序表中已有 n 个元素。又设插入或删除表中各个元素的概率相等，则在插入时 因有 n+1 个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为 1/(n+1)，但在删除时只能在已有 n 个表项范围内删除，所以每个元素位置删除的概率为 1/n。 插入时平均移动元素个数 AMN(Averagy Moving Number )为5.632n 21)n(n 1n1)01)1n(n(1n1in1n1AMNn0i 删除时平均移动元素个数 AMN 为6321n 21)n(n n10)12)(n1)(nn11)i(nn1AMN1n0i7.利用顺序表的操作

19、，实现以下的函数。并分析你所编制的函数的时间复杂度，并分析(2) 与(3)的时间复杂度出现差异的原因。-_(1) 从顺序表中删除具有给定值 x 的所有元素。 (2) 从顺序表中删除其值在给定值 s 与 t 之间（要求 s 小于 t）的所有元素。 (3) 从有序顺序表中删除其值在给定值 s 与 t 之间（要求 s 小于 t）的所有元素。 (4) 将两个有序顺序表 la,lb 合并成一个新的有序顺序表 lc。 (5) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。【解答】 (1) 从顺序表中删除具有给定值 x 的所有元素。void DelValue(listtype * L, in

20、t x ) int i = 0, j; while ( i length )/*循环, 寻找具有值 x 的元素并删除它*/ if (L-datai = x ) /*删除具有值 x 的元素, 后续元素前移*/for (j = i;j length-1; j+ ) L-dataj = L-dataj+1; L-length-; /*表长减 1*/ else i+; (2) 实现删除其值在给定值 s 与 t 之间（要求 s 小于 t）的所有元素的函数如下：void DelValue_s_to_t (listtype *L,int s, int t) int i,j; if ( L-length =

21、0 | s = t ) printf(“List is empty or parameters are illegal!n”); exit(1); i = 0; while ( i length)/*循环, 寻找具有值 x 的元素并删除它*/if (L-datai=s j+ ) L-dataj = L-dataj+1; L-length-; /*表长减 1*/ else i+; (3) 实现从有序顺序表中删除其值在给定值 s 与 t 之间的所有元素的函数如下：void DelValue_s_to_t_1 (listtype *L,int s int t) int i,j,k; if ( L-l

22、ength = 0 | s = t ) printf(“List is empty or parameters are illegal!n”); exit(1); for (i = 0; i length; i+ ) /*循环, 寻找值 s 的第一个元素*/ if ( L-datai = s ) break; /*退出循环时, i 指向该元素*/if ( i length ) for (j = 1; i + j length; j+ )/*循环, 寻找值 t 的第一个元素*/ if (L-datai+j t ) break;/*退出循环时, i+j 指向该元素*/for (k = i+j; k

23、 length; k+ ) /*删除满足条件的元素, 后续元素前移*/L-datak-j = L-datak; L-length-= j; /*表长减 j*/-_ (4) 实现将两个有序顺序表合并成一个新的有序顺序表的函数如下：listtype * Merge(listtype *LA,listtype *LB ) /*合并有序顺序表 LA 与 LB 成为一个新的有序顺序表并由函数返回listtype *LC; int value1,value2; int i,j,k; initiatelist(LC); if (LA-length + LB-length MAXSIZE) printf(“表

24、上溢/n”; exit(1); i = 0, j = 0, k = 0; value1 = LA-datai; value2 = LB-dataj; while (i length i+; value1=LA-datai;else LC-datak = value2; j+; value2=LB-dataj; k+; while( i length)/*当 LA 表未检测完, 继续向结果表传送*/LC-datak = value1; i+; k+; value1 = LA-datai; while( j length)/*当 LB 表未检测完, 继续向结果表传送*/LC-datak = val

25、ue2; j+; k+; value2 = LB-dataj; LC-length = k; return LC; (5) 实现从表中删除所有其值重复的元素的函数如下：void DelDouble(listtype *L) int i,j,k; int tmp; if(L-length = 0 ) printf(“表空n”; exit(1); i=0; while ( i length ) /*循环检测*/j = i + 1; tmp = L-datai; while( j length ) /*对于每一个 i, 重复检测一遍后续元素*/-_if( tmp = L-dataj) /*如果相等,

26、删除此结点，后续元素前移*/for( k = j+1; k length; k+ ) L-datak-1 = L-datak; L-length-; /*表最后元素位置减 1*/ else j+; i+;/*检测完 L-datai, 检测下一个*/ 8.线性表可用顺序表或链表存储。试问： (1) 两种存储表示各有哪些主要优缺点? (2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总 数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？ (3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的 元素，这时，应采用哪种存储表示？为什么？ 【

27、解答】 (1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标) 直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期 间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均 需要移动一半(或近一半)元素，修改效率不高。 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有 空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理 顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改 效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取

28、效率不高。 (2) 如果有 n 个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也 可能自动改变、在此情况下，应选用链接存储表示。 如果采用顺序存储表示，必须在一个连续的可用空间中为这 n 个表分配空间。初始时因不 知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得 快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少 量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入； 在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。 如果采用链接存储表示，一个表的存储空间可以连续，可

29、以不连续。表的增长通过动态存 储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放 实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于 n 个表(包括表的总数可能变化)共存的情形，处理十分简便和快捷。所以选用链接存储表示 较好。 (3) 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的 总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用 顺序存储表示较好。-_/*-链表结构的定义.为简化起见，表元素我们使用整型数据- -此链表带头结点-*/typedef struct mynode int d

30、ata; /*数据域：整型*/ struct mynode *next; /*指针域*/ node, linklisttype;9.试写出计算线性链表长度的算法。int lengthsl(linklisttype *L) linklisttype * p; int len; if(L = NULL)return 1; p = L-next;/* p 指向链表 L 的头结点*/len = 0; while(p != NULL) len+; p = p-next; return len; 10.设有一个表头指针为 h 的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有 结点的链接方向逆转，如

31、下图所示。要求逆转结果链表的表头指针 h 指向原链表的最后一 个结点。【解答】void LinkListInverse(linklisttype *L) linklisttype *p, *pre, *next; if(L = NULL | L-next = NULL ) return; /*表未初始化，或为空表*/p = L-next; pre = L; while( p != NULL ) /*循环修改链表中所有结点的后继指针的指向*/ next = p-next;/*取当前结点的后继指针*/ p-next = pre;/*当前结点的后继改为指向其原来的前驱*/ pre = p , p=n

32、ext;/*指针后移*/ L-next-next = NULL;/*原第一个结点改为最后一个结点*/ L-next = pre;/*链表的头结点指向原最后一个结点*/-_11.设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表，其中一链 表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。【解答】void LinkListDispose(linklisttype * L,linklisttype * LA,linklisttype * LB) /* 将链表 L 分解为 LA、LB 两个链表，其中 LA 中结点值均为正，LB 中结点值均为负， 并删除结

33、点值为零的结点,最后释放 L 的头结点。*/ linklisttype *p , *pt , *pa, * pb; LA = initiatesl(); pa = LA;/*指向 LA 中的最后一个结点*/LB = initiatesl(); pb = LB;/*指向 LB 中的最后一个结点*/ If(L = NULL | L-next = NUUL) return;/*L 为空指针或 L 为空表*/p = L-next;/*p 指向链表 L 的第一个结点*/ while(p != NULL)/*遍历链表 L*/ if(p-data 0)/*将 p 链入链表 LA 的 pa 后*/pa-nex

34、t = p; pa = p; p = p-next; elseif(p-data next = p; pb = p; p = p-next; else/*删除值为 0 的结点*/ pt = p-next;/*记录当前结点的后继，以便删除当前结点*/ free(p); p = pt; pa-next = NULL; pb-next = NULL; free(L); 12设 ha 和 hb 分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的 存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。

35、 【解答】void linklistMerge(linklisttype *LA,linklisttype *LB )-_/*合并有序链表 LA 与 LB,结果存入 LA 中，并释放 LB 的头结点 */linklisttype *pa, *pb , *pre ,*pn; if(LA = NULL | LB = NULL |) return; if(LA-next = NULL)/*LA 为空表，则直接将 LB 链入 LA 即可*/LA-next = LB-next; free(LB); retrun; if(LB-next = NULL) return;/*LB 为空表，则直接返回即可*/p

36、a = LA-next, pb = LB-next ,pre=LA; while (pa != NULL pn = pb-next; pb-next = pa; pb = pn; pre = pre-next else/*pa 指针后移*/pa = pa-next; pre = pre-next; if(pb != NULL)/*将 pb 剩余结点链入 LA*/pre-next = pb; free(LB); 13设 ha 和 hb 分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的 存储空间,

37、不另外占用其它的存储空间。表中允许有重复的数据。 【解答】Linklisttype * linklistMerge_inverse(linklisttype *LA,linklisttype *LB ) /*合并有序链表 LA 与 LB,结果存入 LC 中，并释放 LA、LB 的头结点 ,函数返回 LC*/linklisttype *pa, *pb , *p; if(LA = NULL | LB = NULL |) return; LC = initiatesl(); pa = LA-next, pb = LB-next; while (pa != NULL pa-next = LC-next

38、; LC-next = pa; pa = p; -_else/*将 pa 链为 LC 的第一个结点*/p = pb-next; pb-next = LC-next; LC-next = pb; pb = p; while(pa != NULL)/*将 pa 剩余结点链入 LC*/p = pa-next; pa-next = LC-next; LC-next = pa; pa = p; while(pb != NULL)/*将 pb 剩余结点链入 LC*/p = pb-next; pb-next = LC-next; LC-next = pb; pb = p; free(LA); free(LB

39、); 14.在一个循环链表中寻找值为 x 的结点，并将该结点移到第一个结点之前。 【解答】设此循环链表为单链表，则其类型定义与一般单链表相同typedef struct mynode cyclelisttype; void search_movefirst(cyclelisttype *CL, int x) cyclelisttype * p , *pre; if(CL = NULL) return; p = CL-next; pre = CL; while(p != CL) /*查找 x，注意与普通单链表在判断是否到表尾上的不同*/if(p-data = x) break; else pre

40、 = p; p = p-next; if(p != CL)/*查找成功*/ per-next = p-next;/*在原来位置删除 p*/ p-next = CL-next;/*p 插入到 CL 后*/CL-next = p; -_132)16/(16 12C16.铁路进行列车调度时, 常把站台设计成栈式结构的站台， 如右图所示。试问： (1) 设有编号为 1,2,3,4,5,6 的六辆列车, 顺序开入栈式 结构的站台, 则可能的出栈序列有多少种? (2) 若进站的六辆列车顺序如上所述, 那么是否能够得到 435612, 325641, 154623 和 135426 的出站序列, 如果不能,

41、 说明为什么不能; 如果能, 说明如何得到(即写出“进栈“或“出栈“的序列)。【解答】 (1) 可能的不同出栈序列有 种。 (2) 不能得到 435612 和 154623 这样的出栈序列。因为若在 4, 3, 5, 6 之后再将 1, 2 出栈，则 1, 2 必须一直在栈中，此时 1 先进栈，2 后进栈，2 应压在 1 上面，不可能 1 先于 2 出栈。154623 也是这种情况。出栈序列 325641 和 135426 可以得到。3562244 44111111113 32 32 325 325 3256 32564 32564153441222261 1 13 135 1354 1354

42、2 13542 13542617.试证明：若借助栈可由输入序列 1, 2, 3, , n 得到一个输出序列 p1, p2, p3, , pn (它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在 i top0 top1 = MAXSIZE); 判栈满int DoubleStackFull(DoubleStack * DS) return(DS-top1-DS-top0=1); 入栈int PopDoubleStack(DoubleStack * DS,int StackNo,elemtype x) /*将数据元素 x 插入到栈 StackNo 中*/ if(DoubleSta

43、ckFull(DS) return(FALSE);/*栈满溢出*/ if(StackNo=0)/*对第 0 栈插入*/DS-top0+; DS-datatop0=x;bot0 top0 top1 bot1-_ else/*对第 1 栈插入*/DS-top1-; DS-datatop1=x; return(TRUE); 删除算法elemtype PushDoubleStack(DoubleStack * DS,int StackNo) /*从 StackNo 栈中删除并返回一个元素，若栈空，则返回 NULL*/if(DoubleStackEmpty(DS,StackNo) return(NULL

44、); if(StackNo=0)/*对 0 号栈进行操作*/DS-top0-; return(DS-dataDS-top0+1); else DS-top1+; return(DS-dataDS-top1-1); 19.改写顺序栈的进栈成员函数 Push(x)，要求当栈满时执行一个 stackFull( )操作进行栈 满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组， 原来栈数组中的元素占据新数组的前 MaxSize 位置。 【解答】void push(stack * S,elemtype x) if(StackEmpty(S) stackFull(S);/栈满，做

45、溢出处理S-top +; S-dataS-top = x;/进栈void stackFull(stack *S) elemtype *temp; temp=calloc(3*MAXSIZE,sizeof(elemtype); /创建体积大二倍的数组 for ( int i = 0; i top; i+ ) /传送原数组的数据tempi = S-datai; free(S-data);/删去原数组 MAXSIZE *= 3; /数组最大体积增长二倍 S-data = temp;/新数组成为栈的数组空间20.根据教案中给出的优先级，回答以下问题： (1) 在表达式求值的过程中，如果表达式 e 含有

46、 n 个运算符和分界符，问操作数栈(NS)中-_最多可存入多少个元素？ (2) 如果表达式 e 含有 n 个运算符，且括号嵌套的最大深度为 6 层，问栈中最多可存 入多少个元素？ 【解答】 (1) 如果表达式 e 含有 n 个运算符和分界符，则可能的运算对象有 n+1 个。因此在利 用后缀表达式求值时所用到的运算对象栈中最多可存入 n+1 个元素。 (2) 同上。21.表达式的中缀表示为 a * x - b / x2，试利用栈将它改为后缀表示 ax * bx2/ -。写 出转换过程中栈的变化。(表示乘方运算) 【解答】 若设当前扫描到的运算符 ch 的优先级为 icp(ch)，该运算符进栈后的

47、优先级为 isp(ch)， 则可规定各个算术运算符的优先级如下表所示。运算符 ; ( *,/, %+, -)isp01 7 5 3 8icp08 6 4 2 1isp 也叫做栈内(in stack priority)优先数，icp 也叫做栈外(in coming priority)优先数。 当刚扫描到的运算符 ch 的 icp(ch)大于 isp(stack)时，则 ch 进栈；当刚扫描到的运算符 ch 的 icp(ch)小于 isp(stack)时，则位于栈顶的运算符退栈并输出。从表中可知，icp(“(”)最高， 但当“(”进栈后，isp(“(”)变得极低。其它运算符进入栈中后优先数都升 1，这样可体现在 中缀表达式中相同优先级的运算符自左向右计算的要求。运算符优先数相等的情况只出现 在括号配对“)”或栈底的