一、基础知识部分
1. 算法的复杂性有时间复杂性和空间复杂性之分。
2. 算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。
3. 快速排序算法是基于分治策略的一种排序算法。
4. 矩阵连乘问题的算法可由动态规划设计实现。
5、算法是指解决问题的一种方法或一个过程。
6、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。
7、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
8、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
9. 贪心算法的基本要素是贪心选择质和最优子结构性质。
10. 动态规划算法的两个基本要素是最优子结构性质和重叠子问题性质。
11、合并排序算法是利用（A ）实现的算法
A、分治策略
B、动态规划法
C、贪心法
D、回溯法
12、下列不是动态规划算法基本步骤的是（ A ）。
A、找出最优解的性质
B、构造最优解
C、算出最优解
D、定义最优解
13．下列算法中通常以自底向上的方式求解最优解的是（ B ）。
A、备忘录法B动态规划法C、贪心法D回溯法
14. 备忘录方法是那种算法的变形。
（B ）
A、分治法B动态规划法C、贪心法D回溯法
15．最长公共子序列算法利用的算法是（ B ）。
A、分支界限法B动态规划法C贪心法D回溯法16．贪心算法与动态规划算法的主要区别是（ B ）。
A、最优子结构
B、贪心选择性质
C、构造最优解
D、定义最
优解
17. （D ）是贪心算法与动态规划算法的共同点。
A、重叠子问题
B、构造最优解
C、贪心选择性质D最优子结构性质
18. 矩阵连乘问题的算法可由（B ）设计实现。
A、分支界限算法 B 、动态规划算法C、贪心算法D、回溯算法19、使用分治法求解不需要满足的条件是（ A ）。
A 子问题必须是一样的
B 子问题不能够重复
C 子问题的解可以合并
D 原问题和子问题使用相同的方法解
20．下列是动态规划算法基本要素的是（ D ）。
A、定义最优解B构造最优解C、算出最优解D子问题重叠性质
二、分析解答部分
1 、堆的高度与元素个数之间的关系
2、散列表技术中碰撞的定义与解决方法是什么
3、平摊分析的方法有哪些？重点是势能法的应用。
例、对某个数据结构执行一个n 个操作的序列。
如果i 为2的整数次幂，则第i 个操作的代价为i ，否则为 1.请用势能分析来确定每次操作的平摊代价。
解：不妨设i 2j k，其中k和j均为非负整数，且j取满足等式最大的整数。
定义第i个操作D i的势能函数为 (DJ 2k，下面分析第i个操作D i的平摊代价。
当k0时，第i个操作D i的实际代价C i i，从而
(?C i [ (D i) (D i 1)]
i[0 2(2j 1 2j 1)]
i i
[2j(2 1) 2] i 2
当k0时，第i个操作D i的实际代价C i1，从而
C C i [ (
D i) (D i 1)]
1 [2k 2(k 1)]
3
所以第i个操作D i的平摊代价总为(1)。
4、贪心算法的应用，参考书上的0-1背包问题和部分背包问题的例子。
5、作图说明利用合并排序算法将输入数组A (3,7,12,32,5,20,16,28)按从小到大排序的执行过程。
&作图说明利用堆排序(HEAPSORT将数组A (2,8,17,4,11,14)从小到大排序的执行过程，注意包含建最大堆(BUILD-MAX-HEAP的执行过程。
7、用主方法求解递归式紧确的渐进界，比如
(1) T(n) 6T(》n; (2) T(n) 6T(f) n3; (3) T(n) 6T(》n4;
8、写出利用动态规划解矩阵链乘问题的最小代价的递归式，并由此给出维数序列为A (35,15,5,10,20)的最优加全括号的方案。
9、会写出利用动态规划解最长公共子序列(LCS问题的最大长度的递归式，并
由此确定 A (1, 0, 0, 1, 0, 1, 0, 1)和 B (0, 1, 0, 1, 1, 0, 1, 1, 0)
的最长公共子序列。
10、对某个数据结构执行一个n个操作的序列。
如果i为2的整数次幕，则第i个操作的代价为i，否则为1.请用聚集分析来确定每次操作的平摊代价。
11、猜测下列递归式的良好渐进界，并用代换法证明你的猜测：
(1). T(n) 4T(-) n 的解为(n2) ；(2). T(n) 2T( - ) n 的解为O(nlg n)。
2 2
12、给出红黑树的定义，并由此证明：(1)从根到叶子的最长的可能路径不多于最短
的可能路径的两倍长。
(2) 一棵有n个内节点的红黑树的高度至多为llg( n+1) 13、给出渐进记号©记号、Q记号和0记号的定义，并证明：对任意实常数a
和b,其中b>0,(n (n))
,提示：当n足够大时,
n a 2n。