数据结构模拟试题5参考答案

1、数据结构模拟试题5参考答案一、选择题（20分）1-5 CCDAA6-10DBCBB二、填空题（20分）1结点*p的左右链域为空2深度优先3N-14AN/264，9，14，17，2070入度减1环三、应用题（30分）1参考答案如下： 1）二叉树EABDGCFHI2）对应的森林FHICEABDG2参考答案如下：806040120701003参考答案如下：1）G1的邻接表和G1的逆邻接表123423 V1V2 V3V44 1 1234V1V2V3V44 3 1 1 2）G1的强连通分量4参考答案如下：1）以所有字符的权值作为叶结点构成的哈夫曼树如下：11425716192）所有字符的哈夫曼编码如下：

2、A（7）： 0011B（19）： 011C（5）： 0010D（16）： 010E（42）： 01F（11）： 0005参考答案如下：事件的发生时间 活动的开始时间Vivevlaiell-eV100a1055V267a2000V333a3341V41212a4671V51818a5330V62121a631411a712120a812197a9181806参考答案如下：1）该序列是一个小根堆2）该序列不是一个小根堆，调整如下：3829612023355625287640100四算法设计题（30分）1算法源代码如下： void fun(bitree T, char x, int m) if(T)

3、 m+; if(T-data=x) printf(%d,m); return ; fun (T-lchild,x,m); fun (T-rchild,x,m); main() bitree bt; int m=0;fun(bt,m); 2算法源代码如下： #define maxsizetypedef struct int elemmaxsize; int top2;stack;stack s;1）入栈操作int push(int i,int x) if(i1) printf(输入数据有误); return 0; if(s.top1-s.top0=1) printf(栈满); return 0;

4、 switch(i) case 0: s.elem+s.top0=x; break; case 1: s.elem-s.top1=x; return 1;2）出栈操作int pop(int i, int *x) if(i1) printf(输入数据有误); return 0; switch(i) case 0: if(s.top0=-1) printf(栈空); return -1; else *x=s.elems.top0-; break; case 1: if(s.top0=maxsize) printf(栈空); return -1; else *x=s.elems.top1+; ret

5、urn 1;3算法源代码如下： void dijkshort(mgraph G,int v) int s30; int d30; int pre30; int i,j,k,p,min; for(i=1;i=G.vexnum;i+) di=G.arcsvi; si=0; if(di32767) prei=v;else prei=0; sv=1; for(i=1;i=G.vexnum;i+) min=32767; k=0; for(j=1;j=G.vexnum;j+) if(!sj&djmin) min=dj;k=j; if(k=0) /*已没有顶点可往第一组加*/ return; else sk=1; /*将找到的顶点加入到第一组中*/ for(j=1;jdk+G.arcskj) dj=dk+G.arcskj; prej=k; for(j=1;j=G.vexnum;j+) /*输出结果*/ if(prej) printf(n%c,G.vexsj); p=prej; while(p)printf(%c,G