第003讲：算法的时间复杂度 | 历年考研真题及参考答案

小甲鱼

第003讲：算法的时间复杂度 | 历年考研真题及参考答案

s%qYt
-6e8C+^=z:AM7?0G>`$%bm RkT4
1. 下列程序段的时间复杂度是（     ）【全国联考2022年】a#!<13X
C.G<ZknqUi9}o ;`L+MHX0I1p8urJ

int sum = 0;
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < i; j++)
        sum++;

A. $O(\log_2 n)$  Powered by https://fishc.com.cn
^8?NDRlkXiA+j7W-U~=tK,zT)JfI
B. $O(n)$  来自：https://fishc.com.cn
^*}46tiwo9F?rPVc:7&RZ~aCMB
C. $O(n\log_2 n)$  Powered by https://fishc.com.cn
h.5v*d$2V+?S=p3ya^f>
D. $O(n^2)$版权属于：https://fishc.com.cn
'.PQ7wt_LRr"EJAKl>~6HzbW
&^RKCuDmE }gh~M;+o`L
2. 设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是（     ）【全国联考2019年】l!c3syL}R|
Tj.fz&}U9GPF2-6m?0'V>43bSt+aD1

x = 0;
while (n >= (x + 1) * (x + 1))
    x = x + 1;

A. $O(\log_2 n)$  版权属于：https://fishc.com.cn
TpcMLJQ?YmUt2dkegs0+u
B. $O(n^{1/2})$  来自：https://fishc.com.cn
Y ^o4j*J9|Ks582$(lf#&
C. $O(n)$  Powered by https://fishc.com.cn
~tYL3v|I{U7wa;KD-cx5
D. $O(n^2)$版权属于：https://fishc.com.cn
Z:15KLyp*;VUkxfqD$aB
!'{8PF*TC$2aG%fxeY#40
3. 下列函数的时间复杂度是（     ）【全国联考2017年】N#dEY<
N>T{B=eV}<3wKI5:&7mO8bqkDnRg6A

int func(int n) {
    int i = 0, sum = 0;
    while (sum < n)
        sum += ++i;
    return i;
}

A. $O(\log_2 n)$  版权属于：https://fishc.com.cn
:QH^.3<W#MFR_pao28g{6)9
B. $O(n^{1/2})$  Powered by https://fishc.com.cn
J<^KVI:j4>;%o)N_vrPt1xScE
C. $O(n)$  来自：https://fishc.com.cn
f6|q_=mM1zvR`i0$JA:U2B^4~ToQ W
D. $O(n \log_2 n)$Powered by https://fishc.com.cn
Qz+U~:r}.nb#T$gdZe*x
^4r OHL|}(h$a:NMTG6zv
4. 下列程序段的时间复杂度是（     ）【全国联考2014年】0d~vE%'J
{3f|Avk'6Wr9`a8(O4PI"FtX)%jn+

count = 0;
for (k = 1; k <= n; k *= 2)
   for (j = 1; j <= n; j++)
       count++; 

A. $O(\log_2 n)$  来自：https://fishc.com.cn
KRv^taC{qz(5f<J8*jAuU>#}e7Ykb
B. $O(n)$来自：https://fishc.com.cn
ru!~.{qiGc=SPR'EB_y$02O:
C. $O(n \log_2 n)$Powered by https://fishc.com.cn
4LHGbs$jAut3TiR+JwhnW6~gfMry
D. $O(n^2)$Powered by https://fishc.com.cn
~IEY-WzPxgr5&87JNQ?:;
U*:3_ZE"d{b-iVAs(p;})c
5. 已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是（     ）【全国联考2013年】NnsMcBrkIm
4a":Noi3dj*OEgF9<s+Q;b
A. $O(n)$ 版权属于：https://fishc.com.cn
Ug0K|>#*BNJ!mWdrT^u.
B. $O(mn)$来自：https://fishc.com.cn
!%5o3 b6HjvYCdn<re1t
C. $O(min(m, n))$Powered by https://fishc.com.cn
W_$7cDnk1LbfKS8eABdR&hG^#?jt`
D. $O(max(m, n))$Powered by https://fishc.com.cn
oz$4J&GH 5;{:3rfy?09DRs|6XA
{<nEDHQK^V5b"*Pa_1uA+zT
6. 求整数 n(n≥0) 阶乘的算法如下，其时间复杂度是（     ）【全国联考2012年】D8g`n
W3fe2jG,(QJm`<6a*{5DgN

int fact(int n) {
    if (n <= 1)
        return 1;
    return n * fact(n - 1);
}

A. $O(\log_2 n)$  Powered by https://fishc.com.cn
aNFo<ELub7~ZTGgCkJ.x-0P=Hw
B. $O(n)$来自：https://fishc.com.cn
yAcu}5,~=Omo>i;E)04&
C. $O(n \log_2 n)$来自：https://fishc.com.cn
W2_,">n5~N*P^eSRd|F0sla?.K4YzB
D. $O(n^2)$版权属于：https://fishc.com.cn
fuS.421(rWq*30`%mBo'Ye
~NT"xF'l!oAbuwIXCEVSKv.UQ*1
7. 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（     ）【全国联考2011年】PbxyYUJtz
PS_Yd<a~ylTb$-u3M?6Z"|;N1CF^

x = 2;
while (x < n/2)
    x = 2 * x;

A. $O(\log_2 n)$  Powered by https://fishc.com.cn
%4?VSW.xv9p<$gCm5dG!)uF:&ltn^
B. $O(n)$Powered by https://fishc.com.cn
?:l+AF;`H <6mRceX~JQUED.OzIbki
C. $O(n \log_2 n)$来自：https://fishc.com.cn
BJ_4j>d- uDM&tUxNSbFWGkly
D. $O(n^2)$版权属于：https://fishc.com.cn
6ikz0,:="`HW2LCQ1UEeM5;
g'>)6O~I3ji1QM9KwZx}d|q2#z8u
图一时之快先看答案，你将失去一次锻炼的机会！D g;dc%i1
By,_T$WuI4Zgceh0ipaG#U~8^{}D
请先自己思考和动手，再回复查看参考答案！B1H3ONY
6tWwu:#jRn)_s%KA{O9LU

游客，如果您要查看本帖隐藏内容请回复

来自：https://fishc.com.cn
hQ&K3U^iXW0ae8 ;ybM.%u)oZl