数学二进制的算法
1. 绪 论
A ．2n    B．n!    C．n5
【答】10 000< n*log 2(n)< n5< 2n < n!
D．10 000
E． n*log 2 (n)
2．将下列复杂度由小到大重新排序：
A ． n*log 2(n)    B． n + n2 + n3
C．24
D．n0.5
【答】 24< n0.5< n*log 2 (n) < n + n2 + n3
3.用大“ 0”表示法描述下列复杂度：
A．5n5/2 + n2/5
B．6*log2(n) + 9n
C．3n4+ n* log2(n)
D．5n2 + n3/2
【答】 A ： 0 ( n5/2)    B： 0 (n)
C： 0 (n4)
D： 0 (n2)
1．将下列复杂度由小到大重新排序：
4n2 , log3n, 3n , 20n ,
2000
4．按照增长率从低到高的顺序排列以下表达式：
n2/3。又n!应排在第几位？
【答】按照增长率从低到高依次为： 2000, log3n, log2n , n2/3 , 20n , 4n2 , 3n。
, log2n ,
n的增长率比它们中的每一个都要大，应排在最后一位。
5. 计算下列程序片断的时间代价：
int i=1;
while(i<=n)
{
Printf(“i=%d\n”,i);
i=i+1;
}
【答】循环控制变量i从1增加到n,循环体执行n次，第一句i的初始化执行次数为 句执行n次，循环体中第一句 Printf执行n次，第二句i从1循环到n，共执行n次。 序段总的时间代价为：
1，第二 所以该程
T(n) = 1 + n + 2n = 3n+ 1 = O(n)
6. 计算下列程序片断的时间代价：
int i=1;
while(i<=n)
{
int j=1;
while(j<=n) {
int k=1;

while(k<=n)
{
printf( “i=%d,j=%d,k=%d\n ”,I,j,k);
k=k+1;
}
j=j+1;
}
i=i+1;
【答】循环控制变量i从1增加到n,最外层循环体执行n次，循环控制变量j从1增加到n, 中间层循环体执行n次，循环控制变量k从1增加到n,最内层循环体执行n次，所以该程序段 总的时间代价为：
T(n) = 1 + n + n {1 + n + n[1 + n + 2n +1] +1 +1 } + 1
= 3n3 + 3n2 +4n +2
= O(n3)

2.线性表
1.试写一个插入算法 intinsertPost_seq(palist, p, x )，在palist所指顺序表中， 下标为p的 元素之后，插入一个值为    x的元素，返回插入成功与否的标志。
【答】
数据结构
采用
int insert Po st_seq (P seqList p alist, int p, DataT ype x )    {
/*在palist所指顺序表中下标为 p的元素之后插入元素 x */
int q;
if ( p alist->n >= palist-> MAXNUM ) {
/*溢出*/
printf( “
n )；
return 0;
}
if (pv0 II p>palist->n-1 ) {
/*不存在下标为P的元素*/
n”)； return 0;
printf( “N
}
for(q=palist->n - 1; q>=p+1; q--)    /*插入位置及之后的元素均后移一个位置
*/
p alist->element[q+1] = p alist->element[q]; p alist->element [p+1] = x;
/*插入元素x */
P alist->n = P alist->n + 1;
/*
元素个数加1 */
return 1;
2 试写一个删除算法 deleteV_seq(palist, x )， 元素，返回删除成功与否的标志。
在Palist所指顺序表中,
删除一个值为    x的
【答】
数据结构
采用
int deleteV_seq (P seqList p alist, p, DataT ype x ) { /*在palist所指顺序表中删除值为
x的元素 */
int p,q;
for(p=0;pvn;P++)    /* 查值为 x
的元素的下标*/
if(x==p alist->element[ p]){ for(q=p; qvp alist->n-1; q++) /*
被删除元素之后的元素均前移一个位置

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。