企业官网建设流程全解析

第3章 栈和队列 课后习题

一、单项选择题

1. 栈的插入和删除操作在（ B ）进行。
A. 栈底
B. 栈顶
C. 任意位置
D. 指定位置

2. 一个栈的进栈序列是 2, 4, 6, 8, 10，则栈不可能输出的序列是（ C ）。
A. 2, 4, 6, 8, 10
B. 8, 10, 6, 4, 2
C. 8, 6, 10, 2, 4
D. 10, 8, 6, 4, 2

3. 一个队列的入队序列是 a, b, c, d，按该队列的可能输出序列使各元素依次入栈，该栈的可能输出序列是（ A ）。
A. d, c, b, a
B. c, a, b, d
C. d, b, a, c
D. d, a, b, c

4. 在一个链队中，假设 f 和 r 分别为队头和队尾指针，p 指向一个已生成的结点，为该结点的数据域赋值 e，并使结点入队的运算为 “p -> data = e; p -> next = NULL;” 和（ B ）。
A. f -> next = p; f = p;
B. r -> next = p; r = p;
C. p -> next = r; r = p;
D. p -> next = f; f = p;

5. 对不带头结点的单向链表，判断其是否为空的条件是（ A ）。
(设头指针为 head。)
A. head == NULL
B. head -> next == NULL
C. head -> next == head
D. head = NULL

6. 从一个栈顶指针为 top 的链栈中取栈顶元素，用变量 x 保存该元素的值，则执行（ B ）。
A. x = top -> data; top = top -> next;
B. x = top -> data;
C. top = top -> next; x = top -> data;
D. top = top -> next; x = data;

7. 假定一个链栈的栈顶指针用 top 表示，每个结点的结构由一个数据域 data 和一个指针域 next 组成，当 p 指向的结点进栈时，执行的操作为（ D ）。
A. p -> next = top;
B. top = p; p -> next = top;
C. p -> next = top -> next; top -> next = p;
D. p -> next = top; top = p;

8. 以下说法错误的是（ C ）。
A. 栈的特点是后进先出
B. 队列的特点是先进先出
C. 栈的删除操作在栈底进行，插入操作在栈顶进行
D. 队列的插入操作在队尾进行，删除操作在队头进行

9. 一个递归算法必须包括（ D ）。
A. 递归部分
B. 终止条件和迭代部分
C. 迭代部分
D. 终止条件和递归部分

10. 在一个尾指针为 rear 的不带头结点的单循环链表中，插入一个 s 所指的结点，并将之作为第一个结点，可执行（ D ）。
A. rear → next = s; s → next = rear → next
B. rear → next = s → next
C. rear = s → next
D. s → next = rear → next; rear → next = s

二、填空题

1. 栈的操作特点是后进先出。

2. 一个顺序循环队列存于一维数组 a[Max] 中，队头指针和队尾指针分别为 front 和 rear，则：判断队空的条件为front == rear。判断队满的条件为(rear+1) % Max == front。

3. 一个顺序栈存储于一维数组 a[0…N-1] 中，栈顶指针用 top 表示，空栈时top = -1。满栈时top = N-1。

4. 在一个链队中，front 和 rear 分别为队头和队尾指针，s 所指结点（数据域已赋值）的入队操作为：s → next = NULL;rear → next = s;和 rear = s;

5. 假设一个链栈的栈顶指针为 top，每个结点包含值域data和指针域next，当 p 所指向的结点进栈时，首先执行p → next = top，然后执行top = p。

6. 在一个空队列中，队头指针和队尾指针分别为 front 和 rear，当向其插入一个新结点*p 时：首先执行front = p，然后执行rear = p。
注：“结点”两字说明是链队，而不是顺序队。因为顺序队称存放单位为“元素”，而不称为“结点”。

如果是不带头结点的链队，则先执行front = p，然后执行rear = p

如果是带头结点的链队，则先执行rear->next=p;然后执行rear=p;p->next=NULL;

7. 在一个容量为 15 的循环队列中，若头指针 front = 5，尾指针 rear = 9，则该循环队列中共有4个元素。

8. 引入循环队列的目的是克服假上溢。

三、问答题

1.一个栈的输入序列为A, B, C，输出序列由A, B, C构成，试给出全部可能的输出序列

答：共5种：

A,B,C

A,C,B

B,A,C

B,C,A

C,B,A

2.用栈实现将中缀表达式8 - (3 + 5) * (5 - 6/2)转换成后缀表达式，画出栈的变化过程图。

