算法设计与分析参考试卷

此处不能书写此处不能书写此处不能书…写………此处不能书写……………………………………………装…… 算法设计与分析参考试卷 一、单项选择题

1. 当输入规模为n时，下列算法渐进复杂性中最低的是（A ）。 ． A. 5n B. n2 C. 2n2 D. n! 2.二分搜索算法是利用（A ）实现的算法。

A、分治策略 B、动态规划法 C、贪心法 D、回溯法 3．最大效益优先是（ A ）的一种搜索方式。

A．分支界限法 B．动态规划法 C．贪心法 D．回溯法 4. 回溯法搜索状态空间树是按照（ C ）的顺序。 A．中序遍历 B．广度优先遍历 C．深度优先遍历 D．层次优先遍历 ……此…处…不能…书…写…线…………………………………订……5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 树

6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 法

7．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法

B、动态规划法 C、贪心法

D、回溯法

B、动态规划法 C、贪心法

1 / 5

D、回溯

B、排列树

C、深度优先生成树 D、广度优先生成

…8．快速排序算法是利用（ A ）实现的算法。 A．分治策略 B．动态规划法 C．贪心法 D．回溯法 此处不能书写… 二、填空题

1. 通俗地讲，算法是指解决问题的 一种方法或一个过程 。 2．出于“平衡子问题”的思想，通常分治法在分解原问题时，形成若干子问题，这些子问题的规模都大致 相同 。 三、简答题

1． 简述单源最短路径问题，该问题适合采用什么方法求解。 第 1 页 共 9 页

…………………………此处不能书写 ……一、问题单源最短路径问题[Dijkstra实现]

带权有向图G（E,V), 找出从给定源顶点s到其它顶点v的权最小路径。 “最短路径” = 最小权 二、问题求解： 求1到5的最短路径值？

三、执行过程：

如果大家对这个问题的要求还不是很明白的话那么我再带着大家走一遍：

2 / 5

第2页 共9页

此处不能书写此处不能书写此处不能书…写………此处不能书写……………………………………………装……

第一次：从1-->2：10 此时从1-->3没有路径所有是无穷大 1-->4：30 1-->5：100那么我们发现这一组组最小的是10也就是2这一点，所以我们再把2这一点加到集合里面来，那么2这一点就可以当作一个桥来用， 第二次：此时我们再从1à3就可以通过1-->2-->3:60其他的1-->4：30 1-->5：100 可以发现此时最小的应该是3，所以我们再把3这一点加入到这个集合里面来，如此重复的去做这些事情，到最后可以发现1à5的最短路径应该是60（1-->4-->3-->5）

1. int dijkstra(int s,int t) { 2. 3. 初始化S={空集} 4.

5. d[s] = 0; 其余d值为正无穷大 6. 7. while (NOT t in S) 8. 9. { 10.

11. 取出不在S中的最小的d[i]; 12.

13. for (所有不在S中且与i相邻的点j) 14. 15. if (d[j] > d[i] + cost[i][j]) d[j] = d[i] + cost[i][j]; (

“松弛”操作” ) 16.

17. S = S + {i}; //把i点添加到集合S里 18. 19. } 20.

21. return d[t]; 22. 23. }

……此…处…不能…书…写…线…………………………………订………此处不能书写… 2． 二分搜索要解决什么问题?

二分搜索如何体现分治的思想? 简述二分搜索算法的步骤.

3 / 5

…………………………此处不能书写查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最折 第 3 页 共 9 页

……半坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果xa[n/2]，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解，但是要写一个正确的二分搜索算法也不是一件简单的事。第一个二分搜索算法早在1946年就出现了，但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的，我们可用C++描述如下： template

int BinarySearch(Type a[],const Type& x,int n) { int left=0; int right=n-1;

while(lefta[middle]) left=middle+1; else right=middle-1; } return -1; }

3． 什么是0-1背包问题?

用动态规划解决0-1背包问题时,它的最优子结构(问题)是什么? 第4页 共9页

此处不能书写此处不能书写此处不能书…写………此处不能书写……………………………………………装…… 简述0-1背包问题的动态规划算法.

给定n种物品和1个背包，物品i的重量是wi，其价值为vi，背包的容量为C。问如何选择撞入背包中使得装入背包总价值最大！

4 / 5

……此…处…不能…书…写…线…………………………………订……… 此处不能书写……………………………此处不能书写第 5 页 共 9 页 ……

5 / 5