1、计算机专业基础综合（栈、队列和数组）-试卷 1 及答案解析(总分：76.00，做题时间：90 分钟)一、单项选择题(总题数：21，分数：42.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.栈和队列的主要区别在于( )。（分数：2.00）A.它们的逻辑结构不一样B.它们的存储结构不一样C.所包含的运算不一样D.插入和删除运算的限定不一样3.若循环队列以数组 Q0m 一 1作为其存储结构，变量 rear 表示循环队列中的队尾元素的实际位置，其移动按 rear=(rear+1)MOD m 进行，变量 length 表示当前循环
2、队列中的元素个数，则循环队列的队首元素的实际位置是( )。（分数：2.00）A.rear-lengthB.(rearlength+m)MOD mC.(teat 一 length+1+m)MOD mD.m-length4.一个以向量 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.已知输入序列为 abcd，经过输出受限的双端队列后，能得到的输出序列是( )。（分数：2.00）A.dacbB.cadbC.dbcaD.以上答案都不对7.假设一个序列 1，2，3，n 依次进栈，如果出栈的第一个元素是 n，那么第 i(1in)个出栈的元素是( )。（分数：2.00）A.不确定B.n-i+lC.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.现有两栈，其共享空间为 V1m，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.
6、递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分16.执行完下列语句段后，i 值为( )。 int f(int x)return(x0)?x，x*f(x1)：2)； i=f(f(1);（分数：2.00）A.2B.4C.8D.无限递归17.表达式 a*(b+c)一 d 的后缀表达式是( )。（分数：2.00）A.abcd*+一B.abe+*dC.abc*+dD.一+*abcd18.为了处理参数及返回地址，在递归过程或函数调用时，要用一种称为( )的数据结构。（分数：2.00）A.队列B.多维数组C.栈D.线性表19.若用一个大小为 6 的数组来实现循环队列，且当前 rear 和
7、front 的值分别为 0 和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为( )。（分数：2.00）A.1 和 5B.2 和 4C.4 和D.5 和 120.队尾已到达一维数组的最高下标，不能再插入元素，然而队中元素个数小于队列的长度，这种现象称作( )。（分数：2.00）A.上溢B.下溢C.假溢出D.队列满21.已知有一维数组 A0mn 一 1，若要对应为 m 行、n 列的矩阵，将元素 Ak(0k0)?x，x*f(x1)：2)； i=f(f(1);（分数：2.00）A.2B.4 C.8D.无限递归解析：解析：此题考查的知识点是递归算法的分析。根据题意可
8、计算 f(0)=2，f(1)=2，f(2)=4，所以选B。17.表达式 a*(b+c)一 d 的后缀表达式是( )。（分数：2.00）A.abcd*+一B.abe+*d C.abc*+dD.一+*abcd解析：解析：此题考查的知识点是利用栈完成表达式的中后缀转换。顺序扫描表达式，操作数顺序输出，而运算符的输出顺序根据算术运算符的优先级确定。保证栈外运算符优先级比栈内低，若高则入栈，否则出栈输出。本题中输出顺序为 a 输出，*进栈，(进栈，b 输出，+进栈，c 输出，此时)低于+，所以“+”输出。“)”与“(”相等，出栈删除，一低于*，所以*出栈，此时输出序列为 abe+*，一入栈，输出 d，输
9、出一，结束。所以选 B。18.为了处理参数及返回地址，在递归过程或函数调用时，要用一种称为( )的数据结构。（分数：2.00）A.队列B.多维数组C.栈 D.线性表解析：解析：此题考查的知识点是栈的应用。要处理参数及返回地址，需要后进先出规则，应选 C。A 是先进先出规则，B 是普通的存储结构，D 是普通的逻辑结构。19.若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为( )。（分数：2.00）A.1 和 5B.2 和 4 C.4 和D.5 和 1解析：解析：此题考
10、查的知识点是队列的特征。此题考查顺序存取时的位置计算，按顺时针计算，所以删除 front+l，插入 rear+1，计算后 rear=2，front=4，应选 B。20.队尾已到达一维数组的最高下标，不能再插入元素，然而队中元素个数小于队列的长度，这种现象称作( )。（分数：2.00）A.上溢B.下溢C.假溢出 D.队列满解析：解析：解析：用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质(队尾插入和队头删除)，容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数却小于队列的长度(容量)。21.已知有一维数组 A0mn 一 1，若要对应为 m 行、n 列的矩
11、阵，将元素 Ak(0k=0 (3)queue_empty：判队列为空。(请写明算法的思想及必要的注释。)（分数：2.00）_正确答案：(正确答案：栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈 sl 和 s2 模拟一个队列时，s1 作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈 s1 退栈并逐个压入栈 s2 中，s1 中最先入栈的元素，在 s2 中处于栈顶。s2 退栈，相当于队列的出队，实现了先进先出。显然，只有栈 s2 为空且 s1 也为空，才算是队列空。 (1)int enqueue(stack sl，elemtp x) sl 是容量为 n 的栈，栈中元素类型
12、是 elemtp。本算法将 X 入栈， 若入栈成功返回 1，否则返回 0 if(topl=n&!sempty(s2) topl 是栈 s1 的栈顶指针，是全局变量 printf(”栈满”)；return(0)； sl 满 s2 非空，这时 sl 不能再入栈 if(topl=n&sempty(s2) 若 s2 为空，先将 sl 退栈，元素再压栈到 s2 while(!sempty(s1)pop(sl，x)；push(s2，x)； push(sl，x)：return(1)； x入栈，实现了队列元素的入队 (2)void dequeue(stack s2，s1) s2 是输出栈，本算法将 s2 栈项
13、元素退栈，实现队列元素的出队 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)； 队列不空 )解析：
