关注一下公众号【新威考研】呗,有课程链接,这个解析我会不断更新,但进度肯定慢,别催我,另外如果你觉得解析有问题,可以联系我,我微信：xinweikaoyan001
绪论
大$O,\Omega,\Theta$记号
1.$f(n)=O(g(n))$,当且仅当$g(n)=\Omega (f(n))$.（2010期中,判断）
2.即便有$f(n) =O(g(n))$,也未必有$2^{f\left( n \right)}=O\left( 2^{g\left( n \right)} \right)$（2014期中,判断）
3.若$f(n)=O\left(n^2\right)$且$g(n)=O(n)$,则以下结论正确的是：( )（2010期中,不定项选择）
$~~$A.$f(n)+g(n)=O\left(n^2\right)$
$~~$B.$\frac{f\left( n \right)}{g\left( n \right)}=O\left( n \right)$
$~~$C.$g(n)=O(f(n))$
$~~$D.$f(n)\times g(n)=O\left(n^3\right)$
4.算法$g(n)$的复杂度为$\Theta(n)$.若算法$f(n)$中有5条调用$g(n)$的指令,则$f(n)$的复杂度为（ ）（2010期中,不定项选择）
$~~$A.$\Theta(n)~~~~$B.$O(n)~~~~$C.$\Omega \left( n \right)~~~~$D.不确定
时间复杂度的分析
1.给出函数F(n)复杂度的紧界（假定int字长无限,移位属基本操作,且递归不会溢出）（2010期中）
//第(1)题
void F(int n) //O( )
{ for (int i = 1,r = 1; i < n; i <<= r,r <<= 1); }
//第(2)题
void F(int n) //O( )
{ for (int i = 0, j = 0; i < n; i += j, j++); }
//第(3)题
void F(int n) //O( )
{ for (int i = 1; i < n; i = 1 << i); }
//第(4)题
int F(int n) //O( )
{ return (n < 4) ? n : F(n >> 1) + F(n >> 2); }
//第(5)题
int F(int n) //O( )
{ return (n == 0) ? 1 : G(2, F(n ‐ 1)); }
int G(int n, int m)
{ return (m == 0) ? 0 : n + G(n,m ‐ 1); }
//第(6)题
int F(int n) //O( )
{ return G(G(n ‐ 1)); }
int G(int n)
{ return (n == 0) ? 0 : G(n ‐ 1) + 2 * n ‐ 1; }
//第(7)题
void F(int n) { //O( )
for (int i = 1; i < n; i++)
for (int j = 0; j < n; j += i);
}
//第(8)题
void F(int n) { //expected‐O( )
for (int i = n; 0 < i; i‐‐)
if (0 == rand() % i)
for (int j = 0; j < n; j++);
} | 答案解析 |
|---|
第(1)题:$\log\log n$ 每次迭代有$i=i\cdot 2^r,r=2r$,第$k$次迭代之后有$i=2^{2^0+2^1+2^2+\cdots +2^{k-1}}=2^{2^k-1}$,故$T(n) =O(\log\log n)$ |
第(2)题:$\sqrt{n}$ 每次迭代有$i=i+j,j=j+1$,第$k$次迭代有$i=0+1+2+\cdots k-1=\frac{(k-1)k}{2}$,故$T(n) =O(\sqrt{n})$ |
第(3)题:$\log^* n$ 每次迭代有$i=2^i$,第$k$次迭代有$i_k=2^{i_{k-1}}$,故$T(n) =O(\log^* n)$ |
第(4)题:$n^{\log _2\frac{\sqrt{5}+1}{2}}$ 有递推方程$T\left( n \right) =T\left( \frac{n}{2} \right) +T\left( \frac{n}{4} \right) +O\left( 1 \right)$,用Akra-Bazzi Theorem,问题转化为求$p$,使得$\left( \frac{1}{2} \right) ^p+\left( \frac{1}{4} \right) ^p=1$,求得$p=\log _2\frac{\sqrt{5}+1}{2}$,由Akra-Bazzi Theorem,可知$T(n)=O\left(n^{\log _2\frac{\sqrt{5}+1}{2}}\right)$ |
第(5)题:$2^n$ 用$S(m)$表示$G(n,m)$的时间复杂度,易知$S(m)=O(m)$,并且有递推方程$T(n)=T(n-1)+S(2^{n-1})+O(1)$,可得$T(n)=O(2^n)$ |
第(6)题:$n^2$ 用$S(n)$表示$G(n)$的时间复杂度,易知$G(n)$是线性递归的,所以$S(n)=O(n)$,有递推方程$T(n)=S(n-1)+S((n-1)^2)+O(1)$,可得$T(n)=O(n^2)$ |
第(7)题:$n \log n$ 迭代的总次数约等于$\frac{n}{1}+\frac{n}{2}+\cdots +\frac{n}{n-1}=n\left( 1+\frac{1}{2}+\cdots +\frac{1}{n-1} \right)$,故$T(n)=O(n \log n)$ |
第(8)题:$n \log n$ 易知$T(n)=\mathrm{expected}-O(n \log n)$ |
2.有以下函数
| 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|
| $\prod_{k=1}^n 2^k$ | $n^{\Sigma_{k=1}^n \frac{1}{k}}$ | $\log \left(\sum_{k=1}^n k^k\right)$ | $\sum_{k=1}^n \frac{1}{k^2}$ | $\sum_{k=1}^n k$ |
试以渐进增长速度为序,将以上各函数$f(n)$的编号排序,并在其间加上“<”或“=”（2019期中）
| 答案:$4<3<5<2<1$ |
|---|
| (1)$\prod_{k=1}^n{2^k}=2^{\frac{n\left( n+1 \right)}{2}}=\Theta \left( 2^{\frac{n^2}{2}} \right)$ |
| (2)$n^{\sum_{k=1}^n{\frac{1}{k}}}=\Theta \left( n^{\ln n+\gamma} \right)$ |
| (3)$\log \left( \sum_{k=1}^n{k^k} \right) =\Theta \left( n\log n \right)$ |
| (4)$\sum_{k=1}^n{\frac{1}{k^2}}=\Theta \left( 1 \right)$ |
| (5)$\sum_{k=1}^n{k}=\Theta \left( n^2 \right)$ |
3.给出$T(n)$的解析式,并说明理由（2020期末）
$(A)T(n)= \begin{cases}O(1) & (n \leq 1) \\ 2020 \cdot T\left(n^{\frac{1}{2020}}\right)+O(\log n) & (n \geq 2)\end{cases}$
$(B)T(n)= \begin{cases}O(1) & (n \leq 1) \\ 2^{47} \cdot T\left(\frac{n}{2^{2021}} \right)+O(\sqrt[43]{n}) & (n \geq 2)\end{cases}$
递归
1.若每一递归实例本身仅需常数时间和空间,则（ ）函数的渐进时间复杂度等于渐进空间复杂度.（2014期中,不定项选择）
$~~$A.尾递归$~~~~$B.线性递归$~~~~$C.二分递归$~~~~$D.多分支递归
图灵机
1.设图灵机在初始状态下,只有读写头所对单元格为'0',其余均为'#';此后,连续地执行increase()算法2014次.在此期间,读写头累计移动的次数(就相对误差率而言)最接近于（）（2014期中,不定项选择）
$~~$A.2000$~~~~$B.4000$~~~~$C.8000$~~~~$D.16000$~~~~$E.32000
2.无论是在图灵机模型还是模型中,整数加法都属于基本运算,时间成本均可视作常数.（2019期中,判断）
向量
二分查找
1.对于同一有序向量,每次折半查找绝不会慢于顺序查找.（2010期中,判断）
2.现有长度为15的有序向量A[0..14],各元素被成功查找的概率如下:
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $P_i(\sum = 1)$ | $\frac{1}{128}$ | $\frac{1}{128}$ | $\frac{1}{32}$ | $\frac{1}{8}$ | $\frac{1}{8}$ | $\frac{1}{32}$ | $\frac{1}{16}$ | $\frac{1}{16}$ | $\frac{1}{128}$ | $\frac{1}{64}$ | $\frac{1}{16}$ | $\frac{1}{4}$ | $\frac{3}{16}$ | $\frac{1}{128}$ | $\frac{1}{64}$ |
若采用二分查找算法,试计算该结构的平均成功查找长度.（2010期中）
3.使用binsearch算法版本C在有序向量{ 1, 3, 5, ..., 2013 }中查找,目标为独立均匀分布于[0, 2014]内的整数.若平均失败查找长度为F,则平均成功查找长度S应为（ ）（2014期中,不定项选择）
$~~$A.$\frac{1008F}{1007} + 1$
$~~$B.$\frac{1008F}{1007} - 1$
$~~$C.$\frac{1008(F-1)}{1007} + 1$
$~~$D.$\frac{1008(F+1)}{1007} - 1$
4.我们知道,插值查找、二分查找、顺序查找分别适用于大、中、小规模的数据.当有序向量很长时,我们可以依次使用它们做接力式的查找.若在某系统中经测量确认,三种算法的时间复杂度常系数约为1280:64:1,试估算出分别应在查找范围缩小到多大时切换算法（忽略复杂度的低次项、算法切换过程的时间消耗等因素）（2019期中）
fibonacci查找
1.对有序向量做Fibonacci查找,就最坏情况而言,成功查找所需的比较次数与失败查找相等.（2010期中,判断）
2.对长度为Fib(12) ‐ 1 = 143的有序向量做Fibonacci查找,比较操作的次数至多为:（ ）（2010期中,不定项选择）
$~~$A.12$~~~~$B.11$~~~~$C.10$~~~~$D.9
3.对长度为n = Fib(k) ‐ 1的有序向量做Fibonacci查找.若各元素的数值等概率独立均匀分布,且平均成功查找长度为L,则平均失败查找长度为:（ ）（2010期中,不定项选择）
$~~$A.$\frac{n(L-1)}{n-1}~~~~$B.$\frac{n(L+1)}{n+1}~~~~$C.$\frac{L(n-1)}{n}~~~~$D.$\frac{L(n+1)}{n}$
4.设整数e独立且均匀地取自[0, 25),现通过调用fibSearch( A, e, 0, 7 ),对如下整型向量A[]做查找:
| k | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| A[k] | 1 | 3 | 5 | 7 | 9 | 17 | 19 |
试分别计算其在失败情况下的平均查找长度,以及总体的平均查找长度.（2014期中）
列表
1.无论有序向量或有序列表,最坏情况下均可在$O(\log n)$时间内完成一次查找.（2010期中,判断）
栈和队列
树和二叉树
搜索树
高级搜索树
散列
散列函数
1.相对于除余法,MAD法在（）方面有所改进.（2014期末,2016期末,不定项选择）
$~~$A.计算速度
$~~$B.高阶均匀性
$~~$C.不动点
$~~$D.满射性
$~~$E.以上皆非
2.若元素理想随机,则用除余法作为散列函数时,即使区间长度不是素数,也不会影响数据的均匀性.（2016期末,2017期末,判断）
线性探测
1.将$n$个词条逐个插入一个容量为$M$,采用线性试探策略,初始为空的散列表,$n < M$,则无论它们的插入次序如何,最终的平均成功查找长度都必然一样.（2018期末,判断）
平方探测
1.设散列表H[]容量是M=7,采用除留余数法（H(key)=key%M）确定地址,采用单向平方探测法解决冲突.现从空表开始依次插入关键码{2010,7,4,0},试给出生成的散列表.（2010期末）
2.给定M=17的散列表,给定了基本策略:除余法、单向平方试探、懒情删除,依次将2,19,36,53,70,1481,104这7个数 put 进去,然后执行 remove(1481),最后 2个操作是把 17和15这两个数put进去.
$~~$(1)写出每次操作之后的散列表状态.
$~~$(2)如果在上面操作之后查询1481,问将会出现什么情况？为什么？
$~~$(3)在不改变以上基本策略的基础上,给出两种方案解决上述问题.（2012期末）
| Rank | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Put(2) | |||||||||||||||||
| Put(19) | |||||||||||||||||
| Put(36) | |||||||||||||||||
| Put(53) | |||||||||||||||||
| Put(70) | |||||||||||||||||
| Put(1481) | |||||||||||||||||
| Put(104) | |||||||||||||||||
| Remove(1481) | |||||||||||||||||
| Put(17) | |||||||||||||||||
| Put(15) |
| (1)答案:每次操作之后的散列表状态如下,其中x表示懒惰删除标记 | |||||||||||||||||
| Rank | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Put(2) | 2 | ||||||||||||||||
| Put(19) | 2 | 19 | |||||||||||||||
| Put(36) | 2 | 19 | 36 | ||||||||||||||
| Put(53) | 2 | 19 | 36 | 53 | |||||||||||||
| Put(70) | 70 | 2 | 19 | 36 | 53 | ||||||||||||
| Put(1481) | 70 | 2 | 19 | 36 | 1481 | 53 | |||||||||||
| Put(104) | 70 | 2 | 19 | 104 | 36 | 1481 | 53 | ||||||||||
| Remove(1481) | 70 | 2 | 19 | 104 | 36 | x | 53 | ||||||||||
| Put(17) | 17 | 70 | 2 | 19 | 104 | 36 | x | 53 | |||||||||
| Put(15) | 17 | 70 | 2 | 19 | 104 | 36 | x | 53 | 15 | ||||||||
| (2)答案解析 |
|
如果在上面操作之后查询1481,会一直试探查找,一直循环停不下来,因为会不断试探的位置都是目前已经被占用了的位置.
|
| (3)答案解析 |
|
方案一:如果散列表中的元素和懒惰删除标记的总数超过散列表长的一半,则进行重散列操作.（实际上本题有时代的局限性,因为在当年的书上和PPT上的代码还是元素个数超过散列表长的一半才重散列,目前最新的代码已经改成元素和懒惰删除标记的总数超过散列表长的一半就进行重散列了）
方案二:用变量记录连续试探的次数,如果试探次数超过散列表长的一半并且测探的桶要么不是要找的元素要么有懒惰删除标记,则停止试探并宣布查找失败. |
2.长为2017的哈希表,使用单向平方试探,若在某次插入时无法找到空桶而必须扩容,此时哈希表中可能的数据个数有（）（不考虑正在插入的元素）（2017期末,不定项选择）
$~~$A.1005$~~~~$B.1008$~~~~$C.1013$~~~~$D.1018
3.采用单向平方策略的散列表,只要长度$M$不是素数,则每一组同义词在表中都不会超过$\lfloor \frac{M}{2} \rfloor $个.（2018期末,判断）
双平方探测
1.我们知道,采取双平方试探策略时,应该将散列表长取作素数M=4k+3.尽管这样可以极大地减低查找链前M个位置发生冲突的概率,但仍不能杜绝.（2014期末,2016期末,判断）
2.若采用"双向平方试探"策略的散列表长度取作$M=2021$,则关键码0 及其同义词所对应的试探链可记作:
$$
\left\{ a_0,a_1,a_2,\cdots \right\} =\left\{ 0,1,4,\cdots \right\}
$$
$$
\left\{ b_0,b_1,b_2,\cdots \right\} =\left\{ 0,2020,2017,\cdots \right\}
$$
试问:$\left\{a_i \mid i=0,1,2,\ldots\right\} \cap\left\{b_j \mid j=0,1,2, \ldots\right\}$ 除0以外,还包含哪些试探位置？为什么？（2020期末）
基数排序
1.radixSort的底层排序算法如果将桶排序改成quick排序,仍然正确.（2013期末,判断）
2.底层排序的稳定性保证了radixsort的正确性和稳定性.（2017期末判断）
3.只要底层的排序算法是正确且稳定的,则radixSort也必然是正确且稳定的（2018期末判断）
跳转表
1.跳转表的期望高度为$O(\log n)$.（2013期末,判断）
2.在存在n个词条的跳转表中,各塔高度的期望为$\Theta(\log n)$.（2016期末,2018期末,判断）
3.跳转表若变成投掷骰子上面为六才上升一层,则纵向移动变大.（2013期末,判断）
4.将硬币换成理想的骰子,且约定投出六朝上时新塔才停止生长.于是对于同样存放n个元素的跳转表而言,（）的期望值将有所增长,但仍保持O(1).（2014期末,不定项选择）
$~~$A.查找过程中,在同一高度连续跳转的次数
$~~$B.查找过程中,由“向右”到“向下”转折的次数
$~~$C.查找过程中,沿同一座塔连续下行的层数
$~~$D.（在查找定位之后）为创建一座新塔所需的时间
其他
1.（）属于针对闭散列策略的冲突排解方法.（2014期末,不定项选择）
$~~$A.mutiple slots
$~~$B.linear probing
$~~$C.overflow area
$~~$D.separate chaining
$~~$E.quadratic probing
$~~$F.double hashing
2.某散列表 $\mathcal{H}\left[0, M=2^s\right.$)采用封闭散列策略（初始令 $c=d=0$）:对于任何$key$,首先试探 $\mathcal{H}[key ~ \% ~ M]$ ;以下,只要冲突,就令$c \leftarrow c+1$ 再$d \leftarrow d+c$,并继而试探$\mathcal{H}[(k e y+d) \% M]$.以$M=2^4=16$为例,关键码$key=27$的前五个试探位置依次是:11,12,14,1,5.但如同对于平方试探策略,我们首先需要确认,这种试探序列是否总能覆盖所有桶单元.若是,请给出证明;否则,试举一（$s$ 和 $key$ 组合的）反例.（2016期末,2018期末）
图
BFS,DFS,PFS
1.某有向图的邻接矩阵如下,现从顶点1出发做DFS遍历,遇多顶点歧义时编号小者优先.试在右侧标出各边的分类结果（树边T,前向边F,后向边B,跨边C）（2010期末）
（todo,2012年期末也有一道类似的题目）2.给了一个7节点的有向图,节点标号为1∼7,指定当存在歧义性的时候优先考虑标号小的节点.一共有多少条树边,跨边,前向边和后向边？（2012期末）
(todo对应的邻接矩阵有待给出)3.BFS,DFS的复杂度可能不是O(N+E)（2013期末,判断）
| 答案:对 |
|
这个和用什么存储结构有关,如果用邻接表的话,确实是$O(N+E)$如果采用邻接矩阵,则是$O(N^2)$
|
4.PFS每次迭代可能多次调用priorUpdater(),总复杂度O(n)（2013期末,2016期末,2018期末,判断）
| 答案:错 |
|
PFS每次迭代可能多次调用priorUpdater(),总复杂度O(e),2016和2018期末题把2013年的复杂度O(n)改成了O(e),本质上讲就是同一道题,这里就不分开做解析了.
|
5.有向图经DFS后若共有k条边被标记为backward，则它应恰有k个环路（2013期末,2018期末,判断）
| 答案:错 |
|
比如V={A,B,C,D},E={A—>B,B—>D,A—>C,C—>D,D—>A},以A为起点做DFS,仅有一条backward,但是图有两个环,一个A—>B—>D—>A一个A—>C—>D—>A
|
6.我们知道,因同一顶点的邻居被枚举的次序不同,同一有向图G所对应的DFS森林未必唯一.然而只要起始于G中某顶点s的某次DFS所生成的是一棵树,则起始于s的任何一次DFS都将生成一棵树.（2014期末,判断）
| 答案:对 |
|
设图G中某次以顶点s为起点的DFS生成了一棵树T,这表明T包含了s的所有可达顶点.由于DFS的特性,无论访问邻居的顺序如何,从s出发的DFS必定访问所有s可达的顶点（否则与T的存在矛盾）.因此,任何从s开始的DFS都会覆盖全部s可达的顶点,且这些顶点必然通过DFS的递归访问被连接成以s为根的单一树（每个顶点仅通过一条路径被首次访问,确保树的结构）.因此,起始于s的任何DFS均生成一棵树.
|
7.设在有向图G中,存在一条自顶点v通往u的路径.于是,若在某次DFS中有“dTime[v]$ \lt $dTime[u]”,则在这次DFS所生成的DFS森林中,v必是u的祖先（2014期末,判断,2016期末,简答）
| 答案:错 |
比如V={v,s,u},E={s—>v,v—>s,s—>u}.以s开始做DFS,先找v的情况下,s—>v和s—>u都是树边,在DFS森林中,v不是u的祖先,但是存在v通往u的路径,v—>s—>u,2016年简答题和这个判断题没有本质的区别,不再单独做解析. |
8.在无向连通图G中选定一个顶点s,并将各顶点v到s的距离记作dist(v)（特别地,dist(s) = 0）.于是在G.BFS(s)过程中,若辅助队列为Q,则“dist(Q.front())+1 $\geq $ dist(Q.rear())”始终成立.（2014期末,判断）
| 答案:对 |
PPT中讲过的结论,只有第k代的节点出队之后才会把第k+1代的节点拉进队列,所以队列中的节点的代差最多差一代.
|
9.有向图的DFS不仅起点任意,而且每一步迭代往往都会有多个顶点可供选择,故所生成的DFS森林并不唯一确定,且其中所含（）的数量也可能不同.（2014期末,不定项选择）
$~~$A.树边
$~~$B.前向边
$~~$C.后向边
$~~$D.跨越边
$~~$E.以上皆非
| 答案:ABCD |
ABD选项的例子:V={A,B,C},E={A—>B,B—>C,A—>C},如果遍历顺序是ABC,则有2条树边,1条前向边,0条跨越边;如果是遍历顺序是CAB,则有1条树边,0条前向边,2条跨越边.
C选项的例子:V={A,B,C},E={A—>B,B—>C,C—>B,C—>A},如果遍历顺序是ABC,则C—>B,C—>A都是后向边,如果遍历顺序是CBA,则只有B—>C是后向边. |
10.对于同一无向图,起始于顶点s的DFS尽管可能得到结构不同的DFS树,但s在树中的度数必然固定.（2018期末,判断）
| 答案:对 |
todo |
11.在图DFS算法中的default分支，将dTime(v)$\lt$dTime(u)改为dTime(v)$\lt$fTime(u)同样可行（2018期末,判断）
| 答案:对 |
todo |
12.若用完全二叉堆来实现,则各顶点在出堆之前,深度只可能逐步减少（或保持）而不致增加.（2018期末,判断）
| 答案:对 |
todo |
最小生成树,最短路径,双连通分量
1.某无向网络及其邻接矩阵的上三角部分如下,现从顶点A出发采用Prim算法构造最小生成树,试在下三角区域标出树边及其被选用的次序.遇多边歧义时,按边端点合成数的字典序小者优先.（2010期末）
（todo）2.对于正权值有向图,如果把所有的边权都平方之后,Dijkstra算法得到的最短路径树不变（2012期末,判断）
| 答案:错 |
比如图1为$V=\{A, B, C\}, E=\{A B=2, B C=3, A C=4\}$把对应的边的权值都平方之后,对应的图2为$V_1=\{A_1, B_1, C_1\}, E_1=\{A_1 B_1=4, B_1C_1=9, A_1 C_1=16\}$
|
3.如果把朋友圈视为一无向图,那么即使A君看不到你给B点的赞,你们仍可能属于同一个双联通分量.（2016期末）
（todo）