算法设计与分析试题2007A

中国科学院研究生院

试 题 专 用 纸

课程编号：

课程名称：计算机算法设计与分析 任课教师：陈玉福

———————————————————————————————————————————————

姓名 学号 成绩 一． (共20分，每小题5分) 回答下列问题

1．已知求解问题?的两个算法A1,A2的时间复杂性函数分别为T1(n)?n2n/2和

T2(n)?nlog2n。现在有两台计算机C1,C2，它们的速度比为64。如果采用算法A1，计算机C1求解问题?的一个实例I所用的时间为T，那么，采用算法A2时，计算机C2能够在时间T内求解问题?的多大输入规模的实例？

2．何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什么问题的什么特性提高效率的？

3．阐述回溯算法与分枝限界算法的区别和联系，各自强调改善那方面以提高效率？ 4．多项式时间确定性算法与多项式时间非确定性算法的主要区别是什么？

二． (12分) 下面是插入排序算法，试分析它在最坏情况下的时间复杂度和平均时间复杂

度。

插入排序算法

proc InSort(a, n)

for i from 2 to n do t:=a[i]; integer j;

for j from i-1 to 1 do

if t

end{for} end{InSort}

三． (12分) 用动态规划算法求下图中从顶点0到顶点6的所有最短路径和最长路径。

4 6 8 5 4 5 7 6 8 4 9 4 9 4 4 5 4 4 4

共 2 页 第 1 页

四． (11 分) 将宽度优先搜索算法中的队列改成栈，其它不变，则得到D－检索算法。下

面是一个无向图及其邻接链表，试画出图G的D－检索生成树，并标出各节点被访问的次序号。

A B C D E F G H

B A A B B C C D C 0 D F H 0 H H H 0 E F G 0

F 0 E 0 D H E 0 G 0 B E F C A G 无向图G和它的邻接链表

五． (15分) 有5个物体，其重量分别为3，5，7，8，9，价值分别为4，6，7，9，10。有

一背包，载重量为22，物体不可分割地往背包里装。试画出用优先级队列式分枝限界算法LCKNAP解此0/1背包问题所生成的解空间树，并给出最优解。

六． (共10分,每小题5分) 假定已知“无向图的Hamilton圈”问题是NP-完全问题.

1. 证明旅行商问题判定模式也是NP-完全问题；

2. 证明旅行商问题优化模式不是NP-完全问题，但是NP难问题。

共 2 页 第 2 页