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

《【考研类试卷】计算机学科专业基础综合数据结构-栈、队列和数组(三)及答案解析.doc》由会员分享，可在线阅读，更多相关《【考研类试卷】计算机学科专业基础综合数据结构-栈、队列和数组(三)及答案解析.doc（18页珍藏版）》请在麦多课文档分享上搜索。

1、计算机学科专业基础综合数据结构-栈、队列和数组(三)及答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：20，分数：40.00)1.栈和队列的主要区别在于_。 A.它们的逻辑结构不一样 B.它们的存储结构不一样 C.所包含的运算不一样 D.插入和删除运算的限定不一样（分数：2.00）A.B.C.D.2.若循环队列以数组 Q0m-1作为其存储结构，变量 rear表示循环队列中的队尾元素的实际位置，其移动按 rear=(rear+1)MOD m进行，变量 length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是_。 A.rear-length B.

2、(rear-length+m)MOD m C.(rear-length+1+m)MOD m D.m-length（分数：2.00）A.B.C.D.3.一个以向量 Vn存储的栈，其初始栈项指针 top为 n+1，则对于 x，其正确的进栈操作是_。 A.top=top+ 1;Vtop=x B.Vtop=x;top=top+1 C.top = top-1;Vtop=x D.Vtop=x;top=top-1（分数：2.00）A.B.C.D.4.为了增加内存空间的利用率和减少溢出的可能性，两个栈可以共享一片连续的内存空间，此时应将两栈的栈底分别设在_。 A.内存空间的首地址 B.内存空间的尾地址 C.内

3、存空间的两端 D.内存空间的中间（分数：2.00）A.B.C.D.5.已知输入序列为 abed，经过输出受限的双端队列后，能得到的输出序列是_。 A.daeb B.eadb C.dbea D.以上答案都不对（分数：2.00）A.B.C.D.6.假设一个序列 1，2，3，n 依次进栈，如果出栈的第一个元素是 n，那么第 i(1in)个出栈的元素是_。 A.不确定 B.n-i+1 C.i D.n-i（分数：2.00）A.B.C.D.7.假设一个序列 1，2，3，n 依次进栈，如果第个出栈的元素是 i，那么第 i个出栈的元素是_。 A.i-j-1 B.i-j C.j-i+1 D.不确定的（分数：2.

4、00）A.B.C.D.8.已知当前栈中有 n个元素，此时如果有新的元素需要执行进栈操作，但发生上溢，则由此可以判断，此栈的最大容量为_。 A.n-1 B.n C.n+1 D.n/2（分数：2.00）A.B.C.D.9.设有 5个元素 a，b，c，d，e 顺序进栈，下列几个选项中，不可能的出栈序列是_。 A.a，b，c，d，e B.d，e，c，b，a C.a，c，e，b，d D.c，b，a，d，e（分数：2.00）A.B.C.D.10.有 6个元素按 6，5，4，3，2，1 的顺序依次进栈，不合法的出栈序列是_。 A.543612 B.453126 C.346521 D.234156（分数：2.

5、00）A.B.C.D.11.有 5个元素，其入栈次序为 A，B，C，D，E，在各种可能的出栈次序中，以元素 C，D 最先出栈的次序不包括_。 A.CDEBA B.CDBEA C.CDBAE D.CDAEB（分数：2.00）A.B.C.D.12.对于 4个元素依次进栈，可以得到_种出栈序列。 A.10 B.12 C.14 D.16（分数：2.00）A.B.C.D.13.现有两栈，其共享空间为 V1m，topi代表第 i个栈(i=1，2)栈顶，栈 1的底在 V1，栈 2的底在 Vm，若两栈均采用顺序存储方式存储，则栈满的条件是_。 A.|top2-top1|=0 B.top1+1=top2 C.t

