中北大学大二软件专业算法导论期末参考题及答案.pdf

中北大学20XX学年第二学期?算法导论?试题

院系：软件学院专业：软件工程年级：20XX级

一、选择题

1.算法分析中，记号O表示〔B〕，记号Ω标售〔A〕,记号Θ表示〔D〕

A渐进下界B渐进上界C非紧上界D紧渐进界E非紧下界

2.以下关于渐进记号的性质是正确的有：〔A〕

Af(n)=Θ(g(n)),g(n)=Θ(h(n))⇒f(n)=Θ(h(n))

Bf(n)=O(g(n)),g(n)=O(h(n))⇒h(n)=O(f(n))

CO(f(n))+O(g(n))=O(min{f(n),g(n)})

Df(n)=O(g(n))⇔g(n)=O(f(n))

3.记号O的定义正确的选项是〔A〕。

AO(g(n))={f(n)|存在正常数c和n0使得对所有n≥n有：0

0

≤f(n)≤cg(n)}；

BO(g(n))={f(n)|存在正常数c和n使得对所有n≥n有：0≤

00

cg(n)≤f(n)}；

CO(g(n))={f(n)|对于任何正常数c0，存在正数和n00使

得对所有n≥n有：0≤f(n)cg(n)}；

0

DO(g(n))={f(n)|对于任何正常数c0，存在正数和n0使

0

得对所有n≥n有：0≤cg(n)f(n)}；

0

4.记号Ω的定义正确的选项是〔B〕。

AO(g(n))={f(n)|存在正常数c和n使得对所有n≥n有：0

00

≤f(n)≤cg(n)}；

BO(g(n))={f(n)|存在正常数c和n使得对所有n≥n有：0

00

≤cg(n)≤f(n)}；

C(g(n))={f(n)|对于任何正常数c0，存在正数和n0使

0

得对所有n≥n有：0≤f(n)cg(n)}；

0

D(g(n))={f(n)|对于任何正常数c0，存在正数和n0使

0

得对所有n≥n有：0≤cg(n)f(n)}；

0

5.T〔n〕表示当输入规模为n时的算法效率，以下算法效率最优的

是(C)

AT〔n〕=T〔n–1〕+1，T〔1〕=1

BT〔n〕=2n2

CT〔n〕=T〔n/2〕+1，T〔1〕=1

DT〔n〕=3nlog2n

6.动态规划算法的根本要素为〔C〕