};
2、堆分配存储方式下，串连接函数。 typedef struct {
char * ch； int len； } HString；
HString *s， t;
Status StrCat(s， t) /* 将串t连接在串s的后面 */ {
int i;
char *temp;
f if (temp==NULL) return(0); for (i=0; ;i++) temp［i］=s->ch［i］;
for ( ;i
fr s->ch=temp; return(1); }
3、向单链表的末尾添加一个元素的算法。 LNode是一个包含（data，Next）的结构体
Void InsertRear(LNode*& HL,const ElemType& item) {
LNode* newptr; newptr=new LNode;
If (______________________) {
cerr<<\exit(1); }
________________________=item; newptr->next=NULL; if (HL==NULL)
HL=__________________________; else{
LNode* P=HL;
While (P->next!=NULL) ____________________; p->next=newptr; }
}
4、L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。
LinkList f30(LinkList L, int c) {
LinkList Lc,p,pre; pre=L;
p= (1) ; p=L->next
Lc=(LinkList) malloc(sizeof(ListNode)); Lc->next=Lc; while(p!=L) if(p->data>c) {
pre->next=p->next;
(2) ; p->next=Lc->next Lc->next=p; p=pre->next; } else {
pre=p;
(3) ; p=p->next }
return Lc; }
5、已知图的邻接链表的顶点表结点结构为
边表结点EdgeNode的结构为
adjvex vertex firstedge next 下列算法计算有向图G中顶点vi的入度。请在空缺处填入合适的内容，使其成为一个完整
的算法。 int FindDegree(ALGraph *G,int i)//ALGraph为图的邻接表类型 {
int dgree, j;
EdgeNode *p;
degree= (1) ; 0 for(j=0;j
p=G->adjlist［j］. firstedge; while ( (2) ) p {
if( (3) ) p->adjvex==i {
degree++; break; }
p=p->next; } }
return degree;
}
六 简单应用题
1、已知一个非空二叉树，其按中根和后根遍历的结果分别为： 中根：C G B A H E D J F I
后根：G B C H E J I F D A
试将这样二叉树构造出来;若已知先根和后根的遍历结果，能否构造这棵二叉树，为什么?
(基本方法：先由后根序列确定根结点，再到中序序列中分割该二叉树)
2、对于下图，画出按Kruskal（克鲁斯卡尔）算法和Prim（普里姆）算法构造最小生成树的过程。
3、画出由下面的二叉树转换成的森林。
4、用Floyed（弗洛伊徳）算法求下图每一对顶点之间的最短路径及其长度，将计算过程的中间和最后结果填入下表：
A 1 2 3 PATH 1 2 3
A 1 2 (0)(0) A 3 1 2 (1)(1) A 3 1 2 (2)(2) A 3 1 2 (3)(3) 3 PATH 1 2 3 PATH 1 2 3 PATH 1 2 3 PATH 1 2 3 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Rchild 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)
2、假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注:已知树中结点数）
由于以双亲表示法作树的存储结构，找结点的双亲容易。因此我们可求出每一结点的层次，取其最大层次就是树有深度。对每一结点，找其双亲，双亲的双亲，直至（根）结点双亲为0为止。
int Depth(Ptree t) //求以双亲表示法为存储结构的树的深度，Ptree的定义参看教材
{int maxdepth=0;
for(i=1;i<=t.n;i++) {temp=0; f=i;
while(f>0) {temp++; f=t.nodes[f].parent; } // 深度加1,并取新的双亲
if(temp>maxdepth) maxdepth=temp; //最大深度更新
}
return(maxdepth);//返回树的深度 } //结束Depth
3、设计建立有向图正邻接矩阵的函数（数据输入格式自定）。 Typedef struct
{ int data[ maxsize][maxsize]; int dem,e; }sqgraph;
sqgraph crt (sqgraph g)
{ scanf(n,e);g.dem=n; for (i=1;i<=n;i++) for (j=1;j<=n;j++) g.data[i][j]=0;