6、op1+top2=m D.top1=top2（分数：2.00）A.B.C.D.14.一个递归算法必须包括_。 A.递归部分 B.终止条件和递归部分 C.迭代部分 D.终止条件和迭代部分（分数：2.00）A.B.C.D.15.执行完下列语句段后，i 值为_。int f(int x) return (x0)? x*f(x-1);2); i=f(f(1); A.2 B.4 C.8 D.无限递归（分数：2.00）A.B.C.D.16.表达式 a*(b+c) -d的后缀表达式是_。 A.abcd*+- B.abc+*d- C.abc*+d- D.-+*abcd（分数：2.00）A.B.C.D.17.为了

7、处理参数及返回地址，在递归过程或函数调用时，要用一种称为_的数据结构。 A.队列 B.多维数组 C.栈 D.线性表（分数：2.00）A.B.C.D.18.若用一个大小为 6的数组来实现循环队列，且当前 rear和 front的值分别为 0和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front的值分别为_。 A.1和 5 B.2和 4 C.4和 2 D.5和 1（分数：2.00）A.B.C.D.19.队尾已到达一维数组的最高下标，不能再插入元素，然而队中元素个数小于队列的长度，这种现象称作_。 A.上溢 B.下溢 C.假溢出 D.队列满（分数：2.00）A.B.C.D.20.

8、已知有一维数组 A0mn-1，若要对应为 m行、n 列的矩阵，将元素 Ak(0kmn)表示成矩阵的第 i行、第 j列的元素(0im，0jn)，则下面的对应关系是_。 A.i=k/n，j=k%m B.i=k/m，j=k%m C.i=k/n，j=k%n D.i=k/m，j=k%n（分数：2.00）A.B.C.D.二、B综合应用题/B(总题数：13，分数：60.00)21.简述栈、队列、循环队列的定义。（分数：4.00）_22.假设以 I和 O分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由 I和 O组成的序列表示。(1)试指出判别给定序列是否合法的一般规则。 (2)两个不同合法序列(对同一

9、输入序列)能否得到相同的输出元素序列?如能得到，请举例说明。（分数：4.00）_23.有 5个元素，其入栈次序为 A，B，C，D，E，在各种可能的出栈次序中，以元素 C，D 最先出栈(即 C第一个且 D第二个出栈)的次序有哪几个?（分数：4.00）_24.为了增加内存空间的利用率和减少溢出的可能性，通常采用两个栈利用同一块存储空间的方法。通常两个栈的栈底设在内存空间的两端，而栈顶相向，迎面增长。已知有两个栈 s1、s2 都采用顺序栈方式，并且共享一个存储区0 maxsize-1。 设计共享存储空间的两个栈 s1、s2 的入栈和出栈算法。要求： (1)给出算法的基本设计思想。 (2)根据设计思想

10、，采用 C或 C+或 Java语言描述算法，关键之处给出注释；（分数：4.00）_25.一个 nn的对称矩阵，如果以行或列为主序存入内存，则其容量为多少?（分数：4.00）_26.设有一个 nn的上三角矩阵(a ij)，将其上三角中的元素按先行后列的顺序存于数组 Bm中，使得Bk =aij且 k=f1(i)+f2(j)+c，请推导出函数 f1、f 2和常数 c，要求 f1和 f2中不含常数项。（分数：5.00）_27.已知有一整数序列a 1，a 2，a 3，a n。栈 A中只保存整数，即序列中元素为整数时允许其入栈。设计一个算法实现如下功能：用栈结构存储入栈的整数，当 ai-1 时，将 ai进

11、栈；当 ai=-1时，输出栈项整数并出栈。（分数：5.00）_28.设结点结构为(data，link)，试用一个全局指针 p和某种链接结构实现一个队列，画出示意图，并给出入队 addq和出队 deleq过程，要求它们的时间复杂性都是 O(1)(不计 new和 dispose时间)。（分数：5.00）_29.判断括号是否匹配是栈的主要应用之一。设字符表达式存储在数组 En中，#为字符表达式的结束符。给出一个算法，用于判断表达式中括号(和)是否配对。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C或 C+或 Java语言描述算法，关键之处给出注释。（分数：5.00）_30.从键

12、盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔，操作符只可能有+、-、*、/四种运算，例如：234-34+2*$。（分数：5.00）_31.假设以 I和 O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由 I和 O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 (1)下面所示的序列中哪些是合法的? AIOIIOIOO BIOOIOIIO CIIIOIOIO DIIIOOIOO (2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回 true，否则返回

13、 false(假定被判定的操作序列已存入一维数组中)。（分数：5.00）_32.设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch 和 link，其中 ch域为字符类型。（分数：5.00）_33.请利用两个栈 s1和 s2来模拟一个队列。已知栈的三个运算定义如下： (1)push(st,x)：元素 x入 st栈； (2)pop(st,x)：st 栈顶元素出栈，赋给变量 x； (3)sempty(st)：判 st栈是否为空。 那么如何利用栈的运算来实现该队列的三个运算： (1)enqueue：插入一个元素入队列； (2)dequeue

14、：删除一个元素出队列； (3)queue_empty：判队列为空。 (请写明算法的思想及必要的注释。)（分数：5.00）_计算机学科专业基础综合数据结构-栈、队列和数组(三)答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：20，分数：40.00)1.栈和队列的主要区别在于_。 A.它们的逻辑结构不一样 B.它们的存储结构不一样 C.所包含的运算不一样 D.插入和删除运算的限定不一样（分数：2.00）A.B.C.D. 解析：栈和队列的逻辑结构都是线性的，都有顺序存储和链式存储，有可能包含的运算不一样，但不是其主要区别。任何数据结构在针对具体问题时所包含的运算都可

15、能不同。所以正确答案是 D。2.若循环队列以数组 Q0m-1作为其存储结构，变量 rear表示循环队列中的队尾元素的实际位置，其移动按 rear=(rear+1)MOD m进行，变量 length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是_。 A.rear-length B.(rear-length+m)MOD m C.(rear-length+1+m)MOD m D.m-length（分数：2.00）A.B.C. D.解析：按照循环队列的定义，因为元素移动按照 rear=(rear+1) MOD m进行，则当数组 Qm-1存放了元素之后，下一个入队的元素将存放到 Q0中，

16、因此队列的首元素的实际位置是(rear-length+1+m)MOD m。3.一个以向量 Vn存储的栈，其初始栈项指针 top为 n+1，则对于 x，其正确的进栈操作是_。 A.top=top+ 1;Vtop=x B.Vtop=x;top=top+1 C.top = top-1;Vtop=x D.Vtop=x;top=top-1（分数：2.00）A.B.C. D.解析：此题考查的知识点是入栈的具体操作。操作时要看栈顶的地址，先取得空间，再入栈。本题栈顶为n+1，应该用减法，所以选 C。D 是先存入，破坏原有数据，所以错。4.为了增加内存空间的利用率和减少溢出的可能性，两个栈可以共享一片连续的内

17、存空间，此时应将两栈的栈底分别设在_。 A.内存空间的首地址 B.内存空间的尾地址 C.内存空间的两端 D.内存空间的中间（分数：2.00）A.B.C. D.解析：两个栈共享一个内存空间时，需要把两个栈的栈底设在内存空间的两端。5.已知输入序列为 abed，经过输出受限的双端队列后，能得到的输出序列是_。 A.daeb B.eadb C.dbea D.以上答案都不对（分数：2.00）A.B. C.D.解析：输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。 分析选项 A，输入序列为 abed，输出序列为 dacb，由输出受限性质可知以 da开头的结果只有 dabc，选项 A

18、为错误答案。分析选项 B，输入序列为 abed，输出序列为 cadb，其输入输出顺序为：先在输出端输入 a，然后在非输出端输入 b，这时队列中的序列为 ba。再在输出端输入 c，这时队列中的序列为 bac；输出 c，再输出 a；再在输出端输入 d，这时队列中的序列为 bd；输出 d，再输出 b。最后得到输出序列为 cadb。 分析选项C，输入序列为 abed，输出序列为 dbca，由输出受限性质可知以 db开头的结果只有 dbac，选项 C为错误答案。6.假设一个序列 1，2，3，n 依次进栈，如果出栈的第一个元素是 n，那么第 i(1in)个出栈的元素是_。 A.不确定 B.n-i+1 C.

19、i D.n-i（分数：2.00）A.B. C.D.解析：进栈的顺序是：1，2，n，且出栈的第一个元素是 n，那么根据栈后进先出的特点可知，出栈的顺序依次为：n，2，1，那么第 n-i+1个出栈元素就是第 i个进栈的元素。7.假设一个序列 1，2，3，n 依次进栈，如果第个出栈的元素是 i，那么第 i个出栈的元素是_。 A.i-j-1 B.i-j C.j-i+1 D.不确定的（分数：2.00）A.B.C.D. 解析：此题考查的知识点是栈的后进先出特点。若输出序列的第一个元素是 i，只能说明前 i-1个元素均入栈，而第 j个元素何时入、出栈并不能确定，所以选 D。8.已知当前栈中有 n个元素，此时

20、如果有新的元素需要执行进栈操作，但发生上溢，则由此可以判断，此栈的最大容量为_。 A.n-1 B.n C.n+1 D.n/2（分数：2.00）A.B. C.D.解析：由于栈中有 n个元素是执行进栈操作，但是发生上溢，则说明此栈中最多可以包含 n个数据元素，即栈的最大容量为 n。9.设有 5个元素 a，b，c，d，e 顺序进栈，下列几个选项中，不可能的出栈序列是_。 A.a，b，c，d，e B.d，e，c，b，a C.a，c，e，b，d D.c，b，a，d，e（分数：2.00）A.B.C. D.解析：由进栈出栈规则可知，对于 a，b，c，d，e 顺序进栈的五个元素，A、B、D 均为可能的出栈序列

21、，所以选 C。10.有 6个元素按 6，5，4，3，2，1 的顺序依次进栈，不合法的出栈序列是_。 A.543612 B.453126 C.346521 D.234156（分数：2.00）A.B.C. D.解析：此题考查的知识点是栈的后进先出特点。考查出栈序列，要保证先入栈的一定不能在后入栈的前面出栈，C 选项中的 6在 5前入栈，5 没有出栈，6 却出栈了，所以不合法。其他都符合规律。所以选 C。11.有 5个元素，其入栈次序为 A，B，C，D，E，在各种可能的出栈次序中，以元素 C，D 最先出栈的次序不包括_。 A.CDEBA B.CDBEA C.CDBAE D.CDAEB（分数：2.00

22、）A.B.C.D. 解析：以元素 C，D 最先出栈的次序有三个：CDEBA、CDBEA、CDBAE。12.对于 4个元素依次进栈，可以得到_种出栈序列。 A.10 B.12 C.14 D.16（分数：2.00）A.B.C. D.解析：n 个入栈元素可得到*种出栈序列。本题 4个元素，可有 14种出栈序列。13.现有两栈，其共享空间为 V1m，topi代表第 i个栈(i=1，2)栈顶，栈 1的底在 V1，栈 2的底在 Vm，若两栈均采用顺序存储方式存储，则栈满的条件是_。 A.|top2-top1|=0 B.top1+1=top2 C.top1+top2=m D.top1=top2（分数：2.0

23、0）A.B. C.D.解析：此题考查的知识点是入栈的具体操作。判断栈是否满要看两个栈顶是否相邻，当 top1+1=top2或 top2-1=top1时都表示栈满，所以选 B，而 A，C 没有任何意义。D 表示已经出现覆盖了，也是错的。14.一个递归算法必须包括_。 A.递归部分 B.终止条件和递归部分 C.迭代部分 D.终止条件和迭代部分（分数：2.00）A.B. C.D.解析：此题考查的知识点是递归算法的组成部分。一个递归算法主要包括终止条件和递归部分，所以选B。A 不全面，C、D 不是递归算法。15.执行完下列语句段后，i 值为_。int f(int x) return (x0)? x*f

24、(x-1);2); i=f(f(1); A.2 B.4 C.8 D.无限递归（分数：2.00）A.B. C.D.解析：此题考查的知识点是递归算法的分析。根据题意可计算 f(0)=2，f(1)=2，f(2)=4，所以选 B。16.表达式 a*(b+c) -d的后缀表达式是_。 A.abcd*+- B.abc+*d- C.abc*+d- D.-+*abcd（分数：2.00）A.B. C.D.解析：此题考查的知识点是利用栈完成表达式的中后缀转换。顺序扫描表达式，操作数顺序输出，而运算符的输出顺序根据算术运算符的优先级确定。保证栈外运算符优先级比栈内低，若高则入栈，否则出栈输出。本题中输出顺序为 a输

25、出，*进栈，(进栈，b 输出，+进栈，c 输出，此时)低于+，所以“+”输出。“)”与“(”相等，出栈删除，-低于*，所以*出栈，此时输出序列为 abc+*，-入栈，输出 d，输出-，结束。所以选 B。17.为了处理参数及返回地址，在递归过程或函数调用时，要用一种称为_的数据结构。 A.队列 B.多维数组 C.栈 D.线性表（分数：2.00）A.B.C. D.解析：此题考查的知识点是栈的应用。要处理参数及返回地址，需要后进先出规则，应选 C。A 是先进先出规则，B 是普通的存储结构，D 是普通的逻辑结构。18.若用一个大小为 6的数组来实现循环队列，且当前 rear和 front的值分别为 0

26、和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front的值分别为_。 A.1和 5 B.2和 4 C.4和 2 D.5和 1（分数：2.00）A.B. C.D.解析：此题考查的知识点是队列的特征。此题考查顺序存取时的位置计算，按顺时针计算，所以删除front+1，插入 rear+1，计算后 rear=2，front=4，应选 B。19.队尾已到达一维数组的最高下标，不能再插入元素，然而队中元素个数小于队列的长度，这种现象称作_。 A.上溢 B.下溢 C.假溢出 D.队列满（分数：2.00）A.B.C. D.解析：用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质(队

27、尾插入和队头删除)，容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数却小于队列的长度(容量)。20.已知有一维数组 A0mn-1，若要对应为 m行、n 列的矩阵，将元素 Ak(0kmn)表示成矩阵的第 i行、第 j列的元素(0im，0jn)，则下面的对应关系是_。 A.i=k/n，j=k%m B.i=k/m，j=k%m C.i=k/n，j=k%n D.i=k/m，j=k%n（分数：2.00）A.B.C. D.解析：本题是求一维数组向二维数组转化的问题。最简单的方法是把数组 A的第 0n-1 共 n个元素放到数组 B的第一行，数组 A的第 n2n-1 共 n个元

28、素放到数组 B的第二行中，依此类推，数组 A的最后 n个元素放到数组 B的最后一行中。 求 Ak在数组 B中的位置，应先确定 Ak处在哪一行，显然应该是 k/n行；然后再确定处在 k/n行的哪一列，显然是 k%n。二、B综合应用题/B(总题数：13，分数：60.00)21.简述栈、队列、循环队列的定义。（分数：4.00）_正确答案：(1)栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出(LIFO)表。 (2)队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开

29、(删除)，故队列也常称先进先出(FIFO)表。 (3)循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。)解析：22.假设以 I和 O分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由 I和 O组成的序列表示。(1)试指出判别给定序列是否合法的一般规则。 (2)两个不同合法序列(对同一输入序列)能否得到相同的输出元素序列?如能得到，请举例说明。（分数：4.00）_正确答案：(1)通常有两条规则。第一是给定序列中 I的个数和 O的个数相等；第二是从给定序列的开始，到给定序列中的任一位

