【考研类试卷】栈、队列和数组及答案解析.doc

《【考研类试卷】栈、队列和数组及答案解析.doc》由会员分享，可在线阅读，更多相关《【考研类试卷】栈、队列和数组及答案解析.doc（15页珍藏版）》请在麦多课文档分享上搜索。

1、栈、队列和数组及答案解析(总分：92.00，做题时间：90 分钟)一、单项选择题(总题数：26，分数：52.00)1.二维数组 A 的每个元素是由 6 个字符组成的串，其行下标 i=0，1，8，列下标 j=1，2，10。若A 按行先存储，元素 A8，5的起始地址与当 A 按列先存储时的元素( )的起始地址相同。设每个字符占一个字节。（分数：2.00）A.A8，5B.A3，10C.A 5，8D.A0，92.数组 A110，26，28以行优先的顺序存储，设第一个元素的首地址是 100，每个元素占 3 个存储长度的存储空间，则元素 A5，0，7的存储地址为( )。（分数：2.00）A.913B.91

2、0C.915D.9233.设有一个二维数组 Amn，假设 A00存放位置在 644，A22存放位置在 676，每个元素占一个空间，问 A33存放在( )位置。（分数：2.00）A.688B.678C.692D.6964.假设以行序为主序存储二维数组 Aarray1100，1100，设每个数据元素占 2 个存储单元，基地址为 10，则 LOC5，5=( )。（分数：2.00）A.808B.818C.1010D.10205.设 A 是 n*n 的对称矩阵，将 A 的对角线及对角线上方的元素以列为主的次序存放在一维数组B1n(n+1)/2中，则上述任一元素 aij(1i，jn，且 ij)在 B 中的

3、位置为( )。（分数：2.00）A.i(i-1)/2+jB.j(j-1)/2+iC.j(j-1)/2+i-1D.i(i-1)/2+j-16.若一个栈的输入序列为 1，2，3，n，输出序列的第一个元素是 i，则第 j 个输出元素是( )。（分数：2.00）A.i-j-1B.i-jC.j-i+1D.不确定的7.二维数组 Amn 按行序为主序存放在内存，每个数组元素占 1 个存储单元，则元素 aij的地址计算公式是( )。（分数：2.00）A.loc(aij)-loc(all)+(i-1)*m+(j-1)B.loc(aij)-loc(all)+(j-1)*m+(i-1)C.loc(aij)-loc(

4、all)+(i-1)*n+(j-1)D.loc(aij)-loc(all)+(j-1)*n+(i-1)8.循环队列存储在数组 A 0m中，则入队时的操作为( )。（分数：2.00）A.rear=rear+1B.rear=(rear+1)%(m 一 1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)9.设下三角矩阵 A 为：（分数：2.00）A.B.C.D.10.设有二维数组 A1:U1，1:U 2，已知数据元素 A1，1在位置 2，A2，3在位置 18，A3，2在位置28，则元素 A4，5在位置( )。（分数：2.00）A.46B.45C.48D.3011.设有一

5、个 10 阶的下三角矩阵 A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的 55 个存储单元中，每个数组元素占 1 个字节的存储空间，则 A54地址与 A00的地址之差为( )。（分数：2.00）A.10B.19C.28D.5512.假设按低下标优先存储整型数组 A-3:8，3:5，-4:0，0:7时，第一个元素的字节存储地址是 100，每个整数占 4 个字节，则 A0，4，-2，5的存储地址是( )。（分数：2.00）A.1783B.1784C.1985D.198413.将一个 A1100，1100的下三角矩阵按行优先存入一维数组 B15050中，A 中元素 A66，65，在 B

6、数组中的位置 K 为( )。（分数：2.00）A.4419B.2209C.4417D.231914.设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a1，1为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a8，5的地址为( )。（分数：2.00）A.13B.33C.18D.4015.数组 A05，06的每个元素占五个字节，将其按列优先次序存储在起始地址为 1000 的内存单元中，则元素 A5，5的地址是( )。（分数：2.00）A.1175B.1180C.1205D.121016.若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素