答：后缀表达式：8 3 5 + 5 6 2 / - * -

为了简单起见，先在栈中放入一个结束符“@”,其优先级最低。栈的变化变化过程如下：

3.什么情况下可以利用递归来解决问题？写递归程序时应注意什么？

答：适用情况：问题可分解为规模更小、结构相同的子问题，且存在明确的终止条件。

注意点：必须有终止条件（递归出口）；递归调用参数应逐步逼近终止条件；避免栈溢出；尽量用尾递归或改为迭代以提高效率。

4.简述在栈的栈顶插入一个元素的操作过程

答：

检查栈是否已满，若满则溢出；

栈顶指针top加1；

将元素存入data[top]位置。

5.简述在链栈中插入一个元素的操作过程

答：

创建新结点p，赋值数据；

p → next = top；

top = p；

若原栈为空，则此时top即为唯一结点。

6.在循环队列中，仅依据头尾指针相等，无法判断队列是“空”还是“满”，解决此问题的两种方法是什么？

答：

方法一：少用一个元素空间，约定(rear + 1) % MaxSize == front为队满，front == rear为队空。

方法二：增设一个标志位（如tag），每次入队时置tag = 1，出队时置tag = 0；当front == rear且tag == 1时为队满；当front == rear且tag == 0时为队空。

四、算法设计题

1. 缩写将十进制正整数转换为16进制数输出的算法。

思路：除16取余，逆序输出（用栈实现）。

#include <stdio.h> void decToHex(int n) { int stack[100], top = -1; if (n == 0) { printf("0"); return; } while (n > 0) { stack[++top] = n % 16; n /= 16; } while (top != -1) { int r = stack[top--]; if (r < 10) printf("%d", r); else printf("%c", 'A' + r - 10); } }

2.在栈顶指针为HS的链栈中，写出计算该链栈中结点个数的函数。

struct Node { int data; struct Node* next; }; int countNodes(struct Node* HS) { int cnt = 0; struct Node* p = HS; while (p != NULL) { cnt++; p = p->next; } return cnt; }

3. 在HQ的链队中，编写算法求链队中的结点个数。

struct QueueNode { int data; struct QueueNode* next; }; struct LinkQueue { struct QueueNode *front, *rear; }; int countQueue(struct LinkQueue HQ) { int cnt = 0; struct QueueNode* p = HQ.front; while (p != NULL) { cnt++; p = p->next; } return cnt; }

4.设从键盘输入一个整数的序列：a1,a2,a3,⋯,an。试编写算法，要求用栈结构存储输入的数据，当ai≠−1时，将ai进栈；当ai=−1时，输出栈顶整数并出栈。算法应对异常情况（如栈满等）给出相应的信息.

#include <stdio.h> #define MAX 100 int stack[MAX], top = -1; void push(int x) { if (top == MAX - 1) { printf("栈满，无法入栈\n"); return; } stack[++top] = x; } void pop() { if (top == -1) { printf("栈空，无法出栈\n"); return; } printf("%d ", stack[top--]); } int main() { int a[] = {3, 5, -1, 7, -1, -1, 8}; // 示例输入序列 int n = sizeof(a) / sizeof(a[0]); for (int i = 0; i < n; i++) { if (a[i] != -1) push(a[i]); else pop(); } return 0; }

5.斐波那契数列的定义为：它的第1项和第2项均为1，以后各项为其前两项之和。若斐波那契数列中的第n项用Fib(n)表示，则计算公式为：

试编写计算Fib(n)的递归算法.

int Fib(int n) { if (n == 1 || n == 2) return 1; return Fib(n - 1) + Fib(n - 2); }

6.如果希望循环队列中的元素都能得到利用，则需要设置一个标志域tag，并以tag的值为0或1来区分尾指针和头指针值相同的队列的状态是“空”还是“满”，试编写与此结构相应的入队和出队的算法.

#define MaxSize 5 typedef struct { int data[MaxSize]; int front, rear; int tag; // 0:空 1:满 } Queue; void initQueue(Queue *q) { q->front = q->rear = 0; q->tag = 0; } int enQueue(Queue *q, int x) { if (q->front == q->rear && q->tag == 1) { printf("队满\n"); return 0; } q->data[q->rear] = x; q->rear = (q->rear + 1) % MaxSize; q->tag = 1; return 1; } int deQueue(Queue *q, int *x) { if (q->front == q->rear && q->tag == 0) { printf("队空\n"); return 0; } *x = q->data[q->front]; q->front = (q->front + 1) % MaxSize; q->tag = 0; return 1; }