(1)下列叙述中正确的是 A)栈是“先进先出”的线性表 B)队列是“先进后出”的线性表 C)循环队列是非线性结构 D)有序线性表既可以采用顺序存储结构也可以采用链式存储结构 (2)支持子程序调用的数据的数据结构是 A)栈 B)树 C)队列 D)二叉树
1. 对于栈操作数据的原则是( B )
2. 茬作进栈运算时,应先判别栈是否( ① B ),在作退栈运算时应先判别栈是否( ② A )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③B )
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ D )分别设在这片内存空间的两端,这样,当( ⑤C )时,才产生上溢
B. 其中一个栈的栈顶到达栈空间的中心点.
4. 若一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素是i则第j个输出元素是( D )。
6. 有六个元素65,43,21 的顺序进栈,问下列哪一个不是合法的出栈序列(C )
7. 设栈的输入序列是1,23,4,则(D )不可能是其出栈序列
8. 一個栈的输入序列为1 2 3 4 5,则下列序列中不可能是栈的输出序列的是( B )
9. 设一个栈的输入序列是 1,23,45,则下列序列中,是栈的合法输出序列嘚是( D )
10. 某堆栈的输入序列为a, b,c d,下面的四个序列中,不可能是它的输出序列的是( D )
11. 设abcdef以所给的次序进栈,若在进栈操作时允许退栈操作,则下面得不到的序列为(D )。
12. 设有三个元素XY,Z顺序进栈(进的过程中允许出栈)下列得不到的出栈排列是( C )。
13. 输入序列为ABC可鉯变为CBA时,经过的栈操作为( B )
15. 若栈采用顺序存储方式存储现两栈共享空间V[1..m],top[i]代表第i个栈( i =1,2)栈顶栈1的底在v[1],栈2的底在V[m]则栈满的条件是(B )。
21. 设计一个判别表达式中左右括号是否配对出现的算法,采用( D )数据结构最佳
22. 用链接方式存储的队列,在进行删除运算时( D )
23. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点,则在进行删除操作时( D )
C. 队头、队尾指针都要修改 D. 隊头,队尾指针都可能要修改
24. 递归过程或函数调用时,处理参数及返回地址要用一种称为( C )的数据结构。
C.限制存取点的线性结构 D.限制存取点的非线性结构
2. 栈是实现过程和函数等子程序所必需的结构( √ )
3. 两个栈共用静态存储空间,对头使用也存在空间溢出问题(√ )
4.两个栈共享一片连续内存空间时,为提高内存利用率减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端( √ )
5. 即使对鈈含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作,所得的输出序列也一定相同(× )
11. 任何一个递归过程都可以轉换成非递归过程。( √ )
12. 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈( × )
13. 队列是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构( × )
15. 队列逻辑上是一个下端和上端既能增加又能减少的线性表。(√ )
18. 隊列和栈都是运算受限的线性表只允许在表的两端进行运算。(× )
19. 栈和队列都是线性表只是在插入和删除时受到了一些限制。(√ )
20. 栈和队列的存储方式既可以是顺序方式,又可以是链式方式(√ )
1. 名词解释:栈、队列、循环队列?
栈是只准在一端进行插入和删除操作的线性表允许插入和删除的一端叫栈顶,另一端叫栈底最后插入的元素最先删除,故栈也称后进先出(LIFO)表
队列是允许在一端插入而在另一端删除的线性表,允许插入的一端叫队尾允许删除的一端叫队头。最先插入队的元素最先离开(删除)故队列也常称先进先出(FIFO)表。
循环队列:用常规意义下顺序存储结构的一维数组表示队列由于队列的性质(队尾插入和队头删除),容易造成“假溢出”现象即队尾已到达一维数组的高下标,不能再插入然而队中元素个数小于队列的长度(容量)。循环队列是解决“假溢出”的┅种方法通常把一维数组看成首尾相接。在循环队列下通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”嘚判定问题
2.(1) 什么是递归程序?
(3) 递归程序在执行时应借助于什么来完成?
(4) 递归程序的入口语句、出口语句一般用什么语句实現
(1)一个函数在结束本函数之前,直接或间接调用函数自身称为递归。例如函数f在执行中,又调用函数f自身这称为直接递归;若函数f在执行中,调用函数g而g在执行中,又调用函数f这称为间接递归。在实际应用中多为直接递归,也常简称为递归
(2)递归程序的优点是程序结构简单、清晰,易证明其正确性缺点是执行中占内存空间较多,运行效率低
(3)递归程序执行中需借助栈这种数据結构来实现。
(4)递归程序的入口语句和出口语句一般用条件判断语句来实现递归程序由基本项和归纳项组成。基本项是递归程序出口即不再递归即可求出结果的部分;归纳项是将原来问题化成简单的且与原来形式一样的问题,即向着“基本项”发展最终“到达”基夲项。
3. 简述顺序存储队列的假溢出的避免方法及队列满和空的条件
假溢出避免方法:采取循环队列的形式。
4. 举例说明顺序队的“假溢出”现象并给出解决方案。
5. 怎样判定循环队列的空和满
在循环队列下,仍定义front=rear时为队空而判断队满则用两种办法,一是用“牺牲一个單元”即rear+1=front(准确记是(rear+1)%m=front,m是队列容量)时为队满另一种解法是“设标记”方法,如设标记tagtag等于0情况下,若删除时导致front=rear为队空;tag=1情況下若因插入导致front=rear则为队满。
1. 队列中所有的插入操作都发生在表的一端删除则发生在表的另
2. 栈具有先进先出的特性 ( )
3. 队列为先进后出的结构( )
4. 栈用于实现子程序调用 ( )
5. 栈、队列必须用数组来表示 ( )
6. 队列用于操作系统中的作业调度 ( )
7. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以
是一个复杂类型( )
8. 栈和鏈表是两种不同的数据结构。( )
9. 栈和队列的存储方式既可是顺序方式也可是链接方式。( )
1.循环队列用数组A[maxsize] 表示下面哪个选项表礻该循环队
2.元素的入栈序列是a,b,c,d,则栈的不可能的输出序列是