算法设计与分析复习题目及答案.docx
一。选择题
1、二分搜索算法是利用（A）实现的算法。
A、分治策略
B、动态规划法
C、贪心法
D、回溯法
2、下列不是动态规划算法基本步骤的是（B）。
A、找出最优解的性质
B、构造最优解
C、算出最优解
D、定义最优解
3、最大效益优先是（A）的一搜索方式。
A、分支界限法
B、动态规划法
C、贪心法
D、回溯法
4、在下列算法中有时找不到问题解的是（B）。
A、蒙特卡罗算法
B、拉斯维加斯算法
C、舍伍德算法
D、数值概率算法
5. 回溯法解旅行售货员问题时的解空间树是（B）。
A、子集树
B、排列树
C、深度优先生成树
D、广度优先生成树6．下列算法常以自底向上的方式求解最优解的是（B）。
A、备忘录法
B、动态规划法
C、贪心法
D、回溯法
7、衡量一个算法好坏的标准是（ C ）。
A 运行速度快
B 占用空间少
C 时间复杂度低
D 代码短
8、以下不可以使用分治法求解的是（ D ）。
A 棋盘覆盖问题
B 选择问题
C 归并排序
D 0/1 背包问题
9. 实现循环赛日程表利用的算法是（A）。
A、分治策略
B、动态规划法
C、贪心法
D、回溯法
10、下列随机算法中运行时有时候成功有时候失败的是（ C ）
A 数值概率算法
B 舍伍德算法
C 拉斯维加斯算法
D 蒙特卡罗算法11．下面不是分支界限法搜索方式的是（D
A、广度优先
B、最小耗费优先
C、最大效益优先
12．下列算法常以深度优先方式系统搜索问题解的是（
A、备忘录法
B、动态规划法
C、贪心法
13.备忘录方法是那种算法的变形。（ B ）
A、分治法
B、动态规划法
C、贪心法
14．哈弗曼编码的贪心算法所需的计算时间为（B
n
B、 O（nlogn ）n ）
A、O（ n2 ）C、O（2
15．分支限界法解最大团问题时，活结点表的组织形式是（A、最小堆B、最大堆C、栈
组）。
D、深度优先
D）。
D、回溯法
D、回溯法
）。
D、 O（ n）
B）。
D 、数
16．最长公共子序列算法利用的算法是（B）。
A、分支界限法
B、动态规划法
C、贪心法
D、回溯法17．实现棋盘覆盖算法利用的算法是（A）。
A、分治法
B、动态规划法
C、贪心法
D、回溯法
18.下面是贪心算法的基本要素的是（C）。
A、重叠子问题
B、构造最优解
C、贪心选择性质
D、定义最优解
19.回溯法的效率不依赖于下列哪些因素（D）
A.满足显约束的值的个数
B. 计算约束函数的时间
C. 计算限界函数的时间
D. 确定解空间的时间
20.下面哪种函数是回溯法中为避免无效搜索采取的策略（B）
A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数
21、下面关于 NP 问题说确的是（ B ）
A NP 问题都是不可能解决的问题
B P 类问题包含在 NP 类问题中
C NP 完全问题是 P 类问题的子集
D NP 类问题包含在 P 类问题中
22、蒙特卡罗算法是（B）的一种。
A、分支界限算法
B、概率算法
C、贪心算法
D、回溯算法
23.下列哪一种算法不是随机化算法（C）
A. 蒙特卡罗算法
B. 拉斯维加斯算法
C.动态规划算法
D.舍伍德算法
24. （D）是贪心算法与动态规划算法的共同点。
A、重叠子问题
B、构造最优解
C、贪心选择性质
D、最优子结构性质
25. 矩阵连乘问题的算法可由（B）设计实现。
A、分支界限算法
B、动态规划算法
C、贪心算法
D、回溯算法
26.分支限界法解旅行售货员问题时，活结点表的组织形式是
（A）。
A、最小堆
B、最大堆
C、栈
D、数组
27、Strassen 矩阵乘法是利用（A）实现的算法。
A、分治策略
B、动态规划法
C、贪心法
D、回溯法
29、使用分治法求解不需要满足的条件是（ A ）。
A子问题必须是一样的
B子问题不能够重复
C子问题的解可以合并
D原问题和子问题使用相同的方法解
30、下面问题（ B ）不能使用贪心法解决。
A 单源最短路径问题
B N 皇后问题
C 最小花费生成树问题
D 背包问题
31、下列算法中不能解决 0/1 背包问题的是（ A）
A 贪心法
B 动态规划
C 回溯法
D 分支限界法
32、回溯法搜索状态空间树是按照（ C ）的顺序。
A 中序遍历
B 广度优先遍历
C 深度优先遍历
D 层次优先遍历
33、下列随机算法中运行时有时候成功有时候失败的是（ C ）
A 数值概率算法
B 舍伍德算法
C 拉斯维加斯算法
D 蒙特卡罗算法
34．实现合并排序利用的算法是（A）。
A、分治策略
B、动态规划法
C、贪心法
D、回溯法35．下列不是动态规划算法基本要素的是（D）。
A、定义最优解
B、构造最优解
C、算出最优解
D、子问题重叠性质
36．下列算法常以自底向下的方式求解最优解的是（B）。
A、分治法
B、动态规划法
C、贪心法
D、回溯法37．采用广度优先策略搜索的算法是（A）。
A、分支界限法
B、动态规划法
C、贪心法
D、回溯法
38、合并排序算法是利用（A）实现的算法。
A、分治策略
B、动态规划法
C、贪心法
D、回溯法
39、在下列算法中得到的解未必正确的是（B）。
A、蒙特卡罗算法
B、拉斯维加斯算法
C、舍伍德算法
D、数值概率算法
40、背包问题的贪心算法所需的计算时间为（B）
A、O（n2 n）
B、O（nlogn ）
C、O（ 2n）
D、O（n）41．实现大整数的乘法是利用的算法（C）。
A、贪心法
B、动态规划法
C、分治策略
D、回溯法42．0-1 背包问题的回溯算法所需的计算时间为（A）
A、O（ n2n）
B、O（nlogn ）
C、O（2n ） D 、 O （ n）
43．采用最大效益优先搜索方式的算法是（A）。
A、分支界限法
B、动态规划法
C、贪心法
D、回溯法44．贪心算法与动态规划算法的主要区别是（B）。
A、最优子结构
B、贪心选择性质
C、构造最优解
D、定义最优解
45. 实现最大子段和利用的算法是（B）。
A、分治策略
B、动态规划法
C、贪心法
D、回溯法
46.优先队列式分支限界法选取扩展结点的原则是（C）。
A、先进先出
B、后进先出
C、结点的优先级
D、随机
47.背包问题的贪心算法所需的计算时间为（B）。
A、O（ n2n）
B、O（nlogn ）
C、 O（2n）
D、 O（ n）
48、广度优先是（A）的一搜索方式。
A、分支界限法
B、动态规划法
C、贪心法
D、回溯法
49、舍伍德算法是（B）的一种。
A、分支界限算法
B、概率算法
C、贪心算法
D、回溯算法
50、在下列算法中有时找不到问题解的是（B）。
A、蒙特卡罗算法
B、拉斯维加斯算法
C、舍伍德算法
D、数值概率算法
51 下列哪一种算法是随机化算法（D）
A. 贪心算法
B. 回溯法
C.动态规划算法
D.舍伍德算法
52.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的
（B）。
A、重叠子问题
B、最优子结构性质
C、贪心选择性质
D、定义最优解53．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大
排序，故算法的时间复杂度为(B)。
A、O（ n2n）
B、O（nlogn ）
C、 O（2n）
D、 O（ n）
54. 以深度优先方式系统搜索问题解的算法称为(D)。
A、分支界限算法
B、概率算法
C、贪心算法
D、回溯算法
55. 实现最长公共子序列利用的算法是（B）。
A、分治策略
B、动态规划法
C、贪心法
D、回溯法
56、算法是由若干条指令组成的有穷序列，而且满足以下性质（D）（1）输入：有 0 个或多个输入
（2）输出：至少有一个输出
（3）确定性：指令清晰，无歧义
（4）有限性：指令执行次数有限，而且执行时间有限
A (1)(2)(3)B(1)(2)(4)C(1)(3)(4) D (1) (2)(3)(4)
57、函数 32n +10nlog n的渐进表达式是 ( B).
A. 2n
B. 32n
C. nlog n
D. 10nlog n
58、大整数乘法算法是 ( A).算法
A.分治
B.贪心
C.动态规划
D.穷举
59、用动态规划算法解决最大字段和问题，其时间复杂性为( B).
A.logn
B.n
C.n2
D.nlogn
60、解决活动安排问题，最好用（ B）算法
A.分治
B.贪心
C.动态规划
D.穷举
61、设 f(N),g(N)是定义在正数集上的正函数 ,如果存在正的常数 C 和自然数 N0,使
得当 N≥N0时有 f(N)≤Cg(N),则称函数 f(N)当 N 充分大时有下界 g(N),记作
f(N)∈○ (g(N)),即 f(N)的阶 ( A)g(N)的阶 .
A.不高于
B.不低于
C.等价于
D.逼近
62、回溯法在解空间树 T 上的搜索方式是 ( A ).
A.深度优先
B.广度优先
C.最小耗费优先
D.活结点优先
63、回溯算法和分支限界法的问题的解空间树不会是(D).
A.有序树
B.子集树
C.排列树
D.无序树
64、在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活
结点的是( B ).
A.回溯法
B.分支限界法
C.回溯法和分支限界法
D.回溯法求解子集树问题
65、从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除 ( C )之外都是最常见的方式 .
A.队列式分支限界法
B.优先队列式分支限界法
C.栈式分支限界法
D.FIFO分支限界法
二、填空题
1.算法的复杂性有时间复杂性和空间复杂性之分。
2、程序是算法用某种程序设计语言的具体实现。
3、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。
4.矩阵连乘问题的算法可由动态规划设计实现。
5、拉斯维加斯算法找到的解一定是正确解。
6、算法是指解决问题的一种方法或一个过程。
7、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。
8、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的
关键特征。
9、以深度优先方式系统搜索问题解的算法称为回溯法。
10、数值概率算法常用于数值问题的求解。
11、计算一个算法时间复杂度通常可以计算循环次数、基本操作的频率
或计算步骤。
12、利用概率的性质计算近似值的随机算法是 __数值概率算法，运行时以一定的概率得到正确解的随机算法是__蒙特卡罗算法。
14、解决 0/1 背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是动态规划，需要排序的是回溯法，分支限界法。
15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函
数的界， N 皇后问题和 0/1 背包问题正好是两种不同的类型，其中同时使用约束
条件和目标函数的界进行裁剪的是0/1 背包问题，只使用约束条件进行裁剪的是N 皇后问题。
16、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态
规划算法的主要区别。
17、矩阵连乘问题的算法可由动态规划设计实现。
18、拉斯维加斯算法找到的解一定是正确解。
19.贪心算法的基本要素是贪心选择质和最优子结构
性质。
21. 动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
22.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。
23、大整数乘积算法是用分治法来设计的。
24、以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。
25、舍伍德算法总能求得问题的一个解。
26、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
27.快速排序算法是基于分治策略的一种排序算法。
28.动态规划算法的两个基本要素是.最优子结构性质和重叠子问题性质。
30.回溯法是一种既带有系统性又带有跳跃性的搜索算法。
31.分支限界法主要有队列式（FIFO）分支限界法和优先队列式分支限界法。
32．分支限界法是一种既带有系统性又带有跳跃性的搜索算法。
33．回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数。
34.任何可用计算机求解的问题所需的时间都与其规模有关。
35.快速排序算法的性能取决于划分的对称性。
36. Prim 算法利用贪心策略求解最小生成树问题，其时间复杂度是O(n2)。
37. 图的m 着色问题可用回溯法求解，其解空间树中叶子结点个数是
m n，解空间树中每个结点的孩子数是m。
三、算法填空
1.背包问题的贪心算法
void Knapsack(int n,float M,float v[],float w[],float x[])
{
So rt(n,v,w);
int i;
for (i=1;i<=n;i++) x[i]=0;
float c=M;
for (i=1;i<=n;i++) {
if (w[i]>c) break;
x[i]=1;
c - =w[i] ;
}
if (i<=n) x[i]=c/w[i] ;
}
2.最大子段和 : 动态规划算法
int MaxSum(int n, int a[])
{
int sum=0, b=0 ；//sum 存储当前最大的b[j], b 存储 b[j]
for(int j=1 ； j<=n ； j++){
if (b>0) b+= a[j]；
else b=a[i] ;；// 一旦某个区段和为负，则从下一个位置累和
if(b>sum) sum=b ;
}
return sum ；
}
3.快速排序
template
void QuickSort (Type a[], int p, int r)
{
if (p int q=Partition(a,p,r); QuickSort (a,p,q-1) ; // 对左半段排序 QuickSort (a,q+1,r) ; // 对右半段排序 } } 4.排列问题 Template void perm(Type list[],int k, int m ) { // 产生 [list[k:m] 的所有排列 if(k==m) { // 只剩下一个元素 for (int i=0;i<=m;i++)cout< cout< } else// 还有多个元素待排列，递归产生排列 for (int i=k; i<=m; i++ ) { swap(list[k]，list[i]); perm(list,k+1;m) ; swap(list[k],list[i]); } } 5.给定已按升序排好序的n 个元素 a[0:n-1] ，现要在这 n 个元素中找出一特定元素 x。 据此容易设计出二分搜索算法： template int BinarySearch(Type a[], const Type& x, int l, int r) { while (l<=r ){ int m = ((l+r)/2); if (x == a[m]) return m; if (x < a[m]) r = m-1; else r = m+1; } return -1; } 6、合并排序描述如下： template void Mergesort(Type a[ ], int left, int right) { if (left int i=( left+right)/2; Mergesort(a, left, i ); Mergesort(a, i+1, right); Merge(a,b, left,i,right);// 合并到数组 b Copy(a,b, left,right ); // 复制到数组 a } } 7、以下是计算 x m的值的过程 int power ( x, m ) {// 计算 x m的值并返回。 y=( 1 );i=m; While(i- - >0) y=y*x; (return y) ; } 四、问答题 1.用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2.算法定义： 算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过 程 3.算法的三要素 1、操作 2、控制结构 3、数据结构 4.算法具有以下 5 个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本 运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 5.算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分治法、贪婪法、动态规划法、回溯法、分支限 界法 6.迭代法 : 也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 7.利用迭代算法解决问题，需要做好以下三个方面的工作： 1)、确定迭代模型。在可以用迭代算法解决的问题中，至少存在一个直接或 间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。 2)、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下 一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以 使用递推或倒推的方法来完成。 3)、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必 须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是 所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。 8.分治法的基本思想是： 将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。 9.分治法所能解决的问题一般具有以下几个特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有 最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不 包含公共的子子问题。 10、分治法的基本步骤 分治法在每一层递归上都有三个步骤： （1）分解：将原问题分解为若干个规模较小，相互独立，与原问题 形式相同的子问题； （2）解决：若子问题规模较小而容易被解决则直接解，否则递归地 解各个子问题； （3）合并：将各个子问题的解合并为原问题的解。 11.动态规划的基本思想 前文主要介绍了动态规划的一些理论依据，我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段法反而 麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。 动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。 由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为 更小的、相似的子问题，并通过求解子问题产生一个全局最优解。 贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择； 而分治法中的各个子问题是独立的（即不包含公共的子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。 不足之处：如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心 策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。 解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类 问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过 程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，（亦即各子问题可包含公共的子问题）也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。 因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树 中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。 12、动态规划算法的基本步骤 设计一个标准的动态规划算法，通常可按以下几个步骤进行： （1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若 干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动 态规划求解。 （2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状 态表示出来。当然，状态的选择要满足无后效性。 （3）确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状 态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶 段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。 （4）写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用 形式化表达式。 一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。 动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计 算。实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行： （1）分析最优解的性质，并刻划其结构特征。 （2）递归地定义最优值。 （3）以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。 （4）根据计算最优值时得到的信息，构造一个最优解。 步骤（ 1）～（3）是动态规划算法的基本步骤。在只需要求出最优值的情形，步 骤（4）可以省略，若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（ 3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速地构造出一个最优解。 总结：动态规划实际上就是最优化的问题，是指将原问题的大实例等价于同 一最优化问题的较小实例，自底向上的求解最小实例，并将所求解存放起来，存放的结果就是为了准备数据。与递归相比，递归是不断的调用子程序求解，是自顶向下的调用和求解。 13.分治法与动态规划法的相同点是： 将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。 算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj 大学期末思修考试 2019最新大学思想道德修养与法律基础试题[含答案] 一、选择题 1．“只有在集体中，个人才能获得全面发展其才能的手段，也就是说，只有在集体中才可能有个人自由。”这说明（） A、没有集体利益，就不可能有个人利益 B、集体主义坚决排斥个人利益和个性自由 C、广大人民只有靠集体奋斗才能实现自身的正当利益 D、只有集体的事业兴旺发达，才能保障个人的正当利益充分实现 2．法具有维护有利于统治阶级的社会关系和社会秩序的作用。这指的是法的（） A、社会作用 B、规范作用 C、指引作用 D、制裁作用 3．理想作为一种精神现象，是（）B A．人与生俱来的 B．是社会实践的产物 C．是人们成年后的必然产物 D．是人类进化到今天的结果 4．道德是一种行为规范，它所包含和要解决的主要矛盾是（）D A．善与恶、正义与非正义 B．公正和偏私、诚实和虚伪 C．经济基础和上层建筑 D．个人利益和整体利益 5．“知之为知之，不知为不知，是知也。”这句话告诉我们，在学习上一定要培养 （A）的优良学风。 A求实B一丝不苟C勤奋D敢为人先 6．下列著作不能说明作者身处逆境而有作为的有（D）。 A《周易》B《离骚》C《史记》D《论语》 二，多项选择题 7．信念与信仰的关系是（ABCD）。 A信仰是一个人做什么和不做什么的根本标准和态度 B信念是非要去做、去执行的坚决态度C信仰属于信念 D信仰是信念的最高表现形式E信念属于信仰 8．设立有限责任公司依法应具备的条件包括( ABC )。 A 有公司名称 B 符合法定人数的股东 C 有固定的生产经营场所 D 事先经由主管行政部门审批 9．依照法律服兵役和参加民兵组织是中华人民共和国公民的光荣义务。规定这一义务的法有（） A《宪法》 B《国防法》 C《兵役法》 D《反分裂国家法》 10．不同的人由于社会环境、思想观念、利益需要、人生经历和性格特征等方面的差异，会形成不同的乃至截然相反的信念。即使是同一个人，也会形成关于社会生活不同方面的信念，如在政治、经济、文化以及事业、学业和生活等方面，都会形成相应的不同层次的信念。这体现信念的（C）。 A．阶级性 B．稳定性 C．多样性 D．科学性 11．我国传统法文化中的消极因素有( CD )。 A 重视调解在解决一般纠纷中的作用 B 注重成文法 C 法即是刑 D 轻视诉讼和权利观念淡薄 12．检察院认为被告人犯罪情节轻微，依法免除刑罚的，应当制作( D )。 A 免予起诉决定书 B 免予起诉意见书 C 不起诉书 D 不起诉决定书 二、填空题 13．我国的人民民主专政实质上是 ___________________________ 。 三、单选题 14．在当代中国，爱国主义首先体现在对（）的热爱上，这是中华人民共和国每一个公民必须坚持的立场和态度。（标准答案：D) A. 自己家庭 B. 自己的事业 C. 世界的发展 D. 社会主义中国 考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：① 因为：;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知： 1-10n n 2 2+是n ;的渐近表达式。 ② 因为：;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知： 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】 5x =6x =7x = 算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中 for(i=0;i 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 思修重点 1．大学生怎样尽快适应大学新生活？ 在学习要求，生活环境，社会活动都有变化的大学中首先要认识大学生活的新特点。要培养自主学习的能力，独立思考问题解决问题的能力：要学会过集体生活也要独立：要积极参与社会活动。 提高独立生活能力。树立独立生活的意识。 虚心求教，细心体察。大胆实践，不断积累生活经验 实力新的学习理念。树立自主学习的理念。树立全面学习的理念。树立创新学习的理念。树立终身学习的理念。 培养优良的学风。勤奋。严谨。求实。创新。 树立远大的理想。 2.结合实际谈谈学习“思修”课的意义和方法。 这是一门融思想性，政治性，知识性，综合性，实践性于一体的学科。 意义：（1）有助于当代大学生认识立志，树德和做人的道理，选择正确的成才之路。 （2）有助于当代大学生掌握丰富的思想道德和法律知识，为提高思想道德和法律素养打下知识基础。 （3）有助于当代大学生摆正“德’与“才”的位置，做到德才兼备，全面发展。 方法：注重学习科学理论。 注重学习和掌握高思想道德和法律修养的基本知识。 注重联系实际注重行知统一。 3.谈谈你对社会主义核心价值体系的科学内涵及重要意义的理解？ 科学内涵；马克思主义指导思想，中国特色社会主义共同理想，以爱国主义为核心的民族精神和以改革创新为核心的时代精神，社会主义荣辱观，构成社会主义核心价值体系的基本内容。 巩固马克思主义指导地位，坚持不解地用马克思主义中国化最新成果武装全党，教育人民。 用中国特色社会主义共同理想凝聚力量 用以爱国主义为核心的民族精神和以改革创新为核心的时代精神鼓舞斗志 用社会主义荣辱观引领风尚，巩固全党全国各族人民团结奋斗的共同思想基础。 这四个方面内容相互联系，相互贯通，相互促进，是有机统一的整体。 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?，则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人 内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 思修期末考试模拟试题及答案 本书为高等教育出版社出版2015年修订版（仅供参考） 1．大学生怎样尽快适应大学新生活？ 3 2.结合实际谈谈学习“思修”课的意义和方法。 3 3.谈谈你对社会主义核心价值体系的科学内涵及重要意义的理解？ 3 4.什么是理想什么是信念？ 4 5，理想信念对大学生成才的作用 4 6.如何认识个人理想与中国特色社会主义共同理想的关系？ 4 7.联系实际，谈谈大学生如何实现自己的崇高理想？ 4 8.什么是爱国主义？如何理解其科学内涵及优良传统？ 5 9.新时期的爱国主义有那些内容？ 5 10.什么是民族精神？中华民族精神的内涵是什么？ 5 11.什么是时代精神？内涵是什么？ 5 12.做一个忠诚的爱国者需要在哪些方面努力？ 6 13.什么是人生观？什么是人生价值？ 6 14.人的本质是什么？如何理解？ 6 15人生态度与人生观是什么关系？如何端正人生态度？ 6 16.对人生价值评价要坚持那几方面的统一？ 6 17.人生价值实现的条件是什么？ 7 18.什么是健康？怎样协调自我身心关系？ 7 19.促进个人与他人的和谐应坚持的原则是什么？ 7 20.如何促进个人与社会的和谐？ 7 21.道德的本质、功能和作用是什么？ 8 22.中华民族优良道德传统的主要内容是什么？ 9 23.如何理解为人民服务是社会主义道德建设的核心，集体主义是社会主义道德建设的原则？ 9 24.社会主义荣辱观的科学内涵是什么？ 10 25.谈谈当代大学生怎样树立诚信品质？ 10 26.公共生活有序化对经济建设发展有何重要意义？ 10 27.社会公德的基本特征和主要内容是什么？ 10 28.遵守网络生活中道德要求的重要意义是什么？ 11 29.举例说明法律规范在公共生活中的作用。 11 30.简述《治安管理处罚法》的基本精神和主要内容。 11 31.什么是职业道德？职业道德的基本要求是什么？ 12 32.《劳动法》和《公务员法》的基本原则是什么？ 33.联系实际，谈谈大学生如何树立正确的择业观与创业观。34.家庭美德的基本规范是什么？ 35.简述我国婚姻家庭法的基本原则及关于结婚的相关规定。36.简述法律的一般含义及社会主义法律的本质。 37.什么是法律制定、法律遵守、法律执行及法律适用？ 38.建设社会主义法治国家的主要任务是什么？ 39.联系实际，谈谈如何理解法律权利与义务的关系。 40.什么是法律思维方式？它的特征是什么？ 41.大学生应该如何增强法制观念，维护法律的权威？ 42.我国宪法的特征和基本原则是什么？ 43.我国的国家制度包括哪些制度？ 44.我国公民的基本权利和义务有哪些？ 45.什么是民法？我国民法的基本原则是什么？ 46.简述我国民事权利制度的主要内容。 47.简述我国合同法律制度的主要内容。 48.什么是刑法？我国刑法的基本原则是什么？ 49.什么是犯罪？犯罪构成包括哪些要件？ 50.什么是正当防卫？什么是紧急避险？其成立条件分别是什么 1．大学生怎样尽快适应大学新生活？ 在学习要求，生活环境，社会活动都有变化的大学 中首先要认识大学生活的新特点。要培养自主学习的能 力，独立思考问题解决问题的能力：要学会过集体生活 也要独立：要积极参与社会活动； 提高独立生活能力。 树立独立生活的意识； 虚心求教，细心体察； 大胆实践，不断积累生活经验； 实力新的学习理念。树立自主学习的理念。树立全面学习的理念。树立创新学习的理念。树立终身学习的理念； 培养优良的学风、勤奋、严谨、求实、创新； 树立远大的理想。 2.结合实际谈谈学习“思修”课的意义和方法。 这是一门融思想性，政治性，知识性，综合性，实 湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14 精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（提 出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 ．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档． 精品文档 #include 思修期末考试试题题库及答案（50题）1．大学生怎样尽快适应大学新生活？ 在学习要求，生活环境，社会活动都有变化的大学中首先要认识大学生活的新特点。要培养自主学习的能力，独立思考问题解决问题的能力：要学会过集体生活也要独立：要积极参与社会活动；提高独立生活能力。树立独立生活的意识；虚心求教，细心体察；大胆实践，不断积累生活经验；实力新的学习理念。树立自主学习的理念。树立全面学习的理念。树立创新学习的理念。树立终身学习的理念；培养优良的学风、勤奋、严谨、求实、创新；树立远大的理想。 2.结合实际谈谈学习“思修”课的意义和方法。 这是一门融思想性，政治性，知识性，综合性，实践性于一体的学科。 意义：（1）有助于当代大学生认识立志，树德和做人的道理，选择正确的成才之路。（2）有助于当代大学生掌握丰富的思想道德和法律知识，为提高思想道德和法律素养打下知识基础。（3）有助于当代大学生摆正“德’与“才”的位置，做到德才兼备，全面发展。方法：注重学习科学理论。注重学习和掌握高思想道德和法律修养的基本知识。注重联系实际注重行知统一。 3.谈谈你对社会主义核心价值体系的科学内涵及重要意义的理解？ 科学内涵；马克思主义指导思想，中国特色社会主义共同理想，以爱国主义为核心的民族精神和以改革创新为核心的时代精神，社会主义荣辱观，构成社会主义核心价值体系的基本内容。巩固马克思主义指导地位，坚持不解地用马克思主义中国化最新成果武装全党，教育人民。用中国特色社会主义共同理想凝聚力量用以爱国主义为核心的民族精神和以改革创新为核心的时代精神鼓舞斗志用社会主义荣 辱观引领风尚，巩固全党全国各族人民团结奋斗的共同思想基础。这四个方面内容相互联系，相互贯通，相互促进，是有机统一的整体。重要意义：是党在思想理论建设上的一个重大理论创新。是我们党深刻总结历史经验，科学分析当前形势提出的一项重大任务。涉及经济，政治，文化，思想等社会方面，是社会主义意识形态的本质体现，是社会主义思想道德建设的思想理论基础，是激励全民奋发向上的精神力量和维系全民族团结和睦的精神纽带。适应了社会主义市场经济发展的要求，适应了社会主义先进文化建设要求，适应现阶段社会主义思想道德建设的要求也是引领当代大学生成长成才的根本指针。 4.什么是理想什么是信念？ 理想；人们在实践中形成的，对未来社会和自身发展的向往和追求，是人们的世界观，人生观，和价值观在奋斗目标上的集中体现。信念；是认知，情感和意志的有机统一体，是人们在一定的认识基础上确立的对某种思想或事物坚信不疑并身体力行的心理态度和精神状态。信念是对理想的支持也是人们追求理想目标的强大动力。 5，理想信念对大学生成才的作用：指引人生的奋斗目标；提供人生的前进动力；提高人生的精神境界；引导大学生做什么人走什么路为什么学 7.联系实际，谈谈大学生如何实现自己的崇高理想？ （1）立志当高远。立志做大事。立志需躬行。 （2）认清实现理想的长期性，艰巨性和曲折性理想的实现是一个过程，要做好充足的准备； 要正确对待实现理想过程中的顺境和逆境，善于利用顺境，勇于正视逆境和战胜逆境 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。 大一思修期末考试试题（选择题） 一、单项选择题（本大题共20小题，每小题2分，共40分）在每小题列出的四个备选项中只有一个是符合题目要求的 ⒈人生观的核心是（ A ） A、人生目的 B、人生价值 C、人生态度 D、人生理想 ⒉世界观是人们对（ D ）的最根本看法和总和。 A 社会 B 人生意义 C 自然界 D 整个世界 ⒊人生观是（ C ）的反应。 A 自我认识 B 政治关系 C 社会存在 D 自然条件 ⒋人生的目的是对（B）这一人生根本问题的认识和回答。 A 人为什么发展 B 人为什么活着 C 人为什么工作 D 人为什么努力 ⒌人生的社会价值是个人的人生对（D）的意义。 A 自我与社会 B 集体与社会 C 自我与他人 D 社会与他人 ⒍人生的价值趋向是对（D）的意义。 A 自我价值 B 社会价值 C 价值质量 D 价值目标 ⒎理想是人在实践中形成的具有（D）的对美好未来的追求和想法。 A 实现豁然性 B 不可能性 C超越客观性 D 实现可能性 ⒏理想人的确立于（D） A 中年 B 童年 C 青年 D 青年时期 ⒐处于核心地位的理想类型（B） A 生活 B社会理想 C 道德理想 D职业理想 ⒑信念突出的本质特征（A） A“信” B“诚” C “真” D“疑” ⒒社会主义的核心是（A） A 为人民服务 B尊老爱幼 C ⒓道德是由一定的社会经济基础所决定的为其服务的（D） A 政治制度 B 文化传统 C 传统习惯 D 上层建筑 ⒔道德核心问题是( C) A物 B 自然 C 人 D 社会 ⒕为人民服务低层次的要求（A） A人人为我，我为人人 B 全心全意为人民服务 C 毫不利己，专门为人 D 人人为自己，上帝为人家 ⒖反应阶级民族或社会利益的道德( B) A 狭义 B 广义 C 高尚 D 法律规定 ⒗在一定职业生活中所遵循的具有自身职业准则的（D） A 职业规范 B职业行为准则 C 职业守则 D 职业道德 ⒘我国职业道德的本质特征( 奉献社会) ⒙伴随道德认识所表现出来一种内心体验是（C） A 道德评价 B 道德意志 C 道德情感 D 道德习惯 ⒚法律主要体现（统治阶级）的意志 ⒛法律以（B）为基础。 A 意志 B 经济关系 C 政策 D 政治 第一章作业 1.证明下列Ο、Ω和Θ的性质 1）f=Ο(g)当且仅当g=Ω(f) 证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得?n≥n0，有f≤c1*g(n)。由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。 必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。 2）若f=Θ(g)则g=Θ(f) 证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。 3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。 证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n≥n1，有 F(n) ≤ c1 (f(n)+g(n)) = c1 f(n) + c1g(n) ≤ c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。 4）log(n!)= Θ(nlogn) 证明： ?由于log(n!)=∑=n i i 1 log ≤∑=n i n 1 log =nlogn ，所以可得log(n!)= Ο(nlogn)。 ?由于对所有的偶数n 有， log(n!)= ∑=n i i 1 log ≥∑=n n i i 2 /log ≥∑=n n i n 2 /2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。 当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得?n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。 综合以上两点可得log(n!)= Θ(nlogn) 2. 设计一个算法，求给定n 个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3） 算法： V oid findsecond(ElemType A[]) { for (i=2; i<=n;i++) if (A[1] 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性: 确定性,有穷性,可行性,0个或多个输入,一个或多个输出。 2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低。 3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解。 6.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个基本要素是最优子结构和重叠子问题。 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质； ②构造最优值的递归关系表达式； ③最优值的算法描述； ④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ②N1={i|ai《计算机算法设计与分析》习题及答案
算法设计与分析考试题及答案
最新大学思修期末考试题(含答案)
算法设计与分析试卷A及答案
算法设计与分析课后部分习题答案
算法设计与分析考试题及答案
思修期末考试试题及答案
算法设计与分析试卷及答案
算法设计与分析试卷(2010)
大一思想道德修养与法律基础期末考试试题及答案
算法设计与分析试卷及答案
算法设计与分析第2版 王红梅 胡明 习题答案
思修期末考试试题题库及答案(50题)
算法设计与分析试卷(2010)
计算机算法设计与分析期末考试复习题
最新大一思修期末考试试题
算法设计与分析习题解答
算法设计与分析试题与答案
- 计算机算法设计与分析(第三版)课后习题答案详解
- 算法设计与分析习题答案1-6章
- 算法设计与分析基础习题参考答案
- 算法设计与分析大作业答案
- 算法设计与分析课后部分习题答案
- 算法设计与分析基础课后习题答案solu3
- 算法设计与分析答案
- 算法设计与分析考试题及答案
- 算法设计与分析试卷答案
- 算法设计与分析-习题参考答案
- 算法设计与分析考试题及答案
- OpenJudge算法设计与分析习题解答
- 算法设计与分析课后部分习题答案
- 算法设计与分析习题答案
- 算法设计与分析答案屈婉玲
- 《计算机算法设计与分析》习题及答案
- 算法设计与分析试题及答案
- 《算法设计与分析实用教程》习题参考解答
- 计算机算法设计与分析(第三版)课后习题答案详解
- 算法设计与分析复习题目及答案