《2009软件工程专业数据结构B参考答案及评分标准》由会员分享，可在线阅读，更多相关《2009软件工程专业数据结构B参考答案及评分标准（6页珍藏版）》请在金锄头文库上搜索。
1、数据结构试卷（B）参考答案及评分标准一单项选择题（本大题共13小题，每题2分，共26分。将选择的答案填写在题干中的括号内）12345678910111213DACAABCBBBDDA、C二填空题（本大题共14小题，每题1分，共14分。将答案填写在横线上）1相邻2尾指针3p-rchild40546递增7入度8最长9110最好每次划分都能得到两个长度大致相等的子文件11堆12起泡13n+114n三判断对错题（本大题共6小题，每题1分，共6分。正确的打标记“”，错误的打标记“”，标记填写在括号内）123456四综合应用题（本大题共6小题，每题5分，共30分）1解： 构建的3阶B-树如下： （5分）1
2、022304756809920 29509840 582解：首先构造哈夫曼树，并为各分支打标记，如下图。（哈夫曼树：3分；哈夫曼编码：2分。）492524101486c5300001111abde然后，根据这棵哈夫曼树得到5个字母的哈夫曼编码，如下表：字母abcde对应的哈夫曼编码011110110010003解：首先选取顶点5，用普里姆算法构造连通网络G的最小生成树，依次所选择的边是：(5,2)，(2,3)，(3,1)，(3,6)，(6,4) （5分。答案不唯一；图示亦给分）4解：最好分成块 （2分）每块的最佳长度是 （2分） （1分）5解： （散列表：3分；查找不成功的平均查找长度：2分）
3、根据散列函数和采用拉链法处理冲突，建立散列表如下：04971152373418456在等概率情况下，查找不成功的平均查找长度 注：采用线性探查处理冲突给1分6解：各趟排序结果如下 （第一趟：2分；第二趟2分；第三趟1分）初始关键字49386597761327一趟排序结果38496597137627二趟排序结果38496597132776三趟排序结果13273849657697五算法设计题（本大题共3小题，每题8分，共24分）（注：答案不唯一；如用自然语言描述算法，亦相应给分）1解： void jomove(int S,int n) int temp,i,j; i=0; j=n-1; while
4、(ij) （4分，包括前面的初始化） while(ij)&(Si%2=1) i+;（4分，外循环的整个循环体） while(ij)&(Sj%2=0) j- -; if(irchild);/* RDL遍历*t右子树 */ （5分） printf(t%dn,p-key); /* 输出结点*t的关键字 */ inorder(t-lchild);/* RDL遍历*t左子树 */ 或非递归算法：BIGTOSMALL(bstnode *t)seqstack s; SETNULL(&s); p=t; while(1) while(p) PUSH(&s,p); p=p-rchild; if(EMPTY(&s)
5、 return; p=POP(&s); printf(“%d ”,p-key); p=p-lchild; 或递归算法#define maxsize 64keytype smaxsize; int t=-1;void inorder(bstnode *t)if(t) /* 二叉树t非空 */ inorder(t-lchild);/* LDR遍历*t左子树 */ s+t=p-key; /* 结点*t的关键字按中序序列顺序存放于数组s(栈)中 */ inorder(t-rchild);/* LDR遍历*t右子树 */ void print(void)while(t-1) /* 顺序出栈并输出各结点的
6、关键字 */printf(t%dn,st-);3解：typedef structint j; /* 找到的正整数在结点内数组中的下标 */ struct node *s; /* 找到的正整数所在结点的指针 */rcd; /* 返回值的类型 */void lsearch(linklist *head, int n, rcd *temp) /* temp用于传回查找结果 */ linklist *p; int i; p=head-next; while(p) （4分，包括前面的初始化、“p=p-next;” ）for(i=0;inext;”)、“temp-s=NULL;” ）if(p-datai=n)temp-j=i; temp-s=p; /* 查找成功 */ p=p-next; temp-s=NULL; /* 查找失败 */
