算法设计题(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次,
领取专属 10元无门槛券
私享最新 技术干货