关注一下公众号呗,有课程链接,这个解析我会不断更新,但进度肯定慢,别催我
绪论
大$O,\Omega,\Theta$记号
1.$f(n)=O(g(n))$,当且仅当$g(n)=\Omega (f(n))$.（2010期中,判断）
| 答案:对 |
|
按照O符号定义,$f(n)=O(g(n))$,则存在$c>0,N>0$,当$n>N$时有$f(n)\lt cg(n)$成立,则令$d=\frac{1}{c}$则有$g(n)>df(n)$成立,即$g(n)=\Omega (f(n))$成立.
|
2.即便有$f(n) =O(g(n))$,也未必有$2^{f\left( n \right)}=O\left( 2^{g\left( n \right)} \right)$（2014期中,判断）
| 答案:对 |
例子:$f\left( n \right) =2n,g\left( n \right) =n$,有$f\left( n \right) =O\left( g\left( n \right) \right)$,但$2^{2n}\ne O\left( 2^n \right)$,即$2^{f\left( n \right)}\ne O\left( 2^{g\left( n \right)} \right) $,对于这类判断题一定不要想当然. |
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)$
| 答案:AD |
|
由题意可知:$\exists c_1$,$N_1 \gt 0$,当$n \gt N_1$时,有$f\left( n \right) \lt c_1n^2$.$\exists c_2$,$N_2 \gt 0$,当$n \gt N_2$时,有$g\left( n \right) \lt c_2n$.我们令$N_3=\max \left\{ N_1,N_2 \right\} $,$c_3=\max \left\{ c_1,c_2 \right\}$.
|
|
A选项:当$n \gt N_3$时,有$f\left( n \right) +g\left( n \right) \lt 2c_3n^2$.
|
|
B选项反例:$f(n)=n^2,g(n)=\sqrt{n}$.
|
|
C选项反例:$f(n)=\sqrt{n},g(n)=n$.
|
|
D选项:当$n \gt N_3$时,有$f\left( n \right) \times g\left( n \right) \lt c_1c_2n^3$.
|
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.不确定
| 答案:D |
|
因为只是有调用$g(n)$的指令,不代表实际调用了,可能在$if$语句里面调用的,如果$if$语句条件不满足则可能不调用.
|
时间复杂度的分析
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}$
| 答案解析 |
|---|
$(A)$如果我们令$m=2^n$,$S(m)=T(n)=T(2^m)$,则有$S(m)=2020·S\left(\frac{m}{2020}\right)+O(m)$,由主定理易知,$T(n)=S(m)=O(m\log m)=O(\log n\log\log n)$ |
| $(B)$由主定理易知,$T(n)=O(\sqrt[43]{n}\log n)$ |
递归
1.若每一递归实例本身仅需常数时间和空间,则（ ）函数的渐进时间复杂度等于渐进空间复杂度.（2014期中,不定项选择）
$~~$A.尾递归$~~~~$B.线性递归$~~~~$C.二分递归$~~~~$D.多分支递归
| 答案:AB |
|---|
尾递归和线性递归的递归深度都是$O(n)$,又因为每一递归实例本身仅需常数时间和空间,所以渐进时间复杂度等于渐进空间复杂度. |
图灵机
1.设图灵机在初始状态下,只有读写头所对单元格为'0',其余均为'#';此后,连续地执行increase()算法2014次.在此期间,读写头累计移动的次数(就相对误差率而言)最接近于（）（2014期中,不定项选择）
$~~$A.2000$~~~~$B.4000$~~~~$C.8000$~~~~$D.16000$~~~~$E.32000
| 答案:C |
|
容易算出,如果最低位是0,则移动2次,这类数在0到2013中一共有1007个,共移动2014次,最低的2位是01,则移动4次,这类数在1到2013中共有504个,共移动2016次,依次可以算出最低的3位是011的数共需要移动1512次,最低的4位是0111的数共需要移动1008次,最低的5位是01111的数共需要移动630次,最低的6位是011111的数共需要移动372次,最低的7位是0111111的数共需要移动224次,最低的8位是01111111的数共需要移动128次,最低的9位是011111111的数共需要移动72次,最低的10位是0111111111的数共需要移动40次,最低的11位是01111111111的数共需要移动22次,一共移动8038次,当然加到372的时候就应该能估计出来和8000最相近了.
|
2.无论是在图灵机模型还是模型中,整数加法都属于基本运算,时间成本均可视作常数.（2019期中,判断）
| 答案:错 |
|---|
因为图灵机的处理单元是每个二进制位本身,而且需要移动读写头,所以加法运算的时间成本不能视为$O(1)$,甚至执行increase()操作的最坏情况都是$\Omega(n)$的,其中$n$是整数的二进制的位数. |
向量
二分查找
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期中）
| 答案:$\frac {659}{128}$ |
|---|
容易算出查找秩为$i$的元素的查找长度为$L_0\sim L_{14}=\{5,4,6,3,6,5,7,2,6,5,7,4,7,6,8\}$,故平均成功查找长度为$\sum_{i=1}^{14} L_i P_i = \frac {659}{128}$ |
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$
| 答案:无答案 |
|---|
| 本题原打算考习题解析2-18结论,但是实际上习题解析2-18(b)已经被勘误过了,习题解析2-18对应的结论对于二分查找版本C不适用. |
4.我们知道,插值查找、二分查找、顺序查找分别适用于大、中、小规模的数据.当有序向量很长时,我们可以依次使用它们做接力式的查找.若在某系统中经测量确认,三种算法的时间复杂度常系数约为1280:64:1,试估算出分别应在查找范围缩小到多大时切换算法（忽略复杂度的低次项、算法切换过程的时间消耗等因素）（2019期中）
| 答案解析 |
|---|
即计算$n$大于多少时,$1280 \log \log n <64 \log n$,$n$大于多少时,$64\log n<n$,答案分别约为$2^{144}$和$590$,故当问题查找范围缩小到$2^{144}$时,改用二分查找.查找范围缩小到$590$时,改用顺序查找 |
fibonacci查找
1.对有序向量做Fibonacci查找,就最坏情况而言,成功查找所需的比较次数与失败查找相等.（2010期中,判断）
| 答案:对 |
|---|
最后和向量中的某个元素进行比较,确定查找成功需要比较两次,第一次比较e是否小于S[mi],第二次比较e是否大于S[mi],如果不小于也不大于,说明查找成功,如果大于(同时也是最坏情况下的失败查找的情况),说明查找失败,因此最坏情况下成功查找所需的比较次数与失败查找所需的比较次数相等. |
2.对长度为Fib(12) ‐ 1 = 143的有序向量做Fibonacci查找,比较操作的次数至多为:（ ）（2010期中,不定项选择）
$~~$A.12$~~~~$B.11$~~~~$C.10$~~~~$D.9
| 答案:B |
|---|
可以证明对长度为Fib(k)‐1的有序向量做Fibonacci查找,比较操作的次数至多为S(k) = k-1次,假设命题对长度为Fib(k-1)-1和长度为Fib(k-2)-1的有序向量成立,则对长度为Fib(k)‐1的有序向量来说,比较操作的次数至多为max{S(k-1)+1,S(k-2)+2}=k-1,又因为对于长度为Fib(3)‐1 = 1和Fib(4)‐1 = 2的有序向量来说结论成立,所以原命题成立. |
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}$
| 答案:B |
|---|
根据习题解析2-18结论,答案选B,但是要注意,这里习题解析已经勘误过了,此结论对于二分查找版本B和版本C并不适用. |
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期中）
| 答案:$\frac{25}{6}$和$4.12$ |
|---|
易知查找A[0]到A[6]的查找长度分别是5,4,3,5,2,5,4.八种失败的情况（比A[0]小,在A[0]和A[1]之间,A[1]和A[2]之间,...,比A[6]大）的查找长度分别是4,5,4,4,5,4,5,4.因此失败查找长度$L_{f a i l}=\frac{4+5+4+4+5+4 \times 7+5+4 \times 5}{18}=\frac{75}{18}=\frac{25}{6}$.总体的平均查找长度是$L_{\text {all }}=\frac{75+28}{25}=4.12$ |
列表
1.无论有序向量或有序列表,最坏情况下均可在$O(\log n)$时间内完成一次查找.（2010期中,判断）
| 答案:错 |
|---|
对于有序列表来说,找到中间的位置就需要$O(n)$的时间了,所以即便利用二分查找,最坏情况下也不能在$O(\log n)$时间内完成一次查找.（当然本题也可以归类到向量中） |
栈和队列
树和二叉树
搜索树
高级搜索树
散列
散列函数
1.相对于除余法,MAD法在（）方面有所改进.（2014期末,2016期末,不定项选择）
$~~$A.计算速度
$~~$B.高阶均匀性
$~~$C.不动点
$~~$D.满射性
$~~$E.以上皆非
| 答案:BC |
|---|
0的散列地址总是0,这是一个不动点;另外如果用除余法,那么连续关键码在散列表中的位置也是连续的,而用MAD法就会有"更高阶"的均匀性(邓书263页). |
2.若元素理想随机,则用除余法作为散列函数时,即使区间长度不是素数,也不会影响数据的均匀性.（2016期末,2017期末,判断）
| 答案:对 |
|---|
可以保证除余法散列函数得到的余数也是随机的,使得数据是均匀的. |
线性探测
1.将$n$个词条逐个插入一个容量为$M$,采用线性试探策略,初始为空的散列表,$n < M$,则无论它们的插入次序如何,最终的平均成功查找长度都必然一样.（2018期末,判断）
| 答案:对 |
|
假设前 $m-1$ 个词条 $k_1, k_2, \cdots, k_{m-1}$ 的插入次序不影响总的查找长度,也就是$S_{m-1}=\sum_{i=1}^{m-1}{L_i}$ 不变.现在要证明插入前 $m$ 个词条的次序不影响总的查找长度.
情况1:$k_m$ 和 $k_1 \sim k_{m-1}$ 没有冲突,那么 $k_m$ 无论作为第几个插入,其查找长度必然是1.总有$S_m=S_{m-1}+1$,即总的查找长度不变. 情况2:$k_m$ 和 $k_1 \sim k_{m-1}$ 中的词条有冲突,假设 $k_m$ 作为最后一个词条插入到散列表并且冲突了 $i$ 次,则 $L_m=i+1, S_m=S_{m-1}+i+1$,那么必然有 $k_{p_1}, k_{p_2}, \cdots, k_{p_i}$ 这 $i$ 个关键码的占用了 $r_1 \sim r_i$ 一共 $i$ 个位置,导致了插入 $k_m$ 时连续试探了 $i$ 次之后才找到空桶.如果 $k_m$ 不是最后一个插入,要么插入的最终的位置不变,此时 $S_m$仍然等于$S_{m-1}+i+1$.要么它的最终插入的位置只可能是 $r_1 \sim r_i$ 其中的一个 $r_j, j \in[1, i]$,那么原本最终插入的位置在 $r_j \sim r_i$ 的 $i-j-1$ 个元素查找长度都比原来多 1 ,而 $k_m$ 的查找长度比原来少 $i-j-1$.此时$S_m$ 仍然等于 $S_{m-1}+i+1$. 又$n=1$时,结论成立. 综上,命题得证. |
平方探测
1.设散列表H[]容量是M=7,采用除留余数法（H(key)=key%M）确定地址,采用单向平方探测法解决冲突.现从空表开始依次插入关键码{2010,7,4,0},试给出生成的散列表.（2010期末）
答案解析:2010,7,4插到1,0,4的位置,插入0时和7,2010,4连续发生冲突,最后插入9%7=2的位置 |
|||||||
|---|---|---|---|---|---|---|---|
| H[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| key | 7 | 2010 | 0 | 4 | |||
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
| 答案:CD |
|
这道题肯定不是按最新代码的逻辑来看的,否则插入操作是必然能够找到空桶然后成功插入的,然后在插入之后再看元素个数加上懒惰删除标记的个数的总和的二倍是不是大于表长,如果大于则扩容.所以这道题的逻辑应该是有变量在计数,如果插入操作试探了$\lceil \frac{M}{2} \rceil$次仍然找不到空桶,则扩容,从这个逻辑上来看应该选CD.所以散列这一章的往年的期中期末题得用历史的眼光看,不过近年的826真题没出现过这种逻辑和最新代码不符的情况.
|
3.采用单向平方策略的散列表,只要长度$M$不是素数,则每一组同义词在表中都不会超过$\lfloor \frac{M}{2} \rfloor $个.（2018期末,判断）
| 答案:错 |
|---|
反例:$\left\{ 0,1,2,3,\cdots \right\} ^2\%10=\left\{ 0,1,4,9,6,5 \right\}$,表长不是素数的话,$n^2\%M$可能的取值的个数可能大于$\lceil \frac{M}{2} \rceil$也可能小于$\lceil \frac{M}{2} \rceil$. |
双平方探测
1.我们知道,采取双平方试探策略时,应该将散列表长取作素数M=4k+3.尽管这样可以极大地减低查找链前M个位置发生冲突的概率,但仍不能杜绝.（2014期末,2016期末,判断）
| 答案:错 |
|
散列表长取作素数M=4k+3,采用双平方探测,查找链前M个位置必然不会发生冲突.还有另外一个结论,散列表长取作素数M=4k+1,查找链前M个位置必然会发生冲突.
|
2.todo(2020期末)
基数排序
1.radixSort的底层排序算法如果将桶排序改成quick排序,仍然正确.（2013期末,判断）
| 答案:错 |
|
quick排序是不稳定的,如果用不稳定的排序算法作为radixSort的底层排序算法,会导致radixSort排序算法出错,而不仅仅是稳不稳定的事情了,比如21和23两个数排序,按个位数排序时,结果是21,23.按十位数排序时,由于底层算法的不稳定性,这两个2可能交换位置,那么就变成23,21了,导致排序算法出错.
|
2.底层排序的稳定性保证了radixsort的正确性和稳定性.（2017期末判断）
| 答案:对 |
|
比如21和23两个数排序按个位数排序时,结果是21,23.如果底层算法的不稳定,在按十位排序时,这两个2可能交换位置,那么就变成23,21了,导致排序算法出错.底层算法的正确性不足以保证radixSort的正确性,需要底层算法是稳定的,才能保证radixSort的正确性和稳定性,具体证明可见邓老师PPT
|
3.只要底层的排序算法是正确且稳定的,则radixSort也必然是正确且稳定的（2018期末判断）
| 答案:对 |
|
比如21和23两个数排序按个位数排序时,结果是21,23.如果底层算法的不稳定,在按十位排序时,这两个2可能交换位置,那么就变成23,21了,导致排序算法出错.底层算法的正确性不能保证radixSort的正确性,需要底层算法是稳定的,才能保证radixSort的正确性和稳定性,具体证明可见邓老师PPT
|
跳转表
1.跳转表的期望高度为$O(\log n)$.（2013期末,判断）
| 答案:对 |
|
不要混淆跳转表的高度和塔的高度,跳转表的高度的期望是$\Theta(\log n)$,各塔的期望高度是$O(1)$,此问题也是高频考点之一.
|
2.在存在n个词条的跳转表中,各塔高度的期望为$\Theta(\log n)$.（2016期末,2018期末,判断）
| 答案:错 |
|
不要混淆跳转表的高度和塔的高度,跳转表的高度的期望是$\Theta(\log n)$,各塔的期望高度是$O(1)$,此问题也是高频考点之一.
|
3.跳转表若变成投掷骰子上面为六才上升一层,则纵向移动变大.（2013期末,判断）
| 答案: |
|---|
| todo |
4.将硬币换成理想的骰子,且约定投出六朝上时新塔才停止生长.于是对于同样存放n个元素的跳转表而言,（）的期望值将有所增长,但仍保持O(1).（2014期末,不定项选择）
$~~$A.查找过程中，在同一高度连续跳转的次数
$~~$B.查找过程中，由“向右”到“向下”转折的次数
$~~$C.查找过程中，沿同一座塔连续下行的层数
$~~$D.（在查找定位之后）为创建一座新塔所需的时间
| 答案: |
|---|
| todo |
其他
1.（）属于针对闭散列策略的冲突排解方法.（2014期末,不定项选择）
$~~$A.mutiple slots
$~~$B.linear probing
$~~$C.overflow area
$~~$D.separate chaining
$~~$E.quadratic probing
$~~$F.double hashing
| 答案:BEF |
|
多槽位（mutiple slots）,独立链（separate chaining）和公共溢出区（overflow area）是开散列策略,线性试探（linear probing）,平方试探（quadratic probing）和双散列（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期末）
| 答案:能覆盖所有桶单元,证明如下: |
第 $k$ 次试探的偏移量$d_k=\frac{k(k + 1)}{2}$,相当于首次试探时 $k = 0$.假设第 $a$ 次和第 $b$ 次冲突,$a,b \in[0, M)$,则有:
\[ \begin{aligned} & \frac{a(a + 1)}{2} \equiv \frac{b(b + 1)}{2}(\bmod M) \\ & \Longrightarrow \frac{a(a + 1)}{2}-\frac{b(b + 1)}{2} \equiv 0(\bmod M) \\ & \Longrightarrow a(a + 1)-b(b + 1) \equiv 0(\bmod 2 M) \\ & \Longrightarrow(a - b)(a + b + 1) \equiv 0(\bmod 2 M) \end{aligned} \] 注意到: $a + b + 1$,$a - b$ 必一奇一偶,但 $2 M = 2^{s + 1}$ 没有奇因子,矛盾.因此前 $M$ 次试探必然可以取遍整个散列表. |