1、计算机专业基础综合（栈、队列和数组）模拟试卷 2 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 栈和队列的主要区别在于( )。（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）nlength3 一个以向量 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、 abcd，经过输出受限的双端队列后，能得到的输出序列是 ( )。（A）dacb（B） cadb（C） dbca（D）以上答案都不对6 假设一个序列 1，2，3，n 依次进栈，如果出栈的第一个元素是 n，那么第i(1in)个出栈的元素是( )。（A）不确定（B） n-i+1（C） i（D）n-i7 假设一个序列 1，2，3，n 依次进栈，如果第一个出栈的元素是 i，那么第 j个出栈的元素是( ) 。（A）i 一 j 一 1（B） i 一 j（C） j 一 i+1（D）不确定的8 已知当前栈中有 n 个元素，此时如果有新的元素需要执行进栈操作，但发生上溢，则由此可以判断，此栈的最大容量为( )。
4、（A）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 现有两栈，其共享空间为 V1m，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)retur
6、n(x0)?x*f(x 一 1)：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）
7、 4 和 2（D）5 海外 119 队尾已到达一维数组的最高下标，不能再插入元素，然而队中元素个数小于队列的长度，这种现象称作( )。（A）上溢（B）下溢（C）假溢出（D）队列满20 已知有一维数组 A0mn 一 1，若要对应为 m 行、n 列的矩阵，将元素Ak(0k1)printf(“栈号输入不对 ”)；exit(0)； if(stop1一 stop0=1)printf(“栈已满n”)；return(0)； switch(i)case 0： sstack+stop0=x；return 1；break；case 1： sstack一一 stop1=x；return 1；退栈操作：elemtp
8、pop(int i)if(i1)printf(“栈号输入错误 n”)；exit(0)；switch(i)case 0：if(s top0=一 1)printf(“栈空n”)；return 一 1；else return sstacks top0一一 ；case 1：if(s top1=maxsize)printf(“栈空n”)；return1；else return sstacks top1+；【知识模块】 栈、队列和数组25 【正确答案】 n(n+1) 2(压缩存储)或 n2(不采用压缩存储)。 提示：此问题考查的知识点是数组的存放问题。对称矩阵可以只存上三角或下三角。所用空间为1，2，3，
9、n 之和。【知识模块】 栈、队列和数组26 【正确答案】 上三角矩阵第 1 行有 n 个元素，第 il 行有 n 一(i1)+1 个元素，第 1 行到第 i 一 1 行是等腰梯形，而第 i 行上第 j 个元素( 即 aij)是第 i 行上第 j 一i+1 个元素，故元素 aij 在一维数组中的存储位置(下标 k)为： k=(n+(n 一(i 一 1)+1)(i 一 1)2+(j 一 i+1)=(2n 一 i+2)(i 一 1)2+j-i+1 进一步整理为：则得 f2(j)=jc=-n。提示：此问题考查的知识点是上三角矩阵的存储方式。【知识模块】 栈、队列和数组27 【正确答案】 #define
10、 maxsize 栈空间容量void InOutS(int smaxsize)int top=0； top 为栈项指针，定义 top=0 时为栈空for(i=1；i=0&x=0&xj)printf(“序列非法n”)；exit(0) ；i+； 不论 Ai是I或O，指针 i 均后移if(j!=k)prjntf(“序列非法n”) ；return(false) ；elseprintf(“序列合法 n”)；return(true)；提示：在入栈出栈序列(即由I 和O组成的字符串)的任一位置，入栈次数(I的个数)都必须大于等于出栈次数(即O 的个数)，否则视作非法序列，立即给出信息，退出算法。整个序列(即
11、读到字符数组中字符串的结束标记O)，入栈次数必须等于出栈次数(题目中要求栈的初态和终态都为空)，否则视为非法序列。【知识模块】 栈、队列和数组32 【正确答案】 表达式中的括号有以下三对：(、)、 、 ，使用栈，当为左括号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为空，则结论表达式括号配对：否则，结论表达式括号不配对。int Match(LinkedList la)算术表达式存储在以 la 为头结点的单循环链表中，本算法判断括号是否正确配对char s； s 为字符栈，容量足够大p=la 一link； p 为工作指针，指向待处
12、理结点stack Init(s)； 初始化栈 swhile(p!=la) 循环到头结点为止switch(p 一ch)case(：pLish(s，p 一ch) ；break；case)：if(StackEmpry(s)|StackGetTop(s)!=()printf(”括号不配对n”)；return(0)；else pop(s)；break；case：push(S ，p-ch) ；break；case：if(StackEmpty(s)llStackGetTop(S)!=)printf(“括号不配对n”)；retum(0)；else pop(s)；break；case：push(s，p-ch)
13、； break；case：if(StackEmpty(s)|StackGetTop(S)!=)printf(“括号不配对n”)；retum(0)；else pop(s)；break； p=p 一link ；后移指针 whileif(StackEmpty(s) printf(“括号配对n”) ；return(1) ； else printf(“括号不配对 n”)；return(0)； 提示：算法中对非括号的字符未加讨论。遇到右括号时，若栈空或栈顶元素不是其对应的左圆(方、花) 括号，则结论括号不配对，退出运行。最后，若栈不空，结论仍是括号不配对。【知识模块】 栈、队列和数组33 【正确答案】 栈
14、的特点是后进先出，队列的特点是先进先出。所以，用两个栈sl 和 s2 模拟一个队列时，s1 作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈 s1 退栈并逐个压入栈 s2 中，s1 中最先入栈的元素，在 s2 中处于栈顶。s2 退栈，相当于队列的出队，实现了先进先出。显然，只有栈 s2 为空且 s1 也为空，才算是队列空。(1)int enqueue(stack s1，elemtp x)s1 是容量为 n 的栈，栈中元素类型是 elemtp。本算法将 x 入栈，若入栈成功返回 1，否则返回 0if(top1=n&!sempty(s2) top1 是栈 s1 的栈顶指针，是全局
15、变量printf(“栈满”) ；return(0)； s1 满 s2 非空，这时 s1 不能再入栈if(top1=n&sempty(s2) 若 s2 为空，先将 s1 退栈，元素再压栈到 s2while(!sempty(s1)pop(s1，x)；push(s2，x)；push(s1，x)；return(1)； x 入栈，实现了队列元素的入队(2)void dequeue(stack s2，s1)s2 是输出栈，本算法将 s2 栈顶元素退栈，实现队列元素的出队if(!sempty(s2) 栈 s2 不空，则直接出队 pop(s2，x) ； printf(“ 出队元素为” ，x)；else 处理
16、s2 空栈if(sempty(s1)printf(“队列空”) ；exit(0)； 若输入栈也为空，则判定队空else 先将栈 s1 倒入 s2 中，再做出队操作 while(!sempty(s1)pop(s1，x)；push(s2，x)；pop(s2，x)； s2 退栈相当于队列出队printf(“出队元素”，x)；(3)int quelle_empty() 本算法判用栈 s1 和 s2 模拟的队列是否为空if(sempty(s1)&sempty(s2)return(1)； 队列空else return(0)； 队列不空提示：算法中假定栈 s1 和栈 s2 容量相同。出队从栈 s2 出，当 s2 为空时，若 s1不空，则将 s1 倒入 s2 再出栈。入队在 s1，当 s1 满后，若 s2 空，则将 s1 倒入s2，之后再入队。因此队列的容量为两栈容量之和。元素从栈 s1 倒入 s2，必须在s2 空的情况下才能进行，即在要求出队操作时，若 s2 空，则不论 s1 元素多少(只要不空)，就要全部倒入 s2 中。【知识模块】 栈、队列和数组
