一．填空题（每空2分，共30分） 1．算法的时间复杂性指算法中 的执行次数。 2．在忽略常数因子的情况下，O、?和?三个符号中， 提供了算法运行时间的一个上界。 3．设Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示输入I出现的概率，则算法的平均情况下时间复杂性A(n)= 。 4．分治算法的时间复杂性常常满足如下形式的递归方程： , n?n0?f(n)?d ? f(n)?af(n/c)?g(n) , n?n0? 其中，g(n)表示 。 5. 分治算法的基本步骤包括 。 6．回溯算法的基本思想是 。 7．动态规划和分治法在分解子问题方面的不同点是 。 8．贪心算法中每次做出的贪心选择都是 最优选择。 9．PQ式的分支限界法中，对于活结点表中的结点，其下界函数值越小，优先级越 。 10．选择排序、插入排序和归并排序算法中， 算法是分治算法。 11．随机算法的一个基本特征是对于同一组输入， 不同的运行可能得到 的结果。 12.对于下面的确定性快速排序算法，只要在步骤3前加入随机化步骤 ，就可得到一个随机化快速排序算法，该随机化步骤的功能是 。 算法 QUICKSORT 输入：n个元素的数组A[1..n]。 输出：按非降序排列的数组A中的元素。
1. quicksort(1, n) ＿＿＿＿＿号学 ＿ 栏＿＿ ＿ ＿ ＿ 名 姓 息 级 年 ＿ 信＿＿ ＿ ＿ ＿ 业 专生 ＿ ＿ ＿ ＿ ＿ ＿ 考系＿＿＿＿＿＿院学＿＿＿＿＿＿end QUICKSORT 过程 quicksort(A, low, high) // 对A[low..high]中的元素按非降序排序。 2. if low pro2(n) ex1(n/2) end if return end ex1 3．用Floyd算法求下图每一对顶点之间的最短路径长度，计算矩阵D0，D1，D2和D3，其中Dk[i, j]表示从顶点i到顶点j的不经过编号大于k的顶点的最短路径长度。 线 三．算法填空题（共34分） 1．（10分）设n个不同的整数按升序存于数组A[1..n]中，求使得A[i]=i 订的下标i 。下面是求解该问题的分治算法。 算法 SEARCH 输入：正整数n，存储n个按升序排列的不同整数的数组A[1..n]。 输出：A[1..n]中使得A[i]=i的一个下标i，若不存在，则输出 no 装solution。 i=find ( (1) ) if i>0 then output i else output “no solution” end SEARCH 过程 find (low, high) // 求A[low..high] 中使得A[i]=i的一个下标并返回，若不存在，
相关推荐：
loading