计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编5.docx

计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编 5(总分：80.00，做题时间：90 分钟)一、 单项选择题(总题数：28，分数：56.00)1.对于栈操作数据的原则是 青岛大学2001 年】A. 先进先出B. 后进先出 VC. 后进后出D. 不分顺序考查栈的概念栈是一种后进先出的数据结构2•在初始为空的堆栈中依次插入元素f, e, d, c, b, a以后，连续进行了三次删除操作，此时栈项元素是 北京航空航天大学2002年】A. cB. d VC. bD. e考查栈的基本性质数据入栈时，先入栈的元素后出栈，只需简单地画图即可看出栈顶元素应是d3. 六个不同元素依次进栈,能得到 种不同的出栈序列北京邮电大学2007 年】A. 42B. 82C. 132 VD. 192考查栈的基本性质设有n个不同元素时，有f(n)种出栈序列若第一个元素是第i个出栈的，则在这个 元素之前是编号为2〜i的元素出栈，之后是编号为i+1〜n的元素出栈所以第一个元素是第i个出栈对 应 f(i-l)*f(n—i)种出栈顺序f(l)=l f(2)=2 f(3)=f(2)+f(l)*f(l)+f(2)=5 f(4)=f(3)+f(l)+f(2)十 f(2)+f(1)+f(3)=14 f(5)=f(4)+(1)+f(3)+“2)+f(2)+f(3)*(1)+f(4)=42 f(6)=f(5)+(1)+f(4)+f(2)+f(3)+f(3),f(2)+f(4)+f(1)+f(5)=42+14+10+10+14+42=1324. 入栈序列为1， 2， 3， 4， 5 ，则可能得到的出栈序列是 。

【上海交通大学2 005】A. 12534B. 31254C. 32541 VD. 14235考查栈的性质C的情况是由以下操作得到：1、2、3先入栈，接着3弹栈，2弹栈，然后4、5入栈，5弹 栈， 4 弹栈，最后 1 弹栈其他各种情况，都不可能由栈的操作得到5. 一个栈的输入序列为1， 2， 3， 4， 5，则下列序列中不可能是栈的输出序列的是 北京理工大学2000年】【北京交通大学2006年】【中南大学2003年】A. 23415B. 54132 VC. 23145D. 15432考查栈的性质考生可通过画图得出正确答案A是可能的：先是1、2入栈，然后2弹栈，3入栈，3弹 栈，4入栈，4弹栈，1弹栈，5入栈，5弹栈C是可能的：1和2入栈，2弹栈，3入栈，3弹栈，1弹栈， 4入栈，4弹栈，5入栈，5弹栈D是可能的：1入栈，l弹栈，2345入栈，5432弹栈6. 若已知一个栈的入栈序列为1, 2, 3, 4,其出栈序列为pl, p2, p3, p4,则p2, p4不可能是 华中科技大学2007 年】A. 2、 4B. 2、 1C. 4、 3 VD. 3、4考查栈的性质对于A,可能的顺序：1入栈，1弹栈，2入栈，2弹栈，3入栈，3弹栈，4入栈，4弹栈。

对于B,可能的顺序：1入栈，2入栈，3入栈，3弹栈，2弹栈，4入栈，4弹栈，1弹栈对于D,可能的 顺序： 1 入栈， 1 弹栈， 2 入栈， 3 入栈， 3 弹栈， 2 弹栈， 4 入栈， 4 弹栈 C 则没有对应的序列7•某堆栈的输入序列为a, b, c, d,下面的四个序列中，不可能是它的输出序列的是_北京航空航 天大学 2005 年】【北京邮电大学2005 年】A. a，c， b， dB. b，c， d， aC. c, d, b, aD. d， c， a， b 丿考查栈的性质A可能的序列：a入栈，a出栈，b入栈，c入栈，c出栈，b出栈，d入栈，d出栈B可能 的序列： a、b 入栈， b 出栈， c 入栈， c 出栈， d 入栈， d 出栈， a 出栈 C 可能的序列： a、b、c 入栈， c 出栈， d 入栈， d 出栈， b 出栈， a 出栈8•输入序列为ABC，可以变为CBA时，经过的栈操作为 中山大学1999年】A. push， pop， push， pOp， push， popB. push， push， push， pOp， pOp， pop 丿C. push， push， pop， pOp， push， popD. push， pOp， push， push， pOp， pop考查栈的性质。

本题属于比较简单的类型正确的顺序：A入栈，B入栈，c入栈，c弹栈，B弹栈，A弹栈 9•若栈采用顺序存储方式存储，现两栈共享空间V[1.. m]，top[i]代表第i个栈j=1，2)栈顶，栈1的 底在V【1】，栈2的底在V[m]，则栈满的条件是 南京理工大学1999年】A. 1top[2]top[1]1=0B. top[1]+1=top[2] 丿C. top[1]+top[2]=mD. top[1]=top[2]考查栈共享空间的问题可以通过画图来寻找问题的解，当空间V装满后，必有栈1的栈项+1=栈2的栈顶， 即 top[1]+1=top[2] 10. 向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应该执行____北京理工大学 2005年】A. h．>next=s：B. s->next=h；C. s．>next=h： h->next=s；D. s-〉next=h —〉next. h-〉next=S； 丿 考查链栈的插入操作实际上考查的是在一个链表的头结点后插入一个新结点的操作，因此如果熟练掌握 了链表的插入操作，本题是比较容易的由于该链表是带头结点的，因此h指向的是头结点，所以插入新 结点的操作是：s 一〉lqext=h —〉Fiext； h 一〉rtext=s；11. 执行完下列语句段后，i值为 。

