一、单选题
1、下面关于算法的描述，正确的是（d ）
A、 一个算法只能有一个输入 B、 算法只能用框图来表示
C、 一个算法的执行步骤可以是无限的
D、一个完整的算法，不管用什么方法来表示，都至少有一个输出结果
2、一位爱好程序设计的同学，想通过程序设计解决“韩信点兵”的问题，他制定的如下工作过程中，更恰当的是（c ）
A、设计算法，编写程序，提出问题，运行程序，得到答案 B、分析问题，编写程序，设计算法，运行程序，得到答案 C、分析问题，设计算法，编写程序，运行程序，得到答案 D、设计算法，提出问题，编写程序，运行程序，得到答案
3、有5位运动员100米成绩依次为13.8，12.5，13.0，13.2，13.4，（c ）
原始数据 第一趟 第二趟 第三趟 第四趟 13.8 12.5 12.5 12.5 12.5 13.8 13.0 13.0 13.0 13.0 13.2 13.2 13.2 13.2 13.8 13.4 13.4 13.4 13.4 13.8 若采用选择排序算法对其进行从小到大排序，则第二趟的排序结果是
(A) 12.5 13.8 13.2 13.4 13.0 (B) 12.5 13.4 13.2 13.8 13.0 (C) 12.5 13.0 13.8 13.2 13.4 (D) 12.5 13.2 13.8 13.4 13.0
4、下面说法正确的是（a ）
A、算法+数据结构=程序 B、算法就是程序 C、数据结构就是程序 D、算法包括数据结构 5、数列1，4，7，10，13，??的递推公式为( d )。
(A) f(1)=1;f(n)=n+3 (B) f(1)=1;f(n)=n*2-1 (C) f(1)=1;f(n)=n*2+1 (D) f(1)=1;f(n)=f(n-1)+3
6、用选择排序法对数据7，6，3，9，2从大到小排序，共需经过多少次数据对调。a (A) 3 (B) 4 (C) 5 (D) 10
7、动态规划算法的基本要素为（c ）。 A、最优子结构性质与贪心选择性质 B、重叠子问题性质与贪心选择性质 C、最优子结构性质与重叠子问题性质 D.、预排序与递归调用
8、算法分析中，记号O表示（ b ），记号?表示（ a ），记号?表示（d ）。 A、渐进下界 B、渐进上界 C、非紧上界 D、紧渐进界 E、非紧下界 9、以下关于渐进记号的性质是正确的有：（ a） A、f(n)??(g(n)),g(n)??(h(n))?f(n)??(h(n))
B、f(n)?O(g(n)),g(n)?O(h(n))?h(n)?O(f(n)) C、O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D、f(n)?O(g(n))?g(n)?O(f(n))
10、下列算法中通常以自底向上的方式求解最优解的是（ b ）。 A、备忘录法
B、动态规划法
C、贪心法 D、回溯法
11、衡量一个算法好坏的标准是（ c ）。
A、运行速度快 B、占用空间少 C、时间复杂度低 D、代码段 12、实现棋盘覆盖算法利用的算法是（a ）。 A、分治法
B、动态规划法
C、贪心法
D、回溯法
13、下面关于NP问题说法正确的是（？ ）。 A、NP问题都是不可能解决的问题 B、P类问题包含在NP类问题中 C、NP完全问题是P类问题的子集 D、NP类问题包含在P类问题中
14、矩阵连乘问题的算法可由（ b ）设计实现。
A、分支界限算法 B、动态规划算法 C、贪心算法 15、（ d）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质
D、最优子结构性质
16、Strassen矩阵乘法是利用（ a ）实现的算法。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法 17、使用分治法求解不需要满足的条件是（ a）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并
D 原问题和子问题使用相同的方法解
18、解决一个问题通常有多种方法。若说一个算法“有效”是指(d )。
A、这个算法能在一定的时间和空间资源限制内将问题解决 B、这个算法能在人的反应时间内将问题解决 C、这个算法比其他已知算法都更快地将问题解决 D、A和C
19、下列不是动态规划算法基本步骤的是（ d ）。
A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 20、
二、 填空题（20分，每空2分） 1、 算法的性质包括输入、输出、确定性、能行性＿＿＿、有限性。 2、 动态规划算法的基本思想就将待求问题分解成若干个子问题、先求解子问题，然后
从这些子问题的解得到原问题的解。<最优解>
3、 设计动态规划算法的4个步骤： （1） 找出最优解的性质 ＿，并刻画其结构特征。 （2） ＿＿递归地定义最优值＿＿＿＿＿。 （3） ＿＿以自底向上的方式计算出最优值＿＿＿＿＿。 （4） 根据计算最优值得到的信息，＿＿构造最优解＿＿＿＿＿。
4、 最优二叉搜索树即是＿?＿＿的二叉搜索树。 5、 算法的复杂性是 算法效率 的度量，是评价算法优劣的重要依据。 6、 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这
些子问题互相 独立 且与原问题相同。
7、 计算机的资源最重要的是 时间 和空间 资源。因而，算法的复杂性有时间复杂性 和 空间复杂性 之分。
8、 算法复杂度依赖于三个方面：待求解问题的规模、算法的输入和算法本身。(如
何理解)
8、下面程序段的所需要的计算时间为 o(n2) 。 Int MaxSum(int n, int *a, int &besti, int &bestj) {
int sum=0;
for(int i=1;i<=n;i++){ int thissum=0;
for(int j=i;j<=n;j++){ This sum+=a[j]; if(thissum>sum) { sum=this sum; besti=i; bestj=j; } } }
return sum; }
? 10、程序是 算法 + 数据结构 用某种程序设计语言的具体实现。 11、算法是指解决问题的 方法 或 步骤的描述 。 12、从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归的 。
13、计算一个算法时间复杂度通常可以计算 循环次数 、 基本操作的频率 或计算步。
14、设菲波那契（Fibonacci）数列中Fn为第n个月时兔子的对数，则有递归方程
为 Fn=Fn(n-1)+Fn(n-2) (n>1时) Fn=1
三、简答题
1、在“神州号”程序中，我们只判断了飞船成功飞行的条件。当飞船速度继续加大时，飞船将达到第二宇宙、第三宇宙速度。。。。。。。（见下表）
试编写程序，输入不同的飞船速度，判断它的各种飞行状况。 飞船速度（ V） 单位（km/s） 7.91<=V<11.19 11.19<=V<16.67 V>16.67 飞行状况 飞船绕地球似做匀速圆周运动 飞船离开地球的控制 ,围绕太阳转 飞船挣脱太阳引力飞出太阳系 2、算法具有的5个属性
确定性、能行性、输入、输出、有穷性/有限性 3、 算法设计的质量指标
4、
一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，问到第 12 个月时，该饲养场共有兔子多少只？
5、
对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。
6、老板有一袋金块（共n块，n是2的幂（n>=2）），最优秀的雇员得到其中最重
的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重的金块。
? n≤2，识别出最重和最轻的金块，一次比较就足够了。
? n＞2，第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B
中最重和最轻的金块。设A中最重和最轻的金块分别为HA 与LA，以此类推，B中最重和最轻的金块分别为HB 和LB。第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。在第二步中，若n＞2，则递归地应用分而治之方法。
7、Tom很顽皮。一天，他把假币投到储钱罐里。之后，他担心爸爸揍它，想从
N个钱币里找出那个假币。他知道假币的重量比其他钱币轻，但不知道如何找到它，于是禁不住哭了。也许你能帮他。请描述一个通过使用天平找到假币的算法，并分析你算法的运行时间。
1任意取1枚硬币，与其他硬币进行比较，若发现轻者，这那枚为伪币。最多可能有15次比较。
2将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为伪币。最多可能有8次比较。
3:将硬币分为两组后一次比较可以将硬币的范围缩小到了原来的一半,这样充分地利用了只有1枚伪币的基本性质。
8、请用快速排序法升序排序下面实例，给出每一趟排序的结果。 ．．．．．．．．．．（3，20，5，9，2，30，25，18，16，3）
第一趟>>3，20，5，9，2，30，25，18，16，3 第二趟>>3 ,5, 9, 2 ,16 ,3,18, 20 ,30 ,25 第三趟>>2, 3, 3 ,5 ,9 ,16, 18 ,20 ,25 ,30