算法与设计六套试卷(7)

//则返回0。 if (2) then return 0 else mid=?(low?high)/2? if (3) then return mid else if A[mid]

for i=1 to n C[i, i]= （1） for d=1 to n-1 for i=1 to n-d ＿＿＿＿＿号学 栏＿＿ ＿ ＿ ＿ ＿ 名 息姓 级 年线 ＿ 信 ＿ ＿ ＿ ＿ ＿ 业 生专订 ＿ ＿ ＿ ＿ ＿ 考＿ 系 ＿装＿＿＿＿＿院学＿＿＿＿＿＿ j= (2) C[i, j]= ∞ for k=i+1 to j x= (3) if x

x=x0; y=y0 ; tag[x, y]=1 m=n*n i=1; k[i]=0 while (1) and not flag while k[i]<8 and not flag k[i]= (2) x1= x+dx[k[i]]; y1= y+dy[k[i]] if ((x1,y1)无越界and tag[x1, y1]=0) or ((x1,y1)=(x0,y0) and i=m) then x=x1; y=y1 tag[x, y]= (3) if i=m then flag=true else i= (4) (5) end if end if end while i=i-1 (6) (7) end while if flag then outputroute(k) //输出路径 else output “no solution” end HORSETRAVEL

33

＿＿＿＿＿号学 ＿＿ 栏＿＿ ＿ ＿ 名 姓 息 级 年线 ＿ ＿ ＿ 信 ＿ ＿ ＿ 业 专订 ＿ 生 ＿ ＿ ＿ ＿ ＿ 系 考＿装＿＿＿＿＿院学＿＿＿＿＿＿ 四．算法设计题（15分） 1. 一个旅行者要驾车从A地到B地，A、B两地间距离为s。A、B两地之间有n个加油站，已知第i个加油站离起点A的距离为di公里，0=d1?d2???dn?s，车加满油后可行驶m公里，出发之前汽车油箱为空。应如何加油使得从A地到B地沿途加油次数最少？给出用贪心法求解该最优化问题的贪心选择策略，写出求该最优化问题的最优值和最优解的贪心算法，并分析算法的时间复杂性。 福建师范大学数学与计算机科学学院 2006 — 2007学年第二学期考试 C 卷

34

＿＿＿号学 ＿＿＿＿ 栏＿＿ 名 姓 息 级 年线 ＿ ＿ ＿ ＿ ＿ 信 ＿ 业 专订 ＿ ＿ ＿ 生 ＿ ＿ ＿ 系 ＿装 ＿ 考＿＿＿＿院学＿＿＿＿＿＿

专 业：计算机科学与技术 年 级： 2005级 课程名称: 算法设计与分析 任课教师： 潘日晶 试卷类别：开卷（ ）闭卷（√） 考试用时： 120 分钟 考试时间: 年 月 日 午 点 分 题号 一 二 三 四 五 总得分 评卷人 得分 题号 六 七 八 九 十 得分 35