数据结构试题库(4)

for ( int j=0; j

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; } } }

123. 阅读算法并根据输入数据画出链表。

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?

124. 阅读算法并指出下列各段程序完成的功能。

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; }

head t e x t ^ 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); }

两个多项式相加

125. 阅读下面的程序，说明程序的具体功能。 typedef int elementype typedef struct node { elemtype data;

strunct node *next; }linklist;

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的数据元素。

126. 阅读下面的程序，说明程序的具体功能。

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进制 127. 阅读下面的程序，说明程序的具体功能。

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，

128. 阅读下面的程序，分别说明程序中四个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].e=M.data[p].e;

T.item [q].j=M. item[p].i; ++cpot[col]; } } return OK; }

第一个for循环：初始化每一列中非零元素的个数为0 第二个for循环，计算每一列中非零元素的个数； 第三个for循环，计算每一列的第一个元素的首地址； 第四个for循环，转置过程；

++cpot[col]：语句的功能是当每一列进行一次转置后，其位置向后加

1。

129. 已知二叉树的二叉链表存储表示，指出建立如图所示树的结构时输入的字符序列。

typedef struct BiTNode { char data;

struct BiTNode *lchild,*rchild; } BiTNode;

void CreateBiTree( BiTNode *T) { char ch; scanf(&ch);

if(ch= =? ?) T=NULL;

else{ T=(BiTNode *)malloc(sizeof(BiTNode)); while (T==NULL)

T=(BiTNode *)malloc(sizeof(BiTNode)); T–>data=ch;

CreateBiTree(T–>lchild); CreateBiTree(T–>rchildd);

GB D E F C A } }

AB?D??CE?FG????

130. 已知二叉树的二叉链表存储表示，写出中序遍历的递归算法。

typedef struct BiTNode { char data;

struct BiTNode *lchild,*rchild; } BiTNode,*BiTree;

void inorder( BiTNode *p) { if (p!=NULL)

{ inorder(p–>lchild); printf(“%c”,p–>data) inorder(p–>rchild); } }

131. 阅读下面的程序，分别指出程序中三个for循环、整个程序以及语句scanf(\ 的功能。

void funcgraph(MGraph &G) { int i,j,k,w; char v1,v2;

printf(\ scanf(\ printf(\ for (i=0;i

for (j=0;j

G.arcs[i][j]=0; for (k=0;k

{ printf(\

scanf(\i=LocateVex(G,v1); j=LocateVex(G,v2);