河南农业大学算法结构考试2008B卷.docVIP

1 max←min←A[1] 2 for i←2 to n 3 do if A[i]max 4 then max←A[i] 5 else if A[i]min 6 then min←A[i] 7 return max min 得分 评卷人 四、利用主方法解递归方程 T(n)＝4T(n/2)+ n2。(10分) 得分 评卷人 五、证明：N2/2-5N=O(N2) (6分) 得分 评卷人 六．设A=（5，7，12，25，34，37，43，46，58，80，92，105），推导出查找元素80的变量low,high和mid的运行轨迹。(8分) 1 3 院、部 班 级 姓名 学号 课头号 ………………………………………………密………………………线……………………………………………… 河南农业大学2008—2009学年第1 学期 《算法分析与设计》考试试卷（B卷） 题号 总分 分数 得分 评卷人 一、名词解释（8分）. 算法正确性 递归 动态 前缀码 得分 评卷人 二、填空：(28分) 算法具有以下五大特性是 ， ， ， ，和 。 2. 循环不变式的三个性质 ， ， 。 3.替换方法的两个步骤是 和 。 4.贪心算法解决的问题都具有 的性质以及 。 5.最重要的计算机资源是 和 。 得分 评卷人 三、分析找最大值、最小值算法MAXMIN（A）的最佳情况和最坏情况（6分） MAXMIN(A) 院、部 班 级 姓名 学号 课头号 ………………………………………………密………………………线……………………………………………… 院、部 班 级 姓名 学号 得分 评卷人 七．写出用动态规划解装配线调度问题的最优解值的伪代码程序。(18分) 得分 评卷人 八．如表，写出哈夫曼编码过程(16分) a b c d e 频率 10 24 40 20 6