(完整word版)哈工大深圳算法设计与分析试卷-师兄只能帮你到这啦(额外再加8道保命题)-何震宇

哈尔滨工业大学深圳研究生院 2008年 秋 季学期期末考试试卷HIT Shenzhen Graduate School Examination PaperCourse Name: Lecturer::This exam is closed book . You may not use the text book, your notes, computer, or any other materials during the exam.No credit will be given for questions left unanswered, so you should be sure to answer all questions, even if you are only taking your best guess.Write your answer to each question or problem in the paper provided. If necessary, extra sheets will be provided. Make sure your name is written on all of these pages.Please be sure to write neatly and answer all questions unambiguously. This exam has a total of _100_ points, and you have 120 minutes.Time : 09:00-11:00, Monday, Dec. 8, 2008错误!未找到引用源。

Single choice [10 points]1、Which of the following sorting algorithms is not stable? ( B ) (A) Insertion sort (B) Quick sort (C) Merge sort (D) Bubble sort2、We say that ()f n is asymptotically larger than ()g n if ( D ). (A) ()()()f n O g n = (B) ()()()f n g n =Ω (C) ()()()f n o g n = (D) ()()()f n g n ω=3、An order-statistic tree is an augmented red-black tree. In addition to its usual fields, each node x has a fieldsize[x], which is the number of nodes in the subtree rooted at x , For an order-statistic tree with n nodes, the time for insertion, deletion and maintenance of the size field are ( A ) (A) (lg )O n (lg )O n (lg )O n(B) (lg )O n (lg )O n (lg )O n n (C) (lg )O n (lg )O n(1)O(D) (lg )O n(lg )O n n ()O n4、There ’s a B-tree whose minimum degree is t, every node other than the root must have at least __ keys, at most __ keys, every internal node other than the root has at least __ children ( D ). (A) t-1 2t t (B) t-1 2t-1 t (C) t 2t t+1 (D) t-1 2t+1 t5、Which of the following statements about P, NP,NPC is correct? ( C ) (A) P = NP , NPC ⊇ NP (B) P ⊇NP , NPC ⊇ P (C) P ⊆NP , NPC ⊆NP (D) P = NPC , P ⊇ NP错误!未找到引用源。

算法设计与分析1、(1) 证明：O(f)+O(g)=O(f+g)（7分）(2) 求下列函数的渐近表达式：（6分）① 3n 2+10n;② 21+1/n;2、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))，并简述理由。

