参考答案：链地址表全对给8分。错一个结点扣1分，扣完为止。
0 1 2 3 4 5 6 7 8 9 10 11 12
ASLsucc=(7+4)/13=11/9（1分） ASLunsucc=(5+4)/13=9/13（1分）
四、算法设计题(10分)
(254) 阅读下列递归算法，写出非递归方法实现相同功能的C程序。
void test(int &sum)
{ int x； scanf(x)；
if(x=0) sum=0 else {test(sum); sum+=x;} printf(sum)； }
＃include
{ int x,sum=0,top=0,s[]; (1分) scanf(“%d”,&x) while (x<>0)
{ s[++top]:=a; scanf(“%d”,&x); }(3分) while (top)
sum+=s[top--]; (3分)
printf(“%d”,sum); (1分)
→ 13 → 46 → 53 ^ → 41 → 22 ^ ^ ^
^ ^
^ ^
→ 1 → 67 ^ ^ ^
→ 30 ^ → 51 ^
}
(255) 试写出把图的邻接矩阵表示转换为邻接表表示的算法。
设图的邻接矩阵为g[n][n]（针对无向图），定义邻接表节点的类型为 struct edgenode { int adjvex; edgenode next; }
typedef edgenode *adjlist[n]; void matritolist (int g[][], adjlist gl, int n ) { edgenode *p, *q;
for (int i=0 i p = ( edgenode *) malloc(sizeof (edgenode)); p->adjvex=j; p->next=null; if (gl[i]=null) { gl[i]==p; q=p; } else ( q->next=p; q=p; } } } (256) 阅读算法并根据输入数据画出链表。 linklist createlistr1( ) { char ch; linklist head=(listnode*)malloc(sizeof(listnode)); listnode *p，*r； r=head; while((ch=getchar( ))!=‵\\n′) { p=(listnode*)malloc(sizeof(listnode)); while (p) p=(listnode*)malloc(sizeof(listnode)); p–>data=ch; r–>next=p; r=p; } r–>next=NULL; return(head); } 输入数据为：text? (257) 阅读算法并指出下列各段程序完成的功能。 void add_poly(Lnode *pa,Lnode *pb) { Lnode *p,*q,*u,*pre; int x; p=pa->next; q=pb->next; pre=pa; while((p!=NULL) && ((q!=NULL)) { if (p->exp < q->exp) { pre=p; p=p->next; } else if (p->exp= =q->exp) { x=p->coef+q->coef; if (x!=0) { p->coef=x; pre=p;} else { pre->next=p->next; free(p); } p=pre->next; u=q; q=q->next; free(u); } else { u=q->next;q->next=p;pre->next=q; pre=q; q=u; } } if (q!=NULL) pre->next=q; free(pb); } 两个多项式相加 (258) 阅读下面的程序，说明程序的具体功能。 typedef int elementype typedef struct node { elemtype data; strunct node *next; }linklist; head t r x t ^ void function( linklist *head, elemtype x ) { linklist *q, *p; q=head; p=q-next; while (p !=NULL) && (p->data != x ) { q=p; p=p->next; } if (q==NULL) printf (“there is no this node ::\\n”); else { q ->next =p ->next ; free (p); } } 该程序的功能是：在带头结点的单链表中，删除单链表中枝为z的数据元素。 (259) 阅读下面的程序，说明程序的具体功能。 void function( ) { initstack(s); scanf (“%”,n); while(n) { push(s,n%8); n=n/8; } while(! Stackempty(s)) { pop(s,e); printf(“%d”,e); } } 该程序的功能是：10进制数转换为8进制 (260) 阅读下面的程序，说明程序的具体功能。 void print(int w) { int i; if ( w!=0) { print(w-1); for(i=1;i<=w;++i) printf(“=,”,w); printf(“/n”); } } 运行结果： 1， 2，2， 3，3，3， (261) 阅读下面的程序，分别说明程序中四个for循环和语句 ++cpot[col];的具体功能。 void FastTransposeSMatrix(Matrix M, Matrix &T) { T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) { for (col=1;col<=M.nu;++col) num[col]=0; for (t=1;t<=M.tu;++t) ++num[M. item[t].j]; cpot[1]=1; for (col=2;col<=M.nu;++col) cpot[col]=cpot[col-1]+num[col-1]; for (p=1;p<=M.tu;++p) { col=M. item[p].j; q=cpot[col]; T.item[q].i=M.data[p].j; T.item [q].j=M. item[p].i; T.item[q].e=M.data[p].e; ++cpot[col]; } } return OK; } 第一个for循环：初始化每一列中非零元素的个数为0 第二个for循环，计算每一列中非零元素的个数； 第三个for循环，计算每一列的第一个元素的首地址； 第四个for循环，转置过程； ++cpot[col]：语句的功能是当每一列进行一次转置后，其位置向后加1。 (262) 已知二叉树的二叉链表存储表示，指出建立如图所示树的结构时输入的字符序列。 typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; } BiTNode; void CreateBiTree( BiTNode *T) B D E F C A G