习题三
一、选择题
l．一个栈的序列是：a，b，c，d，e，则栈的不可能输出的序列是（C）。
A．a，b，c，d，e B．d，e，c，b，a C．d，c，e，a，b D．e，d，c，b，a
2．若一个栈的输人序列是1，2，3，…，n，输出序列的第一个元素是n，则第k个输出元素是（ C）。
A．k B．n-k-1 C．n-k+1 D．不确定
3．判定一个栈S（最多有n个元素）为空的条件是（ B ）。
A．S->top！＝0 B．S->top= =0 C．S->top!=n D．S->top= =n
4．判定一个栈S（最多有n个元素）为满的条件是（D ）。
A．S->top!=0 B．S->top= =0 C．S->top!=n D．S->top= =n
5．向一个栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（ B ）。
A．top->next=S； B．S->next=top；top=S；
C．S->next＝top->next；top->next＝S；D．S->next＝top；top＝S->next；
6．向一个带头结点、栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（ C ）。
A．top->next=S； B．S->next=top；top=S；
C．S->next=top->next；top->next=S； D．S->next=top；top=S->next；
7．判定一个队列Q（最多有n个元素）为空的条件是（ C ）。
A．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n
C．Q->rear = = Q->front D．Q->rear +1= = Q->front
8．判定一个队列Q（最多有n个元素）为满的条件是（A）。
A．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n
C．Q->rear = = Q->front D．Q->rear +1= = Q->front
9．判定一个循环队列Q（最多有n个元素）为空的条件是（ A ）。
A．Q->rear = = Q->front B．Q->rear = = Q->front＋l
C．Q->front= =(Q->rear +1)％n D．Q->front= =(Q->rear -1)％n
10．判定一个循环队列Q（最多有n个元素）为满的条件是（ C ）。
A．Q->rear = = Q->front B．Q->rear = = Q->front＋l
C．Q->front= =(Q->rear +1)％n D．Q->front= =(Q->rear -1)％n
11．在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的操作是（ C ）。
A．front＝front->next B．S->next=rear；rear=S
C．rear->next=S；rear=S D．S->next=front；front＝S
12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（ A ）。
A．front=front->next B．rear=rear->next
C．rear->next=front D．front->next＝rear
13．栈与队列都是（ C ）。
A．链式存储的线性结构 B．链式存储的非线性结构
C．限制存取点的线性结构 D．限制存取点的非线性结构
14．若进栈序列为l，2，3，4，则（ C ）不可能是一个出栈序列。
A．3，2，4，1 B．l，2，3，4 C．4，2，3，1 D．4，3，2，l
15．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机
将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ B ）结构。
A．堆栈 B．队列 C．数组 D．线性表
二、填空回
1．栈（stack）是限定在表尾一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为栈顶，而另一端称为栈底。不含元素的栈称为空栈
。
2．在栈的运算中，栈的插人操作称为进栈或入栈的删除操作称为退栈或出栈。
3．根据栈的定义，每一次进栈的元素都在原栈顶元素之上，并成为新的栈顶元素；每一次出栈的元素总是当前的栈顶元素，因此最后进栈的元素总是最先出栈，所以栈也称为后进先出线性表，简称为LIFO表。
4．栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有顺序和链式_两种存
储结构，分别称为、顺序栈_和_链栈。
5．当栈满的时候，再进行人栈操作就会产生溢出，这种情况的溢出称为上溢__；当栈空的时候，如果再进行出栈操作，也会溢出，这种情况下的溢出称为下溢。
6．栈的链式存储结构简称为链栈，是一种_特殊的单链表。
7．人们日常计算用到的表达式都被称为中缀表达式，这是由于这种算术表达式的运算符被置于两个操作数中间。
8．计算机中通常使用后缀表达式，这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为波兰式。
9．队列（Queue）也是一种特殊的线性表_，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为队尾，允许删除的一端称为队头。
10．队列的特点是先进先出，因此队列又被称为先进先出．的线性表，或称为FIFO表。
11．队列的顺序存储结构又称为顺序队列，是用一组地址连续的存储单元依次存放队列中的元素。
12．由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行，因此需要设置两个指针分别指向队头元素和队尾元素，这两个指针又称为队头指针和队尾指针
。
13．循环顺序队列（Circular Sequence Queue）经常简称为循环队列，它是将存储顺序队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是通过数学上的、取模运算来实现的。
14．在算法或程序中，当一个函数直接调用自己或通过一系列语句间接调用自己的时候，则称这个函数为递归函数，也称为自调用函数。函数直接调用自己，则称为直接递归调用；当一个函数通过另一个函数来调用自己则称为间接递归调用。
15．在循环队列中规定：当Q->rear= =Q->front的时候循环队列为空_， 当（Q->rear+1）％MAXSIZE＝front的时候循环队列为满。
16．用链表方式表示的队列称为链队列。
17．已知栈的输人序列为1，2，3，…，n，输出序列为a1，a2，…，an，符合a2= =n的输出序列共有n-1。
18．一个栈的输人序列是12345，则栈的输出序列为43512是不可能的
（填是否可能）。
19．一个栈的输人序列是12345，则栈的输出序列为12345是可能的（填是否可能）。
20．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，则作入栈操作的条件是top!=maxsize。
21．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，如果把栈顶元素弹出并送到X中，则需执行语句x=sq[top]; top=top-1。
22．栈的特性是先进后出。
23．对栈进行退栈时的操作是先取出元素，后移动栈顶指针。
24．设s[1．．max]为一个顺序存储的栈，变量top指示栈顶位置，栈为满的条件是top==max。
25．设链栈的栈顶指针为top，则栈非空的条件是top!=nil
。
26．已知循环队列用数组]存储元素值，用f，r分别作为头尾指针， 则当前元素个数为(n+r-f)mod n。
27．在一个循环队列中，队首指针指向队首元素的前一个位置。（前一个或后一个）
28．队列中允许进行删除的一端称为队首。
29．链队列实际上是一个同时带有头指针和尾指针的单链表（1．．n），尾指针指向该单链表的第n个元素。
30．设双向链表链列为lq，lq的头指针为lq.Front，尾指针为lq.Rear，则队列为空的条件是lq->front==lq->rear数据结构与算法第二版课后题答案。
31．从循环队列中删除一个元素，其操作是先取出一个元素，后移动栈顶指针。
32．队列中允许进行插入的一端称为队尾。
三、判断题
1．栈和队列都是限制存取点的线性结构。对
）
2．不同的人栈和出栈组合可能得到相同输出序列。错误：不同的入栈和出栈组合得到不同输出序列。
）
3．消除递归一定要用栈。（错误：某些情况如尾递归可以转换为递推的形式。
）
4．循环队列是顺序存储结构。（正确）
5．循环队列不会产生溢出。（错误：循环队列不会产生假溢出 ）
6．循环队列满的时候rear= =front。（ 错误 ）
7．在对链队列（带头结点）做出队操作时不会改变front指针的值。（正确）
四、综合题
1．设有4个元素A、B、C和D进栈，给出它们所有可能的出栈秩序。
A、B、C、D
A、B、D、C
发表评论