栈和队列 习 题
4．1 判断题(在你认为正确的题后的括号中打√，否则打X)。
(1)堆栈和队列都是特殊的线性表。 (√ )
(2)堆栈和队列都将插入和删除操作限制在表的端点处进行。 ( √ )
(3)只允许在表的一端进行插入和删除操作的线性表称为堆栈。 ( √ )
(4)没有元素的堆栈称为空栈，空栈用不着栈顶指针。 (X )
(5)只要堆栈不空，就能任意删除堆栈的元素。 (X )
(6)堆栈允许删除的一端称为栈顶，而栈底元素是不能删除的。 ( X )
(7)n个元素进栈的顺序一定与它们出栈的顺序相反。 ( X )
(8)对采用链式存储结构的堆栈进行操作不必判断溢出。 (X )
(9)给出顺序堆栈的栈顶元素位置的指针是一个指针类型的变量。 ( X )
(10)判断顺序堆栈是否为空的标志是top是否等于0(top为栈顶指针)。 (√ )
(11)插入和删除操作比较简单是链接堆栈和链接队列的优点之一。 (√ )
(12)n个元素进队的顺序与它们出队的顺序一定是相同的。 ( √ )
(13)没有任何元素的队列称为空队。空队用不着队头指针与队尾指针。 ( X )
(14)元素进出队列一定满足“先进先出”的规律。 ( √ )
(15)链接队列不存在溢出问题。 ( X )
(16)在链接队列中删除一个元素是在链表的最前端进行的。 (√ )
(17)采用循环链表作为存储结构的队列称为循环队列。 (√ )
(18)堆栈和队列都可以用来解决递归问题。 (X )
(19)堆栈和队列都不适合采用散列存储方法。 ( √ )
(20)无论是顺序队列还是链接队列，插入、删除操作的时间复杂度都是O(1)。 ( √ )
4．2单项选择题。
A(1)堆栈和队列的共同之处在于它们具有相同的——。
A．逻辑特性 B．物理特性 C．运算方法 D．元素类型
C(2)堆栈和队列都是特殊的线性表，其特殊性在于_______。
A．它们具有一般线性表所没有的逻辑特性
B．它们的存储结构比较特殊
C．对它们的使用方法做了限制
D．它们比一般线性表更简单
D(3)若5个元素的出栈序列为1，2，3，4，5，则进栈序列可能是——。
A．2，4，3，1，5 B．2，3，1，5，4 C．3，1，4，2，5 D．3，1，2，5，4
A(4)某队列初始为空，若它的输入序列为a，b，c，d，它的输出序列应为——。
A．a，b，c，d B．d，c，b，a C．a，c，b，d D．d，a，c，b
公式(5)当4个元素的进栈序列给定以后，由这4个元素组成的可能的出栈序列应该有——。
A．24种 B．17种 C．16种 D．14种
*(6)设n个元素的进栈序列为1，2，3，…，n，出栈序列为p1，p2，p3，…，pn，若Pi=n，则B(1≤i<n)的值——。
A．为i B．为n-i C．为n-i+l D．有多种可能
A(7)设n个元素的进栈序列为p1，p2，p3，…，pn，出栈序列为1，2，3，…，n，若Pn=l，则n(1≤i< n)的值——。
A．为i B．为n-i C．为n-i+l D．有多种可能
D(8)若堆栈采用顺序存储结构，正常情况下，往堆栈中插入一个元素，栈顶指针top的变化是 ______.
A．不变 B．top=0 C．top-- D．top++
C(9)若堆栈采用顺序存储结构，正常情况下，删除堆栈中一个元素，栈顶指针top的变化是 ______.
A．不变 B．top=0 C．top-- D．top++
B(10)若队列采用顺序存储结构，元素的排列顺序——。
A．与元素的值的大小有关
B．由元素进入队列的先后顺序决定
C．与队头指针和队尾指针的取值有关
D.与作为顺序存储结构的数组的大小有关
C(11)“链接队列”这一概念不涉及——。
A．数据的存储结构 B．数据的逻辑结构
C.对数据进行的操作 D．链表的种类
C(12)若堆栈采用链式存储结构，栈顶指针为top，向堆栈插入一个由p所指的新结点的过程是依次执行：——，top=p。
A．p=top B．top=p C．p->link=top D．top->link=p
B(13)若非空堆栈采用链式存储结构，栈顶指针为top，删除堆栈的一个元素的过程是依次执行：p=top，——，free(p)。
A．top=p B．top=p->link C．p=top->link D．p=p->link
C(14)若队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，向队列中插入一个由p所指的新结点的过程是依次执行：——，rear=p。
A．rear=p B．front=p C．rear->link=p D．front->link=p
D(15)若非空队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，删除队列的一个元素的过程是依次执行：p=front，——，free(p)。
A．rear=p B．rear=p->link C．rear=p->link D．front=p->link
C(16)在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循环队列队空的条件是——。
A．front=rear+1 B。rear=front+1 C．front--rear D．b叭t：0
A (17)若描述某循环队列的数组为ClUELIE[M]，当循环队列满时，队列中有——个元素。
A．M B．M-1 C．M十1 D．M+2
D (18)在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据打印，该缓 冲区应该是一个——结构。
A．线性表 B．数组 C．堆栈 D．队列
C(19)设计一个递归问题的非递归算法通常需要设置——结构。
A．线性表 B．数组 C．堆栈 D．队列
*(20)中缀表达式A-(B+C／D)*E的后缀形式是——。
A．ABC+D／*E— B．ABCD／+E*— C．AB-C十D／E* D．ABC-+D／E*
4．3 填空题。
(1)堆栈和队列的逻辑结构都是 线性 结构。
(2)堆栈的插入和删除操作都是在栈顶位置进行，而队列的插入操作在队尾进行，删除操作在队头进行。
(3)对某堆栈执行删除操作时，只有在栈顶情况下，才会将栈底元素删除。
(4)在具体的程序设计过程中，堆栈的顺序存储结构一般是利用一个数组描述的，同时还要定义一个整型变量来栈顶。
(5)若堆栈采用顺序存储结构，在不产生溢出的情况下往堆栈中插人一个新元素，首先移动，然后写入。
(6)若队列采用顺序存储结构，未溢出时插入一个元素首先插入一个元素，然后再写入。
(7)当堆栈的最大长度难以估计时，堆栈最好采用链式存储结构。
(8)递归算法都可以通过设置堆栈机制改写成等价的非递归算法。
*(9)中缀形式的算术表达式A+(B-C)／D*E的后缀形式为——。
*(10)后缀形式的算术表达式ABCD/-E*+的中缀形式为——。
4．4 已知堆栈采用链式存储结构，初始时为空，请画出a，b，c，d四个元素依次进栈以后该堆栈的状态，然后再画出此时的那个栈顶元素出栈后堆栈的状态。
字符串长度的正确表示4．5 若按从左到右的顺序依次读人已知序列{a，b，c，d，e，f，g1中的元素，然后结合堆栈操作，能得到下列序列中的哪些序列(每个元素进栈一次，下列序列表示出栈的次序)?
{d，e，c，f，b，g，a} {f，e，g，d，a，c，b}
{e，f，d，g，b，c，a} {c，d，b，e，f，a，g}
4．6 设有编号1，2，3，4的四辆列车，顺序进入一个栈式结构的站台，请写出这四辆列车开出车站的所有可能的顺序。
4．7 设STACK[M]为n(n>2)个堆栈共享。各栈栈顶指针为top[n]，分别指出各栈栈顶元素的位置；栈底指针为bot[n+1]，分别指出各栈栈底元素的位置。初始时，
bop[i]=bot[i]=i*ROUND(M／n—0．5) (i=1，2，....，n)
其中，ROUND()为四舍五人取整函数。请写一算法，该算法向任意指定的第i个堆栈插入一个新的元素x。仅当M个空间全部占用时才产生溢出，并报告相应信息(1≤i≤n)。
4．8 设中缀表达式E存放于字符数组中，并以@作为结束标志。请写出判断一个中缀表达式E中左、右圆括号是否配对的算法。
4．9 写出将中缀表达#(a+b)／c-d#变换为后缀表达式的过程中，每读到一个单词时堆栈的状态(#为中缀表达式的左、右分界符)。
4．10 已知n为大于等于零的整数，请写出利用堆栈计算下列递归函数f(n)的非递归算法。
4．11 已知Ackerman函数定义如下：
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论