（15分）(1);5log )(;log )(2+==n n g n n f (2);)(;log )(2n n g n n f == (3);log )(;)(2n n g n n f == 3、试用分治法对数组A[n]实现快速排序。

（13分）4、试用动态规划算法实现最长公共子序列问题。

（15分）5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n 公里，而旅途中有若干个加油站。

试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少。

（12分）6、试用动态规划算法实现下列问题：设A 和B 是两个字符串。

我们要用最少的字符操作，将字符串A 转换为字符串B ，这里所说的字符操作包括：(1)删除一个字符。

(2)插入一个字符。

(3)将一个字符改为另一个字符。

将字符串A 变换为字符串B 所用的最少字符操作数称为字符串A 到B 的编辑距离，记为d(A,B)。

试设计一个有效算法，对任给的两个字符串A 和B ，计算出它们的编辑距离d(A,B)。

（16分）⎣⎦2/)(;3)(i i g i i f ==。

对于给定的两个整数n 和m ，要求用最少的变换f 和g 变换次数将n 变为m 。

（16分）1、⑴证明：令F(n)=O(f),则存在自然数n 1、c 1，使得对任意的自然数n ≥n 1，有：F(n)≤c 1f(n)……………………………..（2分）同理可令G(n)=O(g),则存在自然数n 2、c 2，使得对任意的自然数n ≥n 2，有：G(n)≤c 2g(n)……………………………..（3分）令c 3=max{c 1,c 2},n 3=max{n 1,n 2},则对所有的n ≥n 3，有： F(n)≤c 1f(n)≤c 3f(n)G(n)≤c 2g(n)≤c 3g(n)……………………………..（5分） 故有：O(f)+O(g)=F(n)+G(n)≤c 3f(n)+c 3g(n)=c 3(f(n)+g(n)) 因此有：O(f)+O(g)=O(f+g)……………………………..（7分） ⑵ 解：① 因为;01033)103(lim 222=+-+∞→n n n n n n 由渐近表达式的定义易知： 3n 2是3n 2+10n 的渐近表达式。

（1）用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制（2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程（3）算法的三要素1、操作2、控制结构3、数据结构算法具有以下5个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

确定性：算法中每一条指令必须有确切的含义。

不存在二义性。

只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。

输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。

输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。

算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。

效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。

一般这两者与问题的规模有关。

经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。

利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代模型。

在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

二、建立迭代关系式。

所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。

迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

三、对迭代过程进行控制。

在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。

不能让迭代过程无休止地重复执行下去。

迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。

《算法设计与分析》历年期末试题整理(含答案)（1）用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现 7、程序调试 8、结果整理文档编制（2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程（3）算法的三要素1、操作2、控制结构3、数据结构算法具有以下5 个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

确定性：算法中每一条指令必须有确切的含义。

不存在二义性。

只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。

输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。

输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。

算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。

效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。

一般这两者与问题的规模有关。

经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。

利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代模型。

在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

二、建立迭代关系式。

所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。

迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

三、对迭代过程进行控制。

在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。

不能让迭代过程无休止地重复执行下去。

chengcheng算法分析考试试卷（A卷）课程名称算法分析编号题号一二三四总分得分评阅人一、填空题（每小题3分，共30分）1、一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

2、这种不断回头寻找目标的方法称为回溯法。

3、直接或间接地调用自身的算法称为递归算法。

4、 记号在算法复杂性的表示法中表示紧致界。

5、由分治法产生的子问题往往是原问题较小模式，这就为使用递归技术提供了方便。

6、建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。

7、下列各步骤的先后顺序是②③④①。

①调试程序②分析问题③设计算法④编写程序。

8、最优子结构性质的含义是问题最优解包含其子问题最优解。

9、贪心算法从初始阶段开始，每一个阶段总是作一个使局部最优的贪心选择。

10、拉斯维加斯算法找到的解一定是正确的。

二、选择题（每小题2分，共20分）1、哈夫曼编码可利用（ C ）算法实现。

A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是基本计算模型的是（ B ）。

A、RAMB、ROMC、RASPD、TM3、下列算法中通常以自顶向下的方式求解最优解的是（ C）。

A、分治法B、动态规划法C、贪心法D、回溯法chengcheng 4、在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是( A )A、回溯法B、分支限界法C、回溯法和分支限界法D、动态规划5、秦始皇吞并六国使用的远交近攻，逐个击破的连横策略采用了以下哪种算法思想？ BA、递归；B、分治；C、迭代；D、模拟。

6、FIFO是（ A ）的一搜索方式。

A、分支界限法B、动态规划法C、贪心法D、回溯法7、投点法是（ B ）的一种。

A、分支界限算法B、概率算法C、贪心算法D、回溯算法8、若线性规划问题存在最优解，它一定不在（ C ）A．可行域的某个顶点上 B．可行域的某条边上 C．可行域内部 D．以上都不对9、在一般输入数据的程序里，输入多多少少会影响到算法的计算复杂度，为了消除这种影响可用（ B ）对输入进行预处理。

算法分析与设计试题及答案一、选择题1. 下列哪个是属于分治算法的例子？A. 冒泡排序B. 归并排序C. 顺序查找D. 选择排序答案：B2. 在排序算法中，时间复杂度最优的是：A. 冒泡排序B. 插入排序C. 归并排序D. 快速排序答案：C3. 哪个不是动态规划的特点？A. 具有重叠子问题B. 通过递归求解C. 需要保存子问题的解D. 具有最优子结构答案：B4. 在图的广度优先搜索算法中，使用的数据结构是：A. 栈B. 队列C. 数组D. 堆栈答案：B5. 在最小生成树算法中，下列哪个不属于贪心策略？A. Kruskal算法B. Prim算法C. Dijkstra算法D. Prim-Kruskal混合算法答案：C二、简答题1. 请简述分治算法的思想和应用场景。

答案：分治算法的思想是将原问题分解成若干个规模较小且类似的子问题，然后解决子问题，最后将子问题的解合并得到原问题的解。

其应用场景包括排序算法（如归并排序、快速排序）、搜索算法（如二分查找）等。

2. 什么是动态规划算法？请给出一个动态规划算法的示例。

答案：动态规划算法是一种通过将问题分解成子问题并解决子问题来解决复杂问题的方法。

它的特点是具有重叠子问题和最优子结构性质。

以斐波那契数列为例，可以使用动态规划算法求解每一项的值，而不需要重复计算。

3. 图的深度优先搜索和广度优先搜索有什么区别？答案：图的深度优先搜索（Depth First Search，DFS）是一种先访问子节点再访问兄弟节点的遍历算法，通常使用递归或者栈实现。

而广度优先搜索（Breadth First Search，BFS）则是以层次遍历的方式展开搜索，使用队列来实现。

DFS更适合用于搜索路径，BFS则适用于寻找最短路径等。

4. 请简述贪心算法的特点及其应用场景。

答案：贪心算法的特点是每一步都采取当前状态下最优的选择，以期望得到全局最优解。

然而，贪心算法并不一定能求解所有问题的最优解，但对于一些特定问题，贪心算法往往能得到近似最优解。

湖南科技学院二○ 年 学期期末考试信息与计算科学专业 年级《算法设计与分析》 试题考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 一、填空题（每小题3 分，共计30 分）1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。

()()log log f n n n g n n ==2. 算法的时间复杂性为1,1()8(3/7),2n f n f n n n =⎧=⎨+≥⎩，则算法的时间复杂性的阶为__________________________。

3. 快速排序算法的性能取决于______________________________。

4. 算法是_______________________________________________________。

5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。

6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。

7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。

8. ____________________________是问题能用动态规划算法求解的前提。

9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。

10. 回溯法在问题的解空间树中，按______________策略，从根结点出发搜索解空间树。

二、简答题（每小题10分，共计30分）1. 试述回溯法的基本思想及用回溯法解题的步骤。

2. 有8个作业{1,2,…,8}要在由2台机器M1和M2组成的流水线上完成加工。

算法设计与分析试卷一、填空题（20分，每空2分）1、算法的性质包括输入、输出、＿＿＿、有限性。

2、动态规划算法的基本思想就将待求问题＿＿＿＿＿、先求解子问题，然后从这些子问题的解得到原问题的解。

3、设计动态规划算法的4个步骤：（1）找出＿＿＿＿，并刻画其结构特征。

（2）＿＿＿＿＿＿＿。

（3）＿＿＿＿＿＿＿。

（4）根据计算最优值得到的信息，＿＿＿＿＿＿＿。

4、流水作业调度问题的johnson算法：（1）令N1=＿＿＿,N2={i|ai>=bj};（2）将N1中作业依ai的＿＿＿。

5、对于流水作业高度问题，必存在一个最优调度π，使得作业π（i）和π（i+1）满足Johnson 不等式＿＿＿＿＿。

6、最优二叉搜索树即是＿＿＿的二叉搜索树。

二、综合题（50分）1、当（a1,a2,a3,a4,a5,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为∑ak(2<=k<=4)＿＿＿＿（5分）2、由流水作业调度问题的最优子结构性质可知，T（N，0）=＿＿＿＿＿＿（5分）3、最大子段和问题的简单算法(10分)int maxsum(int n,int *a,int & bestj){intsum=0;for (int i=1;i<=n;i++)for (int j=i;j<=n;j++)int thissum=0;for(int k=i;k<=j;k++)＿＿＿＿＿;if(thissum>sum){sum=thissum;＿＿＿＿＿＿；bestj=j;}}return sum;}4、设计最优二叉搜索树问题的动态规划算法OptimalBinarysearchTree? (15分)Void OptimalBinarysearchTree(int a,int n,int * * m, int * * w){for(int i=0;i<=n;i++) {w[i+1][i]=a[i]; m[i+1][i]=＿＿＿＿;}for(int r=0;r<n;r++)for(int i=1;i<=n-r;i++){int j=i+r;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=＿＿＿＿＿＿;s[i][j]=i;for(int k=i+1;k<=j;k++){int t=m[i][k-1]+m[k+1][j];if(＿＿＿＿＿) {m[i][j]=t; s[i][j]=k;}}m[i][j]=t; s[i][j]=k;}}5、设n=4, (a1,a2,a3,a4)=(3,4,8,10), (b1,b2,b3,b4)=(6,2,9,15) 用两种方法求4个作业的最优调度方案并计算其最优值？（15分）三、简答题（30分）1、将所给定序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有哪三种情形？(10分)答：2、由0——1背包问题的最优子结构性质，可以对m（i,j）建立怎样的递归式? (10分)3、0——1背包求最优值的步骤分为哪几步？（10分）参考答案：填空题：确定性分解成若干个子问题最优解的性质递归地定义最优值以自底向上的方式计算出最优值构造最优解{i|ai<bi} ai的非减序排序；将N2中作业依bi的非增序排序min{bπ(i),aπ(i+1)}≥min{bπ(i+1),aπ(i)}最小平均查找长度综合题：20 min{ai+T(N-{i},bi)}(1=<i<=n) thissum+=a[k] besti=i 0 m[i+1][j] t<m[i][j]法一：min(ai,bj)<=min(aj,bi)因为min(a1,b2)<=min(a2,b1) 所以1→2 (先1后2) 由min(a1,b3)<=min(a3,b1) 得1→3 （先1后3）同理可得：最后为1→3→4→2法二：johnson算法思想 N1＝{1，3，4} N2＝{2} N¹1＝{1，3，4} N¹2＝{2} 所以 N¹1→N¹2 得：1→3→4→2简答题：1 、（1）a[1:n]的最大子段和与a[1:n/2]的最大子段和相同。

