栈和队列习题
4．1 判断题(在你认为正确的题后的括号中打√，否则打X)。
(1)堆栈和队列都是特殊的线性表。( )
(2)堆栈和队列都将插入和删除操作限制在表的端点处进行。( )
(3)只允许在表的一端进行插入和删除操作的线性表称为堆栈。( )
(4)没有元素的堆栈称为空栈，空栈用不着栈顶指针。( )
(5)只要堆栈不空，就能任意删除堆栈的元素。( )
(6)堆栈允许删除的一端称为栈顶，而栈底元素是不能删除的。( )
(7)n个元素进栈的顺序一定与它们出栈的顺序相反。( )
(8)对采用链式存储结构的堆栈进行操作不必判断溢出。( )
(9)给出顺序堆栈的栈顶元素位置的指针是一个指针类型的变量。( )
(10)判断顺序堆栈是否为空的标志是top是否等于0(top为栈顶指针)。( )
(11)插入和删除操作比较简单是链接堆栈和链接队列的优点之一。( )
(12)n个元素进队的顺序与它们出队的顺序一定是相同的。( )
(13)没有任何元素的队列称为空队。空队用不着队头指针与队尾指针。( )
(14)元素进出队列一定满足“先进先出”的规律。( )
(15)链接队列不存在溢出问题。( )
(16)在链接队列中删除一个元素是在链表的最前端进行的。( )
(17)采用循环链表作为存储结构的队列称为循环队列。( )
(18)堆栈和队列都可以用来解决递归问题。( )
(19)堆栈和队列都不适合采用散列存储方法。( )
(20)无论是顺序队列还是链接队列，插入、删除操作的时间复杂度都是O(1)。( )
4．2单项选择题。
(1)堆栈和队列的共同之处在于它们具有相同的——。
A．逻辑特性B．物理特性C．运算方法D．元素类型
(2)堆栈和队列都是特殊的线性表，其特殊性在于_______。
A．它们具有一般线性表所没有的逻辑特性
B．它们的存储结构比较特殊
C．对它们的使用方法做了限制
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 (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．有多种可能
(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．有多种可能
(8)若堆栈采用顺序存储结构，正常情况下，往堆栈中插入一个元素，栈顶指针top的变化是______.
A．不变B．top=0 C．top-- D．top++
(9)若堆栈采用顺序存储结构，正常情况下，删除堆栈中一个元素，栈顶指针top的变化是______.
A．不变B．top=0 C．top-- D．top++
(10)若队列采用顺序存储结构，元素的排列顺序——。
A．与元素的值的大小有关
B．由元素进入队列的先后顺序决定
C．与队头指针和队尾指针的取值有关
n与作为顺序存储结构的数组的大小有关
(11)“链接队列”这一概念不涉及——。
A．数据的存储结构B．数据的逻辑结构
C.对数据进行的操作D．链表的种类
(12)若堆栈采用链式存储结构，栈顶指针为top，向堆栈插入一个由p所指的新结点的过程是依次执行：——，top=p。
A．p=top B．top=p C．p->link=top D．top->link=p
(13)若非空堆栈采用链式存储结构，栈顶指针为top，删除堆栈的一个元素的过程是依次执行：p=top，——，free(p)。
A．top=p B．top=p->link C．p=top->link D．p=p->link
(14)若队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，向队列中插入一个由p所指的新结点的过程是依次执行：——，rear=p。
A．rear=p B．front=p C．rear->link=p D．front->link=p
(15)若非空队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，删除队列的一个元素的过程是依次执行：p=front，——，free(p)。
A．rear=p B．rear=p->link C．rear=p->link D．front=p->link
(16)在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循环队列队空的条件是——。
A．front=rear+1 B。rear=front+1 C．front--rear D．b叭t：0
(17)若描述某循环队列的数组为ClUELIE[M]，当循环队列满时，队列中有——个元素。
A．M B．M-1 C．M十1 D．M+2
(18)在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据打印，该缓冲区应该是一个——结构。
A．线性表B．数组C．堆栈D．队列
(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函数定义如下：
(1)写出递归算法；
(2)利用堆栈写出非递归算法；
(3)根据非递归算法，求出A(：K(2，1)的值。
4．12 已知求两个正整数m和n的最大公约数的过程可以表达为如下递归函数：
请写出求解该递归函数的非递归算法。m MOD n表示m对n取模。
4．13 假设以数组Q[M]存放循环队列的元素，同时设置变量rear与qlen分别指示循环队列中队尾元素的
位置和队列中元素的个数。请给出此循环队列的队满条件，并写出相应的进队与出队算法(在出队算法中要求返回队头元素)。
4．14 编写一非递归算法，对于给定的十进制整数n，打印出对应的r进制整数(2≤r≤16，r<>10)。
4．15 梵塔问题是这样的：一个底盘上有三根竖着的针，初始时A针穿着一叠盘片(如图4，20所示)，现要求将这一叠盘片移到C针上，并且任何时刻不得将大盘放在小盘之上，而且每一次只允许移动一张盘片。写一算法，打印出正确的操作步骤。
提示：将n张盘片由A依次移到C，B作为辅助针。当n=1时，可以直接完成。否则，将顶上的n—1张盘片移到B针上，用C针作为辅助针；然后移第n张盘片，最后将B上的n—1张盘片移到C针上，并用A针作为辅助针。
栈和队列历年试题
1．栈和队列都是（）
A．限制存取位置的线性结构B．顺序存储的线性结构
C．链式存储的线性结构D．限制存取位置的非线性结构
2．若数组-1]为两个栈s1和s2的共用存储空间，且仅当-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为（）
A．1和n+1 B．1和n/2 C．－1和n D．－1和n+1
3.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为( )
A.4
B.5
C.6
D.7
4．假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为________________，不可能得到的出栈序列为________________。5．在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现：
_____________；
sq -> data[sq -> top]=x；
6．链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的_____________。
7．如图所示，设输入元素的顺序是A，B，C，D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D，则输出序列为_______________。
8．队列中允许进行删除的一端为________________。
9.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为________。
10、设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？
11．如图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可能的输入序列。（5分）
第五章广义表字符串数组
习题
5．1单项选择题。
(1)空的广义表是指广义表——。
A．深度为0 B。尚未赋值
C．不含任何原子元素D．不含任何元素
(2)广义表中元素分为——。
A．原子元素B．表元素
C．原子元素和表元素D．任意元素
(3)广义表的长度是指——。
A．广义表中元素的个数B．广义表中原子元素的个数
C．广义表中表元素的个数Di广义表中括号嵌套的层数
(4)广义表的深度是指——。
久广义表中元素的个数B．广义表中原子元素的个数
C．广义表中表元素的个数D．广义表中括号嵌套的层数
(5)在一个长度为n，包含m个原子元素的广义表中，——。
A．m和n相等B．m不大于n C．m不小于n D．m与n无关
(6)广义表A=(( )，(a)，(b，(c，d)))的长度为——。
A．2 B．3 C．4 D．5
(7)广义表A：(( )，(a)，(b，(c，d)))的深度为——。
A．2 B．3 C．4 D．5
5．2有人说，m*n阶矩阵是一种广义表结构，你认为如何?请说明你的理由。
5．3请分别写出下列各广义表的长度与深度：
(1)A=((a))
(2)B=(a，(b，c，d)，e，())
(3)C=(x，((y)，B，A))
(4)D=(A,D)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。