栈和队列课后习题答案 下载本文

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

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

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) 参考答案:

向一个链栈插入一个新结点时,首先把栈顶指针的值赋给新结点的指针域,然后把新结点的存储位置赋给栈顶指针。 (6) 参考答案:

① 一种是在定义结构体时,附设一个存储循环队列中元素个数的变量如n,当n=0时,

队空。当n=MaxSize时为队满。

② 另一种方法是少用一个元素控件,约定当尾指针加1等于头指针时,认为是队满,

可用于求模运算来实现,即front=rear,称为队空。当(rear+1)%MaxSize=front时,称为队满,此时,循环队列中能装入的元素个数为(MaxSize-1)。

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