安徽大学数据结构期末考试题 (2)

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分）

此题答案不唯一。算法设计不完全正确，可酌情给分。