《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？1. 确定性、可行性、输入、输出、有穷性2.2.算法分析的目的是什么？2. 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。

3.3.算法的时间复杂性与问题的什么因素相关？3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。

4.算法的渐进时间复杂性的含义？4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。

时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。

5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。

最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max{ T(n，I) } , I∈Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n) =∑P(I)T(n，I) I∈Dn6.简述二分检索（折半查找）算法的基本过程。

6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]<x，则A[i：(i+j)/2-1]找x，否则在A[ (i+j)/2+1：j] 找x。

上述过程被反复递归调用。

7.背包问题的目标函数和贪心算法最优化量度相同吗？7. 不相同。

目标函数：获得最大利润。

最优量度：最大利润/重量比。

8.采用回溯法求解的问题，其解如何表示？有什么规定？8. 问题的解可以表示为n元组：（x1,x2,……x n），x i∈S i, S i为有穷集合，x i∈S i, （x1,x2,……x n）具备完备性，即（x1,x2,……x n）是合理的，则（x1,x2,……x i）(i<n)一定合理。

《算法设计与分析》试卷及答案算法设计与分析考试复习试卷《算法设计与分析》试卷1一、多项选择题（每空2分，共20分）：1、以下关于算法设计问题的叙述中正确的是__________。

A、计算机与数值问题的求解——方程式求根、插值问题、数值积分、函数逼近等有关B、利用计算机无法解决非数值问题C、计算机在解决分类、语言翻译、图形识别、解决高等代数和组合分析等方面的数学问题、定理证明、公式推导乃至日常生活中各种过程的模拟等问题中，主要进行的是判断、比较，而不是算术运算D、算法设计与分析主要研究对象是非数值问题，当然也包含某些数值问题2、算法的特征包括_________。

