发布时间 : 星期三 文章安徽大学数据结构期末考试题 (2)更新完毕开始阅读547a258fe009581b6bd9eba6
4、用Dijkstra算法思想计算源点A到各顶点的最短路径如下表所示
其中A到B、C、D、E最短路径正确分别得1分，A到F、G最短路径正确分别得2分 5.
一次划分后{24，21，32，13，15}35{86，71，110，54，44，130} (2分) 二次划分后{15，21，13}24{32}35{44，71，54}86{110，130} （4分） 三次划分后{13}15{21}24{32}35， 44 {71，54，}86，110{130} （6分） 四次划分后{13}15{21}24{32}35，44，{54}71，86，110{130} （8分） 结束{13，15，21，24，32，35，44，54，71，86，110，130} 仅写出最终的排序序列，不得分。 6、（1）
（2）ASL=（1*7+4+5+6*2）/11=28/11
正确答出线性探测法给5分（其中正确计算哈希地址给2分，正确解决冲突给3分） 正确算出平均查找长度给3分。 四、算法设计题
1．Function getnumber(bt:link):intrger Begin
If bt=nil then getnumber:=0 （1分） Else if (bt^.lchild<>nil) and (bt^rchild<>nil)
Then getnumber :=getnumber(bt^.lchild)+getnumber(bt^.rchild)+1 （4分） Else getnumber :=getnumber(bt^.lchild)+getnumber(bt^.rchild) （7分） End
此题答案不唯一。算法设计不完全正确，可酌情给分。 2. Procedure print_order(head:linklistp); Var p,s,:linklistp; Temp:interger; Begin
P:=head;temp:=p^.next.data;s:=p; （1分） Repeat
While (p^.next.data<>nil) do Begin
If p^.next.data Temp:=p^.next.data; End （4分） P:=p^next End; （5分） P:=head; Write(s^.next.data); （6分） S:=p; Until p^.next=nil End. （8分） 此题答案不唯一。算法设计不完全正确，可酌情给分。