可南广播电视大学现黄中心 第三章找和队列课后习题答案 1、单项选择思 (1)B (2)B (3)D (4) D (5) (6)C (7)B (8)C (9)B (10)C 2、填空题 (1)后进先出先进先出 (2)fromt=rear (rear+1)Max =front (3)p=0op=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)参考答案： 835+562/-*- (3)参考答案： 一个过程（或函数）直接或间接调用白己，这种过程（或函数）叫域归过程（或函数） 运归算法一般用于解决三类问题： 第1页北6页 版权所有河南电大现教中心植额，都箱dpm恒cm
河南广播电视大学现教中心 第1页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 第三章 栈和队列 课后习题答案 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)数据的定义是按通归定义的。(Fiborc函数) 2)间愿解法按域归算法实现。（回测） 3)数据的结构形式是按递归定义的。《树的遍历，图的搜需) 设计递归算法的方法与 ①寻找递归通式。分解问题： ②设置递归出口，确定喝归终止条件。 (4)参考答案： 向一个顺序找括入一个元素时，首先使栈项指针后移一个位置，然后把特插入元素写入 到这个位置上， (5》参考答案： 白一个绒找插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结 点的存储位置鼠给栈顶指针。 (6)参考答案： ①一种是在定义结构体时，附设一个存错循环队列中元素个数的变量如：当0时， 队空。当n-x5e时为队满。 ②另一种方法是少用一个元素控件，约定当尾指针加1等于头指针时，认为是队满， 可用于求横运算来实现，即front=心罐，称为队空。当(re+1)%MSi2-fct时， 称为队满，北到，循环队列中能装入的元素个数为(MS远1)· 4、算法设计圈 (1)参考算法代码： void Transform(long num） 把一个正整数um转为一个十大进制数输出 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<ex; clse! switch(x) cass 10: coutCA' 第2风共6项 版权所有河南电大现教中心范额。邮箱5@m加m
河南广播电视大学现教中心 第2页 共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<<x; else{ switch(x) { cass 10: cout<<'A';
河南广播电视大学现黄中心 break. Gas11上 coutocB. break. cass 12: coutnext:! return(n). (3》参考算法代码： int Qucount LQueue *HO刀 Snode "p=HQ->front. int n-0. while (pl-NULL) [n++; p-p->next return(n). (4)参考答案1 #include #include 第3项共6项 版权所有河南电大规教中心抛顾，都箱Ba血m
河南广播电视大学现教中心 第3页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn break; cass 11: coutnext;} 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
河南广播电视大学现教中心 #define MAXSIZE 100 typedef int EleType, typodef struct! EleType ele[MAXSIZE] int top, Stack: int initial(Stack 'stack) ck->cp=-1: return 0. int push(Stack 'stack.EleType clement) if (stack->top =MAXSIZE-1) printf("ERROR:stack is fullnn"); return O. stack-2topt+: stack->elefstack->top]=element. return I; int pop(Stack *stack.EleType "element) if(sak->09=-1) printf("ERROR:stack is empty". return D. element =stack-ele[stack->top]: stack-2top--. return I; int maind Stack 'stack EleType ai,element int value. i间(stack=(Sack*)malloo(sizeof(Stack》=NU printf("ERROR:can not allocate memory for stack!'n"); ex减O方 initial(stack); 第4顶北6页 版权所有河南电大现教中心植额，都箱dpm恒cm
河南广播电视大学现教中心 第4页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn #define MAXSIZE 100 typedef int EleType; typedef struct{ EleType ele[MAXSIZE]; int top; }Stack; int initial(Stack *stack) { stack->top = -1; return 0; } int push(Stack *stack, EleType element) { if (stack->top == MAXSIZE-1) { printf("ERROR: stack is full!\n"); return 0; } stack->top++; stack->ele[stack->top] = element; return 1; } int pop(Stack *stack, EleType *element) { if (stack->top == -1) { printf("ERROR: stack is empty"); return 0; } *element = stack->ele[stack->top]; stack->top--; return 1; } int main() { Stack *stack; EleType ai, element; int value; if((stack = (Stack*)malloc(sizeof(Stack))) == NULL) { printf("ERROR: can not allocate memory for stack!\n"); exit(0); } initial(stack);
河南广厂播电现大学现数中心 while(((value-scanf("%d",&ai))=1 )&ai1) uck,aI水 if(a动=1W输入错误 printf("ERROR:input error!'in"): 0 i调=-1M全部出栈 while (stack->top I=-1) pop(stack,&element): printf"%d "element); return 0. (5)速归算法参考代码： long Fib(in n) 讯一1n一2)终止递自条件 re国urnl else return Fib每-1 +Fibn-21 (6)参考答案： 带g域的循环队列入队算法： Status EnCyQueue(CyQue联kQ,tx) 值Q.0—Q.r心&&Qag=1)作g域的值为0表示空1表示清” return OVERFLOW Q.hase[Q.rear]-x Q rear(Q rear+1%MAXSIZE: iMQ.ronQ.rer） Q.g=.风列满 //EnCyQueue 带电域的惭环队列出队算法： Status DeCyQueue(CyQueue &Q.int &x) i间Q.fonQ.re&&Q.ag0) return INFEASIBLE: Q.front=(Q.front+1)%MAXSIZE. 第5项共6项 版权所有河南电大现教中心范额，好箱5@m加cm
河南广播电视大学现教中心 第5页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn while(((value = scanf("%d", &ai)) == 1 ) && ai != -1) { push(stack, ai); } if (value != 1)// 输入错误 { printf("ERROR: input error!\n"); exit(0); } if(ai == -1)//全部出栈 { while (stack->top != -1) { pop(stack, &element); printf("%d ", element); } } return 0; } （5） 递归算法参考代码： long Fib(int n) { if(n==1||n==2) //终止递归条件 return 1; else return Fib(n-1)+Fib(n-2); } （6） 参考答案： 带 tag 域的循环队列入队算法： Status EnCyQueue(CyQueue &Q,int x) { if(Q.front==Q.rear&&Q.tag==1) //tag 域的值为 0 表示"空",1 表示"满" return OVERFLOW; Q.base[Q.rear]=x; Q.rear=(Q.rear+1)%MAXSIZE; if(Q.front==Q.rear) Q.tag=1; //队列满 }//EnCyQueue 带 tag 域的循环队列出队算法： Status DeCyQueue(CyQueue &Q,int &x) { if(Q.front==Q.rear&&Q.tag==0) return INFEASIBLE; Q.front=(Q.front+1)%MAXSIZE;
河南广播电视大学现数中心 x=Q.base[Q.from]: imQ.fron=Q.er） Q.g士：风列空 return OK. DeCyQueue 第5页共6页 版权所有河南电大观教中心范隔，船箱@up恤团
河南广播电视大学现教中心 第6页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn x=Q.base[Q.front]; if(Q.front==Q.rear) Q.tag=1; //队列空 return OK; }//DeCyQueue