试卷编号专业班级学号姓名。
试题均为5号字备注：1、先修、重修同学必须注明（先修、重修）
2、试卷背面为演算区（不准用自带草纸）
装订线。大连海事大学第2009-20010学年第 1 学期。
算法设计与分析》试卷 （工学硕士09级）
参***）计算题部分（共15分）
证明题部分（共25分）
三、对于函数f(n)和g(n)，若lim g(n)/f(n)存在，则f(n)＝ωg(n))当且仅当存在确定的常数c，有lim g(n)/f(n)≤c。
证明：先证充分性：若f(n)=ωg(n))，则lim g(n)/f(n)≤c5分。
根据ω的定义，当f(n)=ωg(n))成立时，即存在正常数a和n0，使得对于所有的n≥n0，有f(n)≥a*g(n)。
考虑到f(n)的非负性，以及a为正常数，所以有：
g(n)/f(n)≤1/a，因为lim g(n)/f(n)存在，可令c=1/a，所以有因为lim g(n)/f(n)≤c。 充分性成立。 5分。
再证明必要性（有两种方法：一是根据定义推理；二是利用反证法）。
因为lim g(n)/f(n)存在，可设为a，且有lim g(n)/f(n)≤c。
于是，根据极限定义有，对于给定的任意小的常数ε＞0，存在n1，使得对于一切n≥n1时，有。
g(n)/f(n)-a|≤ε也即有-ε≤g(n)/f(n)-a≤ε，a-ε≤g(n)/f(n)≤εa，所以有。
g(n)/f(n)≤εa，考虑到f(n)的非负性，所以有f(n)≥c*g(n)，其中c=1/(εa)>0为常数。再取n0=n1,也就是说，存在正常数c和n0，使得对于一切的n≥n0，有f(n)≥c*g(n)，从而有f(n)=ωg(n))。
证毕。 5分。
四、证明依据贪婪算法greedy_knapsack构造问题的解时，能够生成一个最优解。 (10分)
证明：设x=(x1, …xn)是greedy_knapsack所生成的解。如果所有的xi等于1，显然这个解就是最优解(效益值为σpi)。
于是，设j是使xj≠1的最小下标。由算法可知，对于l≤i＜j，xi=1；对于j＜i≤n，xi=0；对于j，0≤xj＜1。
如果x不是一个最优解，则必定存在一个可行解y=(y1, …yn)，使得σpiyi＞σpixi。
不失一般性，可以假定σwiyi=m。且设k是使得yk≠xk的最小下标。显然，这样的k必定存在。
由上面的假设，可以推得yk＜xk。这个结论可从以下三个方面，即k＜j，k=j或k＞j分别加以证明。
若k＜j，则xk=1。因yk≠xk，从而yk＜xk；
若k=j，则由于σwixi=m，且对于l≤i＜j，有xi=yi=1，而对于j＜i≤n，有 xi=0。
若yk＞xk，显然有σwiyi＞m，与y是可行解矛盾；
若yk=xk，与假设yk≠xk矛盾，故yk＜xk。
若k＞j，则σwiyi＞m，这是不可能的。
现在，假定把yk增加到xk，那么必须从(yk+1, …yn)中减去同样多的量，使得所用的总容量仍是m。
这导致一个新解z=(z1, …zn)，其中zi=xi，1≤i≤k，并且有。
wi(yi-zi)=wk(zk-yk)。
因此，对于z有。
pizi = piyi + zk-yk)wkpk/wk -σyi-zi)wipi/wi ≥ piyi + zk-yk)wk - yi-zi)wi]*pi/wk = piyi
若σpizi＞σpiyi，则y不可能是最优解；若相等，且z=x，则x就是最优解；
若z≠x，则需重复上述讨论，或者证明y不是最优解，或者把y转换成x，从而证明了x也是最优解。
证毕。 (根据步骤给分)
五、证明n!=оnn5分)
证明：对于任意的n>0,有。
n!=1×2×…×n ≤ n×n×…×n=nn
令c=1，即有。
n! ≤nn
所以，根据大○定义，有。
n!=оnn)
证毕。 5分。
算法题部分（共60分）
六、对于下表左部给定的算法，计算该算法的时间渐进复杂性10分)
七、用贪婪法求解马的遍历问题。题目描述如下： （15分）
依据上述思想构建的程序如下，请填写其中的空白处的语句使程序能够完成上述功能，并给出一个找到解的最小开始位置。
八、采用回溯法求解从自然数1，2，…，n中找出任取r个数的所有组合问题。 （10分）
答案（每问3分，共10分）
a[i]-i<=m-r+li==r-1a[iia[--i]++
n=7、r=4时的执行结果如下：
2024年硕士研究生招生目录
一 学术型学位专业及研究方向。学科 专业名称 招考试科目。研究方向生。人数。070501自然地理学601水文与水资源 思想政治理论 英语 一 数学 三 水文学02湖泊沉积与环境演化 思想政治理论 英语 一 数学 三 第四纪地质学或地球化学或气候学03湖泊 流域地表过程 思想政治理论 英语 一 数学 ...
2024年硕士研究生招生目录
一 学术型学位专业及研究方向。学科 专业名称 招考试科目。研究方向生。人数。070501自然地理学601水文与水资源 思想政治理论 英语 一 数学 三 水文学02湖泊沉积与环境演化 思想政治理论 英语 一 数学 三 第四纪地质学或地球化学或气候学03湖泊 流域地表过程 思想政治理论 英语 一 数学 ...
2024年硕士研究生招生目录
一 学术型学位专业及研究方向。学科 专业名称 招考试科目。研究方向生。人数。070501自然地理学601水文与水资源 思想政治理论 英语 一 数学 三 水文学02湖泊沉积与环境演化 思想政治理论 英语 一 数学 三 第四纪地质学或地球化学或气候学03湖泊 流域地表过程 思想政治理论 英语 一 数学 ...