30、置，I 的个数要大于或等于 O的个数。 (2)可以得到相同的输出元素序列。例如，输入元素为 A，B，C，则两个输入的合法序列 ABC和 BAC均可得到输出元素序列 ABC。对于合法序列ABC，我们使用本题约定的 IOIOIO操作序列；对于合法序列 BAC，我们使用 IIOOIO操作序列。)解析：23.有 5个元素，其入栈次序为 A，B，C，D，E，在各种可能的出栈次序中，以元素 C，D 最先出栈(即 C第一个且 D第二个出栈)的次序有哪几个?（分数：4.00）_正确答案：(3 个：C，D，E，B，A；C，D，B，E，A；C，D，B，A，E。)解析：此题考查的知识点是栈的后进先出特点。按题意，C

31、 先出，说明 A，B 已入栈，D 出栈再出栈，E 可以入栈就出栈，可以有序列 C，D，E，B，A。也可以 B先出 E再入，再出，得序列 C，D，B，E，A。还可以 B，A 都出栈后，E 再入栈出栈，得序列 C，D，B，A，E。只有这三种情况。24.为了增加内存空间的利用率和减少溢出的可能性，通常采用两个栈利用同一块存储空间的方法。通常两个栈的栈底设在内存空间的两端，而栈顶相向，迎面增长。已知有两个栈 s1、s2 都采用顺序栈方式，并且共享一个存储区0 maxsize-1。 设计共享存储空间的两个栈 s1、s2 的入栈和出栈算法。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用