A、有穷性B、确定性C、输入和输出D、能行性或可行性3、以下描述是有关算法设计的基本步骤：①问题的陈述②算法分析③模型的拟制④算法的实现⑤算法的详细设计⑥文档的编制，应与其它环节交织在一起其中正确的顺序是__________。

A、①②③④⑤⑥B、①③⑤②④⑥C、②④①③⑤⑥D、⑥①③⑤②④4、以下说法正确的是__________。

A、数学归纳法可以证明算法终止性B、良序原则是证明算法的正确性的有力工具C、x = 小于或等于x的最大整数（x的低限）D、x = 小于或等于x的最大整数（x的高限）5、汉诺塔（Hanoi）问题中令h（n）为从A移动n个金片到C 上所用的次数，则递归方程为__________，其初始条件为__________，将n个金片从A柱移到C柱上的移动次数是__________；设菲波那契（Fibonacci）数列中Fn为第n个月时兔子的对数，则有递归方程为__________，其中F1=F2=__________。

A、Fn=Fn-1+Fn-2B、h（n）= 2h（n-1）+1C、1D、h（1）= 1E、h（n）=2n-1F、06、在一个有向连通图中（如下图所示），找出点A到点B的一条最短路为____ ______。

A、最短路：1→3→5→8→10，耗费：20B、最短路：1→4→6→9→10，耗费：16。

