算法与数据结构习题三(答案)

习题三

一、选择题

1.一个栈的序列是：a,b,d,e,则栈的不可能输出的序列是（C）。

A.a,b,c,d,eB.d,e,c,b,aC.d,c,e,a,bD.e,d,c,b,a

2.若一个栈的输人序列是1,2,3,…，n,输出序列的第一个元素是n,则第k个输

出元素是（C）。

A.kB.n-k-1C.n-k+1D.不确定

3.判定一个栈S（最多有n个元素）为空的条件是（B）。

A.S->top!=0B.S->top==0C.S->top!=nD.S->top==n

4.判定一个栈S（最多有n个元素）为满的条件是（D）o

A.S->top!=0B.S->top==0C.S->top!=nD.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==nB.Q->rear-Q->front+1==n

C.Q->rear==Q->frontD.Q->rear+1==Q->front

8.判定一个队列Q（最多有n个元素）为满的条件是（A）。

A.Q->rear-Q->front==nB.Q->rear-Q->front+1==n

C.Q->rear==Q->frontD.Q->rear+1==Q->front

9.判定一个循环队列Q（最多有n个元素）为空的条件是（A）o

A.Q->rear==Q->frontB.Q->rear==Q->front+1

C.Q->front==（Q->rear+1）%nD.Q->front==（Q->rear-1）%n

10.判定一个循环队列Q（最多有n个元素）为满的条件是（C）。

A.Q->rear==Q->frontB.Q->rear==Q->front+1

C.Q->front==（Q->rear+1）%nD.Q->front==（Q->rear-l）%n

11.在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的

操作是（C）。

A.front=front->nextB.S->next=rear；rear=S

C.rear->next=S；rear=SD.S->next=front；front=S

12.在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操

作是（A）。

A.front=front->nextB.rear=rear->next

C.rear->next=frontD•front->next=rear

13.栈与队列都是（C）o

A.链式存储的线性结构B.链式存储的非线性结构

C.限制存取点的线性结构D.限制存取点的非线性结构

14.若进栈序列为1,2,3,4,则（C）不可能是一个出栈序列。

A.3,2,4,1B.1,2,3,4C.4,2,3,1D.4,3,2,1

15.在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲

区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓

冲区应该是一个（B）结构。

A.堆栈B.队列C.数组D.线性表

二、填空回

1.栈（stack）是限定在表星一端进行插入或删除操作的线性表。在栈中，允许插人和

删除操作的一端称为栈顶,而另一端称为栈底。不含元素的栈称为空栈

2.在栈的运算中，栈的插人操作称为进栈或入栈的删除操作称为退栈或出栈。

3.根据栈的定义，，一次进栈的元素都在原栈顶元素之上,并成为新的栈顶元素;每

一次出栈的元素总是当前的栈顶元素,因此最后进栈的元素总是最先出栈,所以栈也称为后

进先出线性表,简称为LIFO表。

4.栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有顺序和链式.

两种存储结构，分别称为、顺序栈.和链栈。

5.当栈满的时候，再进行人栈操作就会产生画i，这种情况的溢出称为上溢一；当栈

空的时候，如果再进行出栈操作，也会逛出这种情况下的溢出称为工灌。

6.栈的链式存储结构简称为链找，是一种一特殊的单链表。

7.人们日常计算用到的表达式都被称为中缀表达式，这是由于这种算术表达式的运算

符被置于两个操作数中间。

8.计算机中通常使用后缀表达式,这是一种将运算符置于两个操作数后面的算术表达

式。这种表达式是由波兰科学家谢维奇提出的，因此又称为波兰式。

9.队列（Queue）也是一种特殊的线性表.，但它与栈不同，队列中所有的插人均限定

在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为队尾,允许

删除的一端称为队头。

10.队列的特点是先进先出,因此队列又被称为先进先出.的线性表，或称为FIFO表。

11.队列的顺序存储结构又称为顺序队列,是用一组地址连续的存储单元依次存放队列

中的元素。

12.由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行，因此

需要设置两个指针分别指向队头兀素和队尾元素,这两个指针又称为队头指针和队尾指针

O

13.循环顺序队列（CircularSequenceQueue）经常简称为循环队列,它是将存储顺序

队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接起来形成一个环形

表。首尾相连的状态是通过数学上的、取模运算来实现的。

14.在算法或程序中，当一个函数直接调用自己或通过一系列语句间接调用自己的时

候，则称这个函数为递归函数,也称为自调用函数。函数直接调用自己，则称为直接递归调

见；当一个函数通过另一个函数来调用自己则称为间接递归调用。

15.在循环队列中规定：当Q->rear==Q->front的时候循环队列为空一,当

（Q->rear+l）%MAXSIZE=front的时候循环队列为遒。

16.用链表方式表示的队列称为链队列。

17.已知栈的输人序列为1.2,3,…，n,输出序列为a“a?,…，an,符合a2==n

的输出序列共有上1。

18.一个栈的输人序列是12345,则栈的输出序列为43512是丕回递的

（填是否可能）。

19.一个栈的输人序列是12345,则栈的输出序列为12345是亘能的（填是否可能）。

20.设sq[l..maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，则作入栈

操作的条件是top!-maxsizeo

21.设sq[l..maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，如果把栈

顶元素弹出并送到X中，则需执行语句x=sq[topl;top=top-l。

22.栈的特性是先进后出。

23.对栈进行退栈时的操作是先取出元素，后移动栈顶指针。

24.设s[l..max]为一个顺序存储的栈，变量top指示栈顶位置，栈为满的条件是

tor）==max。

25.设链栈的栈顶指针为top,则栈非空的条件是lop!=nil

O

26.已知循环队列用数组data[L..n]存储元素值，用f,r分别作为头尾指针，则当前

元素个数为（n+r-f）modn。

27.在一个循环队列中，队首指针指向队首元素的前一个位置。（前一个或后一个）

28.队列中允许进行删除的一端称为M直。

29.链队列实际上是一个同时带有头指针和尾指针的单链表（1一n）,尾指针指向该

单链表的第鱼个元素。

30.设双向链表链列为lq,lq的头指针为Iq.Front,尾指针为Iq.Rear,则队列为空的条

件是lq->front==lq->rear。

31.从循环队列中删除一个元素，其操作是先取出一个元素，后移动栈顶指针。

32.队列中允许进行插入的一端称为队尾。

三、