算法设计与分析参考试卷

本文格式为Word版，下载可任意编辑——算法设计与分析参考试卷此处不能书写此处不能书写此处不能书…写………此处不能书写……………装……

算法设计与分析参考试卷

一、单项选择题

1.当输入规模为n时，以下算法渐进繁杂性中最低的是（A）。．

A.5nB.n2C.2n2D.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、贪心法

D、回溯

B、排列树

C、深度优先生成树

D、广度优先生成

…8．快速排序算法是利用（A）实现的算法。

A．分治策略B．动态规划法C．贪心法D．回溯法

此处不能书写…

二、填空题

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

三、简答题

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

第1页共9页

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

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

求1到5的最短路径值？

三、执行过程：

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

第2页共9页

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

第一次：从1-->2：10此时从1-->3没有路径所有是无穷大1-->4：301-->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.intdijkstra(ints,intt){2.

3.初始化S={空集}4.

5.d[s]=0;其余d值为正无穷大6.

7.while(NOTtinS)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.returnd[t];22.23.}

……此…处…不能…书…写…线…………………订………此处不能书写…

2．二分探寻要解决什么问题?

二分探寻如何表达分治的思想?简述二分探寻算法的步骤.

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

第3页共9页

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

template

intBinarySearch(Typea[],constType

intright=n-1;

while(lefta[middle])left=middle+1;

elseright=middle-1;}

return-1;}

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

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

第4页共9页

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

简述0-1背包问题的动态规划算法.

给定n种物品和1个背包，物品i的重量是wi，其价值为vi