浙江大学2000年】intf(intx){return((x〉O)?x*f(x — 1): 2) ；}inti；i=f(f(1))；A. 2B. 4 丿C. 8D. 无限递归考查对递归的理解和应用由题得 f(0)=2； f(1)=1*f(0)=2； f(1))=f(2)=2*f(1)=4，即 f(1))=412. 一个递归算法必须包括 武汉大学2000年】A. 递归部分B. 终止条件和递归部分丿C. 迭代部分D. 终止条件和迭代部分考查对于递归的理解一个递归算法分为终止条件和递归部分两个部分终止条件是递归算法的出口，也 就是终止递归的条件递归部分是一个递推的关系式13. 将递归算法转变成对应非递归算法时，需要使用 保存中间结果华中科技大学2007 年】A. 栈丿B. 队列C. 二叉树D. 单链表 考查递归算法转化为非递归算法的方法栈的一个重要应用就是实现程序中的递归14. 表达式a*(b+c) — d的后缀表达式是 南京理工大学2001年】A. abed*+—B. abc+*d一 丿C. abe*+d—D. -+*abcd 考查后缀表达式的计算方法后缀表达式中，每一个计算符号均位于它的两个操作数的直接后面，按这样的方式逐步根据计算的优先级将每个计算式进行变换即可得到后缀表达式。

或者还可以采用下面的方法： 将表达式构造为一棵树，然后以后序遍历法遍历这棵树即可得到后缀表达式同理可得前缀表达式、中缀将此树按照后序遍历，即可表达式比如在此题中，表达式a*(b+c) 一 d构造的树如图2. 1所示得到 abc+*d15. 中缀表达式(A+B)*(C—D) / (E—F*G)的后缀表达式是 北京邮电大学2005年】A. A+B*C—D / E〜F*GB. AB 十 CD 一*EFG*一/ 丿C. AB+C*D—E/ F—G+D. ABCDEFG+*一/一* 考查由中缀表达式计算后缀表达式的方法本题给出了中缀表达式，可以通过中缀表达式构建表达式的树 结构，然后以后序遍历这棵树，即可得到后缀表达式16. 中缀表达式A 一(B+C/D)}E的后缀形式是 北京航空航天大学2007年】A. ABCD / +E*一 丿B. ABC+D/ *E—C. AB—C+D/ E*D. ABC 一+D / E* 考查由中缀表达式计算后缀表达式的方法按照上题的方法，可以很快得出答案17. 设计一个判别表达式中左、右括号是否配对出现的算法，采用 数据结构最佳西安电子科技大学1996 年】A. 线性表的顺序存储结构B. 队列C. 线性表的链式存储结构D. 栈丿考查栈和队列的应用领域。

栈通常在数制转换、括号匹配检验、表达式求值、行编辑程序设计以及迷宫求 解等方面有应用18. 在链队列的出队操作中，修改尾指针的情况发生在 广东工业大学2002年】A. 变成空队列的时候B. 变成满队列的时候C. 队列只剩一个元素的时候 丿D. 任何时候 考查链队列的出队操作链队列是一种特殊的链表链队列的入队操作是在链表尾部插入一个新的结点， 出队操作是在队头删除一个结点所以只有等到只剩一个元素时，出队操作才会修改尾指针19. 对于循环队列，正确的是 哈尔滨工业大学2007年】A. 无法判断队列是否为空B. 无法判断队列是否为满C. 队列不可能满D. 以上说法都不对丿考查循环队列的基本概念考生可以很容易判断A、B和C三项均不正确20. 循环队列A[0—m 一 1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是 【南京理工大学2001 年】【华中科技大学2007 年】A. (rear一front+m) %m 丿B. rear—front+lC. rear一front 一■ 1D. rear一front考查循环队列元素数的计算方法对于循环队列，计算元素数目的公式就是(rear—front+m) %m。

21. 循环队列存储在数组A[0—m]中，则入队时的操作为 中山大学1999年】A. rear=rear+1B. rear=(rear+1)mod(m ■ 1)C. rear=(rear+1)modmD. rear=(rear+1)mod(re+1) 丿考查循环队列入队操作循环队列新元素入队时操作算法为rear=(rear+1)modmaxsize,本题中 maxsize=m+1因此入队操作为 rear=(rear+1)mod(m+1)22. 最大容量为n的循环队列，队尾指针是rear，队头是front,则队空的条件是 南京理工大学1999 年】A. (rear+1)MODn=frontB. rear=front 丿C. rear+1=frontD. (rear一11M0Dn=front 考查循环队列队空的条件循环队列当队空的时候， rear=front23. 判定一个长度为M的循环队列Q队满的条件是一一北京交通大学2007年】A. Q．front+1==Q．rearB. Q．front==Q．rear+1C. Q．front=Q．rearD. Q. front=(Q. rear+1) %M 丿考查循环队列队满的条件。

原本队列满和空的时候都是Q. front=Q. rear,但是为了区分两种情况，通常 牺牲一个存储空间，即每次入队前先判断(Q. rear+1) %M是否等于Q. front，是的话就认为队列已满所 以，Q. front=(Q. rear+1) %M便是队满。