第3章 栈和队列 课后习题一、单项选择题1. 栈的插入和删除操作在 B 进行。A. 栈底B. 栈顶C. 任意位置D. 指定位置2. 一个栈的进栈序列是 2, 4, 6, 8, 10则栈不可能输出的序列是 C 。A. 2, 4, 6, 8, 10B. 8, 10, 6, 4, 2C. 8, 6, 10, 2, 4D. 10, 8, 6, 4, 23. 一个队列的入队序列是 a, b, c, d按该队列的可能输出序列使各元素依次入栈该栈的可能输出序列是 A 。A. d, c, b, aB. c, a, b, dC. d, b, a, cD. d, a, b, c4. 在一个链队中假设 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 NULLB. head - next NULLC. head - next headD. head NULL6. 从一个栈顶指针为 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 → nextB. rear → next s → nextC. rear s → nextD. s → next rear → next; rear → next s二、填空题1. 栈的操作特点是后进先出。2. 一个顺序循环队列存于一维数组 a[Max] 中队头指针和队尾指针分别为 front 和 rear则判断队空的条件为front rear。判断队满的条件为(rear1) % 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-nextp;然后执行rearp;p-nextNULL;7. 在一个容量为 15 的循环队列中若头指针 front 5尾指针 rear 9则该循环队列中共有4个元素。8. 引入循环队列的目的是克服假上溢。三、问答题1.一个栈的输入序列为A, B, C输出序列由A, B, C构成试给出全部可能的输出序列答共5种A,B,CA,C,BB,A,CB,C,AC,B,A2.用栈实现将中缀表达式8 - (3 5) * (5 - 6/2)转换成后缀表达式画出栈的变化过程图。答后缀表达式8 3 5 5 6 2 / - * -为了简单起见先在栈中放入一个结束符“”,其优先级最低。栈的变化变化过程如下读字符栈中符号输出结果说明888为操作数直接输出--8“-”比“”优先级高“-”进栈(-(8“(”直接进栈3-(8 33为操作数直接输出-(8 3“”比“(”优先级高“”进栈5-(8 3 55为操作数直接输出)-8 3 5 遇到右括号依次退栈输出“”退到左括号左括号退栈但不输出*-*8 3 5 “*”比“-”优先级高“*”进栈(-*(8 3 5 “(”直接进栈5-*(8 3 5 55为操作数直接输出--*(-8 3 5 5“-”比“(”优先级高“-” 进栈6-*(-8 3 5 5 66为操作数直接输出/-*(-/8 3 5 5 6“/”比“-”优先级高“/” 进栈2-*(-/8 3 5 5 6 22为操作数直接输出)-*8 3 5 5 6 2 / -遇到右括号依次退栈输出“/”和“-”退到左括号左括号退栈但不输出8 3 5 5 6 2 / - * -栈中符号依次退栈栈空结束3.什么情况下可以利用递归来解决问题写递归程序时应注意什么答适用情况问题可分解为规模更小、结构相同的子问题且存在明确的终止条件。注意点必须有终止条件递归出口递归调用参数应逐步逼近终止条件避免栈溢出尽量用尾递归或改为迭代以提高效率。4.简述在栈的栈顶插入一个元素的操作过程答检查栈是否已满若满则溢出栈顶指针top加1将元素存入data[top]位置。5.简述在链栈中插入一个元素的操作过程答创建新结点p赋值数据p → next toptop 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; }