1、计算机学科专业基础综合数据结构-栈、队列和数组(一)及答案解析(总分：92.00，做题时间：90 分钟)一、单项选择题(总题数：26，分数：52.00)1.一个栈的输入序列为 123n，若输出序列的第一个元素是 n，输出第 i(1=i=n)个元素是 _ 。（分数：2.00）A.不确定B.n-i+1CiD.n-i2.有六个元素 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 1D.2 3 4 1 5 63.若一个栈的输入序列为 1，2，3，n，输出序列的第一个元素是 i，则第 j个输出
2、元素是 _ 。（分数：2.00）A.i-j-1B.i-jC.j-i+1D.不确定的4.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时 _ 。（分数：2.00）A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头、队尾指针都可能要修改5.假设以行序为主序存储二维数组 Aarray1100，1100，设每个数据元素占 2个存储单元，基地址为 10，则 LOC5，5= _ 。（分数：2.00）A.808B.818C.1010D.10206.设有一个 10阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a1，1为第一元素，其存储
3、地址为 1，每个元素占一个地址空间，则 a8，5的地址为 _ 。（分数：2.00）A.13B.33C.18D.407.假设按低下标优先存储整型数组 A-3:8，3:5，-4:0，0:7时，第一个元素的字节存储地址是 100，每个整数占 4个字节，则 A0，4，-2，5的存储地址是( )。（分数：2.00）A.1783B.1784C.1985D.19848.数组 A05，06的每个元素占五个字节，将其按列优先次序存储在起始地址为 1000的内存单元中，则元素 A5，5的地址是 _ 。（分数：2.00）A.1175B.1180C.1205D.12109.设有二维数组 A1:U 1 ，1:U 2 ，
4、已知数据元素 A1，1在位置 2，A2，3在位置 18，A3，2在位置 28，则元素 A4，5在位置 _ 。（分数：2.00）A.46B.45C.48D.3010.将一个 A1100，1100的下三角矩阵按行优先存入一维数组 B15050中，A 中元素 A66，65，在 B数组中的位置 K为 _ 。（分数：2.00）A.4419B.2209C.4417D.231911.设 abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为( )。（分数：2.00）A.fedcbaB.bca fedC.dcefbaD.cabdef12.二维数组 A的每个元素是由 6个字符组成的串，
5、其行下标 i=0，1，8，列下标 j=1，2，10。若 A按行先存储，元素 A8，5的起始地址与当 A按列先存储时的元素 _ 的起始地址相同。设每个字符占一个字节。（分数：2.00）A.A8，5B.A3，10C.A 5，8D.A0，913.输入序列为 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，pop14.若用一个大小为 6的数组来实现循环队列且当前
6、 rear和 front的值分别为 0和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front的值分别为多少? _（分数：2.00）A.1和 5B.2和 4C.4和 2D.5和 115.表达式 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；*(-16.若对 n阶对称矩阵 A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组 B1(n(n+1)/2中，则在 B中确定 ai(ij)的位置 k
7、的关系为 _ 。（分数：2.00）A.i*(i-1)/2+jB.j*(j-1)/2+iC.i*(i+1)/2+jD.j*(j+1)/2+i17.设有一个 10阶的下三角矩阵 A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的 55个存储单元中，每个数组元素占 1个字节的存储空间，则 A54地址与 A00的地址之差为 _ 。（分数：2.00）A.10B.19C.28D.5518.设 A是 n*n的对称矩阵，将 A的对角线及对角线上方的元素以列为主的次序存放在一维数组B1n(n+1)/2中，则上述任一元素 a ij (1i，jn，且 ij)在 B中的位置为 _ 。（分数：2.00）A.i(
8、i-1)/2+jB.j(j-1)/2+iC.j(j-1)/2+i-1D.i(i-1)/2+j-119.设下三角矩阵 A为： （分数：2.00）A.i(i-1)/2+jB.j(j-1)/2+iC.j(j-1)/2+i-1D.i(i-1)/2+j-120.设有一个二维数组 Amn，假设 A00存放位置在 644，A22存放位置在 676，每个元素占一个空间，问 A33存放在 _ 位置。（分数：2.00）A.688B.678C.692D.69621.有一个 100*90的稀疏矩阵，非 0元素有 10个，设每个整型数占 2字节，则用三元组表示该矩阵时，所需的字节数是 _ 。（分数：2.00）A.60B
9、.66C.18000D.3322.循环队列存储在数组 A 0m中，则入队时的操作为 _ 。（分数：2.00）A.rear=rear+1B.rear=(rear+1)%(m一 1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)23.依次读入数据元素序列a，b，C，d，e，f，g)进栈，每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列? _ Ad，e，c，f，b，g，a Bf，e，g，d，a，C，b Ce，f，d，g，b，C，aDc，d，e，b，f，a，g （分数：2.00）A.B.C.D.24.二维数组 Amn按行序
10、为主序存放在内存，每个数组元素占 1个存储单元，则元素 a ij 的地址计算公式是( )。（分数：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)25.向一个栈顶指针为 hs的链栈中插入一个 S结点时，应执行 _ 。（分数：2.00）A.hsnext=s；B.snext=hs；hs=S；C.snext=hsnext；hs 一next=s；D.snext=hs；hs=hsn
11、ext；26.数组 A110，26，28以行优先的顺序存储，设第一个元素的首地址是 100，每个元素占 3个存储长度的存储空间，则元素 A5，0，7的存储地址为 _ 。（分数：2.00）A.913B.910C.915D.923二、综合应用题(总题数：4，分数：40.00)27.设有两个栈 S 1 ，S 2 都采用顺序栈方式，并且共享一个存储区Omaxsizel，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计 S 1 ，S 2 有关入栈和出栈的操作算法。（分数：10.00）_28.设从键盘输入一整数的序列：a 1 ，a 2 ，a 3 ，a n ，试编写算法实现：用栈
12、结构存储输入的整数，当 a i -1 时，将 a i 进栈；当 a i =-1时，输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。 （分数：10.00）_29.设表达式以字符形式已存入数组 En中，#为表达式的结束符，试写出判断表达式中括号(和)是否配对的 C语言描述算法：EXYX(E)；(注：算法中可调用栈操作的基本算法。) （分数：10.00）_30.设矩阵 A为 （分数：10.00）_计算机学科专业基础综合数据结构-栈、队列和数组(一)答案解析(总分：92.00，做题时间：90 分钟)一、单项选择题(总题数：26，分数：52.00)1.一个栈的输入序列为 123n，若输出
13、序列的第一个元素是 n，输出第 i(1=i=n)个元素是 _ 。（分数：2.00）A.不确定B.n-i+1 CiD.n-i解析：按照堆栈“后进先出”的特点，n 是最后一个入栈的，即 n为栈顶元素。若输出的第一个元素为n，则其余所有元素必定仍在堆栈中。第一个输出元素为 n，则第二个输出元素为 n-1，第 i个输出元素为n-i+1，最后一个(第 n个)输出元素为 1。2.有六个元素 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解析：考查堆栈“后进先出”的
14、特点。对选项 A来说，第一个出栈元素是 5，因为 6先于 5进栈，所以必定在 5之后出栈，其余的元素出栈顺序任意；对选项 B来说，第一个出栈元素是 4，所以 5和 6两个元素必定在 4之后依次出栈；对选项 C来说，第一个出栈元素是 3，则必有 4、5、6 三个元素依次在 3后面出栈，但是选项 C中的顺序是 3、4、6、5，这是不符合要求的；对选项 D来说，第一个出栈元素是 2，则必有 3、4、5、6 依次在 2后面出栈，D 也是符合要求的，因此答案选 C。 总结：这种问题如何解决呢?我们看第一个出栈元素，然后确定先于第一个元素进栈的所有其他元素，这些元素一定在第一个出栈元素之后顺序出栈。如果第
15、一个元素仍然无法判断出来，可继续看后面的元素，依次类推。举例如下： 假设第一个出栈的元素是 1，则出栈顺序一定是 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进栈
16、，然后 1出栈，此时栈顶就变成 2了，则下一个出栈的只能是 2，而不能是4。3.若一个栈的输入序列为 1，2，3，n，输出序列的第一个元素是 i，则第 j个输出元素是 _ 。（分数：2.00）A.i-j-1B.i-jC.j-i+1D.不确定的 解析：不知道 i，j 的大小关系，所以无法确定。4.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时 _ 。（分数：2.00）A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头、队尾指针都可能要修改 解析：如果当前队列中仅有一个元素，则删除它时队头、队尾指针都需要修改。5.假设以行序为
17、主序存储二维数组 Aarray1100，1100，设每个数据元素占 2个存储单元，基地址为 10，则 LOC5，5= _ 。（分数：2.00）A.808B.818 C.1010D.1020解析：公式：Loc(A ij )=10(基地址)+(5-1)*100+(5-1)*2=818。6.设有一个 10阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a1，1为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a8，5的地址为 _ 。（分数：2.00）A.13B.33 C.18D.40解析：n 阶对称矩阵 A中的元素满足下述条件：a ij =a ji (1-i，j-n)。对称矩阵中的每一对
18、数据元素可以共用一个存储空间，因此可以将 n 2 个元素压缩存储到 n(n+1)/2个元的空间中，即可以一维数组保存。 假设用一维数组 sn(n+1)/2作为对称矩阵 A的存储结构，则 sk和矩阵元素 a ij 的下标 i、j 的对应关系为： 当 i-j 时，k=i(i-1)/2+j； 当 ij 时，k=j(j-1)/2+i；7.假设按低下标优先存储整型数组 A-3:8，3:5，-4:0，0:7时，第一个元素的字节存储地址是 100，每个整数占 4个字节，则 A0，4，-2，5的存储地址是( )。（分数：2.00）A.1783B.1784 C.1985D.1984解析：8.数组 A05，06的
19、每个元素占五个字节，将其按列优先次序存储在起始地址为 1000的内存单元中，则元素 A5，5的地址是 _ 。（分数：2.00）A.1175 B.1180C.1205D.1210解析：LOC(i，j)-LOC(0，0)+(mj+i)L。9.设有二维数组 A1:U 1 ，1:U 2 ，已知数据元素 A1，1在位置 2，A2，3在位置 18，A3，2在位置 28，则元素 A4，5在位置 _ 。（分数：2.00）A.46 B.45C.48D.30解析：题目中没有给出该数组是行优先存储还是列优先存储，因此需要首先判断数组的存储方式。 因为 Loc(A3，2)Loc(A2，3)，所以数组一定是按行存储的。
20、 因为 A1，1是起始位置，则有 L 1 -2。利用已知条件，根据计算地址的公式有： Loc(A2，3)=L 1 +(2-1)U 2 d+(3-1)d-18，即 2+U 2 d+2d=18 (方程 1) Loc(A3，2)=L 1 +(3-1)U 2 d+(2-1)d-28，即 2+2U 2 d+d-28 (方程 2) 由以上两方程联立，得方程组，解得：U 2 =6，d=2。由此得到数组 A的列数为 6，每个元素占 2个空间。则： Loc(A4，5)=L 1 +(4-1)U 2 d+(5-1)d -2+362+42=46 可以看出，该题目中仅仅求得了列数 U 2 和每个数据元素所占的空间数就求
21、得了某个数据元素的地址，而行数 U 1 并没有求得。这再次说明，在行优先为主的存储方式中，列数是不可或缺的。10.将一个 A1100，1100的下三角矩阵按行优先存入一维数组 B15050中，A 中元素 A66，65，在 B数组中的位置 K为 _ 。（分数：2.00）A.4419B.2209 C.4417D.2319解析：k=i(i-1)/2+j-1。11.设 abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为( )。（分数：2.00）A.fedcbaB.bca fedC.dcefbaD.cabdef 解析：见 2解析。12.二维数组 A的每个元素是由 6个字符组
22、成的串，其行下标 i=0，1，8，列下标 j=1，2，10。若 A按行先存储，元素 A8，5的起始地址与当 A按列先存储时的元素 _ 的起始地址相同。设每个字符占一个字节。（分数：2.00）A.A8，5B.A3，10 C.A 5，8D.A0，9解析：二维数组 A0:8，1:10，设起始地址为 0，数组元素 Ai，j按行存储公式为：Loc(Ai，j)=L 1 +(i-1)U 2 d+(j-1)d，数组元素 Ai，j按列存储公式为：Loc(Ai，j)=L 1 +(j-1)U 2 d+(i-1)d，可得 i=3，j=10。13.输入序列为 ABC，可以变为 CBA时，经过的栈操作为 _ 。（分数：2
23、.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，经过 pop，pop，pop 出栈操作后，输出为 CBA。14.若用一个大小为 6的数组来实现循环队列且当前 rear和 front的值分别为 0和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front的值分别为多少? _（分数：2.00）A.1和 5B
24、.2和 4 C.4和 2D.5和 1解析：初始化创建空队列时，令 front=rear=0，每当插入新的队列尾元素时，rear 增 1，每当删除一个队列首元素时，front 增 1。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。初始情况如下图所示： 经过二次删除和一次插入后： 15.表达式 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之前： 16
25、.若对 n阶对称矩阵 A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组 B1(n(n+1)/2中，则在 B中确定 ai(ij)的位置 k的关系为 _ 。（分数：2.00）A.i*(i-1)/2+jB.j*(j-1)/2+i C.i*(i+1)/2+jD.j*(j+1)/2+i解析：n 阶对称矩阵中的元素满足下述条件：a ij =a ji ，(1=i，j=n)。对称矩阵中的每一对数据元素可以共用一个存储空间，因此可以将 n 2 个元素压缩存储到 n(n+1)/2个元的空间中，即可以一维数组保存。 假设用一维数组 Bn(n+1)/2作为对称矩阵 A的存储结构，则 B
26、k和矩阵元素 a ij 的下标 i、j 的对应关系为： 当 i-j 时，k=i(i-1)/2+i； 当 ij 时，k=j(j-1)/2+i； (以上公式是针对 a ij 和 a ji 保存在同一个单元中的情况) 因为存储下三角元素，所以 ij，k=j(j-1)/2+i。17.设有一个 10阶的下三角矩阵 A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的 55个存储单元中，每个数组元素占 1个字节的存储空间，则 A54地址与 A00的地址之差为 _ 。（分数：2.00）A.10B.19C.28 D.55解析：从此题分析可以得出，该题以列为主储存： 18.设 A是 n*n的对称矩阵，将
27、A的对角线及对角线上方的元素以列为主的次序存放在一维数组B1n(n+1)/2中，则上述任一元素 a ij (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。19.设下三角矩阵 A为： （分数：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解析：如何将 a ij 保存在数组 B中，保存在哪个位置?也就是说，设 k为 a ij 保存在 B中时的下标，那么 k和 i、j 有什么关系? Ai，
28、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中。20.设有一个二维数组 Amn，假设 A00存放位置在 644，A22存放位置在 676，每个元素占一个空间，问 A33存放在 _ 位置。（分数：2.00）A.688B.678C.692 D.696解析：二维数组 A可以看成
29、由 U 1 个一维数组组成，每个一维数组有 U 2 个元素。如下图： 21.有一个 100*90的稀疏矩阵，非 0元素有 10个，设每个整型数占 2字节，则用三元组表示该矩阵时，所需的字节数是 _ 。（分数：2.00）A.60B.66 C.18000D.33解析：稀疏矩阵可采用压缩存储，仅存储其中的非零元素。存储时，除了记下非零元素的值外，还要记录其行标 i和列标 j，即用(i，j，aij)三元组表示。由此可得出如下结论：稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。 三元组结构： typedef struct int i，j；行标和列标 ElemType e；元素值 Triple；
30、typedef struct Triple dataMAXSIZE+1；从 Data1开始使用，Data0不用 int mu，nu，tu；矩阵的行数、列数及非零元素个数 TSMatrix；22.循环队列存储在数组 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)； Qfro
31、nt=Qrear=0； 返回 Q中元素的个数 return(Q.rearQ.front+MAXSIZE)%MAXSIZE； 插入元素(队尾插入) 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； 此题可
32、知，MAXSIZE=m+1。23.依次读入数据元素序列a，b，C，d，e，f，g)进栈，每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列? _ Ad，e，c，f，b，g，a Bf，e，g，d，a，C，b Ce，f，d，g，b，C，aDc，d，e，b，f，a，g （分数：2.00）A. B.C.D.解析：见 2解析。24.二维数组 Amn按行序为主序存放在内存，每个数组元素占 1个存储单元，则元素 a ij 的地址计算公式是( )。（分数：2.00）A.loc(aij)-loc(all)+(i-1)*m+(j-1) B.loc(aij)-loc(
33、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)解析：二维数组就是平常所说的矩阵，也可以看成是数据元素是一维数组的一位数组。由于计算机内部存储器的地址是一维线性排列的，故在存储数据时，必须将二维数组转换为计算机的内部存储形式才可以。一般有两种存储方式：以行为主的存储方式(rowmajor)和以列为主的存储方式(columnmajor)。 设二维数组 A1:U 1 ，1:U 2 ，该数组有(U 1 -1)+1=U 1 行，有(U 1 -1)+1=U 1 列。设每个元素占 d个空
34、间，数组的起始地址为 L 1 。 以行为主(rowmajor)：也称行优先存储。其特点为：以每一行为单位，一行一行地放入内存，如 C语言、PASCAL 语言等都是如此处理二维数组的。 以列为主(columnmajor)：也称列优先存储。其特点为：以每一列为单位，一列一列地放入内存，如Fortran语言就是如此处理二维数组的。二维数组 A可以看成由 U 2 个一维数组组成，每个一维数组有 U 1 个元素。同 1)类似，有： *第 j列数据元素的起始地址为：(j-1)U 1 d+L 1 *数组元素 Ai，j的地址为：Loc(A i，j)=L 1 +(j-1)U 1 d-6(i-1)d 重要说明：二
35、维数组 Am*n的含义是：该数组有 m行(0m-1 第一维)，有 n列(0n-1，第二维)，占用m*n个存储空间。假设每个数据元素占用 L个存储单元(可理解为字节)，则二维数组 A中任意一个元素 a ij 的存储位置为： 行优先：LOC(i，j)=LOC(0，0)+(ni+j)L 列优先： LOC(i，j)=LOC(0，0)+(mj+i)L 二维数组是一种随机存储结构，因为存取数组中任一元素的时间都相等(单链表则不是，因为需要顺链访问，访问时间同数据元素的存储位置有关)。25.向一个栈顶指针为 hs的链栈中插入一个 S结点时，应执行 _ 。（分数：2.00）A.hsnext=s；B.snext
36、=hs；hs=S； C.snext=hsnext；hs 一next=s；D.snext=hs；hs=hsnext；解析：由于栈的插入、删除操作只能在一端进行，而对于单链表来说，在首端插入、删除结点要比在尾端相对容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。 栈的链式存储结构在 C语言中可用下列类型定义实现： typedef struct node 链栈的结点结构 StackEntry item； 栈的数据元素类型 struct node*next； 指向后继结点的指针 NODE； typedef struct stack NODE*top； STACK； 下面给
37、出链栈各项基本操作的算法。 初始化栈 S void InitStack(STACK*S) Stop=NULL； 入栈 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=pn
38、ext；free(p)； 获取栈顶元素内容 void GetTop(STACK S，StackEntry*item) if(StackEmpty(S)exit(“Stack is empty“)； else*item=S.topitem； 判断栈 S是否空 int StackEmpty(STACK S) if(S.top=NULL)return TRUE； else FALSE； 26.数组 A110，26，28以行优先的顺序存储，设第一个元素的首地址是 100，每个元素占 3个存储长度的存储空间，则元素 A5，0，7的存储地址为 _ 。（分数：2.00）A.913 B.910C.915D.9
39、23解析：见 7解析。二、综合应用题(总题数：4，分数：40.00)27.设有两个栈 S 1 ，S 2 都采用顺序栈方式，并且共享一个存储区Omaxsizel，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计 S 1 ，S 2 有关入栈和出栈的操作算法。（分数：10.00）_正确答案：()解析：两栈共享向量空间，将两栈栈底设在向量两端，初始时，s 1 栈顶指针为-1，s 2 栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。 #define maxsize 两栈共享顺序存储空间所能达到的最多元素数 #define elemtp
40、 int 假设元素类型为整型 typedef struct elemtp stack-maxsize； 栈空间 int top2； top 为两个栈顶指针 stk； stk s； s 是如上定义的结构类型变量，为全局变量 (1)入栈操作： int push(int i，int x) 入栈操作。i 为栈号，i=0 表示左边的栈 s 1 ，i=1 表示右边的栈 s 2 ，x 是入栈元素。入栈成功返回1，否则返回 0。 if(i0 i1)printf(“栈号输入不对”)；exit(0)；) if(s.top1-s.top0=1)printf(“栈已满/n”)；return(0)；) switch(i
41、) case 0:sstack+s.top0=x；return(1)；break； case 1:s.stacks.top1=x；return(1)； push (2)退栈操作 elemtp pop(int i) 退栈算法。i 代表栈号，i=0 时为 s 1 栈，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.t
42、op1=maxsizeprintf(“栈空/n”)；retturn(-1)；) else return(s.stacks.top 1+)； 请注意算法中两栈入栈和退栈时的栈顶指针的计算。s 1 栈是通常意义下的栈，而 s 2 栈入栈操作时，其栈顶指针左移(减 1)，退栈时，其栈顶指针右移(加 1)。28.设从键盘输入一整数的序列：a 1 ，a 2 ，a 3 ，a n ，试编写算法实现：用栈结构存储输入的整数，当 a i -1 时，将 a i 进栈；当 a i =-1时，输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。 （分数：10.00）_正确答案：()解析：#define m
43、axsize 栈空间容量 void InOutS(int s maxsize) s 是元素为整数的栈，本算法进行入栈和退栈操作 int top=0； top 为栈顶指针，定义 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(“出
44、栈元素是% d/n”，stop)；) 29.设表达式以字符形式已存入数组 En中，#为表达式的结束符，试写出判断表达式中括号(和)是否配对的 C语言描述算法：EXYX(E)；(注：算法中可调用栈操作的基本算法。) （分数：10.00）_正确答案：()解析：判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配 int EXYX(char E，int n) /E是有 n字符的字符数组，存放字符串表达式，以#结束。本算法判断表达式中圆括号是否匹配 char s
45、E30； s 是一维数组，容量足够大，用作存放括号的栈 int top=0； top 用作栈顶指针 S Etop=#； #先入栈，用于和表达式结束符号#匹配 int i=0； 字符数组 E的工作指针 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+； 读入其他字符，不作处理 本题是用栈判断括号匹配的特例：只检查圆括号
