资源描述：
《安徽大学数据结构期末试卷05-06-1-A答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《数据结构》试卷A参考答案与评分标准一、单项选择（每小题2分，共20分）1.D2.B3.B4.A5.B6.A7.B8.C9.D10.A二、填空题（每空2分，共20分）1.物理位置相邻2.中序遍历log2（i）log2（j）=3．4．4次5.孩子兄弟表示法6.移动7.健壮性8．12534768910；123456789109.n+1三、应用题(第2题6分，1、3、4题每题8分，5题10分，共40分)1．解：设A为最小生成树顶点集，B为最小边集，W为权值。求最小路径如下：（1）A={0，1}B={<0，1>}W=6；（2）A={0，1，6}B={<0，1
2、><1，6>}W=10（3）A={0，1，6，2}B={<0，1><1，6><6，2>}W=19（4）A={0，1，6，2，3}B={<0，1><1，6><6，2><2，3>}W=24（5）A={0，1，6，2，3，4}B={<0，1><1，6><6，2><2，3><3，4>}W=34（6）A={0，1，6，2，3，4，5}B={<0，1><1，6><6，2><2，3><3，4><0，5>}W=46015643245612105此题评分标准：六个步骤每步1分，画出最小生成树2分，具体情况酌情给分IABCDEFGHJK2．GHJIK森林转化为二叉树的过
3、程如下：FECDBA此题评分标准：每正确转换一棵二叉树给1分，直接写出结果不扣分，具体情况酌情给分。3．快速排序的每趟结果如下：第一趟排序结果：{1295}23{6839624833}第二趟排序结果：{59}1233{33396248}68第三趟排序结果：59122333{396248}68第四趟排序结果：5912233339{6248}68第五趟排序结果：5912233339486268此题评分标准：正确给出每趟排序结果给2分，排序思想不对，不给分。具体情况酌情给分。4．①顺序查找顺序表如下：存储地址012345678910数据元素10243217
4、31304647406349查找次数1234567891011查找成功平均查找长度ASL=（11+1）/2=6②二分查找二分查找的判定树如下3247241030634017493146查找成功平均查找长度ASL=（1＊1+2＊2＋3＊4＋4＊4）/11=33247241030634017493146③二叉排序树查找二叉排序树如下图所示查找成功平均查找长度：ASL=（1+2+2*3+2*4+3*5+6+7）/11=45/11≈410,24,32,17,31,30,46,47,40,63,49④散列查找：(a)线性探测法解决充突得到的散列表如下：哈希地址
5、0123456789101112131415数据元素3217464763492440103031查找次数11556512111查找成功平均查找长度：ASL=（1＊6+2+5＊3+6）/11＝29/11＝2.6(b)拉链法解决充突得到的散列表如下010^30311040^32^1746^4763^63^123456789101112131415查找成功平均查找长度：ASL=（1＊6+2*4+3）/11＝17/11＝1.5评分标准：正确给出顺序查找的存储形式和平均查找长度ＡＳＬ给2分正确给出二分查找的存储形式和平均查找长度ＡＳＬ给２分正确写出二叉排序树查
6、找的存储形式和平均查找长度ＡＳＬ给2分正确写出散列查找（线性探测法）的存储形式和平均长度ＡＳＬ给2分正确写出散列查找（拉链法）的存储形式和平均查找长度ＡＳＬ给２分５．解：各路径如下：始点终点最短路径路径长度评分标准AＢ（Ａ,C,E,G,Ｂ）１42分Ｃ（ＡＣ）２1分Ｄ（Ａ,Ｃ,Ｆ,Ｄ）１１2分Ｅ（Ａ,Ｃ,Ｅ）１０1分Ｆ（Ａ,Ｃ,Ｆ）６1分Ｇ（Ａ,Ｃ,Ｅ,Ｇ）１21分四１．判定一棵二叉树是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。intJudgeComplete(BiTreebt){tag=0;
7、p=bt;if(p==null)return(1);InitQueue(Q);//Q是队列,初始化队列EnQueue(Q,p);//入队操列，队中元素是二叉树结点指针,根结点指针入队while(!QueueEmpty(Q)){//队列非空p=DeQueue(Q);//出队if(p->lchild&&!tag)EnQueue(Q,p->lchild);//左子女入队else{if(p->lchild)return0;//前边已有结点为空，本结点不空elsetag=1;//首次出现结点为空}if(p->rchild&&!tag)EnQueue(Q,p->
8、rchild);//右子女入队else{if(p->rchild)return0;elsetag=1;}}/
