练习题及答案3.pdf

1、已知二叉树的先序访问序列ABDGECF，中序访问序列 DGBEAFC，请写出后续 访问序列。  答案：GDEBFCA   （4分）  2、设顺序循环队列中，队头指示器front，队尾指示器 rear，存储单元个数 maxsize。 写出入队和出队时 rear和 front 的计算公式，队空时的判断公式，队满时的判断 公式，队列长度计算公式。  答案：  出队时： front=(front+1)% maxsize 入队时：rear=(rear+1)% maxsize 队空时： front rear 队满时：(rear+1)% maxsize front 队列长度：(maxsize+rear-front)% maxsize   （错一个扣1分。）  3、已知单链表中结点类为 Node，p指向第 i‐1个结点，若将第 i个结点删除，所 使用语句包括：p‐next=q‐next; x=q‐data;  NodeT *q=p‐next;       delete  q;  请给出这些语句的正确排列顺序。  答案：NodeT *q=p‐next; x=q‐data; p‐next=q‐next;  delete q;    或 NodeT *q=p‐next; p‐next=q‐next;  x=q‐data; delete q;    4、给定一组权值{6，2，3，3，4，9}用哈夫曼算法构造哈夫曼树。  答案：    编程题：  1、如图表示大小不一的一摞饼，a[i]表示第 i 层饼大小。设计一个函数 void   sort(int a[],int n) 对 n个饼进行翻转，使得大饼在下小饼在上排放。要求每次只 能选择上方的一堆饼，一起翻转。    答案：#include iostream using namespace std; //头文件和命名空间2分 void swap(int *low,int *high) { int temp; while(lowhigh) //实现交换3分 { temp=*low; *low=*high; *high=temp; low++; high--; } } void sort(int *a,int n) { if(n 1) return; //递归返回2分 int max_i=0; int max_val=*a; for(int i=0;in;i++) if(a[i]max_val){max_val=a[i];max_i=i;} //算法结构5分 swap(a[max_i],a+n-1); swap(a,a+n-1); sort(a+1,n-1); }