《算法设计与分析》课程笔试样题一 （90分钟，开卷笔试，100分）
学年 学期 班
一、设n为正整数，利用大“O(·)”记号，将下列程序段的执行时间表示为n的函数，分析下列程序段的时间复杂度（每小题7.5分，共15分） 1．程序段1
i=1; k=0; while(i y=0; n=100; while ((y+1)*(y+1) 三、设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的二叉搜索树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度（20分） 四、下面是利用贪心算法求解单源点最短路径问题的伪代码，请你阅读代码并在空白处填上适当的代码（20分） Procedure SHORTEST_PATHS(v, COST, DIST, n) // G是一个n个结点的有向图，它由成本邻接矩阵COST(n, n)表示，DIST(j)表示结点v到结点j的最短路径长度，这里1≤ j ≤n，DIST(v)置成0。 boolean S(1:n); real COST(1:n, 1:n), DIST(1:n); integer u, v, n, i, w; for i=1 to n do S(i)=0; ① ; repeat S(v)=1; DIST(v)=0; u=v; for i=2 to n do for所有S(w)=0的结点w do 找DIST(u)+COST(u, w)最小的节点w; repeat DIST(w)=min(DIST(w), ② ) ; S(w)=1; ③ ; repeat end SHORTEST_PATHS 五、下列代码为求多段图问题的伪C语言代码： ForwardShortestPath(float c[][n], int k, int n) { float C[n]; int d[n], p[k]; C[0:n-2]=MAX; C[n-1]=0; for(i=n-2; i>=0; i--) for(j=i+1; j<=n-1; j++) if((c[i][j]>0)&&(c[i][j]+C[j] for(p[0]=0, p[k-1]=n-1, i=1; i 其中，n为图的节点数，k为段数，c[][]为成本邻接矩阵，C[]为各节点到汇点的最短路径长度，d[]为各节点到汇点的最短路径上的后向邻接节点，p[]存储最短路径上的节点序列。请回答： 1) 该算法属于什么算法类型？（5分） 2) 使用的那一种递推方法？（5分） 3) 时间复杂度为多少？（5分） 4) 当用邻接表表示图时，时间复杂度为多少？（5分） 5) 在空白处填上适当的语句。（10分） （共30分） 参考答案及评分标准 一、(每小题7.5分，共15分) 1． 分析： i=1; // 1 k=0; // 1 while(i 根据各语句的频度，可得该程序段的时间消耗为T(n)=1+1+n+(n-1)+(n-1)=3n，可表示为T(n)=O(n)。（没有分析扣2分） 2． 分析： 由于n的值在程序中不变，由while的循环条件( (y+1)*(y+1) ?n?1??，可表示为T(n)=O(n)。（没有分析扣2分） 的执行时间为? 二、（每小题7.5分 共15分） 1．算法是解决问题的方法和过程，它具有四个特点： 1）输入0个或多个信息； 2）输出至少一个信息； 3）确定性，组成算法的每个指令是清晰的，无二义的，整个过程是确定的； 4）有限性。 1、2、3点答对每点给2分，第4点答对给1.5分。 2．分枝限界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分枝），并为每个子集内的解的值计算一个下界或上界（称为限界）。在每次分枝后，对凡是界限超出已知可行解值那些子集不再做进一步分枝。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的限界。因此这种算法一般可以求得最优解。（部分答对酌情给分） 三、（共 20分，画出图 10分，ASLsucc和ASLunsucc给出正确答案各5分） ASLSUCC114145??Ci?(1?2?2?3?4?4?7)?14i?11414115'159??Ci?(3?1?4?14)?15i?01515ASLunsucc 四：（共20分） ① DIST(i)=COST(v,i) （7分） ② DIST(u)+COST(u,w) （7分） ③ u=w （6分） 五．( 共30分） 1) 动态规划，5分； 2）前向递推法，5分； 3）O(n2)，5分； 4）O(n+e)，e表示图的边数，5分； 5）第①空填d[i]= j，第②空填p[i]=d[p[i-1]]，每空5分。 《算法设计与分析》课程笔试样题二 （90分钟，开卷笔试，100分） 学年 学期 班 一、请你分析下列算法的时间复杂度。（10分） int Maxsum(int n, int a, int &besti, int &bestj) { int sum = 0; for(int i=1; i<=n; i++){ int suma = 0; for(int j=i; j<=n; j++){ suma + = a[j]; if(suma > sum){ sum = suma; besti = i; bestj = j; } } } return sum; } 二、简答题（2小题，共20分）