7、)依次存放于一维数组 B1(n(n+1)/2中，则在 B 中确定（分数：2.00）A.i(ij)的位置 k 的关系为( )。Ai*(i-1)/2+jBj*(j17.设 abcdef 以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为( )。（分数：2.00）A.fedcbaB.bca fedC.dcefbaD.cabdef18.有一个 100*90 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字节，则用三元组表示该矩阵时，所需的字节数是( )。（分数：2.00）A.60B.66C.18000D.3319.若用一个大小为 6 的数组来实现循环队列且当前 rear

8、和 front 的值分别为 0 和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为多少?( )（分数：2.00）A.1 和 5B.2 和 4C.4 和 2D.5 和 120.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时( )。（分数：2.00）A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头、队尾指针都可能要修改21.表达式 3*2(4+2*2-6*3)-5 求值过程中当扫描到 6 时，对象栈和算符栈为，其中为乘幂( )。（分数：2.00）A.3，2，4，1，1；*(+*-B.32，

9、8；*-C.3，2，4，2，2；*(-D.3，2，8；*(-22.一个栈的输入序列为 123n，若输出序列的第一个元素是 n，输出第 i(1=i=n)个元素是( )。（分数：2.00）A.不确定B.n-i+1C.iD.n-i23.输入序列为 ABC，可以变为 CBA 时，经过的栈操作为( )。（分数：2.00）A.push，pop，push，pop，push，popB.push，push，plJsh，pop，pop，popC.push，pLlsh，pop，pop，pllsh，popD.push，pop，push，push，pop，pop24.依次读入数据元素序列 a，b，C，d，e，f，g)进

10、栈，每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列?( )（分数：2.00）A.d，e，c，f，b，g，aB.f，e，g，d，a，C，bC.e，f，d，g，b，C，aD.c，d，e，b，f，a，g25.向一个栈顶指针为 hs 的链栈中插入一个 S 结点时，应执行( )。（分数：2.00）A.hsnext=s；B.snext=hs；hs=S；C.snext=hsnext；hs 一next=s；D.snext=hs；hs=hsnext；26.有六个元素 6，5，4，3，2，1 的顺序进栈，下列( )不是合法的出栈序列。（分数：2.00）A.5 4

11、 3 6 1 2B.4 5 3 1 2 6C.3 4 6 5 2 1D.2 3 4 1 5 6二、综合应用题(总题数：4，分数：40.00)27.设有两个栈 S1，S 2都采用顺序栈方式，并且共享一个存储区Omaxsizel，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计 S1，S 2有关入栈和出栈的操作算法。（分数：10.00）_28.设从键盘输入一整数的序列：a 1，a 2，a 3，a n，试编写算法实现：用栈结构存储输入的整数，当ai-1 时，将 ai进栈；当 ai=-1 时，输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。（分数：10.00

12、）_29.设表达式以字符形式已存入数组 En中，#为表达式的结束符，试写出判断表达式中括号(和)是否配对的 C 语言描述算法：EXYX(E)；(注：算法中可调用栈操作的基本算法。)（分数：10.00）_30.设矩阵 A 为（分数：10.00）_栈、队列和数组答案解析(总分：92.00，做题时间：90 分钟)一、单项选择题(总题数：26，分数：52.00)1.二维数组 A 的每个元素是由 6 个字符组成的串，其行下标 i=0，1，8，列下标 j=1，2，10。若A 按行先存储，元素 A8，5的起始地址与当 A 按列先存储时的元素( )的起始地址相同。设每个字符占一个字节。（分数：2.00）A.A

13、8，5B.A3，10 C.A 5，8D.A0，9解析：二维数组 A0:8，1:10，设起始地址为 0，数组元素 Ai，j按行存储公式为：Loc(Ai，j)=L1+(i-1)U2d+(j-1)d，数组元素 Ai，j按列存储公式为：Loc(Ai，j)=L 1+(j-1)U2d+(i-1)d，可得 i=3，j=10。2.数组 A110，26，28以行优先的顺序存储，设第一个元素的首地址是 100，每个元素占 3 个存储长度的存储空间，则元素 A5，0，7的存储地址为( )。（分数：2.00）A.913 B.910C.915D.923解析：见 7 解析。3.设有一个二维数组 Amn，假设 A00存放位

14、置在 644，A22存放位置在 676，每个元素占一个空间，问 A33存放在( )位置。（分数：2.00）A.688B.678C.692 D.696解析：二维数组 A 可以看成由 U1个一维数组组成，每个一维数组有 U2个元素。如下图：*可得，数组元素 Ai，j的地址为：Loc(Ai，j)=L1+iU2d+jd，解的 n=15，结果为 692。4.假设以行序为主序存储二维数组 Aarray1100，1100，设每个数据元素占 2 个存储单元，基地址为 10，则 LOC5，5=( )。（分数：2.00）A.808B.818 C.1010D.1020解析：公式：Loc(A ij)=10(基地址)+

15、(5-1)*100+(5-1)*2=818。5.设 A 是 n*n 的对称矩阵，将 A 的对角线及对角线上方的元素以列为主的次序存放在一维数组B1n(n+1)/2中，则上述任一元素 aij(1i，jn，且 ij)在 B 中的位置为( )。（分数：2.00）A.i(i-1)/2+j B.j(j-1)/2+iC.j(j-1)/2+i-1D.i(i-1)/2+j-1解析：解析同 16。6.若一个栈的输入序列为 1，2，3，n，输出序列的第一个元素是 i，则第 j 个输出元素是( )。（分数：2.00）A.i-j-1B.i-jC.j-i+1D.不确定的 解析：不知道 i，j 的大小关系，所以无法确定。

16、7.二维数组 Amn 按行序为主序存放在内存，每个数组元素占 1 个存储单元，则元素 aij的地址计算公式是( )。（分数：2.00）A.loc(aij)-loc(all)+(i-1)*m+(j-1) B.loc(aij)-loc(all)+(j-1)*m+(i-1)C.loc(aij)-loc(all)+(i-1)*n+(j-1)D.loc(aij)-loc(all)+(j-1)*n+(i-1)解析：二维数组就是平常所说的矩阵，也可以看成是数据元素是一维数组的一位数组。由于计算机内部存储器的地址是一维线性排列的，故在存储数据时，必须将二维数组转换为计算机的内部存储形式才可以。一般有两种存储方

17、式：以行为主的存储方式(rowmajor)和以列为主的存储方式(columnmajor)。设二维数组 A1:U1，1:U 2，该数组有(U 1-1)+1=U1行，有(U 1-1)+1=U1列。设每个元素占 d 个空间，数组的起始地址为 L1。以行为主(rowmajor)：也称行优先存储。其特点为：以每一行为单位，一行一行地放入内存，如 C 语言、PASCAL 语言等都是如此处理二维数组的。以列为主(columnmajor)：也称列优先存储。其特点为：以每一列为单位，一列一列地放入内存，如Fortran 语言就是如此处理二维数组的。二维数组 A 可以看成由 U2个一维数组组成，每个一维数组有 U

18、1个元素。同 1)类似，有：*第 j 列数据元素的起始地址为：(j-1)U 1d+L1*数组元素 Ai，j的地址为：Loc(A i，j)=L 1+(j-1)U1d-6(i-1)d重要说明：二维数组 Am*n 的含义是：该数组有 m 行(0m-1 第一维)，有 n 列(0n-1，第二维)，占用m*n 个存储空间。假设每个数据元素占用 L 个存储单元(可理解为字节)，则二维数组 A 中任意一个元素aij的存储位置为：行优先：LOC(i，j)=LOC(0，0)+(ni+j)L列优先： LOC(i，j)=LOC(0，0)+(mj+i)L二维数组是一种随机存储结构，因为存取数组中任一元素的时间都相等(单

19、链表则不是，因为需要顺链访问，访问时间同数据元素的存储位置有关)。8.循环队列存储在数组 A 0m中，则入队时的操作为( )。（分数：2.00）A.rear=rear+1B.rear=(rear+1)%(m 一 1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1) 解析：循环队列的重要操作：初始化：(MAXSIZE 为最大队列长度)Qbase=(QElemType*)malloc(MAXSIZE*sizeof(QElemType)；Qfront=Qrear=0；返回 Q 中元素的个数return(Q.rearQ.front+MAXSIZE)%MAXSIZE；插入元素

20、(队尾插入)if(Q.rear+1)%MAXSIZE=Q.front)return ERROR；队满判断Q.baseQ.rear=e；Q.rear=(Q.rear+1)%MAXSIZE；修改 Q.rear 的方法Q.rear 总是指向下一个可以插入新元素的位置。删除元素(从队首删除)If(Q.front=Q.rear)return ERROR；队空的判断e=Q.base Q.front；Q.front=(Q.front+1)%MAXSIZE；此题可知，MAXSIZE=m+1。9.设下三角矩阵 A 为：（分数：2.00）A. B.C.D.解析：如何将 aij保存在数组 B 中，保存在哪个位置?也

21、就是说，设 k 为 aij保存在 B 中时的下标，那么 k和 i、j 有什么关系?Ai，j在 B 中的位置=(A 中前 i-1 行非 0 元素的个数)+(A 中第 i 行、第 j 列之前非 0 元素的个数，包括第 j 列)=(1+2+3+(i-1)+j=i(i-1)/2+j则 Ai，j存放在 B 中的元素下标 ki(i 一 1)/2+j(因为 B 的数据元素从 1 开始)。例如：A3，3保存在 B 中的位置为k=3(3=1)/2+3=6，即 A3，3保存在数据元素 B6中。10.设有二维数组 A1:U1，1:U 2，已知数据元素 A1，1在位置 2，A2，3在位置 18，A3，2在位置28，则

22、元素 A4，5在位置( )。（分数：2.00）A.46 B.45C.48D.30解析：题目中没有给出该数组是行优先存储还是列优先存储，因此需要首先判断数组的存储方式。因为 Loc(A3，2)Loc(A2，3)，所以数组一定是按行存储的。因为 A1，1是起始位置，则有 L1-2。利用已知条件，根据计算地址的公式有：Loc(A2，3)=L 1+(2-1)U2d+(3-1)d-18，即2+U2d+2d=18 (方程 1)Loc(A3，2)=L 1+(3-1)U2d+(2-1)d-28，即2+2U2d+d-28 (方程 2)由以上两方程联立，得方程组，解得：U 2=6，d=2。由此得到数组 A 的列数

23、为 6，每个元素占 2 个空间。则：Loc(A4，5)=L 1+(4-1)U2d+(5-1)d-2+362+42=46可以看出，该题目中仅仅求得了列数 U2和每个数据元素所占的空间数就求得了某个数据元素的地址，而行数 U1并没有求得。这再次说明，在行优先为主的存储方式中，列数是不可或缺的。11.设有一个 10 阶的下三角矩阵 A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的 55 个存储单元中，每个数组元素占 1 个字节的存储空间，则 A54地址与 A00的地址之差为( )。（分数：2.00）A.10B.19C.28 D.55解析：从此题分析可以得出，该题以列为主储存：*Ai，j在

24、B 中的位置=(A 中前 j-1 列元素的个数)+(第 j 列第 i 行之前的元素个数，包括第 i 行)-n+(n-1)+(n-(j-1)+1)+(i-j+1)=n(j-1)-j(j-1)/2+i则 Ai，j存放在 B 中的元素下标 k=n(j-1)-j(j-1)/2+i-1。可得 A54地址为 29，A00地址为 1，所以相差 28。12.假设按低下标优先存储整型数组 A-3:8，3:5，-4:0，0:7时，第一个元素的字节存储地址是 100，每个整数占 4 个字节，则 A0，4，-2，5的存储地址是( )。（分数：2.00）A.1783B.1784 C.1985D.1984解析：13.将一

25、个 A1100，1100的下三角矩阵按行优先存入一维数组 B15050中，A 中元素 A66，65，在 B 数组中的位置 K 为( )。（分数：2.00）A.4419B.2209 C.4417D.2319解析：k=i(i-1)/2+j-1。14.设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a1，1为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a8，5的地址为( )。（分数：2.00）A.13B.33 C.18D.40解析：n 阶对称矩阵 A 中的元素满足下述条件：a ij=aji(1-i，j-n)。对称矩阵中的每一对数据元素可以共用一个存储空间，因此可以将

26、n2个元素压缩存储到 n(n+1)/2 个元的空间中，即可以一维数组保存。假设用一维数组 sn(n+1)/2作为对称矩阵 A 的存储结构，则 sk和矩阵元素 aij的下标 i、j 的对应关系为：当 i-j 时，k=i(i-1)/2+j；当 ij 时，k=j(j-1)/2+i；15.数组 A05，06的每个元素占五个字节，将其按列优先次序存储在起始地址为 1000 的内存单元中，则元素 A5，5的地址是( )。（分数：2.00）A.1175 B.1180C.1205D.1210解析：LOC(i，j)-LOC(0，0)+(mj+i)L。16.若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的

27、元素(包括主对角线上所有元素)依次存放于一维数组 B1(n(n+1)/2中，则在 B 中确定（分数：2.00）A.i(ij)的位置 k 的关系为( )。Ai*(i-1)/2+jBj*(j解析：n 阶对称矩阵中的元素满足下述条件：a ij=aji，(1=i，j=n)。对称矩阵中的每一对数据元素可以共用一个存储空间，因此可以将 n2个元素压缩存储到 n(n+1)/2 个元的空间中，即可以一维数组保存。假设用一维数组 Bn(n+1)/2作为对称矩阵 A 的存储结构，则 Bk和矩阵元素 aij的下标 i、j 的对应关系为：当 i-j 时，k=i(i-1)/2+i；当 ij 时，k=j(j-1)/2+i

28、；(以上公式是针对 aij和 aji保存在同一个单元中的情况)因为存储下三角元素，所以 ij，k=j(j-1)/2+i。17.设 abcdef 以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为( )。（分数：2.00）A.fedcbaB.bca fedC.dcefbaD.cabdef 解析：见 2 解析。18.有一个 100*90 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字节，则用三元组表示该矩阵时，所需的字节数是( )。（分数：2.00）A.60B.66 C.18000D.33解析：稀疏矩阵可采用压缩存储，仅存储其中的非零元素。存储时，除了记下非零元素的

29、值外，还要记录其行标 i 和列标 j，即用(i，j，aij)三元组表示。由此可得出如下结论：稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。三元组结构：typedef structint i，j；行标和列标ElemType e；元素值 Triple；typedef structTriple dataMAXSIZE+1；从 Data1开始使用，Data0不用int mu，nu，tu；矩阵的行数、列数及非零元素个数TSMatrix；19.若用一个大小为 6 的数组来实现循环队列且当前 rear 和 front 的值分别为 0 和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 f

30、ront 的值分别为多少?( )（分数：2.00）A.1 和 5B.2 和 4 C.4 和 2D.5 和 1解析：初始化创建空队列时，令 front=rear=0，每当插入新的队列尾元素时，rear 增 1，每当删除一个队列首元素时，front 增 1。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。初始情况如下图所示：*经过二次删除和一次插入后：*20.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时( )。（分数：2.00）A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头、队尾指针

31、都可能要修改 解析：如果当前队列中仅有一个元素，则删除它时队头、队尾指针都需要修改。21.表达式 3*2(4+2*2-6*3)-5 求值过程中当扫描到 6 时，对象栈和算符栈为，其中为乘幂( )。（分数：2.00）A.3，2，4，1，1；*(+*-B.32，8；*-C.3，2，4，2，2；*(-D.3，2，8；*(- 解析：经过入栈后：*开始出栈，遇到 6 之前：*22.一个栈的输入序列为 123n，若输出序列的第一个元素是 n，输出第 i(1=i=n)个元素是( )。（分数：2.00）A.不确定B.n-i+1 C.iD.n-i解析：按照堆栈“后进先出”的特点，n 是最后一个入栈的，即 n 为

32、栈顶元素。若输出的第一个元素为n，则其余所有元素必定仍在堆栈中。第一个输出元素为 n，则第二个输出元素为 n-1，第 i 个输出元素为n-i+1，最后一个(第 n 个)输出元素为 1。23.输入序列为 ABC，可以变为 CBA 时，经过的栈操作为( )。（分数：2.00）A.push，pop，push，pop，push，popB.push，push，plJsh，pop，pop，pop C.push，pLlsh，pop，pop，pllsh，popD.push，pop，push，push，pop，pop解析：ABC 经过 push，push，pLtsh 操作后，从栈顶到栈低元素为 CBA，经过 p

33、op，pop，pop 出栈操作后，输出为 CBA。24.依次读入数据元素序列 a，b，C，d，e，f，g)进栈，每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列?( )（分数：2.00）A.d，e，c，f，b，g，a B.f，e，g，d，a，C，bC.e，f，d，g，b，C，aD.c，d，e，b，f，a，g解析：见 2 解析。25.向一个栈顶指针为 hs 的链栈中插入一个 S 结点时，应执行( )。（分数：2.00）A.hsnext=s；B.snext=hs；hs=S； C.snext=hsnext；hs 一next=s；D.snext=hs；

34、hs=hsnext；解析：由于栈的插入、删除操作只能在一端进行，而对于单链表来说，在首端插入、删除结点要比在尾端相对容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。栈的链式存储结构在 C 语言中可用下列类型定义实现：typedef struct node 链栈的结点结构StackEntry item； 栈的数据元素类型struct node*next； 指向后继结点的指针NODE；typedef struct stackNODE*top；STACK；下面给出链栈各项基本操作的算法。初始化栈 Svoid InitStack(STACK*S) Stop=NULL；入栈

35、void Push(STACK*S，StackEntry item) p=(NODE*)malloc(sizeof(NODE)；if(!p)exit(OVERFLOW)；elsepitem=item；p 一next=stop；stop=p；)出栈void Pop(STACK*S，StackEntry“item) if(StackEmpty(*S)exit(“Stack is empty”)；else*item=Stopitem；pstop；stop=pnext；free(p)；获取栈顶元素内容void GetTop(STACK S，StackEntry*item) if(StackEmpty(

36、S)exit(“Stack is empty“)；else*item=S.topitem；判断栈 S 是否空int StackEmpty(STACK S) if(S.top=NULL)return TRUE；else FALSE；26.有六个元素 6，5，4，3，2，1 的顺序进栈，下列( )不是合法的出栈序列。（分数：2.00）A.5 4 3 6 1 2B.4 5 3 1 2 6C.3 4 6 5 2 1 D.2 3 4 1 5 6解析：考查堆栈“后进先出”的特点。对选项 A 来说，第一个出栈元素是 5，因为 6 先于 5 进栈，所以必定在 5 之后出栈，其余的元素出栈顺序任意；对选项 B

37、来说，第一个出栈元素是 4，所以 5 和 6 两个元素必定在 4 之后依次出栈；对选项 C 来说，第一个出栈元素是 3，则必有 4、5、6 三个元素依次在 3 后面出栈，但是选项 C 中的顺序是 3、4、6、5，这是不符合要求的；对选项 D 来说，第一个出栈元素是 2，则必有 3、4、5、6 依次在 2 后面出栈，D 也是符合要求的，因此答案选 C。总结：这种问题如何解决呢?我们看第一个出栈元素，然后确定先于第一个元素进栈的所有其他元素，这些元素一定在第一个出栈元素之后顺序出栈。如果第一个元素仍然无法判断出来，可继续看后面的元素，依次类推。举例如下：假设第一个出栈的元素是 1，则出栈顺序一定是

38、 6、5、4、3、2、1，没有其他情况。假设第一个出栈的元素是 2，则出栈顺序可能有：213456；231456；234156； 234516； 234561(可首先把 23456 写出，然后可将 1 插到 2 之后的任意位置)假设第一个出栈的元素是 3，则出栈顺序可能有：3 12 456；34 12 56； 345 12 6； 3456 12但是 314526 是不能的。因为 3 出栈之后，当前栈中仍有 4、5、6 三个元素，如果下一个是 1 出栈，则肯定先让 2 进栈，再让 1 进栈，然后 1 出栈，此时栈顶就变成 2 了，则下一个出栈的只能是 2，而不能是4。二、综合应用题(总题数：4，

39、分数：40.00)27.设有两个栈 S1，S 2都采用顺序栈方式，并且共享一个存储区Omaxsizel，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计 S1，S 2有关入栈和出栈的操作算法。（分数：10.00）_正确答案：(两栈共享向量空间，将两栈栈底设在向量两端，初始时，s 1栈顶指针为-1，s 2栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。#define maxsize 两栈共享顺序存储空间所能达到的最多元素数#define elemtp int 假设元素类型为整型typedef structelemtp stac

40、k-maxsize； 栈空间int top2； top 为两个栈顶指针stk；stk s； s 是如上定义的结构类型变量，为全局变量(1)入栈操作：int push(int i，int x)入栈操作。i 为栈号，i=0 表示左边的栈 s1，i=1 表示右边的栈 s2，x 是入栈元素。入栈成功返回 1，否则返回 0。if(i0 i1)printf(“栈号输入不对”)；exit(0)；)if(s.top1-s.top0=1)printf(“栈已满/n”)；return(0)；)switch(i)case 0:sstack+s.top0=x；return(1)；break；case 1:s.stac

41、ks.top1=x；return(1)；push(2)退栈操作elemtp pop(int i)退栈算法。i 代表栈号，i=0 时为 s1栈，i=1 时为 S：栈。退栈成功返回退栈元素，否则返回-1。if(i0 i1)printf(“栈号输入错误/n”)；exit(0)；)switch(i)case 0：if(s.top 0=-1)printf(“栈空/n”)；return(-1)；)else return(Sstack Estop0)；case 1：if(s.top1=maxsizeprintf(“栈空/n”)；retturn(-1)；)else return(s.stacks.top 1+

42、)；请注意算法中两栈入栈和退栈时的栈顶指针的计算。s 1栈是通常意义下的栈，而 s2栈入栈操作时，其栈顶指针左移(减 1)，退栈时，其栈顶指针右移(加 1)。)解析：28.设从键盘输入一整数的序列：a 1，a 2，a 3，a n，试编写算法实现：用栈结构存储输入的整数，当ai-1 时，将 ai进栈；当 ai=-1 时，输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。（分数：10.00）_正确答案：(#define maxsize 栈空间容量void InOutS(int s maxsize)s 是元素为整数的栈，本算法进行入栈和退栈操作int top=0； top 为栈顶指针，

43、定义 top=0 时为栈空for(i=1；i=n；i+) n 个整数序列作处理scan(“%d”，&x)； 从键盘读入整数序列if(x!=-1) 读入的整数不等于-1 时入栈if(top=maxsize-1) printf(“栈满/n”)；exit(0)；else s+top=x；x 入栈else 读入的整数等于-1 时退栈(if(top=0)print(“栈空/n”)；exit(0)；)else print(“出栈元素是%d/n”，stop)；)解析：29.设表达式以字符形式已存入数组 En中，#为表达式的结束符，试写出判断表达式中括号(和)是否配对的 C 语言描述算法：EXYX(E)；(注

44、：算法中可调用栈操作的基本算法。)（分数：10.00）_正确答案：(判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配int EXYX(char E，int n)/E是有 n 字符的字符数组，存放字符串表达式，以#结束。本算法判断表达式中圆括号是否匹配char s E30； s 是一维数组，容量足够大，用作存放括号的栈int top=0； top 用作栈顶指针S Etop=#； #先入栈，用于和表达式结束符号#匹配int i=0； 字符数组 E 的工作指

45、针while(E l!=#) 逐字符处理字符表达式的数组switch(E i)caSe(：s+top=(；i+；break；case)：if(stop=(top；i+；break；)elseprintf(“括号不配对”)；exit(0)；case#：if(s Etop=#)printf(“括号配对n”)；return(1)；elseprintf(“括号不配对/n”)；return(0)；)括号不配对default：i+； 读入其他字符，不作处理本题是用栈判断括号匹配的特例：只检查圆括号的配对。一般情况下是检查花括号(，)、方括号(，)和圆括号(，)的配对问题。编写算法中如遇左括号(，或()就压入栈中，如遇右括号()，或)，则与栈顶元素比较，如是与其配对的括号(左花括号、左方括号或左圆括号)，则弹出栈顶元素；否则，就结论括号不配对。在读入表达式结束符#时，栈中若只剩#，表示括号全部配对成功；否则表示括号不匹配。另外，由于本题只是检查括号是否匹配，故对从表达式中读