算法设计与分析
设f（N），g（N）是定义在正数集上的正函数，如果存在正的常数C和自然数N0，使得当N≥N0时有f（N）≤Cg（N），则称函数f（N）当N充分大时有下界g（N），记作f（N）∈○（g（N）），即f（N）的阶（）g（N）的阶。A、不高于B、不低于C、等价于D、逼近
题目
设f（N），g（N）是定义在正数集上的正函数，如果存在正的常数C和自然数N0，使得当N≥N0时有f（N）≤Cg（N），则称函数f（N）当N充分大时有下界g（N），记作f（N）∈○（g（N）），即f（N）的阶（）g（N）的阶。
- A、不高于
- B、不低于
- C、等价于
- D、逼近
相似问题和答案
第1题：
设R，N分别表示实数、整数和自然数集，下面定义函数f1，f2，f3： fl：R→R，f(x)=2x f2：N→N×N，f(n)=＜n，n+1＞ f3：N→N，f(x)=x mod 3，x除以3的余数 则下面说法正确的是
A．n和f2是单射但不是满射函数
B．f1和f3都是满射函数
C．f2是双射函数
D．以上说法全都是错误的
第2题：
F（n）=1 n>8 n<12
F（n）=2 n<2
F（n）=3 n=6
F（n）=4 n=other
使用+ - * /和 sign（n）函数组合出 F（n）函数
sign（n）=0 n=0
sign（n）=-1 n<0
sign（n）=1 n>0
第3题：
设函数f(x）=e5x，则f(x)的n阶导数f(n)(x)=____．
5ne5x
第4题：
对于三个函数f(n)=2008n3+8n2+96000，g(n)=8n3+8n+2008和h(n)=8888nlogn+3n2，下列陈述中不成立的是 ( )
A．f(n)是O(g(n))
B．g(n)是O(f(n))
C．h(n)是O(nlogn)
D．h(n)是O(n2)
解析：当n充分大时，由题意可得：f(n)与n3是同阶的，g(n)与n3是同阶的，h(n)与n2是同阶的。所以f(n)=O(g(n))，g(n)=O(f(n))，h(n)=O(n2)。
第5题：
递归函数f(n)的功能是计算1+2+…+n，且n≥1，则f(n)的代码段是(49)。
A．if n＞1 then return 1 else return n+f(n-1)
B．if n＞1 then return 1 else return n+f(n+1)
C．if n＞1 then return 0 else return n+f(n+1)
D．if n＜1 then return 0 else return n+f(n-1)
解析：根据题意，当n1时结束递归，函数返回0，否则返回n+f(n-1)进行递归运算。
第6题：
T(n)=O(f(n))中，函数O()的正确含义为
A.T(n)为f(n)的函数
B.T(n)为n的函数
C.存在足够大的正整数M，使得T(n)≤M×f(n)
D.存在足够大的正整数M，使得M×f(n)≤T(n)
第7题：
已知递归函数f(n)的功能是打印n，n-1，…，1，且n＞=1，应采用的代码段是(42)。
A．if n＞1 then f(n-1); printf("% d",n);
B．if n＜1 then f(n+1); printf("% d", n);
C．printf("% d",n); if n＞1 then f(n-1);
D．printf("% d", n); if n＜1 then f(n+1);
解析：n等于1时，递归结束，当n＞1时递归打印n-1。
第8题：
设R、N分别表示实数、整数和自然数集，下面定义函数f1、f2、f3： f1：R→R，f(x)=2x f2：N→N×N，f(n)=＜n，n+1＞ f3：N→N，f(x)=x mod 3，x除以3的余数 则下面说法正确的是( )。
A．f1和f2是单射但不是满射函数
B．f1和f3都是满射函数
C．f2是双射函数
D．以上说法全都是错误的
第9题：
已知递归函数f的定义如下：
int f(int n)
{
if(n ＜=1)return 1； //递归结束情况
else return n*f(n-2)； //递归}
则函数调用语句f(5)的返回值是【 】。
15 解析：本题考查的是递归算法的分析。一个直接或间接地调用自身的算法称为递归算法。在一个递归算法中，至少要包含一个初始值和一个递归关系。本题的，f()函数在n小于等于1时返回1，而在其余情况下返回n*f(n-2)。所以本题的递归算法可以表示为：
题目要求的结果是f(5)，即f(5)＝5*f(3)＝5*3*f(1)＝5*3*1＝15。故应该填15。
第10题：
此题基于以下的叙述：关系模式R（B，C，N，T，A，G），根据语义有如下函数依赖集：F＝{B→C，（N，T）→B，（N，C）→T，（N，A）→T，（A，B）→G}，关系模式R的码是（ ）。
A）（N，T）
B）（N，A）
C）（N，C）
D）（A，B）