《算法与算法复杂性》试卷

算法与算法复杂性分析试卷一、判断题。判断下列命题的正确性，在各题前的括号内，正确的画O,错误的画X。1. ()设Q e NPC。P=NP的充分必要条件是Q e P。2. ()设QeNPC，Q，eNP。如果Q，可由Q多项式归结得到，则Q，eNPC。3. ()NP完全问题就是NP难问题。4. ()已知A和A2是求解某个问题的两个算法，如果A的时间复杂性的渐近特性 优于A2的时间复杂性的渐近特性，那么，对该问题的任意规模的输入，舛的时间复杂 性优于a2的时间复杂性。5. ()O(f (n) + O(g(n)二 O(f (n) + g(n)6. ()如果存在一个正的常数c,使得对于一切n 0，有f (n ) eg (n )，则 记为f (n) g (n)。按照这个记法，若f g和f g，则有：f + f 0,求a的非递归形式的表达式。01n+2n+1nn3. 给定 7 个有序序列,各序列长度分别为 110, 20, 50, 70, 80, 90, 100,按照下面的算 法确定最佳合并顺序并构造最佳合并二叉树。算法4.1求最佳合并顺序输入n个序列的长度表L。输出一棵有最佳合并顺序的二叉树。Procedure OMTREEBegin1. for i=1 to n-1 do；Begin2. GETROOT(T)；3. LEFTSONTLEAST(L);4. RIGHTSONTLEAST(L);5. WEIGHT(T)WEIGHT(LEFTSONT)+WEIGHT(RIGHTSONT);6. INSERT(L,T);end;End.4.下面给出的是从n个元素中找最大元最小元的算法，分析其复杂性。找出集合S中的最大元和最小元输入集合S的元素S1, S2, SNo输出集合S中的最大元和最小元。1.Procedure FINDMAXMINVar A, B, N: integer;S: array1:N;Procedure MAXMIN ( S, I, j, A, B )Var A, B: integer;S: array1:j of integer ;Beginif j-i=1 then2.if Si三Sj then3.begin1A-Si;4.5.End1.ElseBegin2A-Sj;6.BSi；End2;ElseBegin37.MAXMIN( S , i , i+j-1 / 2 , A1, B1);8.MAXMIN( S , i+j+1 / 2 , j, A2, B2);9.if A三A2 then AA10.else AA2 ;11.if Bthen BB, 2 else BB2 ;end3.End.Begin13.read(N,S);14.MAXMIN ( S , ,N , A , B );15.write (A , B);End.三、 算法设计。设计算法求解下列问题并分析算法复杂性。给定 n 个数，从中寻找最大元和次大元。要求：你的算法必须优于先找最大元，再找次 大元这样一些按照简单策略设计的算法。四、 分析论述分枝限界相对回溯法有哪些改进？同样是搜索，为什么分枝限界法需要活结点表，而回 溯法不需要？