1.按分治策略求解棋盘覆盖问题时，对于如图所示的24X24的特殊棋盘，共需要多少个L型件牌：并在棋盘上填写L型骨牌的覆盖情况。

2.假设有7个物品，给出重疑和价值。

若这些物品均不能被分割，且背包容量M=140,使用回溯方法求解此0-1背包问题。

请画出状态空间搜索树。

3.假设有7个物品，它们的重量和价值如下表所示。

若这些物品均可以被分割，且背包容量M = 140,使用贪心算法求解此背包问题。

请写出求解策略和求解过程。

W (35,30,50,60,40,10,25) p (10,40,30,50,35,40,30)4.在给出的电路板中，阴彫部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确立a到b的最短布线方案，要求布线时只能沿宜线或直角进行，在图中标岀求得最优解时各方格情况。

5.画出字符表的哈夫曼编码对应的二叉树。

6.己知4 = (cf)”* , k=\, 2» 3» 4. 5, 6, ri=5,门=10, /?=3,心=8, /3=5»门=20, rz=6,求矩阵链积A1XA2XA3XA4XA5XA6的最佳求积顺序。

7.给出城市网络图，售货员要从城市1岀发，经过所有城市回到城市1,画岀该问题的解空间树, 描述出用优先队列式分支限界法求解时的搜索情况。

表示出优先队列、当前扩展结点等的变化情况。

8.依据优先队列式分支限界法，求从s点到t点的单源最短路径，画出求得最优解的解空间树。

一、假设有7个物品，它们的重量和价值如下表所示。

若这些物品均不能被分割，且背包容量M = 150,使用回溯方法求解此背包问题。

请写岀状态空间搜索树(20分)。

答：按照单位效益从大到小依次排列这7个物品为：FBGDECA.将它们的序号分别记为1〜7。

则可生产如下的状态空间搜索树。

英中各个右点处的限界函数值通过如下方式求得：【排序1分】a. 40+40+30+50+35X 瞥"90.625 (山丄范。

算法设计技术与方法大作业学院________________专业______________姓名__________________________学号_______________________任课老师多项式求值的四种方法1.问题背景分别实现多项式求值的四种运算，若针对不同规模的输入值a,各算法的运行时间，问题规模n 分别取10, 50, 100, 150, 200, 300, 400, 500, 10000, 20000, 50000, 100000 时绘制四种算法运行时间的比较图。

2.程序设计分析题意可知，该题要用四种方法实现对多项式的求值计算，每种方法取从10-100000 不同的规模。

本文采用直接代入法和递归法。

而其中递归法分三类不同思路进行递归：①只3)=只-13) +时"；。

, Q = 1, Q = Qx, P = P + a t Q；②P = a③3'3)=《3)工+。

"—,。

