1、计算机专业基础综合（栈、队列和数组）模拟试卷 1 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 栈和队列的主要区别在于( )。（A）它们的逻辑结构不一样（B）它们的存储结构不一样（C）所包含的运算不一样（D）插入和删除运算的限定不一样2 若循环队列以数组 Q0m 一 1作为其存储结构，变量 rear 表示循环队列中的队尾元素的实际位置，其移动按 rear=(rear+1)MOD m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是( )。（A）rear-length（
2、B） (rearlength+m)MOD m（C） (teat 一 length+1+m)MOD m（D）m-length3 一个以向量 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+l（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）n 一 1（
4、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）CDAEB1
5、2 对于 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)return(x0)?x
6、，x*f(x1)：2)；i=f(f(1);（A）2（B） 4（C） 8（D）无限递归16 表达式 a*(b+c)一 d 的后缀表达式是( )。（A）abcd*+一（B） abe+*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 和（D）5 和
7、 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+stop E0=x；return 1；break；case 1：Sstack一 stop1=X；return 1；退栈操作：elemtp pop(int i)if
8、(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”)；return-1 ；else return sstacks top1+；【知识模块】 栈、队列和数组27 【正确答案】 n(n+1) 2(压缩存储)或 n2(不采用压缩存储)。【知识模块】 栈、队列和数组28 【正确答案】 上三角矩阵第 1 行有 n 个元素，第 i 一 1 行有 n 一(i 一
9、1)+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 进一步整理为：【知识模块】 栈、队列和数组29 【正确答案】 #define maxsize 栈空间容量void InOutS(int smaxsize)int top=0： top 为栈顶指针，定义 top=0 时为栈空for(i=1；i=0&x=0&xj)printf(”序列非法
10、n”)；exit(0)；i+； 不论 Ai是I或O，指针 i 均后移if(j!=k)printf(”序列非法n”) ；return(false) ；elseprintf(”序列合法 n”)；return(true)；【知识模块】 栈、队列和数组36 【正确答案】 表达式中的括号有以下三对：(、)、 、 ，使用栈，当为左括号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为空，则结论表达式括号配对；否则，结论表达式括号不配对。int Match(LinkedList 1a)算术表达式存储在以 la 为头结点的单循环链表中，本算法判断括
11、号是否正确配对char s； s 为字符栈，容量足够大p=la 一link； p 为工作指针，指向待处理结点Stack Init(s)； 初始化栈 swhile(p!=la) 循环到头结点为止switch(p 一 ch)case(：push(s，p 一ch)；break；case)：if(StackEmpty(s)StackGetTop(s)!=()pfintf(”括号不配对 n”)；return(0)；else pop(S)；break；case ：push(s，p 一ch)；break ；case：if(StackEmpty(s)StackGetTop(s)!=)printf(”括号不配对
12、 n”)；return(0)；else pop(s)；break；case：push(s，P 一ch)；break：case：if(StackEmpty(s)StackGetTop(s)!=)printf(”括号不配对 n”)；return(0)；else pop(s)；break；P=p 一link；后移指针 whileif(StackEmpty(S)printf(”括号配对n”) ；return(1)； elseprintf(”括号不配对 n”)；return(0)； 【知识模块】 栈、队列和数组37 【正确答案】 栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈sl 和 s2 模
13、拟一个队列时，s1 作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈 s1 退栈并逐个压入栈 s2 中，s1 中最先入栈的元素，在 s2 中处于栈顶。s2 退栈，相当于队列的出队，实现了先进先出。显然，只有栈 s2 为空且 s1 也为空，才算是队列空。(1)int enqueue(stack sl，elemtp x)sl 是容量为 n 的栈，栈中元素类型是 elemtp。本算法将 X 入栈，若入栈成功返回 1，否则返回 0if(topl=n&!sempty(s2) topl 是栈 s1 的栈顶指针，是全局变量printf(”栈满 ”)；return(0)； sl 满 s2 非
14、空，这时 sl 不能再入栈if(topl=n&sempty(s2) 若 s2 为空，先将 sl 退栈，元素再压栈到 s2while(!sempty(s1)pop(sl，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 退栈相当于队列出队printf(”出队元素 ”，x)：(3)int queue_empty() 本算法判用栈 sI 和 s2 模拟的队列是否为空if(sempty(s1)&sempty(s2)return(1)； 队列空else return(0)； 队列不空【知识模块】 栈、队列和数组
