12
11
11
12
3
12
4
12
6

7
向下取整
81100
19假设
为2的乘幂，并且
2，试求下列算法的时间复杂度及变
量cou
t的值（以
的函数形式表示）。
i
tTimei
t

cou
t0x2
whilex
2
x2cou
t

retur
cou
t

解：olog2
cou
tlog2
2
111已知有实现同一功能的两个算法，其时间复杂度分别为O2
和O
10，假设现实计算机可连续运算的时间为107秒（100多天），又每
秒可执行基本操作（根据这些操作来估算算法时间复杂度）105次。
试问在此条件下，这两个算法可解问题的规模（即
值的范围）各为
多少？哪个算法更适宜？请说明理由。
解：2
1012
40
9
f
101012

16
则对于同样的循环次数
，在这个规模下，第二种算法所花费的
代价要大得多。故在这个规模下，第一种算法更适宜。
112设有以下三个函数：
f
21
4
21000，g
15
4500
3，h
500
35
log

请判断以下断言正确与否：
1f
是Og

2h
是Of

3g
是Oh

4h
是O
35
5h
是O
log

解：1对2错3错4对5错
113试设定若干
值，比较两函数
2和50
log2
的增长趋势，并确定
在什么范围内，函数
2的值大于50
log2
的值。
解：
2的增长趋势快。但在
较小的时候，50
log2
的值较大。当
438时，
250
log2
114判断下列各对函数f
和g
，当
时，哪个函数增长更快？
1f
10
2l
10
3，g
2
4
7
2f
l
52，g
13
25
3f
21
41，g
l
2
4f
2
32
2，g

2
5
解：1g
快2g
快3f
快4f
快
10
f115试用数学归纳法证明：

1i2
12
16i1

0

2xix
11x1i0
x1
0

32i12
1i1

1

42i1
2i1

1
116试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z
的值
解：
i
tmax3i
txi
tyi
tz

ifxy
ifxzretur
x
elseretur
zelse
ifyzretur
y
elseretur
z117已知k阶斐波那契序列的定义为
f00，f10，…，fk20，fk11；f
f
1f
2f
k，
kk1
11
f试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。
解：k0为阶数，
为数列的第
项i
tFibo
accii
tki
t
ifk1exitOVERFLOWi
tpxp
ewi
tk1ifpexitOVERFLOWi
tijfori0ik1i
ifik1pi0elsepi1forik1i
1ixp0forj0jkjpjpj1pk2pk1xretur
pk118假设有A，B，C，D，E五个高等院校进行田径对抗赛，各院校
12
f的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为
项目名性r