3.程序清单具体编程如下：clc;close all;clear all;n=[10 50 100 150 200 300 400 500 10000 20000 50000 100000];x=5;for i=l:12a=rand(l,(n(i)+l))；%产生多项式，最高次幕为n(i)tic;forj=l:n(i); %直接代入法s(j)=a(j)*x A(j);endpl(i)=a(n(i)+l);for j=l:n(i);pl(i)=s ①+pl ⑴；endtl(i)=toc;tic;p2(i)=0；for j=l:(n(i)+l)p2(i)=p2⑴+a(j)*xWl); % 递归法1endt2(i)=toc;tic;p3(；i)=0；q=l；for j=2:(n (i)+l)q=q*x;p3(i)=p3(i)+a(j)*q; % 递归法2endt3(i)=toc;tic;p4 ①=0；for j=l:n(i);p4(i)=x*p4(i)+a(n⑴+l-j); % 递归法3endt4(i)=toc;endfigure(l);subplot(2,2,l);h=semilogx(n,t 1);set(h,'linestyle','-'「linewidth'』,'marker','s','color','g','markersize',6); xlabel(问题规模(n ));ylabel(运行时间(s)，)；title(方法一)；grid on;subplot(2,2,2);h=semilogx(n,t2);set(h,'linestyle','-'「linewidth'』,'marker','s','color','b','markersize',6); xlabelC问题规模(n )，)；ylabel(运行时间(s)，)；title(方法二)；grid on;subplot(2,2,3)；h=semilogx(n,t2);set(h,'linestyle','-'「linewidth'』,'marker','s','color',k,'markersize',6); xlabel（，问题规模（n ），）；ylabel（运行时间（s），）；title（方法三）；grid on;subplot（2,2,4）;h=semilogx（n,t2）;set（h,'linestyle','-',Tinewidth', 1,'marker','s','color',、','markersize',6）; xlabelC问题规模（n ），）；ylabel（运行时间（s），）；title（方法四）；grid on;figure（2）;g=semilogx（n,tl,'g+',n,t2,'bx',n,t3,'k*',n,t4,To‘）；legend（方法一7方法二7方法三，，方法四）；set（g,'linestyleV-','linewidth', 1,'markersize',8）;xlabel（'n=10, 50, 100, 150, 200, 300, 400, 500, 10000, 20000, 50000, 100000'）; ylabel。

e i rb ei n一.填空题： 1. 元运算2. O 3.∑∈nD I I t I p )()(4. 将规模为n 的问题分解为子问题以及组合相应的子问题的解所需的时间5. 分解，递归，组合6. 在问题的状态空间树上作带剪枝的DFS 搜索（或：DFS+剪枝）7. 前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立（不重叠）的8. 局部9. 高10. 归并排序算法11. 不同12. v=random (low, high); 交换A[low]和A[v]的值 随机选主元13. 比较n二.计算题和简答题：1. 阶的关系：(1) f(n)= O(g(n))(2) f(n)=(g(n))Ω (3) f(n)=(g(n))Ω (4) f(n)= O(g(n))3. (1) i>=1 (2)k[i]+1 (3) 1(4) i+1 (5) k[i]=0 (6) tag[x, y]=0(7) x=x-dx[k[i]]; y=y-dy[k[i]]四.算法设计题：1. 贪心选择策略：从起点的加油站起每次加满油后不加油行驶尽可能远，直至油箱中的油耗尽前所能到达的最远的油站为止，在该油站再加满油。

算法MINSTOPS输入：A、B两地间的距离s，A、B两地间的加油站数n，车加满油后可行驶的公里数m，存储各加油站离起点A的距离的数组d[1..n]。

输出：从A地到B地的最少加油次数k以及最优解x[1..k]（x[i]表示第i次加油的加油站序号），若问题无解，则输出no solution。

d[n+1]=s; //设置虚拟加油站第n+1站。

for i=1 to nif d[i+1]-d[i]>m thenoutput “no solution”; return //无解，返回end ifend fork=1; x[k]=1 //在第1站加满油。

s1=m //s1为用汽车的当前油量可行驶至的地点与A点的距离i=2while s1<sif d[i+1]>s1 then //以汽车的当前油量无法到达第i+1站。

《算法设计与分析》课程笔试样题一（90分钟，开卷笔试，100分）学年学期班一、设n为正整数，利用大“O(·)”记号，将下列程序段的执行时间表示为n的函数，分析下列程序段的时间复杂度（每小题7.5分，共15分）1．程序段1i=1; k=0;while(i<n) {k=k+10*i;i++;}2．程序段2y=0; n=100;while ((y+1)*(y+1)<n) y++;二、简答题（每小题7.5, 共15分）1. 什么是算法, 算法具有的特性是什么？2. 什么是分枝限界法?三、设有序顺序表中的元素依次为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 doS(i)=0;①;repeatS(v)=1; DIST(v)=0; u=v;for i=2 to n dofor所有S(w)=0的结点w do找DIST(u)+COST(u, w)最小的节点w;repeatDIST(w)=min(DIST(w), ②) ;S(w)=1;③;repeatend 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]<C[i])){ C[i]=c[i][j]+C[j];①;}for(p[0]=0, p[k-1]=n-1, i=1; i<k-1; k++) ②;}其中，n为图的节点数，k为段数，c[][]为成本邻接矩阵，C[]为各节点到汇点的最短路径长度，d[]为各节点到汇点的最短路径上的后向邻接节点，p[]存储最短路径上的节点序列。