一、填空（共42分）：
1．假设某算法在输入规模为n时的计算时间为T(n)=3×2n。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台计算机上用同一算法在t秒内能解决输入规模为__________的问题。若上述算法的计算时间改进为T(n)=n2，其余条件不变，则在新机器上用t秒事件能解输入规模为___________的问题；若算法计算时间进一步改进为T(n)=8新机器可解输入规模_____________。（12分）
2．一个具有n个圆盘的Hanoi塔，至少移动___________次圆盘才能达到目标状态。（4分）
3．设有n个运动员要进行循环赛，现设计一个满足以下
要求
对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗
的比赛日程表：①每个选手必须与其他n-1名选手比赛各一次；②每个选手一天至多只能赛一次；③循环赛要在最短时间内完成。如果n=2k，循环赛最少需要进行________天；如果n=2k+1，循环赛最少需要进行_____________天。其中，k为正整数。（8分）
4．按分治策略求解棋盘覆盖问题时，对于如图1所示的23×23的特殊棋盘，共需要____________个L型骨牌；并在棋盘上填写L型骨牌的覆盖情况。（4分）
1
2
3
4
5
6
7
8
+ + - + - + +
+ - - - - +
- + + + -
- + + -
- + -
- -
+
1
2
3
4
5
6
7
8
图1 棋盘覆盖
图2 符号三角形
5．用分支限界法求解0-1背包问题时，对于每个物品j有重量wj和价值vj，考虑当前物品i，已装入背包中物品的重量和价值分别为cw、cv，剩余物品的价值上界为urv，剩余容量为c，目前已有的最优价值为bestp，则当左儿子满足约束条件____________属于可行结点时，就将它加入活结点队列中；当右儿子满足上界条件_____________时才将它加入活结点队列中。（每空2分，共计4分）
6．概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到________________（完全不同/基本近似）的效果——求解时间甚至是所得的结果。概率算法大致可以分为四类：数值概率算法、蒙特卡罗算法、拉斯维加斯算法和舍伍德算法。其中________________算法用于求解问题的准确解——但此解未必正确如素数测试问题，而________________算法不会得到不正确的解，但该算法可能找不到问题的解如整数因子分解问题；________________算法则常用于求解数值问题的近似解；________________算法主要体现在设法消除算法最坏情形下的复杂性余特殊实例之间的关联性，如引入随机方法的快速排序算法。（每空2分，共计10分）
二、解答题（要求给出解答步骤，尤其强调所用方法；共58分）
1．证明：n!=o(nn)。（10分）
2．Gray码是一个长度为2n的序列，序列中无相同的元素，每个元素都是长度为n的二进制串，相邻元素恰好只有一位不同。用分支策略设计一个算法对任意的n构造相应的Gray码。（18分）
3．连续邮资问题：假定可以提供n种不同面值的邮票，并且每个信封上最多允许贴m张邮票。用回溯法设计n种不同面值的邮票，使得信封上可贴邮票的连续邮资区间最大。（20分）
4．画出下面字符表的哈夫曼编码对应的二叉树。（10分）
字符
a
b
C
D
e
f
出现频率（%）
12
45
13
16
9
5
西南科技大学试题单（F）
计算机学院:课程名称:《算法分析与设计》课程代码: 14314025命题单位:软件教研室
学院：________ 专业班级：_______学号：□□□□□□□□ 命题共2页第1 页
![[ppt]算法分析与设计_西南科学技大学西南科技大学试题单（F）](https://swf.iask.com/HAL1PePE13l.svg?ssig=PIAnBnxgra&Expires=1720966248&KID=sina,ishare&range=0-47972)
浙公网安备 33021202002483