一、选择题

1.下列叙述中正确的是_________________。正确答案是：以上三种说法都不对

2.下列叙述中正确的是_________________。正确答案是：以上三种说法都不对

3.一个算法应该具有“确定性”等5个特性，下面对另外4个特性的描述中错误的是（   ）。正确答案是：有零个或多个输出

4.下面叙述正确的是（   ）。正确答案是：算法的时间复杂度是指执行算法所需要的计算工作量
5.根据问题条件估计答案的范围，在此范围内对所有可能情况逐一验证，直到全部情况均通过验证为止。这种算法是（  ）。正确答案是：穷举法

二、简答题

6.算法的描述方法主要有哪几种？各有什么特点？

常用的有自然语言、结构化流程图、伪代码和PAD图等，其中最普遍的是流程图，分思法。

流程图（Flow Chart）使用图形表示算法的思路是一种极好的方法，因为千言万语不如一张图。流程图在汇编语言和早期的BASIC语言环境中得到应用。相关的还有一种PAD图，对PASCAL或C语言都极适用。

算法可以宏泛的分为三类：

一、有限的，确定性算法 这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。

二、有限的，非确定算法 这类算法在有限的时间内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。

三、无限的算法 是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。

7.简述穷举法、递归法、回溯法、贪婪法的基本思想？并举例说明之。

1、穷举法
基本思想：

在可能的解空间中穷举出每一种可能的解，并对每一个可能解进行判断，从中筛选出问题的答案。

关键步骤：划定问题的解空间，并在该解空间中一一枚举每一种可能的解。

注意点：

   1、解空间的划定必须保证覆盖问题的全部解：只有问题的解集属于解空间集合才能使用穷举法求解。

   2、解空间集合以及问题的解集一定是离散的集合。即可列的、有限的

————————————————

 2、递归算法

基本思想：

将规模较大的问题分割为规模较小的同类问题，然后将这些子问题逐个加以解决，最终也就将整个大的问题解决了。

分治思想：举例，折半查找就是利用序列之间元素的顺序关系，不断缩小问题的规模，每次都将问题缩小为原来的1/2，采用顺序的方法查找需要O,而折半只需要O(long2n)

递归思想:一种直接或间接地调用原算法本身的一种算法。

设计递归算法需要注意的几点：

1、每个递归函数都必须有一个非递归定义得初始值，作为递归结束标志，或递归结束的出口

2、递归算法的运行较低，时间和空间复杂度都比较高，对于一些对时间和空间要求较高的程序，建议使用非递归算法设计。
————————————————

3、贪心算法
贪心算法不从整体最优上加以考虑，所做的仅是在某种意义上的局部最优解。而局部最优解叠加到一起便是该问题整体上的最优解，或者近似最优解。

严格意义上讲，要使用贪心算法求解问题，该问题应当具备如下性质：

   1、贪心选择性质：指求解的问题的整体最优解可以通过一系列的局部最优解得到。所谓局部最优解，就是指在当前的状态下做出的最好的选择。

   2、最优子结构性质：

一个问题的最优解包含着它的子问题的最优解
————————————————

4、回溯算法
基本思想：

在包含问题的所有解的解空间中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去；如果该结点不包含问题的解，那就说明以该结点为根结点的子树一定不包含问题的最终解，因此要跳过对以该结点为根的子树的系统探索，逐层向其祖先结点回溯。这个过程叫做解空间树的“剪枝”操作。

如果应用回溯法求解问题的所有解，要回溯到解空间树的树根，这样才能保证根结点的所有子树都被探索到才结束。如果只要求得问题的一个解，那么在探索解空间树时，只要搜索到问题的一个解就可以结束了。
————————————————

8.利用穷举法编写一个算法判断给定的正整数n是否是素数，即判断n是否只能被1和自身整除。

#include“math.h”

#include“stdio.h”

void main()

{undefined

int m，i，k；

scanf("%d"，&m)；

ksqrt(m)；

for(i=2；i<=k；i++)

if(m%i==0)break；

if(i>=k+1)

printf("%d is a prime number\n"，m)；

else

printf("%d is not a prime number\n"，m)；

}

三、分析与思考

9.当你需要计划一个外出旅行时，你会如何进行自己的旅行路线设计？请用简单的流程图描述。

第一步、我们选择打开迅捷画图在线网站，在浏览器中搜索该网站后打开，打开后可以看到网站可以制作流程图和思维导图，我们选择点击流程图，跳转到流程图页面后，点击下方的“立即体验”。

第二步、进入到流程图的编辑页面，页面中有多种流程图的模板可选择，我们点击选择EVC企业价值链图栏目，在该栏目的模板中，会有旅游行程路线图的模板。我们选中打开该模板，进行在线编辑。

第三步、我们看到旅游行程图中，有几个重要部分组成，首先是始发地，中转站，目的地，这几个环节我们可以根据自己的实际旅游地点进行更改，比如说可以改成始发地重庆，中转站天津，目的地北京等等，这样可以很明确的看懂自己要去的地方。

第四部、可以在原有的模板下建新的内容，比如说中转站天津，武密可以吧自己想要去的天津玩的地方添加进去，到达北京后，把自己去北京游玩的安排都添加到目的地这个栏目中，就可以很清楚地知道具体的时间安排，制作完成后点击保存即可

10.当你的旅行经费（或时间）有限时，你会如何控制并设计好你的旅行线路，尽可能玩的开心呢？把你的这些思考用自然语言描述出来，和同学一起分享你的旅行的小经验。这些就是来自生活中的小算法。

首先要考虑的是住宿问题，既然想要省钱的话，就不能住在比较豪华的酒店里，那么就只能选择青年旅社了，青年旅社价钱比较低，里面的布置就像学生宿舍一样，你们可以结伴几个人一起住在里面，一天可能要四五十块钱左右，而且住的也比较舒适。

吃饭的话千万不要在景区旁边儿吃，找一个价钱比较亲民的饭店来吃，也不要吃的太好了，因为出来旅游本来就是玩的，想要吃的好的话回家也可以吃，把吃饭的钱省下来，还可以多玩儿一个景区，一般来说景区的饭店都比较昂贵，你可以选择路边儿的小摊儿。

您需要登录后才可以回帖 登录 | 立即注册

本版版规

请不要发布与政治、色情、反动、赌博等其他相关违法帖子，一经发现，作锁定帐号或删除帐号处理。