清华大学计算机考研线下开卷机试考试须知
每年的这个机试考试须知都差不多的,这个仅供参考,各位考生请以当年的为准。线下开卷机试考试须知.pdf
清华大学计算机系本科数据结构期中期末题分类解析
826相关内容归档点这里关注一下公众号【新威考研】呗,有课程链接,这个解析我会不断更新,但进度肯定慢,别催我,另外如果你觉得解析有问题,可以联系我,我微信：xinweikaoyan001如果有公式显示不出来，就稍等一会，如果还是显示不出来，要么是你浏览器问题，要么是你网络的问题 function toggleAnswer(id, button) { var table = document.getElementById(id); // 切换表格显示状态 if (table.style.display === "table") { table.style.display = "none"; // 切换按钮文字为"查看答案与解析" button.innerHTML = "查看答案与解析"; } else { table.style.display = "table"; // 切换按钮文字为"隐藏答案与解析" button.innerHTML = "隐藏答案与解析"; } } 绪论大$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.有以下函数12345$\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)$的编号排序,并在其间加上“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）优先级队列串排序
变上限积分函数的等价无穷小代换要注意的问题
变上限积分函数的等价无穷小代换不能乱用，这里有些老师讲课的时候都没有注意到，变上限积分函数等价无穷小代换的前提条件。以下结论是错误的$x\rightarrow 0$时，$g(x) \sim h(x)$，且$\mathop{\rm lim}\limits_{x \to 0} {f(x)} = 0$,则有$$\int_0^{g(x)} f(t) \mathrm{d} t \sim \int_0^{h(x)} f(t) \mathrm{d} t$$一个“假”的反例有小伙伴认为，如果$$g(x)=x^2+x^3 \sin \frac{1}{x}, h(x)=x^2, f(x)=x$$可以得到$$ \lim _{x \rightarrow 0} \frac{\int_0^{g(x)} f(t) \mathrm{d} t}{\int_0^{h(x)} f(t) \mathrm{d} t}=\lim _{x \rightarrow 0} \frac{g(x)}{h(x)} \cdot \frac{g^{\prime}(x)}{h^{\prime}(x)}=\lim _{x \rightarrow 0} \frac{3 x^2 \sin \frac{1}{x}-x \cos \frac{1}{x}+2 x}{2 x} $$极限“不存在”就说这是一个反例。实际上这是一个“假”的反例，事实上$$ \lim _{x \rightarrow 0} \frac{\int_0^{g(x)-h(x)} f(t) \mathrm{d} t}{\int_0^{h(x)} f(t) \mathrm{d} t}=\lim _{x \rightarrow 0} \frac{\int_0^{x^3 \sin \frac{1}{x}} t \mathrm{~d} t}{\int_0^{x^2} t \mathrm{~d} t}=\lim _{x \rightarrow 0} \frac{\frac{1}{2} x^6 \sin ^2 \frac{1}{x}}{\frac{1}{2} x^4}=0 $$也就是说$$ \lim _{x \rightarrow 0} \frac{\int_0^{g(x)} f(t) \mathrm{d} t}{\int_0^{h(x)} f(t) \mathrm{d} t}=1 $$真正的反例$$ \begin{aligned} \lim _{x \rightarrow 0} \frac{\int_0^x \mathrm{e}^{-\frac{1}{t^2}} \mathrm{~d} t}{\int_0^{\sin x} \mathrm{e}^{-\frac{1}{t^2} \mathrm{~d} t}} & =\lim _{x \rightarrow 0} \frac{\mathrm{e}^{-\frac{1}{x^2}}}{\mathrm{e}^{-\frac{1}{\sin ^2 x} }\cdot \cos x} \\ & =\lim _{x \rightarrow 0} \mathrm{e}^{\frac{1}{\sin ^2 x}-\frac{1}{x^2}}=\mathrm{e}^{\mathop{\rm lim}\limits_{x \to 0} \frac{x^2-\sin ^2 x}{x^4}} \\ & =\mathrm{e}^{\frac{1}{3}} \neq 1 \end{aligned} $$这个被积函数是怎么想出来的呢？我们先看一个结论的证明。变上限积分函数的等价无穷小代换的结论和证明当$x\rightarrow 0$时，$g(x) \sim h(x)$，且$\mathop{\rm lim}\limits_{x \to 0} \frac{g^{\prime}(x)}{h^{\prime}(x)}=1$（这个条件给的很强，比如前面的“假”的反例就不满足，不过考研当中经常可以满足），且在$x=0$的某去心邻域内$g(x) \neq 0, h(x) \neq 0$，则有$$ \int_0^{g(x)} t^m \mathrm{~d} t \sim \int_0^{h(x)} t^m \mathrm{~d} t, m>0 $$其中$m>0$，证明：$$ \lim _{x \rightarrow 0} \frac{\int_0^{g(x)} t^m \mathrm{~d} t}{\int_0^{h(x)} t^m \mathrm{~d} t}=\lim _{x \rightarrow 0}\left[\frac{g(x)}{h(x)}\right]^m \frac{g^{\prime}(x)}{h^{\prime}(x)}=1 $$反例是怎么想到的呢？我们注意到证明的最后一步$\mathop{\rm lim}\limits_{x \to 0} \left[\frac{g(x)}{h(x)}\right]^m \frac{g^{\prime}(x)}{h^{\prime}(x)} = 1$这里的$m$是有限值，所以极限一定是1，那么如果是$1^{\infty}$的形式的话，这个极限就未必是1了，也就是说我们找的被积函数要比$x$的任意有限阶次幂高阶才有可能行，而$\mathop{\rm lim}\limits_{x \to 0} \frac{\mathrm{e}^{-\frac{1}{x^2}}}{x^n}=0$(不论$n$有多大)，因此分子$\mathrm{e}^{-\frac{1}{x^2}}$作为被积函数是可能是反例。总结变上限积分函数的等价无穷小代换是有前提的，不能“无脑”等价，尤其是在大题中如果出现抽象函数，更是要慎用变上限积分函数的等价无穷小代换。