32、C或 C+或 Java语言描述算法，关键之处给出注释；（分数：4.00）_正确答案：(1)栈 s1、s2 共享向量空间，将两栈栈底设在向量两端。初始时，s1 栈项指针为-1，s2 栈顶为 maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。 (2)算法设计如下： #define maxsize /两栈共享顺序存储空间所能达到的最多元素数 #define elemtp int /假设元素类型为整型 typedef stnlct elemtp stackmaxsize; /栈空间 int top2; /top 为两个栈项指针 stk; stk s; /s 是如上定义

33、的结构类型变量，为全局变量 入栈操作： 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: s.stack+s.top0=x; return 1; break; case 1: s.stack-s.top1=x; return 1; 退栈操作： elemtp pop(

34、int i) if(i0|i1) printf(“栈号输入错误/n“); exit(0); switch(i) case 0: if(s.top0 =-1) printf(“栈空/n“); return-1; else return s.stacks.top0-; case 1: if(s.top1 = maxsize)printf(“栈空/n“);return-1; else return s.stacks.top1+; )解析：25.一个 nn的对称矩阵，如果以行或列为主序存入内存，则其容量为多少?（分数：4.00）_正确答案：(n(n+1)/2(压缩存储)或 n2(不采用压缩存储)。)解

35、析：此问题考查的知识点是数组的存放问题。对称矩阵可以只存上三角或下三角。所用空间为1，2，3，n 之和。26.设有一个 nn的上三角矩阵(a ij)，将其上三角中的元素按先行后列的顺序存于数组 Bm中，使得Bk =aij且 k=f1(i)+f2(j)+c，请推导出函数 f1、f 2和常数 c，要求 f1和 f2中不含常数项。（分数：5.00）_正确答案：(上三角矩阵第 1行有 n个元素，第 i-1行有 n-(i-1)+1个元素，第 1行到第 i-1行是等腰梯形，而第 i行上第 j个元素(即 aij)是第 i行上第 j-i+1个元素，故元素 aij在一维数组中的存储位置(下标 k)为：k=(n+

36、(n-(i-1)+1)(i-1)/2+(j-i+1)=(2n-i+2)(i-1)/2+j-i+1进一步整理为：*。则得*。)解析：此问题考查的知识点是上三角矩阵的存储方式。27.已知有一整数序列a 1，a 2，a 3，a n。栈 A中只保存整数，即序列中元素为整数时允许其入栈。设计一个算法实现如下功能：用栈结构存储入栈的整数，当 ai-1 时，将 ai进栈；当 ai=-1时，输出栈项整数并出栈。（分数：5.00）_正确答案：(#define maxsize /栈空间容量 void InOutS(int smaxsize) int top=0; /top 为栈顶指针，定义 top=0时为栈空 f

37、or(i=1; i=n; i+) /n 个整数序列作处理 scanf(“%d“, /从输入整数序列 if(x !=-1) /读入的整数不等于-1 时入栈 if(top = maxsize-1) printf(“栈满/n“); exit(0); else s+top =x; /x入栈 else /读入的整数等于-1 时退栈 if(top = 0) printf(“栈空/n“); exit(0); else printf(“出栈元素是%d/n“, stop-); )解析：28.设结点结构为(data，link)，试用一个全局指针 p和某种链接结构实现一个队列，画出示意图，并给出入队 addq和出队

38、 deleq过程，要求它们的时间复杂性都是 O(1)(不计 new和 dispose时间)。（分数：5.00）_正确答案：(本题要求用链接结构实现一个队列，可用链表结构来实现。一般说，由于队列的先进先出性质，所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针 p”，且要求入队和出队操作的时间复杂性是 O(1)，因此用只设尾指针的循环链表来实现队列。 (1)proc addq(var p:linkedlist, x:elemtp); /p是数据域为 data、链域为 link的用循环链表表示的队列的尾指针 new(s); /申请新结点。假设有内存空间，否则系统给出出错信息 s.data

39、:=x; s.link:= p.1ink; /将 s结点入队 p.link:=s:p:=s; /尾指针 p移至新的队尾 endp; (2)proc deleq(var p:linkedlist, var x:elemtp); /p是数据域为 data、链域为 link的用循环链表表示的队列的尾指针，本算法实 /现队列元素的出队，若出队成功，返回出队元素，否则给出失败信息 if(p.link = p) thenwriteln(“空队列“); retmn(0); /带头结点的循环队列 elses:=p.link.link; /找到队头元素 p.link.link:=s.link; /删队头元素 x

40、: =s.data; /返回出队元素 if(p = s) then p: =p.link; /队列中只有一个结点，出队后成为空队列 dispose(s); /回收出队元素所占存储空间 endp;)解析：上述入队算法中，因链表结构，一般不必考虑空间溢出问题，算法简单。在出队算法中，首先要判断队列是否为空，另外，对出队元素，要判断是否因出队而成为空队。否则，可能导致因删除出队结点而将尾指针删掉成为“悬挂变量”。29.判断括号是否匹配是栈的主要应用之一。设字符表达式存储在数组 En中，#为字符表达式的结束符。给出一个算法，用于判断表达式中括号(和)是否配对。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C或 C+或 Java语言描述算法，关键之处给出注释。（分数：5.00）_正确答案：(1)算法的基本思想：判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则