1、计算机专业基础综合数据结构（栈、队列和数组）模拟试卷 1 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 栈和队列的主要区别在于( )。（A）它们的逻辑结构不一样（B）它们的存储结构不一样（C）所包含的运算不一样（D）插入和删除运算的限定不一样2 若循环队列以数组 Q0.，m1作为其存储结构，变量 rear 表示循环队列中的队尾元素的实际位置，其移动按 rear=(rear+1)MOD m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是( )。（A）reat 一 le
2、ngth（B） (rearlength+m)MOD m（C） (rearlength+1+m)MOD m（D）mlength3 一个以向量 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 一 14 为了增加内存空间的利用率和减少溢出的可能性，两个栈可以共享一片连续的内存空间，此时应将两栈的栈底分别设在( )。（A）内存空间的首地址（B）内存空间的尾地址（C）内存空间的两端（D）内存空间的中间5 已
3、知输入序列为 abed，经过输出受限的双端队列后，能得到的输出序列是( )。（A）daeb（B） eadb（C） dbea（D）以上答案都不对6 假设一个序列 1，2，3，n 依次进栈，如果出栈的第一个元素是 n，那么第i(1in)个出栈的元素是( )。（A）不确定（B） ni+1（C） i（D）ni7 假设一个序列 1，2，3，n 依次进栈，如果第一个出栈的元素是 i，那么第 j个出栈的元素是( ) 。（A）i-j 一 1（B） i-j（C） j-i+1（D）不确定的8 已知当前栈中有 n 个元素，此时如果有新的元素需要执行进栈操作，但发生上溢，则由此可以判断，此栈的最大容量为( )。（A）
4、n 一 1（B） n（C） n+1（D）n29 设有 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，e10 有 6 个元素按 6，5，4，3，2，1 的顺序依次进栈，不合法的出栈序列是( )。（A）543612（B） 453126（C） 346521（D）23415611 有 5 个元素，其入栈次序为 A，B，C，D，E，在各种可能的出栈次序中，以元素 C，D 最先出栈的次序不包括( )。（A）CDEBA（B） CDBEA（C） CDBAE（D）
5、CDAEB12 对于 4 个元素依次进栈，可以得到( )种出栈序列。（A）10（B） 12（C） 14（D）1613 现有两栈，其共享空间为 V1,m，topi 代表第 i 个栈(i=1 ，2) 栈顶，栈 1 的底在 V1，栈 2 的底在 Vm，若两栈均采用顺序存储方式存储，则栈满的条件是( )。（A）|top2-top1|=0（B） top1+1=top2（C） top1+top2=m（D）top1=top214 一个递归算法必须包括( )。（A）递归部分（B）终止条件和递归部分（C）迭代部分（D）终止条件和迭代部分15 执行完下列语句段后，i 值为( )。int f(int x) retu
6、rn(x0)?x*f(x1)：2)； i=f(f(1)；（A）2（B） 4（C） 8（D）无限递归16 表达式 a*(b+c)一 d 的后缀表达式是( )。（A）abcd*+一（B） abc+*d（C） abc*+d（D）一+*abcd17 为了处理参数及返回地址，在递归过程或函数调用时，要用一种称为( )的数据结构。（A）队列（B）多维数组（C）栈（D）线性表18 若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为( )。（A）1 和 5（B） 2 和 4（C） 4
7、和 2（D）5 和 119 队尾已到达一维数组的最高下标，不能再插入元素，然而队中元素个数小于队列的长度，这种现象称作( )。（A）上溢（B）下溢（C）假溢出（D）队列满20 已知有一维数组 A0.，mn 一 1，若要对应为 m 行、n 列的矩阵，将元素 Ak(0kmn)表示成矩阵的第 i 行、第 j 列的元素(0im ，0jn)，则下面的对应关系是( ) 。（A）i=k n ，j=k m（B） i=km，j=km（C） i=kn，j=kn（D）i=k m ，j=k n二、综合应用题41-47 小题，共 70 分。21 简述栈、队列、循环队列的定义。22 假设以 I 和 O 分别表示入栈和出栈
8、操作，则对初态和终态均为空的栈操作可由I 和 O 组成的序列表示。(1)试指出判别给定序列是否合法的一般规则。(2)两个不同合法序列 (对同一输入序列) 能否得到相同的输出元素序列?如能得到，请举例说明。23 有 5 个元素，其入栈次序为 A，B，C，D，E，在各种可能的出栈次序中，以元素 C，D 最先出栈(即 C 第一个且 D 第二个出栈)的次序有哪几个?24 为了增加内存空间的利用率和减少溢出的可能性，通常采用两个栈利用同一块存储空间的方法。通常两个栈的栈底设在内存空间的两端，而栈顶相向，迎面增长。已知有两个栈 s1、s2 都采用顺序栈方式，并且共享一个存储区0maxsize1。设计共享存
9、储空间的两个栈 s1、s2 的入栈和出栈算法。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释；25 一个 nn 的对称矩阵，如果以行或列为主序存入内存，则其容量为多少?26 设有一个 nn 的上三角矩阵(a ij)，将其上三角中的元素按先行后列的顺序存于数组 Bm中，使得 Bk=aij 且 k=f1(i)+f2(j)+c，请推导出函数 f1、f 2 和常数 c，要求 f1和 f2 中不含常数项。27 已知有一整数序列a 1，a 2，a 3，a n。栈 A 中只保存整数，即序列中元素为整数时允许其入栈。设计一个算法实现如下功
10、能：用栈结构存储入栈的整数，当ai一 1 时，将 ai 进栈；当 ai=一 1 时，输出栈顶整数并出栈。28 设结点结构为(data，link)，试用一个全局指针 p 和某种链接结构实现一个队列，画出示意图，并给出入队 addq 和出队 deleq 过程，要求它们的时间复杂性都是O(1)(不计 new 和 dispose 时间)。29 判断括号是否匹配是栈的主要应用之一。设字符表达式存储在数组 En中，#为字符表达式的结束符。给出一个算法，用于判断表达式中括号(和) 是否配对。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释
11、。30 从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔，操作符只可能有+、一、*、四种运算，例如：23434+2*$。31 假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由 I 和 O 组成的序列，称可以操作的序列为合法序列，否则称为非法序列。(1)下面所示的序列中哪些是合法的?AIOIIOIOO BIOOIOIIO CIIIOIOIO DIIIOOIOO(2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回 true，否则返回 fals
12、e(假定被判定的操作序列已存入一维数组中 )。32 设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch 和 link，其中 ch 域为字符类型。33 请利用两个栈 s1 和 s2 来模拟一个队列。已知栈的三个运算定义如下：(1)push(st，X) ：元素 X 入 st 栈：(2)pop(st， X)：st 栈顶元素出栈，赋给变量 X：(3)sempty(st)：判 st 栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：(1)enqueue：插入一个元素入队列；(2)dequeue：删除一个元素出队列：(3)queueemp
13、ty：判队列为空。(请写明算法的思想及必要的注释。)计算机专业基础综合数据结构（栈、队列和数组）模拟试卷 1 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 栈和队列的逻辑结构都是线性的，都有顺序存储和链式存储，有可能包含的运算不一样，但不是其主要区别。任何数据结构在针对具体问题时所包含的运算都可能不同。所以正确答案是 D。【知识模块】 数据结构2 【正确答案】 C【试题解析】 按照循环队列的定义，因为元素移动按照 rear=(rear+1)MOD m 进行，则当数组 Qm1存放了
14、元素之后，下一个入队的元素将存放到 QO中，因此队列的首元素的实际位置是(rearlength+1+m)MOD m。【知识模块】 数据结构3 【正确答案】 C【试题解析】 此题考查的知识点是入栈的具体操作。操作时要看栈顶的地址，先取得空间，再入栈。本题栈项为 n+1，应该用减法，所以选 C。D 是先存入，破坏原有数据，所以错。【知识模块】 数据结构4 【正确答案】 C【试题解析】 两个栈共享一个内存空间时，需要把两个栈的栈底设在内存空间的两端。【知识模块】 数据结构5 【正确答案】 B【试题解析】 输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。分析选项 A，输入序列为
15、abcd，输出序列为 dacb，由输出受限性质可知以 da开头的结果只有 dabc，选项 A 为错误答案。分析选项 B，输入序列为 abcd，输出序列为 cadb，其输入输出顺序为：先在输出端输入 a，然后在非输出端输入 b，这时队列中的序列为 ba。再在输出端输入c，这时队列中的序列为 bac；输出 c，再输出 a；再在输出端输入 d，这时队列中的序列为 bd；输出 d，再输出 b。最后得到输出序列为 cadb。分析选项 C，输入序列为 abcd，输出序列为 dbca，由输出受限性质可知以 db开头的结果只有 dbac，选项 C 为错误答案。【知识模块】 数据结构6 【正确答案】 B【试题解
16、析】 进栈的顺序是：1，2，n，且出栈的第一个元素是 n，那么根据栈后进先出的特点可知，出栈的顺序依次为：n，2，1，那么第 ni+1 个出栈元素就是第 i 个进栈的元素。【知识模块】 数据结构7 【正确答案】 D【试题解析】 此题考查的知识点是栈的后进先出特点。若输出序列的第一个元素是 i，只能说明前 i1 个元素均入栈，而第 j 个元素何时入、出栈并不能确定，所以选 D。【知识模块】 数据结构8 【正确答案】 B【试题解析】 由于栈中有 n 个元素是执行进栈操作，但是发生上溢，则说明此栈中最多可以包含 n 个数据元素，即栈的最大容量为 n。【知识模块】 数据结构9 【正确答案】 C【试题解
17、析】 由进栈出栈规则可知，对于 a，b，c，d，e 顺序进栈的五个元素，A、B、D 均为可能的出栈序列，所以选 C。【知识模块】 数据结构10 【正确答案】 C【试题解析】 此题考查的知识点是栈的后进先出特点。考查出栈序列，要保证先入栈的一定不能在后入栈的前面出栈，C 选项中的 6 在 5 前入栈，5 没有出栈，6却出栈了，所以不合法。其他都符合规律。所以选 C。【知识模块】 数据结构11 【正确答案】 D【试题解析】 以元素 C，D 最先出栈的次序有三个：CDEBA、CDBEA、CDBAE。【知识模块】 数据结构12 【正确答案】 C【试题解析】 n 个入栈元素可得到 种出栈序列。本题 4
18、个元素，可有 14种出栈序列。【知识模块】 数据结构13 【正确答案】 B【试题解析】 此题考查的知识点是入栈的具体操作。判断栈是否满要看两个栈顶是否相邻，当 top1+1=top2或 top2一 1=top1时都表示栈满，所以选 B，而A，C 没有任何意义。D 表示已经出现覆盖了，也是错的。【知识模块】 数据结构14 【正确答案】 B【试题解析】 此题考查的知识点是递归算法的组成部分。一个递归算法主要包括终止条件和递归部分，所以选 B。A 不全面，C、D 不是递归算法。【知识模块】 数据结构15 【正确答案】 B【试题解析】 此题考查的知识点是递归算法的分析。根据题意可计算 f(0)=2，
19、f(1)=2，f(2)=4 ，所以选 B。【知识模块】 数据结构16 【正确答案】 B【试题解析】 此题考查的知识点是利用栈完成表达式的中后缀转换。顺序扫描表达式，操作数顺序输出，而运算符的输出顺序根据算术运算符的优先级确定。保证栈外运算符优先级比栈内低，若高则入栈，否则出栈输出。本题中输出顺序为 a 输出，*进栈，(进栈，b 输出，+进栈，c 输出，此时 )低于+，所以“+”输出。“)”与“(”相等，出栈删除，一低于*，所以*出栈，此时输出序列为 abc+*，一入栈，输出 d，输出一，结束。所以选 B。【知识模块】 数据结构17 【正确答案】 C【试题解析】 此题考查的知识点是栈的应用。要处
20、理参数及返回地址，需要后进先出规则，应选 c。A 是先进先出规则，B 是普通的存储结构，D 是普通的逻辑结构。【知识模块】 数据结构18 【正确答案】 B【试题解析】 此题考查的知识点是队列的特征。此题考查顺序存取时的位置计算，按顺时针计算，所以删除 front+1，插入 rear+1，计算后 rear=2，front=4，应选Bo【知识模块】 数据结构19 【正确答案】 C【试题解析】 用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质(队尾插入和队头删除) ，容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数却小于队列的长度(容量)。【知识模块】 数
21、据结构20 【正确答案】 C【试题解析】 本题是求一维数组向二维数组转化的问题。最简单的方法是把数组A 的第 0n 一 1 共 n 个元素放到数组 B 的第一行，数组 A 的第 n 一 2n 一 1 共 n个元素放到数组 B 的第二行中，依此类推，数组 A 的最后 n 个元素放到数组 B 的最后一行中。求 Ak在数组 B 中的位置，应先确定 Ak处在哪一行，显然应该是 kn 行；然后再确定处在 kn ，行的哪一列，显然是 kn。【知识模块】 数据结构二、综合应用题41-47 小题，共 70 分。21 【正确答案】 (1)栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一
22、端叫栈底。最后插入的元素最先删除，故栈也称后进先出(LiFO)表。(2)队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开(删除)，故队列也常称先进先出(FIFO)表。(3)循环队列是解决 “假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“ 牺牲一个存储单元 ”或“作标记”的方法解决“ 队满”和“ 队空”的判定问题。【知识模块】 数据结构22 【正确答案】 (1)通常有两条规则。第一是给定序列中 I 的个数和 O 的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，I 的个数要大于或等于 O 的个数。
23、(2)可以得到相同的输出元素序列。例如，输入元素为 A，B，C，则两个输入的合法序列 ABC 和 BAC 均可得到输出元素序列 ABC 对于合法序列 ABC，我们使用本题约定的 IOIOIO 操作序列；对于合法序列 BAC，我们使用 IIOOIO 操作序列。【知识模块】 数据结构23 【正确答案】 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
24、都出栈后，E 再入栈出栈，得序列 C，D，B ，A，E。只有这三种情况。【知识模块】 数据结构24 【正确答案】 (1)栈 s1、s2 共享向量空间，将两栈栈底设在向量两端。初始时，s1 栈顶指针为一 1，s2 栈项为 maxsize。两栈项指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈项元素。(2)算法设计如下：#define maxsize 两栈共享顺序存储空间所能达到的最多元素数#define elemtp int 假设元素类型为整型typedef structelemtp stackmaxsize；栈空间int top2； top 为两个栈顶指针stk；stk s； s 是如上
25、定义的结构类型变量，为全局变量入栈操作：int push(int i，int x) A 栈操作。i 为栈号，i=0 表示左边的栈 sl，i=l 表示右边的栈 s2，X 是入栈元素。入栈成功返回 1，否则返回 0if(i0 | i 1)printf(”栈号输入不对”) ；exit(0)； if(s top1一 stop0=1)printf(栈已满n”)；return(0) ； switch(i)case 0：sstack+stop0=X；return 1；break；case 1：sstack一一 stop1=X；return 1；退栈操作：elemtp pop(int i)if(i0 | i
26、1)printf(”栈号输入错误n”) ；exit(0)；switch(i)case 0：if(stop0=一 1)printf(”栈空n”)；return 一 1；else return sstacks top0-；case l：if(stop1=maxsize)printf(”栈空n”)；return1；else return sstacks top1+；【知识模块】 数据结构25 【正确答案】 n(n+1) 2(压缩存储)或 n2(不采用压缩存储)。 提示：此问题考查的知识点是数组的存放问题。对称矩阵可以只存上三角或下三角。所用空间为1，2，3，n 之和。【知识模块】 数据结构26 【正
27、确答案】 上三角矩阵第 1 行有 n 个元素，第 il 行有 n 一(i1)+1 个元素，第 1 行到第 i 一 1 行是等腰梯形，而第 i 行上第 j 个元素( 即 aij)是第 i 行上第 j 一i+1 个元素，故元素 aij 在一维数组中的存储位置(下标 k)为： k=(n+(n 一(i1)+1)(i1)2+(j-i+1)=(2n i+2)(i 一 1)2+j 一 i+1【知识模块】 数据结构27 【正确答案】 #define maxsize 栈空间容量void InOutS(int Smaxsize)int top=0； top 为栈顶指针，定义 top=0 时为栈空for(i=1；i
28、 =n；i+) n 个整数序列作处理SCanf(”d” ， j 和 k 分别为 I 和字母 0 的个数while(Ai!=0)switch(Ai)caseI：j+；break；入栈次数增 1case0；k+ ；if(kj)printf(”序列非法n”) ；exit(0)；i+i 不论 Ai是I或0，指针 i 均后移if(j!=k)printf(”序列非法n”) ；return(false) ；elseprintf(”序列合法 n”)；return(true)：提示：在入栈出栈序列(即由I 和0组成的字符串) 的任一位置，入栈次数(I的个数)都必须大于等于出栈次数(即0 的个数)，否则视作非法序
29、列，立即给出信息，退出算法。整个序列(即读到字符数组中字符串的结束标记0)，入栈次数必须等于出栈次数(题目中要求栈的初态和终态都为空)，否则视为非法序列。【知识模块】 数据结构32 【正确答案】 表达式中的括号有以下三对：(、)、 、 ，使用栈，当为左括号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为空，则结论表达式括号配对；否则，结论表达式括号不配对。int Match(LinkedList la)算术表达式存储在以 la 为头结点的单循环链表中，本算法判断括号是否正确配对char S； s 为字符栈，容量足够大P=la 一l
30、ink ； p 为工作指针，指向待处理结点Stack Init(S)； 初始化栈 swhile(P!=la) 循环到头结点为止switch(p-ch)case(：push(s，p-ch)；break；case)：if(StackEmpty(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；
31、case：push(s，p-ch)；break；case：if(StackEmpty(s)II StackGetTop(s)!=)printf(”括号不配对 n”)；return(0)；else pop(s)：break；P=p-link；后移指针 whileif(StackEmpty(s)f printf(“括号配对n“)；return(1)； elseprintf(”括号不配对 n”)；return(0)； 【知识模块】 数据结构33 【正确答案】 栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1 和 s2 模拟一个队列时，s1 作输入栈，逐个元素压栈，以此模拟队列元素的入队。
32、当需要出队时，将栈 s1 退栈并逐个压入栈 s2 中，s1 中最先入栈的元素，在 s2 中处于栈顶。s2 退栈，相当于队列的出队，实现了先进先出。显然，只有栈 s2 为空且 s1 也为空，才算是队列空。(1)int enqueue(stack S1，elemtp X)s1 是容量为 n 的栈，栈中元素类型是 elemtp。本算法将 x 入栈，若入栈成功返回 1，否则返回 0if(topl=n&!sempty(s2) top1 是栈 s1 的栈顶指针，是全局变量printf(”栈满 ”)；retum(0)； s1 满 s2 非空，这时 s1 不能再入栈if(topl=n&sempty(s2) 若
33、 s2 为空，先将 s1 退栈，元素再压栈到 s2while(!sempty(s1)pop(s1，x)；push(s2，x)；push(sl，x)：return(1) ； x 入栈，实现了队列元素的入队(2)void dequeue(stack s2，s1)s2 是输出栈，本算法将 s2 栈顶元素退栈，实现队列元素的出队if(!sempty(s2) 栈 s2 不空，则直接出队pop(s2，x)；printf(” 出队元素为 ”，x)；else 处理 s2 空栈if(sempty(s1)printf(”队列空 ”)；exit(0)； 若输入栈也为空，则判定队空else 先将栈 s1 倒入 s2 中，再作出队操作 while(!sempty(s1)pop(sl，x)；push(s2，x)；pop(s2，x) ； s2 退栈相当于队列出队pfinff(”出队元素 ”，x)；(3)int queueempty() 本算法判用栈 s1 和 s2 模拟的队列是否为空if(sempty(s1)&sempty(s2)return(1)； 队列空else return(0)： 队列不空【知识模块】 数据结构
