数据结构试题库答案算法设计题

算法设计题(10分)

(1)阅读下列递归算法，写出非递归方法实现相同功能的C程序。

void test(int &sum)

{ int x；

scanf(x)；

if(x=0) sum=0 else

printf(sum)；

}

＃include (1分)

void main() (1分)

{ int x,sum=0,top=0,s[]; (1分)

scanf(“%d”,&x)

while (x0)

{ s[++top]:=a; scanf(“%d”,&x); }(3分)

while (top)

sum+=s[top--]; (3分)

printf(“%d”,sum); (1分)

}

(2)试写出把图的邻接矩阵表示转换为邻接表表示的算法。

设图的邻接矩阵为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

for (int i=0; i

for ( int j=0; j

{ if (g[i][j]!=0 )

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

}

}

(3)阅读算法并根据输入数据画出链表。

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

}

输入数据为：text8

(4)阅读算法并指出下列各段程序完成的功能。

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

}

两个多项式相加

(5)阅读下面的程序，说明程序的具体功能。

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

(6)阅读下面的程序，说明程序的具体功能。

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进制

(7)阅读下面的程序，说明程序的具体功能。

void print(int w)

{ int i;

if ( w!=0)

{ print(w-1);

for(i=1;i

printf(“%3d,”,w);

printf(“/n”);

}

}

运行结果：

1，

2，2，

3，3，3，

(8)阅读下面的程序，分别说明程序中四个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

for (t=1;t

cpot[1]=1;

for (col=2;col

cpot[col]=cpot[col-1]+num[col-1];

for (p=1;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循环：初始化每一列中非零元素的个数为

第二个for循环，计算每一列中非零元素的个数；

第三个for循环，计算每一列的第一个元素的首地址；

第四个for循环，转置过程；

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

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

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

}

}

ABVDVVCEVFGVVV8

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

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

}

}

(11)阅读下面的程序，分别指出程序中三个for循环、整个程序以及语句scanf("%d,%d",&G.vexnum,&G.arcnum);的功能。

void funcgraph(MGraph &G)

{int i,j,k,w;char v1,v2;

printf("Input vexnum & arcnum:");

scanf("%d,%d",&G.vexnum,&G.arcnum);

printf("Input Vertices:");

for (i=0;i

scanf("%c",&G.vexs[i]);

for (i=0;i

for (j=0;j

G.arcs[i][j]=0;

for (k=0;k

{printf("Input Arcs(v1,v2 & w):\n");

scanf("%c%c,%d",&v1,&v2,&w);

i=LocateVex(G,v1);

j=LocateVex(G,v2);

G.arcs[i][j]=w; G.arcs[j][i]=w;

}

}

第一个for循环：将图中的顶点输入到数组G.vexs[i]；

第二个for循环，初始化邻接矩阵；

第三个for循环，将图中边信息存入数组G.vexs[i]中；

本程序的功能是：创建图的邻接矩阵；

scanf("%d,%d",&G.vexnum,&G.arcnum);：语句的功能输入定点数和图中的边数。

设哈希（Hash）表的地址范围为～17，哈希函数为：H（K）＝K MOD 16。

K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：

（10，24，32，17，31，30，46，47，40，63，49）

造出Hash表，试回答下列问题：

（1）画出哈希表的示意图；

（2）若查找关键字63，需要依次与哪些关键字进行比较？

（3）若查找关键字60，需要依次与哪些关键字比较？

（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

解：（1）画表如下：

（2） 查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,no;

然后顺移，与46,47,32,17,63相比，一共比较了6次！

（3）查找60,首先要与H(6)=6%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

（4） 对于黑色数据元素，各比较1次；共6次；

对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，