【考研类试卷】计算机专业基础综合数据结构（栈、队列和数组）-试卷1及答案解析.doc

1、计算机专业基础综合数据结构（栈、队列和数组）-试卷 1及答案解析(总分：70.00，做题时间：90 分钟)一、单项选择题(总题数：21，分数：42.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.栈和队列的主要区别在于( )。（分数：2.00）A.它们的逻辑结构不一样B.它们的存储结构不一样C.所包含的运算不一样D.插入和删除运算的限定不一样3.若循环队列以数组 Q0.，m1作为其存储结构，变量 rear表示循环队列中的队尾元素的实际位置，其移动按 rear=(rear+1)MOD m进行，变量 length表示当前循环队列

2、中的元素个数，则循环队列的队首元素的实际位置是( )。（分数：2.00）A.reat一 lengthB.(rearlength+m)MOD mC.(rearlength+1+m)MOD mD.mlength4.一个以向量 Vn存储的栈，其初始栈顶指针 top为 n+1，则对于 x，其正确的进栈操作是( )。（分数：2.00）A.top=top+1；Vtop=xB.Vtop=x；top=top+1C.top=top一 1；Vtop=xD.Vtop=x；top=top 一 15.为了增加内存空间的利用率和减少溢出的可能性，两个栈可以共享一片连续的内存空间，此时应将两栈的栈底分别设在( )。（分数：

3、2.00）A.内存空间的首地址B.内存空间的尾地址C.内存空间的两端D.内存空间的中间6.已知输入序列为 abed，经过输出受限的双端队列后，能得到的输出序列是( )。（分数：2.00）A.daebB.eadbC.dbeaD.以上答案都不对7.假设一个序列 1，2，3，n 依次进栈，如果出栈的第一个元素是 n，那么第 i(1in)个出栈的元素是( )。（分数：2.00）A.不确定B.ni+1C.iD.ni8.假设一个序列 1，2，3，n 依次进栈，如果第一个出栈的元素是 i，那么第 j个出栈的元素是( )。（分数：2.00）A.i-j一 1B.i-jC.j-i+1D.不确定的9.已知当前栈中有

4、 n个元素，此时如果有新的元素需要执行进栈操作，但发生上溢，则由此可以判断，此栈的最大容量为( )。（分数：2.00）A.n一 1B.nC.n+1D.n210.设有 5个元素 a，b，c，d，e 顺序进栈，下列几个选项中，不可能的出栈序列是( )。（分数：2.00）A.a，b，c，d，eB.d，e，c，b，aC.a，c，e，b，dD.c，b，a，d，e11.有 6个元素按 6，5，4，3，2，1 的顺序依次进栈，不合法的出栈序列是( )。（分数：2.00）A.543612B.453126C.346521D.23415612.有 5个元素，其入栈次序为 A，B，C，D，E，在各种可能的出栈次序中

5、，以元素 C，D 最先出栈的次序不包括( )。（分数：2.00）A.CDEBAB.CDBEAC.CDBAED.CDAEB13.对于 4个元素依次进栈，可以得到( )种出栈序列。（分数：2.00）A.10B.12C.14D.1614.现有两栈，其共享空间为 V1,m，topi代表第 i个栈(i=1，2)栈顶，栈 1的底在 V1，栈 2的底在 Vm，若两栈均采用顺序存储方式存储，则栈满的条件是( )。（分数：2.00）A.|top2-top1|=0B.top1+1=top2C.top1+top2=mD.top1=top215.一个递归算法必须包括( )。（分数：2.00）A.递归部分B.终止条件和

6、递归部分C.迭代部分D.终止条件和迭代部分16.执行完下列语句段后，i 值为( )。 int f(int x) return(x0)?x*f(x1)：2)； i=f(f(1)；（分数：2.00）A.2B.4C.8D.无限递归17.表达式 a*(b+c)一 d的后缀表达式是( )。（分数：2.00）A.abcd*+一B.abc+*dC.abc*+dD.一+*abcd18.为了处理参数及返回地址，在递归过程或函数调用时，要用一种称为( )的数据结构。（分数：2.00）A.队列B.多维数组C.栈D.线性表19.若用一个大小为 6的数组来实现循环队列，且当前 rear和 front的值分别为 0和 3

7、，当从队列中删除一个元素，再加入两个元素后，rear 和 front的值分别为( )。（分数：2.00）A.1和 5B.2和 4C.4和 2D.5和 120.队尾已到达一维数组的最高下标，不能再插入元素，然而队中元素个数小于队列的长度，这种现象称作( )。（分数：2.00）A.上溢B.下溢C.假溢出D.队列满21.已知有一维数组 A0.，mn 一 1，若要对应为 m行、n 列的矩阵，将元素 Ak(0kmn)表示成矩阵的第 i行、第 j列的元素(0im，0jn)，则下面的对应关系是( )。（分数：2.00）A.i=kn，j=kmB.i=km，j=kmC.i=kn，j=knD.i=km，j=kn二

8、、综合应用题(总题数：14，分数：28.00)22.综合应用题 41-47小题。（分数：2.00）_23.简述栈、队列、循环队列的定义。（分数：2.00）_24.假设以 I和 O分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由 I和 O组成的序列表示。(1)试指出判别给定序列是否合法的一般规则。 (2)两个不同合法序列(对同一输入序列)能否得到相同的输出元素序列?如能得到，请举例说明。（分数：2.00）_25.有 5个元素，其入栈次序为 A，B，C，D，E，在各种可能的出栈次序中，以元素 C，D 最先出栈(即 C第一个且 D第二个出栈)的次序有哪几个?（分数：2.00）_26.为了增加

9、内存空间的利用率和减少溢出的可能性，通常采用两个栈利用同一块存储空间的方法。通常两个栈的栈底设在内存空间的两端，而栈顶相向，迎面增长。已知有两个栈 s1、s2 都采用顺序栈方式，并且共享一个存储区0maxsize1。 设计共享存储空间的两个栈 s1、s2 的入栈和出栈算法。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C或 C+或 Java语言描述算法，关键之处给出注释；（分数：2.00）_27.一个 nn的对称矩阵，如果以行或列为主序存入内存，则其容量为多少?（分数：2.00）_28.设有一个 nn的上三角矩阵(a ij )，将其上三角中的元素按先行后列的顺序存于数组 B

10、m中，使得Bk=a ij 且 k=f 1 (i)+f 2 (j)+c，请推导出函数 f 1 、f 2 和常数 c，要求 f 1 和 f 2 中不含常数项。（分数：2.00）_29.已知有一整数序列a 1 ，a 2 ，a 3 ，a n 。栈 A中只保存整数，即序列中元素为整数时允许其入栈。设计一个算法实现如下功能：用栈结构存储入栈的整数，当 a i 一 1时，将 a i 进栈；当 a i =一 1时，输出栈顶整数并出栈。（分数：2.00）_30.设结点结构为(data，link)，试用一个全局指针 p和某种链接结构实现一个队列，画出示意图，并给出入队 addq和出队 deleq过程，要求它们的时

11、间复杂性都是 O(1)(不计 new和 dispose时间)。（分数：2.00）_31.判断括号是否匹配是栈的主要应用之一。设字符表达式存储在数组 En中，#为字符表达式的结束符。给出一个算法，用于判断表达式中括号(和)是否配对。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用 C或 C+或 Java语言描述算法，关键之处给出注释。（分数：2.00）_32.从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔，操作符只可能有+、一、*、四种运算，例如：23434+2*$。（分数：2.00）_33.假设以 I

12、和 O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由 I和 O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 (1)下面所示的序列中哪些是合法的? AIOIIOIOO BIOOIOIIO CIIIOIOIO DIIIOOIOO (2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回 true，否则返回 false(假定被判定的操作序列已存入一维数组中)。（分数：2.00）_34.设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch 和 link，其中 ch域为字符类

13、型。（分数：2.00）_35.请利用两个栈 s1和 s2来模拟一个队列。已知栈的三个运算定义如下： (1)push(st，X)：元素 X入st栈： (2)pop(st，X)：st 栈顶元素出栈，赋给变量 X： (3)sempty(st)：判 st栈是否为空。 那么如何利用栈的运算来实现该队列的三个运算： (1)enqueue：插入一个元素入队列； (2)dequeue：删除一个元素出队列： (3)queueempty：判队列为空。(请写明算法的思想及必要的注释。)（分数：2.00）_计算机专业基础综合数据结构（栈、队列和数组）-试卷 1答案解析(总分：70.00，做题时间：90 分钟)一、单项

14、选择题(总题数：21，分数：42.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.栈和队列的主要区别在于( )。（分数：2.00）A.它们的逻辑结构不一样B.它们的存储结构不一样C.所包含的运算不一样D.插入和删除运算的限定不一样 解析：解析：栈和队列的逻辑结构都是线性的，都有顺序存储和链式存储，有可能包含的运算不一样，但不是其主要区别。任何数据结构在针对具体问题时所包含的运算都可能不同。所以正确答案是 D。3.若循环队列以数组 Q0.，m1作为其存储结构，变量 rear表示循环队列中的队尾元素的实际位置，其移动按 r

15、ear=(rear+1)MOD m进行，变量 length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是( )。（分数：2.00）A.reat一 lengthB.(rearlength+m)MOD mC.(rearlength+1+m)MOD m D.mlength解析：解析：按照循环队列的定义，因为元素移动按照 rear=(rear+1)MOD m进行，则当数组 Qm1存放了元素之后，下一个入队的元素将存放到 QO中，因此队列的首元素的实际位置是(rearlength+1+m)MOD m。4.一个以向量 Vn存储的栈，其初始栈顶指针 top为 n+1，则对于 x，其正确的进栈

16、操作是( )。（分数：2.00）A.top=top+1；Vtop=xB.Vtop=x；top=top+1C.top=top一 1；Vtop=x D.Vtop=x；top=top 一 1解析：解析：此题考查的知识点是入栈的具体操作。操作时要看栈顶的地址，先取得空间，再入栈。本题栈项为 n+1，应该用减法，所以选 C。D 是先存入，破坏原有数据，所以错。5.为了增加内存空间的利用率和减少溢出的可能性，两个栈可以共享一片连续的内存空间，此时应将两栈的栈底分别设在( )。（分数：2.00）A.内存空间的首地址B.内存空间的尾地址C.内存空间的两端 D.内存空间的中间解析：解析：两个栈共享一个内存空间时

17、，需要把两个栈的栈底设在内存空间的两端。6.已知输入序列为 abed，经过输出受限的双端队列后，能得到的输出序列是( )。（分数：2.00）A.daebB.eadb C.dbeaD.以上答案都不对解析：解析：输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。 分析选项A，输入序列为 abcd，输出序列为 dacb，由输出受限性质可知以 da开头的结果只有 dabc，选项 A为错误答案。 分析选项 B，输入序列为 abcd，输出序列为 cadb，其输入输出顺序为：先在输出端输入 a，然后在非输出端输入 b，这时队列中的序列为 ba。再在输出端输入 c，这时队列中的序列为 ba

18、c；输出 c，再输出 a；再在输出端输入 d，这时队列中的序列为 bd；输出 d，再输出 b。最后得到输出序列为 cadb。 分析选项 C，输入序列为 abcd，输出序列为 dbca，由输出受限性质可知以 db开头的结果只有 dbac，选项 C为错误答案。7.假设一个序列 1，2，3，n 依次进栈，如果出栈的第一个元素是 n，那么第 i(1in)个出栈的元素是( )。（分数：2.00）A.不确定B.ni+1 C.iD.ni解析：解析：进栈的顺序是：1，2，n，且出栈的第一个元素是 n，那么根据栈后进先出的特点可知，出栈的顺序依次为：n，2，1，那么第 ni+1个出栈元素就是第 i个进栈的元素。

19、8.假设一个序列 1，2，3，n 依次进栈，如果第一个出栈的元素是 i，那么第 j个出栈的元素是( )。（分数：2.00）A.i-j一 1B.i-jC.j-i+1D.不确定的 解析：解析：此题考查的知识点是栈的后进先出特点。若输出序列的第一个元素是 i，只能说明前 i1个元素均入栈，而第 j个元素何时入、出栈并不能确定，所以选 D。9.已知当前栈中有 n个元素，此时如果有新的元素需要执行进栈操作，但发生上溢，则由此可以判断，此栈的最大容量为( )。（分数：2.00）A.n一 1B.n C.n+1D.n2解析：解析：由于栈中有 n个元素是执行进栈操作，但是发生上溢，则说明此栈中最多可以包含 n个

20、数据元素，即栈的最大容量为 n。10.设有 5个元素 a，b，c，d，e 顺序进栈，下列几个选项中，不可能的出栈序列是( )。（分数：2.00）A.a，b，c，d，eB.d，e，c，b，aC.a，c，e，b，d D.c，b，a，d，e解析：解析：由进栈出栈规则可知，对于 a，b，c，d，e 顺序进栈的五个元素，A、B、D 均为可能的出栈序列，所以选 C。11.有 6个元素按 6，5，4，3，2，1 的顺序依次进栈，不合法的出栈序列是( )。（分数：2.00）A.543612B.453126C.346521 D.234156解析：解析：此题考查的知识点是栈的后进先出特点。考查出栈序列，要保证先入

21、栈的一定不能在后入栈的前面出栈，C 选项中的 6在 5前入栈，5 没有出栈，6 却出栈了，所以不合法。其他都符合规律。所以选 C。12.有 5个元素，其入栈次序为 A，B，C，D，E，在各种可能的出栈次序中，以元素 C，D 最先出栈的次序不包括( )。（分数：2.00）A.CDEBAB.CDBEAC.CDBAED.CDAEB 解析：解析：以元素 C，D 最先出栈的次序有三个：CDEBA、CDBEA、CDBAE。13.对于 4个元素依次进栈，可以得到( )种出栈序列。（分数：2.00）A.10B.12C.14 D.16解析：解析：n 个入栈元素可得到14.现有两栈，其共享空间为 V1,m，top

22、i代表第 i个栈(i=1，2)栈顶，栈 1的底在 V1，栈 2的底在 Vm，若两栈均采用顺序存储方式存储，则栈满的条件是( )。（分数：2.00）A.|top2-top1|=0B.top1+1=top2 C.top1+top2=mD.top1=top2解析：解析：此题考查的知识点是入栈的具体操作。判断栈是否满要看两个栈顶是否相邻，当 top1+1=top2或 top2一 1=top1时都表示栈满，所以选 B，而 A，C 没有任何意义。D 表示已经出现覆盖了，也是错的。15.一个递归算法必须包括( )。（分数：2.00）A.递归部分B.终止条件和递归部分 C.迭代部分D.终止条件和迭代部分解析：

23、解析：此题考查的知识点是递归算法的组成部分。一个递归算法主要包括终止条件和递归部分，所以选 B。A 不全面，C、D 不是递归算法。16.执行完下列语句段后，i 值为( )。 int f(int x) return(x0)?x*f(x1)：2)； i=f(f(1)；（分数：2.00）A.2B.4 C.8D.无限递归解析：解析：此题考查的知识点是递归算法的分析。根据题意可计算 f(0)=2，f(1)=2，f(2)=4，所以选B。17.表达式 a*(b+c)一 d的后缀表达式是( )。（分数：2.00）A.abcd*+一B.abc+*d C.abc*+dD.一+*abcd解析：解析：此题考查的知识点

24、是利用栈完成表达式的中后缀转换。顺序扫描表达式，操作数顺序输出，而运算符的输出顺序根据算术运算符的优先级确定。保证栈外运算符优先级比栈内低，若高则入栈，否则出栈输出。本题中输出顺序为 a输出，*进栈，(进栈，b 输出，+进栈，c 输出，此时)低于+，所以“+”输出。“)”与“(”相等，出栈删除，一低于*，所以*出栈，此时输出序列为 abc+*，一入栈，输出 d，输出一，结束。所以选 B。18.为了处理参数及返回地址，在递归过程或函数调用时，要用一种称为( )的数据结构。（分数：2.00）A.队列B.多维数组C.栈 D.线性表解析：解析：此题考查的知识点是栈的应用。要处理参数及返回地址，需要后进

25、先出规则，应选 c。A 是先进先出规则，B 是普通的存储结构，D 是普通的逻辑结构。19.若用一个大小为 6的数组来实现循环队列，且当前 rear和 front的值分别为 0和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front的值分别为( )。（分数：2.00）A.1和 5B.2和 4 C.4和 2D.5和 1解析：解析：此题考查的知识点是队列的特征。此题考查顺序存取时的位置计算，按顺时针计算，所以删除 front+1，插入 rear+1，计算后 rear=2，front=4，应选 Bo20.队尾已到达一维数组的最高下标，不能再插入元素，然而队中元素个数小于队列的长度，这

26、种现象称作( )。（分数：2.00）A.上溢B.下溢C.假溢出 D.队列满解析：解析：用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质(队尾插入和队头删除)，容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数却小于队列的长度(容量)。21.已知有一维数组 A0.，mn 一 1，若要对应为 m行、n 列的矩阵，将元素 Ak(0kmn)表示成矩阵的第 i行、第 j列的元素(0im，0jn)，则下面的对应关系是( )。（分数：2.00）A.i=kn，j=kmB.i=km，j=kmC.i=kn，j=kn D.i=km，j=kn解析：解析：本题是求一维数组向二维

27、数组转化的问题。最简单的方法是把数组 A的第 0n 一 1共 n个元素放到数组 B的第一行，数组 A的第 n一 2n一 1共 n个元素放到数组 B的第二行中，依此类推，数组A的最后 n个元素放到数组 B的最后一行中。 求 Ak在数组 B中的位置，应先确定 Ak处在哪一行，显然应该是 kn 行；然后再确定处在 kn，行的哪一列，显然是 kn。二、综合应用题(总题数：14，分数：28.00)22.综合应用题 41-47小题。（分数：2.00）_解析：23.简述栈、队列、循环队列的定义。（分数：2.00）_正确答案：(正确答案：(1)栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈

28、顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出(LiFO)表。 (2)队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开(删除)，故队列也常称先进先出(FIFO)表。 (3)循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。)解析：24.假设以 I和 O分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由 I和 O组成的序列表示。(1)试指出判别给定序列是否合法的一般规则。 (2)两个不同合法序列(对同一输入序

29、列)能否得到相同的输出元素序列?如能得到，请举例说明。（分数：2.00）_正确答案：(正确答案：(1)通常有两条规则。第一是给定序列中 I的个数和 O的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，I 的个数要大于或等于 O的个数。 (2)可以得到相同的输出元素序列。例如，输入元素为 A，B，C，则两个输入的合法序列 ABC和 BAC均可得到输出元素序列 ABC对于合法序列 ABC，我们使用本题约定的 IOIOIO操作序列；对于合法序列 BAC，我们使用 IIOOIO操作序列。)解析：25.有 5个元素，其入栈次序为 A，B，C，D，E，在各种可能的出栈次序中，以元素 C，D 最先

30、出栈(即 C第一个且 D第二个出栈)的次序有哪几个?（分数：2.00）_正确答案：(正确答案：3 个:C，D，E，B，A；C，D，B，E，A；C，D，B，A，E。 提示：此题考查的知识点是栈的后进先出特点。按题意，C 先出，说明 A，B 已入栈，D 出栈再出栈，E 可以入栈就出栈，可以有序列 C，D，E，B，A 也可以 B先出 E再入，再出，得序列 C，D，B，E，A 还可以 B，A 都出栈后，E 再入栈出栈，得序列 C，D，B，A，E。只有这三种情况。)解析：26.为了增加内存空间的利用率和减少溢出的可能性，通常采用两个栈利用同一块存储空间的方法。通常两个栈的栈底设在内存空间的两端，而栈顶相

31、向，迎面增长。已知有两个栈 s1、s2 都采用顺序栈方式，并且共享一个存储区0maxsize1。 设计共享存储空间的两个栈 s1、s2 的入栈和出栈算法。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C或 C+或 Java语言描述算法，关键之处给出注释；（分数：2.00）_正确答案：(正确答案：(1)栈 s1、s2 共享向量空间，将两栈栈底设在向量两端。初始时，s1 栈顶指针为一 1，s2 栈项为 maxsize。两栈项指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈项元素。 (2)算法设计如下： #define maxsize 两栈共享顺序存储空间所能达到的最多元素

32、数 #define elemtp int 假设元素类型为整型 typedef struct elemtp stackmaxsize；栈空间 int top2； top 为两个栈顶指针 stk； stk s； s 是如上定义的结构类型变量，为全局变量 入栈操作： int push(int i，int x) A 栈操作。i 为栈号，i=0 表示左边的栈 sl，i=l 表示右 边的栈 s2，X 是入栈元素。入栈成功返回 1，否则返回 0 if(i0 | i1)printf(”栈号输入不对”)；exit(0)； if(stop1一 stop0=1)printf(栈已满n”)；return(0)； sw

33、itch(i) case 0：sstack+stop0=X；return 1；break； case 1：sstack一一 stop1=X；return 1； 退栈操作： elemtp pop(int i) if(i0 | i1)printf(”栈号输入错误n”)；exit(0)； switch(i) case 0：if(stop0=一 1)printf(”栈空n”)；return 一 1； else return sstackstop0-； case l：if(stop1=maxsize)printf(”栈空n”)；return1； else return sstackstop1+； )解析

34、：27.一个 nn的对称矩阵，如果以行或列为主序存入内存，则其容量为多少?（分数：2.00）_正确答案：(正确答案：n(n+1)2(压缩存储)或 n 2 (不采用压缩存储)。 提示：此问题考查的知识点是数组的存放问题。对称矩阵可以只存上三角或下三角。所用空间为 1，2，3，n 之和。)解析：28.设有一个 nn的上三角矩阵(a ij )，将其上三角中的元素按先行后列的顺序存于数组 Bm中，使得Bk=a ij 且 k=f 1 (i)+f 2 (j)+c，请推导出函数 f 1 、f 2 和常数 c，要求 f 1 和 f 2 中不含常数项。（分数：2.00）_正确答案：(正确答案：上三角矩阵第 1行

35、有 n个元素，第 il行有 n一(i1)+1 个元素，第 1行到第i一 1行是等腰梯形，而第 i行上第 j个元素(即 a ij )是第 i行上第 j一 i+1个元素，故元素 a ij 在一维数组中的存储位置(下标 k)为： k=(n+(n 一(i1)+1)(i1)2+(j-i+1)=(2ni+2)(i 一 1)2+j 一i+1 )解析：29.已知有一整数序列a 1 ，a 2 ，a 3 ，a n 。栈 A中只保存整数，即序列中元素为整数时允许其入栈。设计一个算法实现如下功能：用栈结构存储入栈的整数，当 a i 一 1时，将 a i 进栈；当 a i =一 1时，输出栈顶整数并出栈。（分数：2.0

36、0）_正确答案：(正确答案：#define maxsize 栈空间容量 void InOutS(int Smaxsize) int top=0； top 为栈顶指针，定义 top=0时为栈空 for(i=1；i=n；i+) n 个整数序列作处理 SCanf(”d”， j 和 k分别为 I和字母 0的个数 while(Ai!=0) switch(Ai) caseI：j+；break；入栈次数增 1 case0；k+；if(kj)printf(”序列非法n”)；exit(0)； i+i 不论 Ai是I或0，指针 i均后移 if(j!=k)printf(”序列非法n”)；return(false)；

37、 elseprintf(”序列合法n”)；return(true)： 提示：在入栈出栈序列(即由I和0组成的字符串)的任一位置，入栈次数(I的个数)都必须大于等于出栈次数(即0的个数)，否则视作非法序列，立即给出信息，退出算法。整个序列(即读到字符数组中字符串的结束标记0)，入栈次数必须等于出栈次数(题目中要求栈的初态和终态都为空)，否则视为非法序列。)解析：34.设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch 和 link，其中 ch域为字符类型。（分数：2.00）_正确答案：(正确答案：表达式中的括号有以下三对：(、)、，使

38、用栈，当为左括号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为空，则结论表达式括号配对；否则，结论表达式括号不配对。 int Match(LinkedList la) 算术表达式存储在以 la为头结点的单循环链表中，本算法判断括号是否正确配对 char S； s 为字符栈，容量足够大 P=la 一link； p 为工作指针，指向待处理结点 Stack Init(S)； 初始化栈 s while(P!=la) 循环到头结点为止 switch(p-ch) case(：push(s，p-ch)；break； case)：if(Stac

39、kEmpty(s)|StackGetTop(s)!=() printf(”括号不配对n”)；return(0)： else pop(S)： break； case：push(s，p 一ch)；break； case：if(StaekEmpty(s)Il StackGetTop(s)!=) printf(”括号不配对n”)；return(0)； else pop(S)； break； case：push(s，p-ch)；break； case：if(StackEmpty(s)II StackGetTop(s)!=) printf(”括号不配对n”)；return(0)； else pop(s)：

40、 break； P=p-link；后移指针 while if(StackEmpty(s)f printf(“括号配对n“)；return(1)； elseprintf(”括号不配对n”)；return(0)； )解析：35.请利用两个栈 s1和 s2来模拟一个队列。已知栈的三个运算定义如下： (1)push(st，X)：元素 X入st栈： (2)pop(st，X)：st 栈顶元素出栈，赋给变量 X： (3)sempty(st)：判 st栈是否为空。 那么如何利用栈的运算来实现该队列的三个运算： (1)enqueue：插入一个元素入队列； (2)dequeue：删除一个元素出队列： (3)queueempty：判队列为空。(请写明算法的思想及必要的注释。)（分数：2.00）_正确答案：(正确答案：栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈 s1和 s2模拟一个队列时，s1 作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈 s1退栈并逐个压入栈 s2中，s1 中