1、全国自考数据结构导论（栈和队列）模拟试卷 1 及答案与解析一、单项选择题1 栈的顺序表示中，用 top 表示栈顶指针，那么栈空的条件是 _。（A）top=STACKSIZE（B） top=1（C） top=0（D）top=12 一个栈的人栈序列为“abcde”，则以下不可能的出栈序列是 _。（A）bcdae（B） edacb（C） bcade（D）aedcb3 链栈与顺序栈相比，有一个较明显的优点是( )。（A）通常不会出现栈满的情况（B）通常不会出现栈空的情况（C）插入操作更加方便（D）删除操作更加方便4 从栈顶指针为 top 的链栈中删除一个结点，并将被删结点的值保存到 m 中，其操作步骤
2、为_。（A）m=top 一data ；top=top 一next；（B） top=top 一next ；m=top 一data；（C） m=top；top=top 一next；（D）m=top 一data ；5 设有一顺序栈已含 3 个元素，如下图所示，元素 a4 正等待进栈。那么下列 4 个序列中不可能出现的出栈序列是_。（A）a3，a1，a4，a2（B） a3，a2 ，a4 ，a1（C） a3，a4 ，a2 ，a1（D）a4，a3,a2,a16 一个队列的入队序列是“d1，d2，d3，d4，” 则队列的出队顺序是 _（A）d4，d3，d2，d1（B） d1，d2，d3，d4（C） d1，d
3、4，d3，d2（D）d3，d2，d4，d17 假定一个循环队列的队头和队尾指针分别为 P 和 q，则判断队空的条件为_。（A）p=0（B） p+1=q（C） q+1=p（D）p=q8 若以数组 a8存放循环队列的元素，且当前队尾指针 rear 的值为 0，队头指针front 的值为 3。当从队列中出队两个元素，再人队一个元素后，rear 和 front 的值分别为_-。（A）7 和 1（B） 1 和 7（C） 5 和 1（D）1 和 59 若以数组 ak存放循环队列的元素，则当循环队列满时，队列中有_个元素。（A）2k（B） k+1（C） k（D）k 一 110 设数组 A0，m 作为循环队列
4、 sq 的存储空间，front 为队头指针，rear 为队尾指针，则执行入队操作的语句是_。（A）sqfront=(sq front+1)m（B） sqfront=(sqfront+1)(m+1)（C） sqrear=(sqrear+1)m（D）sqrear=(sqrear+1)(m+1)11 若链队列的队头指针和队尾指针分别为 front 和 rear，则从队列中删除一个结点的操作是_。（A）p=front；rear=p 一next ；free(p)；（B） p=rear；front=p；free(p)；（C） p=front；front=P 一next ；free(p)；（D）p=rear
5、；front=P 一next；free(p) ；12 输入序列为 ABC，要变为 CBA，经过的栈操作为 _。（A）push，pop，push，pop，push，pop（B） push， push，push，pop，pop，pop（C） push， push，pop，pop，push ，pop（D）push，pop，push，push，pop，pop13 设有一顺序栈 S，元素 S1，S2，S3，S4，s5， S6 依次进栈，如果 6 个元素出栈的顺序是 s2，s3，S4 ，S6，s5，s1，则栈的容量至少应该是_。（A）2（B） 3（C） 4（D）514 如果以链表作为栈的存储结构，则退栈操
6、作时_。（A）必须判别栈是否满（B）判别栈元素的类型（C）必须判别栈是否空（D）对栈不作任何判别15 前缀表达式“ 一 2+86 3”的运算结果是_ 。（A）1（B） 4（C） 8（D）16二、填空题16 栈的逻辑特点是_，队列的逻辑特点是_；二者的共同点是只允许在它们的_处插入和删除数据元素；其中_可以作为实现递归函数调用的一种数据结构。17 允许在一端插入，在另一端删除的线性表称为_。插入的一端为_，删除的一端为_。18 在一个循环队列 Q 中，判断队空的条件为_ ，判断队满的条件为_。19 判别循环队列空和满的方法有_、_和_。20 已知用数组 sq50存放循环队列的元素，且头指针和尾指
7、针分别为 19 和 2，则该队列的当前长度为_。21 对带有头结点的链队列 lq，判定队列中只有一个数据元素的条件是 _。22 已知链队列 Q 的头、尾指针分别是 front 和 rear，则出队操作是：p=Q 一front；_ ；free(p)。23 一般情况下，将递归算法转化成等价的非递归算法应该设置_。24 对于栈和队列，无论它们采用顺序存储结构还是链式存储结构，进行插入和删除操作的时间复杂度都是_。25 表达式 d(bc)+a 的后缀表达式是_。三、应用题26 从现实生活中举例说明栈和队列的特征。27 举例说明栈的“ 上溢” 、 “下溢”现象以及顺序队的 “假溢出”现象。28 设有编号
8、为 A，B，C，D 的四辆列车，顺序进入一个栈式结构的站台，试写出这四辆列车开出车站的所有可能的顺序。29 对下列函数，画出调用 f(5)时引起的工作栈状态变化情况。int f(int i)if(n=1)return(10)；elsereturn(f(i 一 1)+2)；30 借助栈(可用栈的基本运算)来实现单链表上的逆置运算。31 用一个循环单链表表示队列，该队列只设一个队尾指针 rear,不设队首指针。试编写算法，完成入队、出队操作。32 试写出一个判别表达式中开、闭括号是否配对出现的算法。33 在栈顶指针为 HS 的链栈中，写出计算该链栈中结点个数的函数。34 设从键盘输入一整数的序列：
9、a 1，a 2，a 3，a n，试编写算法实现：用栈结构存储输入的整数，当 ai一 1 时，将 ai 进栈；当 ai=一 1 时，输入栈顶整数并出栈。算法应对异常情况(如栈满等)给出相应的信息。35 如果希望循环队列中的元素都能得到利用，则需要设置一个标志域 tag，并以tag 的值为 0 或 1 来区分尾指针和头指针值相同时的队列状态是“空” 还是“满”。试编写与此结构相应的入队列和出队列的算法。全国自考数据结构导论（栈和队列）模拟试卷 1 答案与解析一、单项选择题1 【正确答案】 D【知识模块】 栈和队列2 【正确答案】 B【知识模块】 栈和队列3 【正确答案】 A【试题解析】 不管是链栈
10、还是顺序栈，其插入、删除操作都是在栈顶进行的，都比较方便，所以不可能选 C，D。对链栈来讲，当栈中没有元素而又要执行出栈操作时，就会出现栈空现象，故 B 也是不正确的。只要内存足够大，链栈上就不会出现栈满现象。而对顺序栈来讲，由于其大小是事先确定好的，因此可能会出现栈满现象。所以 A 是正确的。【知识模块】 栈和队列4 【正确答案】 A【试题解析】 本操作是链栈上的出栈操作，操作顺序应该是先保存被删结点的值，然后再改变栈顶指针的值。【知识模块】 栈和队列5 【正确答案】 A【试题解析】 由于 a1，a2，a3 已进栈，不管 a4 何时进栈，出栈后，a1，a2，a3的相对位置一定是不变的，即 a
11、3 一定在前，a2 居中，a1 一定在后。比较上述四个答案，只在 A 中的 a1 出现在 a2 的前面，这显然是不正确的。【知识模块】 栈和队列6 【正确答案】 B【知识模块】 栈和队列7 【正确答案】 D【知识模块】 栈和队列8 【正确答案】 C【知识模块】 栈和队列9 【正确答案】 D【试题解析】 在循环队列中，为了能正确区分队满、队空两个判断条件，当前头指针 front 所指单元总是空的。因此最多(队满时) 能存放 k-1 个元素。【知识模块】 栈和队列10 【正确答案】 D【试题解析】 首先，执行的人队操作是在队尾进行的，所以 A，B 肯定是不对的。其次，由于存放。sq 的数组为 A
12、0m，共有 m+1 个单元，运算中的模应为m+1，因此 D 是正确的。【知识模块】 栈和队列11 【正确答案】 C【知识模块】 栈和队列12 【正确答案】 B【试题解析】 由于输出的是 CBA，则应将三个元素全部压人栈中，因此应执行三次入栈操作，再执行三次出栈操作。【知识模块】 栈和队列13 【正确答案】 B【试题解析】 S1 ，S2 进栈后，此时栈中有 2 个元素，接着 s2 出栈，栈中尚有 1个元素；s3，s4 进栈后，此时栈中有 3 个元素，接着 s4，s3 出栈，栈中尚有 1 个元素；S5，S6 进栈后，此时栈中有 3 个元素，接着 S6，S5 出栈，栈中尚有 1 个元素；S1 出栈后
13、，此时栈为空栈。由此可知，栈的容量至少应该是 3。【知识模块】 栈和队列14 【正确答案】 C【知识模块】 栈和队列15 【正确答案】 C【知识模块】 栈和队列二、填空题16 【正确答案】 先进后出(或后进先出) 先进先出(或后进后出) 端点 栈【试题解析】 由于只能在栈顶处执行插入、删除操作，使得数据元素的进栈顺序恰好与出栈顺序相反，所以栈的逻辑特点是先进后出(或后进先出)。而对队列来讲，插入、删除操作必须在队列的两端进行，数据元素的进队顺序与出队顺序是一致的，所以队列的逻辑特点是先进先出(或后进后出)。两者的共同点是所有操作只能在端点处进行。栈是实现递归函数调用的必不可少的数据结构，可用栈
14、来保存返回地址、参变量的值。【知识模块】 栈和队列17 【正确答案】 队列 队尾 对头【知识模块】 栈和队列18 【正确答案】 Qfront=Qrear (Qrear+1)QUEUESIZE=Qfront【知识模块】 栈和队列19 【正确答案】 设置一个标志位 设置一个计数器 少用一个存储空间【知识模块】 栈和队列20 【正确答案】 33【知识模块】 栈和队列21 【正确答案】 1q 一front 一next=lq-rear【试题解析】 对带有头结点的链队列，其头指针总是指向头结点，而尾指针总是指向最后一个结点，因此当队列中只有一个数据元素时，头、尾指针满足下列条件：1q 一front 一ne
15、xt=lq 一rear。【知识模块】 栈和队列22 【正确答案】 Q 一front=Q 一front 一next【知识模块】 栈和队列23 【正确答案】 栈。栈的主要作用之一是将递归算法转化为非递归算法【知识模块】 栈和队列24 【正确答案】 O(1)【知识模块】 栈和队列25 【正确答案】 dbc 一 a+【知识模块】 栈和队列三、应用题26 【正确答案】 在日常生活中人们洗碗碟时，总是后洗的碗碟放在先洗碗碟的上面，而人们在使用碗碟时总是从上往下去取，符合栈的“后进先出” 的特性。而比如火车站排队买票，先来者排在前面先购买车票，后来者由队尾开始排队，符合队列的“先进先出 ”的特性。【知识模块
16、】 栈和队列27 【正确答案】 如下图(a)所示，栈顶 top=6，表示栈已满，这时再有元素进栈，即产生“上溢 ”。 如下图(b)所示，栈顶 top=0，表示栈已空，如要进行出栈操作，即产生“下溢”。 假设有一顺序队列，如下图 (c)所示，队尾指针 sqrear=maxsize=6 ，如有元素入队，产生了“ 上溢 ”。这时的“上溢”又称 “假溢出”，因为此时队列中还有2 个存储单元空着(下标为 1，2)。【知识模块】 栈和队列28 【正确答案】 出栈顺序有：A，B，C ，D A，B ，D，C A，C ，B，D A，C，D ，B A，D ，C ，BB，A，C ，D B ，A，D，C B ，C，A
17、，D B，C ，D ，A B ，D ，C，AC，B，A，D C ，B，D，A C，D，B，A D，C，B，A【知识模块】 栈和队列29 【正确答案】 栈调用和返回变化示意如下图所示。【知识模块】 栈和队列30 【正确答案】 void invert(point head)LStackTps；Initstack(s)；P=head；while(pdata)；P=P 一next；P=head；while(notEmptyStack(s)pop(s，P 一data)；P=P 一next；【试题解析】 由于进栈顺序与出栈顺序正好相反，因此，借助栈来实现单链表的逆置运算很方便，也容易理解。方法是先依次让单
18、链表上的元素进栈，然后再依次出栈。【知识模块】 栈和队列31 【正确答案】 void Inqueue(lklistrear，dataType x)S=malloc(sizeof(iklisk)；S 一data=x；if(rear=NULL)rear=S；rear 一next=s：elseS 一next=rear 一next；rear 一next=s；rear=s；voiddelqueue(iklistrear)if(rear=NULL)error(”overflow”)；elseS=rear 一next；if(S=rear)rear=NULL；elserear 一next=s 一next；fr
19、ee(S)；【试题解析】 按题意，该队列可以用下图表示。由图可知，出队操作是在循环单链表的头部进行，相当于删除 a1 结点。而入队操作是在循环单链表的尾部进行，相当于在 an 后插入一个结点。【知识模块】 栈和队列32 【正确答案】 Status Express(char*str) *假设表达式放入一个字符串 str 中，利用栈判断表达式中的括号是否匹配*InitStack(S)；while(*str!=0)if(*str=()Push(S，*str)；if(*str=)(2)出队列操作。void DeQueue(SqQueue【试题解析】 在循环队列中，若用标志位 tag 来判断队满和队空，假设当tag=0，并且头指针和尾指针相等时表示队空；当 tag=1，并且头指针和尾指针相等时表示队满。在这种情况下，实现入队和出队操作的函数如下。【知识模块】 栈和队列
