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); 队列不空 )解析: