[toc]
软件设计师笔记08_算法设计与分析_精简考点
科目一考试有4分左右。
知识点结构图 
基本概念
设计算法时，通常应考虑以下原则：首先说设计的算法必须是"正确的"，其次应有很好的"可读性"，还必须具有"健壮性"，最后应考虑所设计的算法具有"高效率与低存储量"。
一个算法还具有下列5个重要特性。即有穷性、确定性、可行性、输入、输出。
- 有穷性。一个算法必须总是在执行有穷步之后结束，且每步都可在有穷时间内完成。
- 确定性。算法中的每一条指令必须有确切的含义，理解时不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
- 可行性。一个算法是可行的，即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
- 输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
- 输出。一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。
一个“好”算法的要求
正确性、健壮性、高效性
复杂度
复杂度是指算法执行所需要的时间和空间资源的量。分为时间复杂度和空间复杂度。
如图是一些不同数量级的复杂度，复杂度由小到大排列。
时间复杂度
算法的时间复杂度分析主要是分析算法重复执行的次数，即算法从开始到结束所需要的执行次数作为算法的时间度量。
一般不必要精确计算出算法的时间复杂度，只需要大致计算出响应的数量级即可，例如O(1)、O(n)、O(n^2^)等。
空间复杂度
空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小。
分治法 贪心法 回溯法 动态规划法
判断此类题目，就看算法是否是每一步都取最优，并且整体题意没有透露出最终结果是最优的。
分治法：
分治法：将大问题分解为各个小问题，各个小问题相对独立，然后分开解决各个小问题。常见分治法：递归。
动态规划法（全局最优）
动态规划法：与分治法类似的思想，也是将大问题分解为各个小问题，然后分开解决各个小问题。但是此处的各个小问题是互相关联的，因此需要记录下各个小问题的解，然后从中找出最优解。
动态规划法与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的。贪心法（局部最优）
贪心法和动态规划法一样，贪心法也经常用于解决最优化问题。与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。
即贪心法中它所做的每一步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。一般可以快速得到相对满意的解，但得不到全局最优解。
回溯法
回溯法：可以系统地搜索一个问题的所有解或任一解。一般用于解决迷宫类的问题。
真题案例
已知算法A的运行时间函数为T(n)=8T(n/2)+n2，其中n表示问题的规模，则该算法的时间复杂度为（ ）。另已知算法B的运行时间函数为T(n)=XT(n/4)+n2，其中n表示问题的规模。对充分大的n，若要算法B比算法A快，则X的最大值为（ ）。
A 15 B 17 C 63 D 65
正确答案：C
解题思路：使用主定理来求解算法的时间复杂度。主方法适用于形如(T(n) = aT(n / b)+f(n))的式子。
第一问：求算法 A 的时间复杂度
对于算法A，其运行时间函数(T(n)=8T(n / 2)+n^{2}) ，因此这里的(a = 8)，(b = 2) ，(f(n)=n^{2}) 。
计算(\log_{b}a)：根据对数运算法则，(\log_{b}a=\log_{2}8 = 3) 。
比较(f(n))与(n^{\log_{b}a})：(n^{\log_{b}a}=n^{3}) ，(f(n)=n^{2}) ，根据主方法的第一种情况，时间复杂度(T(n)=\Theta(n^{\log_{b}a})=\Theta(n^{3})) ，所以第一问答案是 D。
第二问：求算法 B 中X的最大值
同样使用主方法分析算法 B：算法B的运行时间函数(T(n)=XT(n / 4)+n^{2}) ，其中(a = X)，(b = 4) ，(f(n)=n^{2}) ，(\log_{b}a=\log_{4}X) 。
若算法B和算法A效率一样，即算法B的时间复杂度也为(\Theta(n^{3})) ，根据主方法，当(\log_{4}X = 3) 时，可通过对数运算求解X，即(X = 4^{3}=64) 。
确定X的最大值：要使算法B比算法A快，那么算法B的时间复杂度要低于(\Theta(n^{3})) ，即(\log_{4}X<3) ，所以(X < 4^{3}=64) ，那么X的最大值为63 。
真题案例
本题可使用主定理（Master Theorem）来求解算法的时间复杂度。
主定理适用于形如(T(n)=aT(n / b)+f(n))（(a\geq1)，(b > 1)，(f(n))是渐近正函数 ）的递推式。
由主定理式可知 (a = 6)，(b = 5)，(f(n)=n) 。计算(\log_{b}a)，即(\log_{5}6) 。
比较(f(n))与(n^{\log_{b}a}) ，因此(T(n)=\Theta(n^{\log_{5}6})) 。
真题
算法
以下关于字符串的叙述中，正确的是（ 字符串的长度是指串中所含字符的个数 ）。
通过元素在存储空间中的相对位置来表示数据元素之间的逻辑关系，是（ 顺序存储 ）的特点。
某个算法的时间复杂度递归式T(n)=T(n-l)+n，其中n为问题的规模，则该算法的渐进时间复杂度为（ n^2 ），若问题的规模增加了16倍，则运行时间增加（ 256 ）倍。
在求解某问题时，经过分析发现该问题具有最优子结构性质，求解过程中子问题被重复求解，则采用（ 动态规划 ）算法设计策略;若定义问题的解空间，以深度优先的方式搜索解空间，则采用（ 回溯 ）算法设计策略。
线性表
对于线性表，相对于顺序存储，采用链表存储的缺点是（ 数据元素之间的关系需要占用存储空间，导致存储密度不高 ）。
以下关于线性表存储结构的叙述，正确的是（ 线性表采用顺序存储结构时，访问表中任意一个指定序号元素的时间复杂度为常量级 ）。
当函数调用执行时，在栈顶创建项目用来支持被调用函数执行的一段存储空间称为活动记录或栈帧，栈帧中不包括（ 全局变量 ）。
若一个栈初始为空，其输入序列是1，2，3，…，n-1，n，其输出序列的第一个元素为k(1≤k≤「n/2」)，则输出序列的最后一个元素是 （ 不确定的 ） 。
队列的特点是先进先出，若用循环单链表表示队列，则（ 入队列和出队列操作都不需要遍历链表 ）。
采用循环队列的优点是（ 入队和出队操作都不需要移动队列中的其他元素 ）。
矩阵
- （ 三元组顺序表和十字链表 ）是对稀疏矩阵进行压缩存储的方式。
- 对于一个n阶的对称矩阵A,将其下三角区域(含主对角线)的元素按行存储在一维数组S中,设元素
A[i][j]存放在S[K]中，且S[1]=A[0][0]，则k与i、j (i≤j)的对应关系是（ ）。
树
已知树T的度为4，且度为4的结点数为7个、度为3的结点数5个、度为2的结点数为8个、度为1的结点数为10个，那么T的叶子结点个数为（ 40 ）。(注：树中节点个数称为结点的度，结点的度中的最大值称为树的度。）
当二叉数中的结点数目确定时，（ 完全二叉树 ）的高度一定是最小的。
- 完全二叉树是让二叉树的每一层的结点都尽可能全满，除了最底层，此时树的高度一定是最小的。
二叉树的高度是指其层数， 空二叉树的高度为0，仅有根结点的二叉树高度为若某二叉树中共有1024个结点，则该二叉树的高度是整数区间（
[11, 1024]）中的任一值。具有3个结点的二叉树有5种，可推测出具有4个结点的二叉树有（ 14 ）种。
已知某二叉树的先序遍历序列为A B C D E F、中序遍历序列为B A D C F E，则可以确定该二叉树（ 高度为4（即结点分布在4层上） ）。
某二叉树的中序、先序遍历序列分别为{20,30,10,50,40}、{10,20,30,40,50}，则该二叉树的后序遍历序列为（ 30,20,50,40,10 ）。
设m和n是某二叉树上的两个结点，中序遍历时，n排在m之前的条件是（ m在n的右边 ）。
- 对于二叉树的中序遍历，是先遍历根结点的左子数，再访问根结点，最后遍历根结点的右子树。所以结点n排在结点m之前的条件是n在m的左边，也就是m在n的右边。、
设某二叉树采用二叉链表表示（即结点的两个指针分别指示左、右孩子）。当该二叉树包含k个节点时，其二叉链表节点中必有（ k+1 ）个空的孩子指针。
某二叉树的先序遍历序列为ABCDEF ，中序遍历序列为BADCFE ，则该二叉树的高度(即层数)为（ 4 ）。
若一棵二叉树的高度（即层数）为h，则该二叉树（ 最多有2h-1个结点 ）。
以下关于哈夫曼树的叙述，正确的是（ 哈夫曼树中叶子结点的权值越小则距离树根越远、叶子结点的权值越大则距离树根越近 ）。
具有3个结点的二叉树有（ 5 ）种形态。
设由三棵树构成的森林中，第一棵树、第二棵树和第三棵树的结点总数分别为n1、 n2和n3。将该森林转换为—棵二叉树，那么该二叉树的右子树包含_（ n2+n3 ）个结点。
一个高度为h的满二叉树的结点总数为2h-1，从根结点开始，自上而下、同层次结点从左至右，对结点按照顺序依次编号，即根结点编号为1，其左、右孩子结点编号分别为2和3，再下一层从左到右的编号为4，5，6，7，依此类推。那么，在一棵满二叉树中，对于编号为m和n的两个结点，若n=2m+1,则 （ n是m的右孩子 ）。
图
某图G的邻接表中共有奇数个表示边的表结点，则图G（ 是有向图 ）。
若无向图G有n个顶点e条边，则G采用邻接矩阵存储时，矩阵的大小为（ n2 ）。
对有向图G进行拓扑排序得到的拓扑序列中，顶点Vi在顶点Vj之前，则说明G中（ 一定不存在有向弧
<vj, vi>）。在一个有向图G的拓扑序列中，顶点Vi排列在Vj之前，说明图G中（ 可能存在vi到vj的路径，而不可能存在Vj到vi的路径 ）。
以下关于无向连通图G的叙述中，不正确的是（ G中任意两个顶点之间均有边存在 ）。
设一个包含n个顶点、e条弧的简单有向图采用邻接矩阵存储结构（即矩阵元素
A[i][j]等于1或0，分别表示顶点i与顶点j之间有弧或无弧）,则该矩阵的非零元素数目为（ e ）。某简单无向连通图G的顶点数为n，则图G最少和最多分别有（ n-1,n*(n-1)/2 ）条边。
算法
对长度为n的有序顺序进行折半查找(即二分查找)的过程可用一棵判定树表该判定树的形态符合（ 平衡二叉树 ）的特点。
在线性表L中进行二分查找，要求L（ 序存储，元素有序排列 ）。
对某有序概序表进行折率查找《二分查找》时，进行比较的关键字序列不可能是（ 90,85,61,77,42 ）
在55个互异元素构成的有序表
A[1..55]中进行折半查找（或二分查找，向下取整）。若需要找的元素等于A[19]，则在查找过程中参与比较的元素依次为（A[28]、A[14]、A[21]、A[17]）、A[19]。对于有序表(8,15, 19, 23, 26, 31, 40, 65, 91)，用二分法进行查找时，可能的关键字比较顺序为（ 26,40,65 ）。
以下关于哈希(Hash,散列)查找叙述中，正确的是（ 构造哈希函数时应尽量使关键字的所有组成部分都能起作用 ）。
对于一个初始无序的关键字序列，在下面的排序方法中，（ ②③④⑤ ）第一趟排序结束后，一定能将序列中的某个元素在最终有序序列中的位置确定下来。 ①直接插入排序②冒泡排序③简单选择排序④堆排序⑤快速排序⑥归并排序
归并排序算法在排序过程中，将待排序数组分为两个大小相同的子数组，分别对两个子数组采用归并排序算法进行排序,排好序的两个子数组采用时间复杂度为O(n)的过程合并为一个大数组。根据上述描述，归并排序算法采用了（ 分治 ）算法设计策略。归并排序算法的最好和最坏情况下的时间复杂度为（ ）。
下列排序算法中，占用辅助存储空间最多是（ 归并排序 ）。