5、哈夫曼树在构造时，首先进行初始化存储空间，结果如左下图，当构造完成后，请填写最后状态表，如右下图。（期中考试题）
weight Parent
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
5 29 7 8 14 23 3 11 -- -- -- -- -- -- -- Lchild Rchild 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
weight Parent
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Lchild Rchild 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6、考虑右图：
(1)从顶点A出发，求它的深度优先生成树(4分) (2)从顶点E出发，求它的广度优先生成树(4分)
(3）根据普利姆(Prim) 算法，求它的最小生成树(请画出过程) (设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列)(6分)
答案如下：
七 编写算法题
1、设计函数，求一个单链表中值为x的结点个数。并将结果放在头结点的data 域中。 void count1(lklist head,int x) {
List p;
int count=0; p=head->next; while(p!=NULL)
{
if(p->data = = x) count + +; p=p->next; }
head->data = count; }
2、设计递归函数，求一棵二叉树的深度。 int depth (bitreptr root) {
if(root ==NULL) return 0; else {
int dep1= depth (root ->lchild); int dep2= depth (root ->rchild); if(dep1>dep2) return dep1+1; else return dep2+1; } }
3、设计建立有向图正邻接矩阵的函数（数据输入格式自定）。（实验题目） Typedef struct
{ int data[ maxsize][maxsize]; int dem,e; }sqgraph;
sqgraph crt (sqgraph g)
4、设计函数，将不带表头结点的单链表清除。 void clearList(List L){ List p; p=L->next;
while(p!=NULL) {
q=p->next; free(p); p=q; }
free(L); }
5、设计递归函数，求一棵非空的二叉树的深度。 int depth (bitreptr root)
{
if(root ==NULL) return 0; else {
int dep1= depth (root ->lchild); int dep2= depth (root ->rchild); if(dep1>dep2) return dep1+1; else return dep2+1; } }
6、设线性表A=(a1,a2,a3,?,an)以带头结点的单链表作为存储结构。编写一个函数，删去A中序号为奇数的结点。
void clearOdd(List A){ int count=1; List r=L;
List p=A->next; while(p!=NULL){ q=p->next; if(count%2==1)
{
r->next=q;
free(p); }
else { r=p; } p=q; count++; } }
7、试编写一个算法，能由大到小遍历一棵二元树。
8、假设二元树用左右链表示，试编写一算法，判别给定二元树是否为完全二元树? Typedef struct BiTNode{
TElemType data;
struct BiTNode *LChild, *RChild; }BiTNode, *BiTree;
Status A(BiTree T) { Queue Q; InitQueue(Q); ENQueue(Q,T);
While(not QueueEmpty(Q)) { DeQueue(Q,e);
If(e==NULL) return false; //不是完全二叉树； Else
{
ENQueue(Q,e.LChild); ENQueue(Q.e.RChild); }
}
return true; //是完全二叉树； }
9、利用直接插入排序的方法对一组记录按关键字从小到大的顺序排序。
（算法见课本P265） 实现程序：
void insert_sort(ElemType a[],int n)
//待排序元素用一个数组a表示，数组有n个元素 { int i, j;
ElemType t;
for ( i=1; i while ((j>=0)&& (t { a[j+1]=a[j]; j--; } // 顺序比较和移动 a[j+1]=t; } } 10、给出一棵表示表达式的二叉树，其中运算符和运算对象都用一个字符表示，求该表达式的值。设二叉树用二叉链表表示，表达式中仅包含二元运算，函数operate(a, b, op)可求任何一种二元运算的值，其中参数op表示运算符，a和b分别表示左右两个运算对象。算法中允许直接引用函数operate (函数operate 不必定义)，如果需要还允许引用栈和队列的基本操作。 int computevalue(BiTree T) { if(T!=NULL) { if(T->lchild==NULL&&T->rchild==NULL) return T->data; int value1=computevalue(T->lchild); int value2=computevalue(T->rchild); return operate(value1,value2,T->data); } else return T->data; //若只含有根结点； ｝ 11、编写算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表（可以申明零时变量、指针）。 该链表带头节点、头节点和数据节点的结构定义如下 typedef struct LNode { ElemType data; Struct LNode* next; }List, LNode; 函数定义：void invert(List & L) （期中考试题） 12、编写算法计算给定二叉树中叶结点的个数。 其中树节点定义如下 typedef struct BiTNode{ DataType data; Struct BiTNode *LChild, * RChild; }BiTNode, *BiTree; 函数定义：CountLeaf (BiTree T, int & LeafNum) （期中考试题） 13、写出二叉树前根遍历的递归算法 已知二叉树结点定义为： struct node{ elemtp data; struct node *lc,*rc; ); Typedef struct node * bitreptr(指向根),*tpointer(指向一般结点); void preorder(bitreptr P) //P指向树根节点 void preorder(bitreptr P) { If(P!=0) { printf(P->data); preorder(P->lc); preorder(P->rc); } } 14、在邻接矩阵存储结构上实现图的基本操作： InsertVex(G,v)//插入顶点 Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v { if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK; }//Insert_Vex 15、已知某哈希表的装载因子小于1，哈希函数H（key）为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法，请编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。 void Print_Hash(HashTable H)//按第一个字母顺序输出Hash表中的所有关键字,