三、解答题（共５０分）
1．设有一种数据结构Ｂ的元素集合Ｋ和它的二元关系Ｒ为： B=(K,R)
K={K1,K2??K7}
R={
2. 将下面所示的森林转换成一棵二叉树（按字母序号顺序），并分别写出二叉树的先序、中序、后序的遍历序列。（6分）
3. 假设用于通信的电文有8个字母A,B,C,D,E,F,G,H组成，各字母在电文中出现的频率为5%，25%，4%，7%，9%，12%，30%，8%，试为这8个字母设计哈夫曼编码，并求其带权路长度WPL。(要求权值集取{5,25,4,7,9,12,30,8}，按照左子树权值小于右子树的权值的顺序构造哈夫曼树，并注明每个节点的权值。) (10分)
4对下面的带权图按照普里姆法从顶点V1出发构造一棵最小生成树，并求该生成树的权值。（要求：每加入一个结点，画一个图）（8分）
5，设有一组关键字（4，9，26，10，12，33，22，19），利用哈希函数为：H（key）=key，采用线性探测散列处理冲突，试在0～10的散列地址空间中对该组关键字构造哈希表，并求在关键字的查找概率相等的前提下查找成功的平均查找长度。（要求：直接写出哈希表格，查找长度表示为分数形式）（10分）
6，对长度为n的记录序列进行快速排序时，所需要的比较次数依赖于这几个元素的初始序列。点n=8时，在最好的情况下共需要进行多少次比较？（要求：写出每一趟的划分情况和比较次数。）（10分）
四，算法设计题（共10分）
试编写一个在带有头结点的双向循环链表中为x的结点之前，插入值为y的结点的算法。（要求：用C语言描述，结点类型定义为dlnode） Status InsertPrior-L(DlinkList &L)
五、程序填空题
1.华氏温度与摄氏度的转换公式为：C=5/9×（F-32），其中表示C摄氏温度，F表示华氏温度。要求输出从华氏0°到华氏300°，每隔20°一个值。 main()
{int upper,step;
float fahr=0.0,celsius; upper=300;step=20;
while( 2.求两数中的较大值。 #include {int a ,b,max; printf(“please input:\\n”); scanf(“%d%d”, ); max=a; max=b; printf(the max is :%d\\n“,max); } 3. 输入一行字符，分别统计出其中英文字母、空格、数字和其他字符的个数。 #include int letters=0,space=0,digit=0,other=0; printf(“please input characters\\ n”); while((c=getchar())! =?\\n?) {if(c>=?a?&&c<=?z?|| ) ; else if(c==? ?) ; else if (c>=?0?&&C<=?9?) ; else ; } printf(“%d%d%d%d\\n”,letter,space,digit,other); } 4程序读入20个整数，统计非负数的个数，并计算非负数的和。 #include {int i，a[20],s,count; s=0;count=0; for(i=0;i<20;i++) scanf(“%d”, ); for(i=0;i<20;i++) {if(a[i]<0) ; s+=a[i]; count++; } printf(“s=%d\\t count=%d\\n”,s,count); } 5.计算一个3×3矩形对角线元素之和。 mian（） {float a[3][3],sum=0; int i,j; print(“please input the matrix:\\n”); for(i=0;i<3;i++) for(j=0;j<3;j++) scanf(“%f”, ); for(i=0;i<3;i++) sum= ; prinf(“the result is :%f\\n”,sum); } 六、读程序写结果 1. # include “stdio.h” main() {int a,b,c; printf(“please input:\\n”); scanf(“%d,%d,%d”,&a,&b,&c); if(a printf(“max=%d\\n”,c); else printf(“max=%d\\n”,b); else if(a printf(“max=%d\\n”,c); else printf(“max=%d\\n”,a); } 本程序的功能为 。 2. #include< stdio.h> main() {int count,num,total; count=0;total=0; while(count<10) {count++; printf(“enter the NO.%d=”,count) scanf(“%d”,&num); total+=num; } printf(“Total=%\\n”,total); } 本程序若输入 0 1 2 3 4 5 6 7 8 9十个数，输出的结果是 。 3. #include< stdio.h> int a[2][3]={{1,2,3},{4,5,6}}; main() {int i,j,b[3][2]; for(i=0;i<=1;i++) for(j=0;j<=2;j++) b[j][i]=a[i][j]; for(i=0;i<=2;i++) for(j=0;j<=1;j++) printf(“%d\\”,b[i][j]); } 本程序的输出结果为 。 4. #include< stdio.h> main() {int a [10]={1,2,3,4,5,6,7,8,9,0}; int *p,i; printf(“\\n”); for(p=a;p<(a+10);p++) printf(“%d”,*p); printf(“\\n”); } 本程序的输出的结果是 。 七、编程题(共10分) 请编写一个完整的程序，要求输入一个整型3×4矩阵，求其中最大元素的值并输出。 （答案请联系(mail)：xpengj@163.com）