11
《算法分析与设计》期末复习题
一、选择题
1. 算法必须具备输入、输出和（ D ）等4个特性。
A．可行性和安全性 B．确定性和易读性
C．有穷性和安全性 D．有穷性和确定性
2. 算法分析中，记号O表示（ B ），记号Ω表示（ A ）
A.渐进下界 B.渐进上界
C.非紧上界 D.紧渐进界
3. 假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并完成概算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题（ B ）解题方法：3*2^n*64=3*2^x
A．n+8 B．n+6
C．n+7 D．n+5
4. 设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)=1，T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（ C ）。
A．O(logN) B．O(N)
C．O(NlogN) D．O(N²logN)
5. 直接或间接调用自身的算法称为（ B ）。
A．贪心算法 B．递归算法
C．迭代算法 D．回溯法
6. Fibonacci数列中，第4个和第11个数分别是（ D ）。
A．5，89 B．3，89
C．5，144 D．3，144
1、如图所示的程序框图中，则第3个输出的数是( )
A．1 B. 32 C.2 D. 52
1、解析：前3个分别输出的数是1，32，2.故选C.
2．如图给出的是求201614121的值的一个程序框图，
其中判断框内应填入的条件是 （ ）
A .i>10? B. i<10?
C
.i>20? D .i<20?
2解析：通过列表,我们能清楚了解程序的每一步中的各个变量
是怎样变化的, 第一次:11,,42iSn,
第二次:112,,624iSn,…依此可知循环的条件是i>10？．选Ａ
第1题 第2题
3.(2007年高考山东卷)阅读右边的程序框图，若输入的n是100，则输出的变量S和T的值依次是（ ）
A．2550，2500
B．2550，2550 开始
021Sni，，
1SSn
2nn
1ii
结束 是 否
输出S 开始
12A
1N
12AA
1NN
4?N
结束 是 否 输出A C．2500，2500
D．2500，2550
3解析：依据框图可得
1009896...22550S，999795...12500T.选A.
二、填空题
4．（2008年高考山东卷）执行右边的程序框图，若p=0.8,则输出的n=________..
4解析:第一次循环后，10.82S，此时n=2；第二次循环后，110.824S，开始
00ST，
TTn
SSn
2?n
结束 是
否
输出ST、 输入n
1nn 1nn 此时n3；第三次循环后，1110.8248S，此时4n，输出，故填4.
5.如果执行右面的程序框图，那么输出的S
算法复习试题
一、名词解释：
1、算法：就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。
2、贪心算法：能够得到某种量度意义下的最优解的分级处理方法称为贪心算法。
3、分治法：分治法的求解思想就是把整个问题分成若干个小问题后分的治之
4、递归过程：一个递归过程的执行类似于多个子程序的嵌套调用，递归过程是自己调用自己本身代码。
递归算法的特点：思路清晰，算法的描述简洁且易理解。
5、集合：在研究某一类对象时，可把这类对象的整体称为集合。
6、生成树：设G=(V,E)是一个无向连通图。如果G的生成子图T=(V,E')是一棵树，则称T是G的一棵生成树。
7、算法具有以下5个属性：
有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口
可行性：就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。
8、迭代法：称辗转法，是一种不断用变量的旧值递推出新值的解决问题的方法。
9、贪婪法: 是一种不追求最优解，只希望得到较为满意解的方法。贪婪法不要回溯
10、动态规划：是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
11、分支限界法：是一种用于求解组合优化问题的排除非解的搜索算法。
12、树：树是一个或多个结点的有限集合。
12、二元树：它是结点的有限集合，它或者为空，或者由一个根和两棵树
（左子树和右子树）的不相交的二元树所组成。
13、二分检索树：T是一棵二元树，它或者为空，或者其每个结点含有一个可比 较大小的数据元素。
14、图：图是数据结构，一个图G是由称之为结点V和边E的两个集合组成的
1. The O-notation provides an asymptotic upper bound. The -notation provides an asymptotic
lower bound. The Θ-notation asymptotically a function form above and below.
O型符号提供一个渐近的上限。Θ符号提供一个渐近下界。 Θ-符号渐近函数形式的上方和下方。
2. To represent a heap as an array，the root of tree is A[1], and given the index i of a node, the
indices of its parent Parent(i) { return i/2; }，left child, Left(i) { return 2*i; }，right child,
right(i) { return 2*i + 1; }.
代表一个堆中的一个数组，树的根节点是A[1]，并且给出一个节点i，那么该节点的父节点是 左孩子
右孩子
3. Because the heap of n elements is a binary tree, the height of any node is at most (lg n).
因为n个元素的堆是一个二叉树，任意节点的树高最多是
4. In optimization problems , there can be many possible solutions. Each solution has a value, and
we wish to find a solution with the optimal (minimum or maximum) value. We
