第三章栈和队列课后习题答案

河南广播电视大学现教中心

第三章 栈和队列 课后习题答案

1、 单项选择题 （1） B （2） B （3） D （4） D （5） C （6） C （7） B （8） C （9） B （10） C 2、 填空题

（1） 后进先出 先进先出

（2） front = rear （rear+1）% Max = front （3） top = 0 top =N-1 （4） 空 空 只含有一个结点 （5） p->next=top; top=p; （6） rear->next=p; rear=p; （7） 4 （8） 假上溢 3、 问答题 （1） 参考答案：

栈的操作特点是后进先出，因此输出序列有：

A入，A出，B入，B出，C入C出，输出序列为ABC。 A入，A出，B入，C入，C出，B出，输出序列为ACB。 A入，B入，B出，A出，C入，C出，输出序列为BAC。 A入，B入，B出，C入，C出，A出，输出序列为BCA。 A入，B入，C入，C出，B出，A出，输出序列为CBA。 （2） 参考答案：

8 3 5 + 5 6 2 / - * - （3） 参考答案：

一个过程（或函数）直接或间接调用自己，这种过程（或函数）叫递归过程（或函数）。 递归算法一般用于解决三类问题：

第1页 共6页 版权所有 河南电大现教中心范颖，邮箱fy@open.ha.cn

河南广播电视大学现教中心

1）数据的定义是按递归定义的。（Fibonacci函数） 2）问题解法按递归算法实现。（回溯）

3）数据的结构形式是按递归定义的。（树的遍历，图的搜索） 设计递归算法的方法： ① 寻找递归通式，分解问题； ② 设置递归出口，确定递归终止条件。 （4） 参考答案：

向一个顺序栈插入一个元素时，首先使栈顶指针后移一个位置，然后把待插入元素写入到这个位置上。 （5） 参考答案：

向一个链栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给栈顶指针。b5E2RGbC （6） 参考答案：

① 一种是在定义结构体时，附设一个存储循环队列中元素个数的变量如n，当n=0时，队空。当n=MaxSize时为队满。p1EanqFD ② 另一种方法是少用一个元素控件，约定当尾指针加1等于头指针时，认为是队满，可用于求模运算来实现，即front=rear，称为队空。当（rear+1）%MaxSize=front时，称为队满，此时，循环队列中能装入的元素个数为（MaxSize-1）。DXDiTa9E 4、 算法设计题

（1） 参考算法代码： void Transform(long num)

//把一个正整数num转为一个十六进制数输出 {

Stack a; InitStack(a); while(num!=0){ int k=num % 16; Push(a,k); num/=16; }

while(!StackEmpty(a)) {

int X=Pop(a); if(x<10) cout<

switch(x) {

cass 10: cout<<'A';

第2页 共6页 版权所有 河南电大现教中心范颖，邮箱fy@open.ha.cn

河南广播电视大学现教中心

break; cass 11: cout<<'B'; break; cass 12: cout<<'C'; break; cass 13: cout<<'D'; break; cass 14: cout<<'E'; break; cass 15: cout<<'F'; } } }

cout<

（2） 参考算法代码：

int count(Snode *HS) {

Snode *p=HS; int n=0;

while (p!=NULL) {n++;

p=p->next;} return(n); }

（3） 参考算法代码：

int Qucount(LQueue *HQ) {

Snode *p=HQ->front; int n=0;

while (p!=NULL) {n++;

p=p->next; }

return (n); }

（4） 参考答案：

#include #include

第3页 共6页 版权所有 河南电大现教中心范颖，邮箱fy@open.ha.cn