华南农业学期末考试试卷（A卷）
2008学年第学期 考试科目： 算法分析设计
考试类型：（闭卷） 考试时间： 120 分钟
学号 姓名 年级专业
题号
二
三
四
总分
分
评阅
选择题（20分题2分）
1 述表达正确 D
A．n22 + 2n渐进表达式界函数O(2n)
B．n22 + 2n渐进表达式界函数Ω(2n)
C．logn3渐进表达式界函数O(logn)
D．logn3渐进表达式界函数Ω(n3)
2 输入规模n时算法增长率 A
A．5n B．20log2n C．2n2 D．3nlog3n
3 T（n）表示输入规模n时算法效率算法效率优 C
A．T（n） T（n – 1）+1T（1）1 B．T（n） 2n2
C．T（n） T（n2）+1T（1）1 D．T（n） 3nlog2n
4 棋盘覆盖问题中2k×2k特殊棋盘（特殊方块）需L型骨牌数 A
A．（4k – 1）3 B．2k 3 C．4k D．2k
5 寻找n元素中第k元素问题中快速排序算法思想运分治算法n元素进行划分应选择划分基准？面 答案解释合理D
A．机选择元素作划分基准
B．取子序列第元素作划分基准
C．中位数中位数方法寻找划分基准
D．皆行方法算法复杂度界
6 9村庄坐标位置表示：
i
1
2
3
4
5
6
7
8
9
x（i）
1
2
3
4
5
6
7
8
9
y（i）
1
2
3
4
5
6
7
8
9
现盖邮局9村庄服务请问邮局应该盖 邮局9村庄总距离短C
A．（450） B．（4545） C．（55） D．（50）
7 n拎着水桶水龙头前面排队水水桶水桶必须满水水流恒定 说法正确？A
A．水桶先水排队时间
B．水桶先水排队时间
C．水桶先水某确定时间t水
D．短时间n完水什序实样
8 分治法设计思想难直接解决问题分割成规模较子问题分解决子问题子问题解组合起形成原问题解求原问题子问题 C
A．问题规模相问题性质相 B．问题规模相问题性质
C．问题规模问题性质相 D．问题规模问题性质
9 布线问题 正确描述C
A．布线问题解空间图
B．方格阵列四周设置围墙增设标记附加方格预处理算法简化边界判定
C．采广度优先标号法找起点终点布线方案（方案果存话）定短
D．采先入先出队列作活结点表终点b扩展结点活结点队列空作算法结束条件
10 含n元素子集树问题坏情况解空间叶结点数目 B
A．n B．2n C．2n+11 D．
二填空题（10分题2分）
1算法复杂性高低体现计算机运行该算法需时间存储器资源算法复杂性 复杂性空间复杂性分
参考解答：时间
2出衡子问题思想通常分治法分割原问题形成干子问题时子问题规模致
参考解答：相
3二分搜索算法n序元素表中搜索特定元素佳情况搜索时间复杂性O（ ）坏情况搜索时间复杂性O（ ）
参考解答：1 logn
4已知分治算法耗费计算时间T(n)T(n)满足递方程：
解递方T(n) O（ ）
参考解答：
5动态规划算法变形方法 种方法动态规划算法底填充方顶递方解子问题建立备忘录备需时查样避免相子问题重复求解
参考解答：备忘录方法
三简答题（40分题8分）
1（8分）写出列复杂性函数偏序关系（渐进阶低高排序）：
参考解答：
2（8分）现8位运动员进行网球循环赛设计满足求赛日程表：
（1） 选手必须选手赛次
（2） 选手天赛次
（3） 循环赛进行n – 1天
请利分治法思想8位运动员设计合理赛日程
参考解答：
1
2
3
4
5
6
7
8
2
1
4
3
6
5
8
7
3
4
1
2
7
8
5
6
4
3
2
1
8
7
6
5
5
6
7
8
1
2
3
4
6
5
8
7
2
1
4
3
7
8
5
6
3
4
1
2
8
7
6
5
4
3
2
1
3（8分）某体育馆羽毛球场出租现总10位客户申请租羽毛球场客户租时间单元表示s(i)表示开始租时刻f(i)表示结束租时刻10客户申请表示：
i
1
2
3
4
5
6
7
8
9
10
s(i)
0
3
1
5
3
5
11
8
8
6
f(i)
6
5
4
9
8
7
13
12
11
10
时刻该羽毛球场租位客户请设计租安排方案10位客户里面体育馆满足位客户需求算出针表10客户申请安排位客户申请
参考解答：10位客户申请结束时间f(i)递增排序表：
i
1
2
3
4
5
6
7
8
9
10
s(i)
1
3
0
5
3
5
6
8
8
11
f(i)
4
5
6
7
8
9
10
11
12
13
1） 选择申请1（14）
2） 次检查续客户申请已选择申请相容突选择该申请直申请检查完毕申请4（57）申请8（811）申请10（1113）
3） 满足：申请1（14）申请4（57）申请8（811）申请10（1113）4客户申请已满足客户数
4（8分）矩阵连需少数次数问题递关系式：
中m[ij]计算矩阵连Ai…Aj需少数次数pi1矩阵Ai行矩阵Ai列现四矩阵中矩阵维数分：
A1
A2
A3
A4
50´10
10´40
40´30
30´5
p 0´ p 1
p 1´ p 2
p 2´ p 3
p 3´ p 4
请根递关系计算出矩阵连积A1A2A3A4需少数次数
参考解答：
5（8分）样类特殊01背包问题：选物品重量越轻物品价值越高
n6c20P（4815163）W（5321048）
中n物品数c背包载重量P表示物品价值W表示物品重量请问01背包问题应选择放进物品放进背包物品总价值获总价值少？
参考解答：该0－1背包问题较特殊恰重量越轻物品价值越高优先取重量轻物品放进背包终重量分2345三物品放进背包价值15 + 8 + 6 + 4 33值
四算法设计题（30分前三题题8分题6分）
1优服务次序问题（8分）—— 提示：题采贪心算法实现
问题描述：设n顾客时等项服务顾客i需服务时间ti1
参考解答：贪心策略：短服务时间优先
n顾客服务时间ti排序n顾客服务调度方案排序序均等时间
评分准：
1) 答贪心算法说明贪心策略短服务优先题满分
2) 仅说明贪心算法未说明贪心策略答题完整扣2分
3) 情况酌情考虑
2Gray码构造问题（8分）—— 提示：题采分治递算法实现
问题描述：格雷码长度序列满足：
（a）元素长度n特串
（b）序列中相元素
（c）连续两元素恰1特
例：n2时格雷码{00011110}
Gray码种编码种编码避免读取时数位时序差异造成误读格雷码工程广泛应格雷码便运算请设计种构造方法输入长度序列n输出格雷码（做出种构造方案格雷码唯）
参考解答： 题分治法解决
n＝1时输出格雷码{0 1}
n>1时格雷码长度码序列时问题分二半部分半部分半部分高位设0半部分高位设1剩n1位格雷码构造采递思路
评分准：
1) 答分治算法推导出分治算法程边界设定清晰（仅输出1位格雷码处理）题满分
2) 说明分治算法漏边界条件扣2分
3) 情况酌情考虑
3长升子序列问题（8分）—— 提示：题采动态规划算法实现
定序列递增升子序列里序列(1 7 3 5 9 4 8)升子序列(1 7) (3 4 8)等等子序列中长长度4子序列(1 3 5 8)务：定序列求出长升子序列长度求写出设计算法思想递推函数公式表达
参考解答：设表示：左右扫描直元素结尾序列获长升子序列长度子序列包含元素（）
……中找值加1者1a[i]元素否加入前已获长升子序列果加入前已获长升子序列长度加果加入取元素作单独子序列长度1
求整序列长公子序列长度max{f(i) 1例序列：4 2 6 3 1 5 2
i
1
2
3
4
5
6
7
array
4
2
6
3
1
5
2
f(i)
1
1
2
2
1
3
2
评分准：
1) 答动态规划算法推导出动态规划算法递推函数公式表达边界设定清晰题满分（阅卷时仔细递推公式表达公式表达含义正确表达形式唯）
2) 说明动态规划算法递推函数表达错误含糊扣2分
3) 情况酌情考虑
4骑士问题（6分）—— 提示：题采广度优先搜索算法实现
标准8×8国际象棋棋盘棋盘中格子障碍物已知骑士初始位置目标位置务计算出骑士少需少步初始位置达目标位置法达目标位置输出not reachable请文字伪代码说明算法
注意：骑士进行日字行角跳棋盘障碍物格子达
图（a）：骑士进行日字行角跳n骑士前位置x骑士步跳格子
图（b）：骑士初始位置n目标位置N需7步实例b棋盘障碍
参考解答：搜索题目非常类似书布线问题参考书例
二维数组board[12][12]记录棋盘状况
12*12呢？棋盘8*8减少周围边界判断左右四边加2行2列做围墙（障碍）board棋盘12*12
步骤需解决：
1) 障碍格子：输入障碍格子填写board中应格设置1
2) 起始格子结束格子：起始点start结束点end两点记录board中两格子设置0
3) 围墙：8*8棋盘外面左右加2行2列做围墙围墙障碍样设置1
4) 障碍围墙起始结束格子格子特殊输入外余格子全部初始化0
5) 队列初始空队列骑士做 日字型角跳时候候选位置放入队列中辅助数结构便广度优先搜索
6) 起点开始位置跳周围8位置检查：未标记标记前位置值加1该格子位置加入队列果标记（障碍围墙等）跳继续检查位置骑士跳8位置
7) 取出队列首位置结点继续检查结点周围8位置类步直找终点标记位置
8) 输出终点标记数值（正数）骑士需少移动步数0表示终点法标记输出：not reachable样信息
评分准：
1) 答搜索算法说明采广度优先搜索策略算法描述清晰准确题满分
2) 算法表达含糊准确扣2分
3) 情况酌情考虑
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
2008学年第学期 考试科目： 算法分析设计
考试类型：（闭卷） 考试时间： 120 分钟
学号 姓名 年级专业
题号
二
三
四
总分
分
评阅
选择题（20分题2分）
1 述表达正确 D
A．n22 + 2n渐进表达式界函数O(2n)
B．n22 + 2n渐进表达式界函数Ω(2n)
C．logn3渐进表达式界函数O(logn)
D．logn3渐进表达式界函数Ω(n3)
2 输入规模n时算法增长率 A
A．5n B．20log2n C．2n2 D．3nlog3n
3 T（n）表示输入规模n时算法效率算法效率优 C
A．T（n） T（n – 1）+1T（1）1 B．T（n） 2n2
C．T（n） T（n2）+1T（1）1 D．T（n） 3nlog2n
4 棋盘覆盖问题中2k×2k特殊棋盘（特殊方块）需L型骨牌数 A
A．（4k – 1）3 B．2k 3 C．4k D．2k
5 寻找n元素中第k元素问题中快速排序算法思想运分治算法n元素进行划分应选择划分基准？面 答案解释合理D
A．机选择元素作划分基准
B．取子序列第元素作划分基准
C．中位数中位数方法寻找划分基准
D．皆行方法算法复杂度界
6 9村庄坐标位置表示：
i
1
2
3
4
5
6
7
8
9
x（i）
1
2
3
4
5
6
7
8
9
y（i）
1
2
3
4
5
6
7
8
9
现盖邮局9村庄服务请问邮局应该盖 邮局9村庄总距离短C
A．（450） B．（4545） C．（55） D．（50）
7 n拎着水桶水龙头前面排队水水桶水桶必须满水水流恒定 说法正确？A
A．水桶先水排队时间
B．水桶先水排队时间
C．水桶先水某确定时间t水
D．短时间n完水什序实样
8 分治法设计思想难直接解决问题分割成规模较子问题分解决子问题子问题解组合起形成原问题解求原问题子问题 C
A．问题规模相问题性质相 B．问题规模相问题性质
C．问题规模问题性质相 D．问题规模问题性质
9 布线问题 正确描述C
A．布线问题解空间图
B．方格阵列四周设置围墙增设标记附加方格预处理算法简化边界判定
C．采广度优先标号法找起点终点布线方案（方案果存话）定短
D．采先入先出队列作活结点表终点b扩展结点活结点队列空作算法结束条件
10 含n元素子集树问题坏情况解空间叶结点数目 B
A．n B．2n C．2n+11 D．
二填空题（10分题2分）
1算法复杂性高低体现计算机运行该算法需时间存储器资源算法复杂性 复杂性空间复杂性分
参考解答：时间
2出衡子问题思想通常分治法分割原问题形成干子问题时子问题规模致
参考解答：相
3二分搜索算法n序元素表中搜索特定元素佳情况搜索时间复杂性O（ ）坏情况搜索时间复杂性O（ ）
参考解答：1 logn
4已知分治算法耗费计算时间T(n)T(n)满足递方程：
解递方T(n) O（ ）
参考解答：
5动态规划算法变形方法 种方法动态规划算法底填充方顶递方解子问题建立备忘录备需时查样避免相子问题重复求解
参考解答：备忘录方法
三简答题（40分题8分）
1（8分）写出列复杂性函数偏序关系（渐进阶低高排序）：
参考解答：
2（8分）现8位运动员进行网球循环赛设计满足求赛日程表：
（1） 选手必须选手赛次
（2） 选手天赛次
（3） 循环赛进行n – 1天
请利分治法思想8位运动员设计合理赛日程
参考解答：
1
2
3
4
5
6
7
8
2
1
4
3
6
5
8
7
3
4
1
2
7
8
5
6
4
3
2
1
8
7
6
5
5
6
7
8
1
2
3
4
6
5
8
7
2
1
4
3
7
8
5
6
3
4
1
2
8
7
6
5
4
3
2
1
3（8分）某体育馆羽毛球场出租现总10位客户申请租羽毛球场客户租时间单元表示s(i)表示开始租时刻f(i)表示结束租时刻10客户申请表示：
i
1
2
3
4
5
6
7
8
9
10
s(i)
0
3
1
5
3
5
11
8
8
6
f(i)
6
5
4
9
8
7
13
12
11
10
时刻该羽毛球场租位客户请设计租安排方案10位客户里面体育馆满足位客户需求算出针表10客户申请安排位客户申请
参考解答：10位客户申请结束时间f(i)递增排序表：
i
1
2
3
4
5
6
7
8
9
10
s(i)
1
3
0
5
3
5
6
8
8
11
f(i)
4
5
6
7
8
9
10
11
12
13
1） 选择申请1（14）
2） 次检查续客户申请已选择申请相容突选择该申请直申请检查完毕申请4（57）申请8（811）申请10（1113）
3） 满足：申请1（14）申请4（57）申请8（811）申请10（1113）4客户申请已满足客户数
4（8分）矩阵连需少数次数问题递关系式：
中m[ij]计算矩阵连Ai…Aj需少数次数pi1矩阵Ai行矩阵Ai列现四矩阵中矩阵维数分：
A1
A2
A3
A4
50´10
10´40
40´30
30´5
p 0´ p 1
p 1´ p 2
p 2´ p 3
p 3´ p 4
请根递关系计算出矩阵连积A1A2A3A4需少数次数
参考解答：
5（8分）样类特殊01背包问题：选物品重量越轻物品价值越高
n6c20P（4815163）W（5321048）
中n物品数c背包载重量P表示物品价值W表示物品重量请问01背包问题应选择放进物品放进背包物品总价值获总价值少？
参考解答：该0－1背包问题较特殊恰重量越轻物品价值越高优先取重量轻物品放进背包终重量分2345三物品放进背包价值15 + 8 + 6 + 4 33值
四算法设计题（30分前三题题8分题6分）
1优服务次序问题（8分）—— 提示：题采贪心算法实现
问题描述：设n顾客时等项服务顾客i需服务时间ti1
参考解答：贪心策略：短服务时间优先
n顾客服务时间ti排序n顾客服务调度方案排序序均等时间
评分准：
1) 答贪心算法说明贪心策略短服务优先题满分
2) 仅说明贪心算法未说明贪心策略答题完整扣2分
3) 情况酌情考虑
2Gray码构造问题（8分）—— 提示：题采分治递算法实现
问题描述：格雷码长度序列满足：
（a）元素长度n特串
（b）序列中相元素
（c）连续两元素恰1特
例：n2时格雷码{00011110}
Gray码种编码种编码避免读取时数位时序差异造成误读格雷码工程广泛应格雷码便运算请设计种构造方法输入长度序列n输出格雷码（做出种构造方案格雷码唯）
参考解答： 题分治法解决
n＝1时输出格雷码{0 1}
n>1时格雷码长度码序列时问题分二半部分半部分半部分高位设0半部分高位设1剩n1位格雷码构造采递思路
评分准：
1) 答分治算法推导出分治算法程边界设定清晰（仅输出1位格雷码处理）题满分
2) 说明分治算法漏边界条件扣2分
3) 情况酌情考虑
3长升子序列问题（8分）—— 提示：题采动态规划算法实现
定序列递增升子序列里序列(1 7 3 5 9 4 8)升子序列(1 7) (3 4 8)等等子序列中长长度4子序列(1 3 5 8)务：定序列求出长升子序列长度求写出设计算法思想递推函数公式表达
参考解答：设表示：左右扫描直元素结尾序列获长升子序列长度子序列包含元素（）
……中找值加1者1a[i]元素否加入前已获长升子序列果加入前已获长升子序列长度加果加入取元素作单独子序列长度1
求整序列长公子序列长度max{f(i) 1
i
1
2
3
4
5
6
7
array
4
2
6
3
1
5
2
f(i)
1
1
2
2
1
3
2
评分准：
1) 答动态规划算法推导出动态规划算法递推函数公式表达边界设定清晰题满分（阅卷时仔细递推公式表达公式表达含义正确表达形式唯）
2) 说明动态规划算法递推函数表达错误含糊扣2分
3) 情况酌情考虑
4骑士问题（6分）—— 提示：题采广度优先搜索算法实现
标准8×8国际象棋棋盘棋盘中格子障碍物已知骑士初始位置目标位置务计算出骑士少需少步初始位置达目标位置法达目标位置输出not reachable请文字伪代码说明算法
注意：骑士进行日字行角跳棋盘障碍物格子达
图（a）：骑士进行日字行角跳n骑士前位置x骑士步跳格子
图（b）：骑士初始位置n目标位置N需7步实例b棋盘障碍
参考解答：搜索题目非常类似书布线问题参考书例
二维数组board[12][12]记录棋盘状况
12*12呢？棋盘8*8减少周围边界判断左右四边加2行2列做围墙（障碍）board棋盘12*12
步骤需解决：
1) 障碍格子：输入障碍格子填写board中应格设置1
2) 起始格子结束格子：起始点start结束点end两点记录board中两格子设置0
3) 围墙：8*8棋盘外面左右加2行2列做围墙围墙障碍样设置1
4) 障碍围墙起始结束格子格子特殊输入外余格子全部初始化0
5) 队列初始空队列骑士做 日字型角跳时候候选位置放入队列中辅助数结构便广度优先搜索
6) 起点开始位置跳周围8位置检查：未标记标记前位置值加1该格子位置加入队列果标记（障碍围墙等）跳继续检查位置骑士跳8位置
7) 取出队列首位置结点继续检查结点周围8位置类步直找终点标记位置
8) 输出终点标记数值（正数）骑士需少移动步数0表示终点法标记输出：not reachable样信息
评分准：
1) 答搜索算法说明采广度优先搜索策略算法描述清晰准确题满分
2) 算法表达含糊准确扣2分
3) 情况酌情考虑
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档