算法设计与分析.doc

算法设计与分析
复习资料 仅供参考
选择题
1.以下关于算法的理解错误的是（算法是程序）
2.函数f(n)=logn,g(n)+log3n,则这两个函数阶的关系是（同阶）
3.二分搜索算法对于有N个数据项的有序表L平均作了约（└logn┘+1/2）
4.（回溯法）是一种逐步试探以求出问题解的方法
5.对数据压缩的描述，错误的是（它是不可逆的）
6.动态规划法依据所谓的最优性原理：一个最优的判定序列具有如下性质—不论初始状态和第一步的判定是什么，其他余下的判定必须相对于前一次判定所产生的新状态构成一个最优序列
7.（大整数相乘算法）广泛应用与数据安全与加密领域
8.顺序查找法查找元素Z，若P（Z）=1/4则平均复杂性为7/8（n+1）
9.分配和归并混合排序算法在最坏情形下的时间复杂性为（T（n）=O(n*logn)
10.在BM算法中设模式P=“abcde”,则滑动距离函数dist[a]值为1
11.以下各种技术不是主要应用与数据加密领域的是（快速傅立叶变换）
12.下列算法不属于分配排序技术的是（冒泡排序算法）
13.“在每个判定步上，列出各种可能局部的解，然后按照某种条件，舍弃那些肯不能得到最优解的局部解”，这句话是（贪心法）的主要思想
14.下列哪些不是HASH函数的应用范围(信息认证)
15.RSA数据加密算法在第五步时，将明文信息数据化，并选取长度（小于）logn位的数学作为明文信息块
16.典型的递归方程
T(n)=1 n=1
T(n)=aT(a/b)+D(n) n>1,当D(n)=nx,若a>D(b)
则方程的解(只与a有关)
17.典型的递归方程
T(n)=1 n=1
T(n)=aT(a/b)+D(n) n>1,当D(n)=nx,若a<D(b)
则方程的解依赖于(D(b)和D(n))
18.24/5上取整=5，下取整=4
19.以下关于算法的理解错误的是（评价其优劣是以其在某台计算机上的时间作依据）
20.在分配分块算法中每次扫描把输入数据序列分为（┌n/2┐下取整）个元素的非空组时，出现最坏情形
21.已知数据序列7.10.15.3.8.21.2则逆序的总数为(11)
22.LZ压缩技术是一种基于(字符串匹配)的实用数据压缩算法
23.已知数据16.20则gcd(16.20)为(4)
24.下列哪个属性是用于数字签名和信息认证的HASH函数,不需要满足和认证的(可逆的)
25.strassen矩阵法计算两个n阶矩阵相乘,所须的计算时间复杂性(O(n2.81)) 或(O(n3))
26.RSA公开密钥密码体系是以(素数)为基础的
27.BM算法对模式串的扫描方式是(自右向左)
28.ASCII压缩方法是一种经过（三级）压缩之后，可以压缩掉（62.5%）的信息量
29.对算法的分析必须脱离具体的(计算机结构)和(程序设计语言)
30.RSA算法采用的是非对称的密码体质,即采用不同的加密密钥和解密密钥,且公开加密密钥跟解密密钥保密的方法,对需要保护的信息进行加解密
31.设模式pattern="aabaaaa",利用必进的KMP算法计算出相应的newnext(5)的值为(0)
32.使用大整数相乘算法计算两个n位整数的乘积，所需的一位数乘法次数约为（n1.59)
33.以下关于分支界限法的叙述错误的是八皇后问题的求解过程采用的是（分支限界法）
34.递归式T（n)=T(n/3)+T(2*n/3)+n的解为（T(n)=O(nlogn))\
35.KMP算法（自右向左）扫描数据
36.冒泡法对逆序输入排序时间最长
37.下列哪个属性是用于数字签名和信息认证的HASH函数,必须满足的是(低度敏感性)
38.用较少的信息表示原有的较多的信息,以达到节省存储空间的目的的技术是(数据压缩技术)
39.以下关于贪心法的叙述错误的是(无论选择何种量度标准,贪心法一定能找到待求解问题的最优解)
40.字符串匹配操作是(字符串所有运算的基础)
41.对N个元素进行冒泡排序,最好情况下的时间复杂度为(O(n))\
42.两个矩阵相乘要满足的条件是第一个矩阵的列数和第二个矩阵的行数相等
43.基于比较的排序算法的时间复杂性的下界为(Ω(n2))
44.递归方法
T(n)=1 n=1
T(n)=4T(n/2)+n n>1
的解为(T(n)=O(n2))
45.置换8.3.4.9.7中有4个逆序
46.在顺序表(3.6.8.10.12.15.16.18.21.25.30)中,用二分法查找关键码11,所以需比较的次数是4
47.简单字符串最坏情形下,总共要执行((n-m+1)m)
48.strassen矩阵方法的思想是将相乘的A,B矩阵分成4个矩阵块
49.序列(N,0)......C(N,N)对应的母函数是((1+X)n)
50.在BM算法中,设模式p="pattern",则滑动距离函数dist[n]=7
51.0=10 mod 5
52.设s={1.2.3.4.5},则/s/=5
53.设q表示2出现在线性表L(N个数据)中的概率,假定它出现在一表L中任一位置的,概率相等,若2肯定出现在表L中,则算法的平均复杂性A(N)=(N/2+1)
54.用基数排序法对下面数据进行排序"312.290.180.653.358.432.865.19首先按照第一位的大小依次放到0到9桶中把各桶中的数据收集起来把收集好的数据在按第二位排序依次放到0到9的桶中,则第三号桶的数据为432

填空题
1.解递归方程的另一主要方法是利用母函数
2.大整数计算广泛应用与数据安全与加密领域
3.计算机密码系统主要分为对称密码体制和非对称密码体制
4.若正整数a和m互为素数,则aw(n)≡1 mod m
5.所谓全信息压缩是指可以采用(逆向方式)恢复信息原则
6.非对称密码体制是采用不同的加密密钥和解密密钥,且公开加密密钥而保密解密钥的方法
7.构造单向的HASH函数应满足(冲突概论小条件),她的含义是:已知C=HASH(M1)图形构造,M2使得HASH(M2)=C1是困难,那不能有密文信息推测出明文信息
8.用于映射的汉字字符串排序中构造映射函数应满足(映射可逆性),它的含义是每个汉字对应的映射整数必须唯一,而且由这些整数值可唯一还原原汉字字符
9.在RSA数据加密算法中选取两个素数P和Q,计算N=P*Q和W(N)选取数B使之满足GCD{B,W(N)=1},并计算A,使之满足A*B≡1 MOD W(N),明文信息化时,明文长度应小于logn
10.N个字符上的置换互为C2N个逆序
11.基数排序时间既与待排序数据的个数又与数据的位数及数据的基有关
12.BOYER-MOORE字符串匹配算法采用(自右向左)的方式扫描模式和正文
13.结合KMP算法思想改进后的BM算法速度较快,其不需要时间计算DELTA函数
13.改进冒泡法最坏情况下,对几个数排序,比较次数为(n(n-1)/2,交换次数为(n(n-1)/2)
14.瑞士的N.WIRTH教授提出的著名公式是算法+数据结构=程序
15.两个大整数相乘,其计算所需时间是用两个大整数相乘的次数在估计的
16.两个矩阵A(M,N)和B(N,Q)相乘的复杂性是M*N*Q
17.计算机算法可以分为两类,他们是数值运算和非数值运算
18.对于算法的优劣通常以平均形态和最坏情形两种结果来衡量
19.分支限界法常用于求(最优解),它对解空间状态数进行搜索
20.分配排序是通过(散列方法)将数据分配定位到不同的组中,然后对每组排序并重新组合出来
21.赵一谨硕士改进方法是当FIRSTP匹配成功时,才继续SECONDP的匹配

简答题:
1.基于映射的字符串排序的映射函数的约束条件?
答:映射可逆性,有序性,不可伸缩性,影射函数计算的简单性
2.算法时间复杂性的上界和下界的意义是什么?
答:上界:函数T(N)和F(N),如果存在常数C>O与N0,当N>NO时,有T(N)≤CF(N),则称函数T(N)是F(N)的上界. 下界:函数T(N)和F(N),如果存在常数C>O与N0,当N>NO时,有T(N)≥CF(N),则称函数T(N)是F(N)的下界
3.试用自然语言描述的冒泡排序算法的基本思想?
答:扫描数据序列,比较处于相邻位置的一对数据(关键字),如果它们的大小顺序不对,就交换它们的位置.这样,经过一遍扫描之后,最大关键字的记录将被沉到底,在随后的扫描中,它将不再被考虑.如果再一次遍扫描中没有数据项需要交换,则表明整个排序工作结束,算法终止,在每遍扫描文件中,设立一个标志用以表示在每遍扫描过程中是否存在数据交换
4.下列程序描述了改进的KMP算法,在程序的空白处填上合适的语句,使程序完整?
DEGIN
NEWNEXT[1]=0;
J=2;
WHILE J<=M DO
BEGIN
I=1;
IF(I=0)OR(P[J]<>P[J])THEN
NEWNEXT[J]=2;
ELSE
NEWNEXT[J]=3;
J=J+1;
END;
END
答:NEXT[J];I;NEWNEXT[I];
5.研究排序算法的理由?
答实际应用非常每繁琐,值得剖析且有趣,提供了算法分析技术的基本思想,可计算出算法的最坏和平均情形形式的下界
6.程序描述的冒泡算法如下:
Begin
k=n;
flag=1;
while flag>O do
begin
k=k-1;
flag=0;
for i=1 to k do
if L[i]>L[i+1] then
begin
x=L[i];
L[i]=L[i+1]
L[i+1]=x;
flag=1;
end
end
End.
7.介绍动态规心法基本思想,举出两例该方法具体应用?
答:基本思想:在每一个判定步上,列出各种可能的局部解,然后按某些条件,舍去那些肯定不能得到最优解,经过每一步这样的筛选后,可以大大减少工作量
8.程序如下:
Begin
i=1;
while(i<=n-m+1)do
begin
j=1; while(j<=m)and(p[j]=t[i+j-1])do
j=j+1;
if j>m then
writeln('matched,Begins in position:',i);
i=i+1;
end
End.
问题:该程序描述了哪些算法?说出该算法基本思想?
答:该程序描述算法是:简单的字符串匹配算法. 该算法的思想:将其看成以模式作为关键字查找问题,它将长度为N的下文划分成n-m-1个长度为m的字符串,检查比较每个这样的子串是否与长度为m的模式
9.模式置换压缩方法?
答:所谓模式置换压缩算法是指对于那些多次重复的信息,为它们构造一个模式表,然后根据些模式表作模式置换来实现数据压缩
10.下列程序描述了二分搜索算法
Begin
k=1;
m=n;
flag=o;
while k<=m and flag=0 do
begin
j=[(k+m)/2];
if z=L[j] then
flag=1
else if z<L[j] then
m=j-1
else
k=j+1
end;
if flag=1 then
writeln('j=',j)
else
writeln('j=',0);
End
答:(k+m)/2下取整;flag=1;j-1
11.简要叙述一个分治算法的内容,该算法的优点?
答:分治算法的内容:它将某个输入规模为n的问题,用某种方法划分等介的k个规模分别为n/k的子问题,首先解出k个子问题,然后再有某种方法将这些子问题的解组合起来形成原问题的解. 该算法的优点:如果子问题的规模大致相同时,会收到很好的效果
12.算法的平均复杂性?
答:Dn为规模为n的问题的输入集合,并设I是Dn的一个元素,p(i)是I出现的概率,t(I)时所执行的基本运算次数.A(n)=∑p(I)t(I) i∈Dn
13.指出在最坏情形下,对于具体有N个数据项的有序表L(N≥1)二分搜索算法将Z与表中数据项进行比较的次数是多少?平均作了多少次的比较操作?答:logn下取整+1;logn下取整+1/2
14.程序如下:
Begin
i=1;
while(i<=n-m+1)do
begin
j=1;
while(j<=m)and(p[j]=t[i+j-1])do
j=j+1;
if j>m then
writeln(matched,begin position:',1);
i=i+1
end
End
问题:该算法在最坏情形下的时间复杂性是多少?在最好情况下的时间复杂性是多少?
答:最坏情形下的时间复杂性是:O(m*n). 最好情形下的时间复杂性是:O(n)
15.试描述回溯法的基本思想,并举出两例该算法的具体应用?
答:回溯法的基本思想是:它属于穷举方法.主要思想是:假设用n元组(x1,x2...,xn)表示一个给定问题的解,xi取什于集合Si；如果已有满足约束条件的部分解，则添加xi+1∈Si+1到子组（x1,x2...,xn)中形成新的子组；如果所有的xi+1∈Si+1都不能得到部分解，去掉xi回溯到（x1,x2,x3...,xn-1)中，考察哪些未考查过的元素；如些反复进行，直到得到问题的解或者证明无解为止. 它的具体应用例子有:八皇后问题,哈密而顿回路算法等.
8.谈谈计算机程序与算法的区别?
答:区别:计算机程序的核心是计算机算法;一步一步解问题的过程称为算法,程序是在指定的计算机上执行算法,而算法是抽象的,它凌驾于一切具体执行的计算机之上

计算题
1.已知x=3467,y=4298,取基为10,采用大整数相乘算法,求解x*y?
解:令x0=67,x1=34,y0=98,y1=42
x0*y0=67*98=6566
x1*y1+34*42=1428
(x0-x1)*(y1-y0)+x0*y0+x1*y1=(67-34)*(42-98)+67*98+34*42=-1848+6566+1428=6146
所以x*y=6566+6146*10*10+1428*10*10*10*10=14901166

2.设模式P=ababababca利用改进的KMP算法next[j]和newnext[j]函数值.
解:J 1 2 3 4 5 6 7 8 9 10
P="a b a b a b a b c a"
Next[j]0 1 1 2 3 4 5 6 7 1
Newnext[j]0 1 0 1 0 1 0 1 7 0

3.对如下一组数据,写出按基数排序算法对其进行排序的全过程X={179,208,93,306,55,859,984,9,271,33,95,89}
步骤如下:
1)把数据按第一位依次放到下面0至9的桶中
桶:0 1 2 3 4 5 6 7 8 9
271 空 93,33 984 55,95 306 空 208 179,859,9,89
2)把各桶中的数据收集起来得
271,93,33,984,55,95,306,208,179,859,9,89
3)继续把收集起来的数据按第二位排序,依次放到0至9的各桶中,得
桶:0 1 2 3 4 5 6 7 8 9
306,208,9 空 空 33 空 55,859 空 271,179 984,89 93,95
4)把各桶中的数据收集起来得:
306,208,9,33,55,859,271,179,984,89,93,95
5)继续把收集真情为的数据按第三位排序,依次放到0至9的各桶中,得
桶:0 1 2 3 4 5 6 7 8 9
9,33,55,89,93,95 179 208,271 306 空 空 空 空 859 984
这时排序完毕,排序结果为:
9,33,55,89,93,95,179,208,271,306,859,984

4.已知数据序列1,3,5,7,1,6,,1,2,3,4,5,6,1,3,1,4,依据ASCII码两级压缩方法,写出对上述数据的压缩过程.
解:分组13,57,16,12,34,56,13,14
第一次压缩(8个ASCII码) 0D,39,10,0C,22,38,0D,0E
第二次压缩(7个ASCII码) 将第8个16进制数据0E即00001110的低7位的7个二进制位填入前7个数据的最高位
最后压缩结果为: 0D,39,10,0C,A2,B8,8D

5.请用RSA加密算法对明文"its all greek to me"中的"gr"进行加密.(设p=3,q=5,b=3)
解:加密过程如下:
1):n=p*q=3*5=25,ψ(n)=(p-1)*(q-1)=2*4=8
2):计算a满足a*b≡mod ψ(n),得a=3
3):用07表示g,18表示r
4):密文:C=(73) mod 15 =13
C=(183) mod 15 =12
明文信息gr加密后是13 12

6.用基数排序法对下面数据进行排序:X={856,451,239,12,192,180,7,123,44,100}
解:步骤如下:
1)把数据按第一位依次放到下面0至9的桶中
桶:0 1 2 3 4 5 6 7 8 9
180,100 451 12,192 123 44 865 空 7 空 239
2)把各桶中的数据收集起来得:
180,100,451,12,192,123,44,865,7,239
3)继续把收集起来的数据按第二位排序,依次放到0至9的桶中,得
桶:0 1 2 3 4 5 6 7 8 9
100,7 12 123 239 44 451 865 空 180 192
4)把各桶中的数据收集起来得:
100,7,12,123,239,44,451,865,180,192
5)继续把收集起来的数据按第三位排序,依次放到0至9的各桶中,得
桶:0 1 2 3 4 5 6 7 8 9
7,12,44 100,123,180,192 239 空 451 空 空 空 865 空
这时排序完毕,排序结果为:
7,12,44,100,123,180,192,239,451,865

7.已知数据序列X={3.4,7.0,4.3,5.0,10.0,4.0,6.0,4.8,8.0,1.0,},写出用分配分块排序算法进行排序的过程.
解:迭代步骤1)n=10,min=1.0,max=10.0,median=4.8
G1={1.0},G3={3.4},G4={4.3,4.0},G5={4.8},G6={5.0},G7={6.0},G8={7.0,8.0},G9={},G10={10.0}
迭代步骤2)n=2 g4={4.3,4.0},min=4.0,max=4.3,median=4.0,G1={4.0},G2{4.3}
迭代步骤3)n=2 G8{7.0,8.0},min=7.0,max=8.0,median=7.0,G1+{7.0},G2={8.0}
排序如果为：X={1.0,3.4,4.0,4.3,4.8,5.0,6.0,7.0,8.0,10.0}

8.解递归方法
T(1)=1,n=1
T(n)=4T(n/2)+n2,n>1
解:解的过程如下:因为D(n)=n2,D(b)=4=a;所以T(n)=O(n2logn)

9.请用ASCII码压缩信息0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6
解:用两步,结果为: 0c A2 B8 CE 5A 0C 22

10.已知模式串P="search",正文串T="Substring search is a way".写出滑动dist函数的值,给出BM算法的处理过程.
解:滑动函数dist[h]=6,dist[c]=1,dist[r]=2,dist[a]=3,dist[e]=4,dist[s]=5,dist[μ]=6, μ为其它未出现在模式串中的任何字符
BM法实施过程:检查左数第i(i=6)个字符r,与模式串字符h不等,滑动i=i+dist[r]=6+2=8
检查左数第i(i=8)个字符n,与模式串字符h不等,滑动i=i+dist[n]=8+6=14
检查左数第i(i=14)个字符r,与模式串字符h不等,滑动i=i+dist[r]=14+2=16
检查左数第i(i=16)个字符h,与模式串字符h相等且依次匹配成功,输出匹配成功在11位置.i=i+1=16+1=17
检查左数第i(i=17)个字符‘’,与模式串字符h不等,滑动i=i+dist[‘ ’]=17+6=23
检查左数第i(i=23)个字符w,与模式串字符h不等,滑动i=i+dist[w]=23+6=29
而i大于正文串的长度,所以匹配结束

11.设n=29，试给出用筛选法判定素数算法执行过程中数组mark[i]值的变化情况?
解:mark[2] mark[3] mark[4] mark[5]
初始值0 0 0 0
i=2 0 0 1 0
i=3 0 0 1 0
i=4 0 0 1 0
i=5 0 0 1 0

12.有一组数据序列{7,9,2,16,10,8,5,12,13,14,1},写出按分配和归并混合排序算法进行排序的过程.
解:用分配和归并排序过程如下:
1)n=10,前n/2=4个数据的min=2,max=16
迭代步骤1)G1={2},G2={7,9},G3,G4={16}
迭代步骤2)n=2,前n/2=1个数据的min=7,max=7,G1={7}后n/2=1个数据的min=9,max=9,G1={9}
前n/2个数据的有序序列为{2,7,9,16}
2)n=20,后n/2=4个数据的min=5,max=14
迭代步骤1)G5={5},G6,G7={8},G8={12},G9={13,14}
迭代步骤2)n=2,前n/2=1个数据的min=13,max=13,G1={13}
后n/2=1个数据的min=14,max=14,G1+{14}
后n/2=1个数据的有序序列为{5，8，12，13，14}
3）最后将两个长度为5的子序列{2，7，9，16}和{5，8，12，13，14}归并成一个长度为10的有序序列{2，5，7，8，9，12，13，14，16}

13.设模式P="pattern",求dist[c]的值(注意:C是模式P中的任意字符)
解：P=“p a t t e r n”
则dist[n]=7;dist[a]=5;dist[t]=3;dist[e]=2;dist[r]=1;dist[n]=7
应用题：
1.试采用分治方法写出求解A[1..n]个整数中最大值和最小值的算法,并求出当n=2k算法时间复杂性函数?解:算法maxmin(A,i,j,fmax,fmin)
Begin
if i=j then begin fmax=A[i];
fmin=A[i];
return;
end;
if i=j then begin
if A[i]<A[j]then
begin fmax=A[j];
fmin=A[i];
end;
clse
begin fmax=A[i];
fmin=A[j];
end;
return;
end;
mid=└(i+j)/2┘;
maxmin(A,I,mid,gmax,gmin);
maxmin(A,mid+1,j,hmax,hmin);
if gmax>hmax then fmax=gmax
else fmax=hmax;
if gmin<hmin then fmin=gmin else fmin=hmin;
end.
设T(n)为基本运算次数（元素比较为基本运算），则依据算法的递归过程，有如下的递归式：
T(n) =0 n=1
T(n) =1 n=2
T(└n/2┘)+T(└(n=1)/2┘)+2 n>2
若n=2k,则有
T(n)=2*T(n/2)+2
=2*(2*T(n/4)+2)+2
=4*T(n/4)+4+2
… … … …
=2k-1*T(2)+2+22+… …+2k-1
=2 k-1+2 k-2
=3*n/2-2

2.写出用筛洗法判定素数的算法，并分析当n=53时数组mark[i]值的变化情况?
解:程序如下:
Begin
for i=2 to int(√n) do
mark[i]=0;
i=2;
flag=0;
while(flag=0 and i<=int(√n)) do
begin
if n mod i=0 then
flag=1;
else
begin
s=i+i;
while s<int(√n)do
begin
mark[s]=1;
s=s+I;
end
end
end
i=i+1;
end
if flag=0 then
writeln(‘n=’,n,’是素数’);
else
writeln(‘n=’,n,’是合数’);
End
当n=51时,数组mark[i]的变化情况如下:
Mark[2] mark[3] mark[4] mark[5] mark[6] mark[7]
初始值 0 0 0 0 0 0
i=2 0 0 1 0 1 0
i=3 0 0 1 0 1 0
i=4 0 0 1 0 1 0
i=5 0 0 1 0 1 0
i=6 0 0 1 0 1 0
i=7 0 0 1 0 1 0

3.写出改进的冒泡排序算法,并分析最坏和最好情形的时间复杂度,并举例说明最坏和最好情形下的输入数据序列．
解：程序如下：
Begin
kn;
fag=1;
while flag>0 do
begin
k=k-1;
flag=0
for i=1 to k do
if L[i]>L[i+1] then
begin
x=L[i];
L[i]=L[i+1];
L[i+1]=x;
fag=1;
en
end
End
最好情况下的时间复杂性是:O(n)
最坏情况下的时间复杂性是:O(n2)
最好情况下的输入序列是:1,2,3,4,5,6,7,8,9
最坏情况下的输入序列是:9,8,7,6,5,4,3,2,1

4.写出基数排序算法中将链表中的数据分配到各桶及将各桶中的数据收集到链表中的算法,并对如下一组数据X={207,95,646,198,809,376,917,534,310,209,181,595}进行排序,写出按此算法排序过程.
解:程序如下:
Begin
for i=1 to d do
begin
for j=0 to 9 do
begin
H[j].next=NIL;
H[j].next=NIL;
pHead;
while p<>NIL do
begin
x=关键字 P^.k的第i位
if H[x].next=NIL then
begin
H[x].next=p;
T[x].next=p;
End
else
begin
q=T[x].next;
q^.next=p;
T[x].next=p
end
p=P^.next
end
j=0;
while H[j].next=NIL do
j=j+1;
Head=H[j].next;
q=T[j],bext;
for x=j+1 to 9 do
if H[x].next<>NIL then
begin
q^.next=H[x].next;
q=T[x].next;
end
q^.next=NIL;
end
End.
基数排序的过程如下:
1) 数据按第一位依次放到下面0至9的桶中
桶:0 1 2 3 4 5 6 7 8 9
310 181 空 空 534,334 095,595 646,376 207,917 198 809,209
把各桶中的数据收集起来得:
310,181,534,334,095,595,646,376,207,917,198,809,209
2)把收集起来的数据按第二位排序,依次放到0至9的各桶中得:
桶:0 1 2 3 4 5 6 7 8 9
207,809,209 310,917 空 534,334 646 空 376 181 空 095,595
把各桶中的数据收集起来得:
207,809,209,310,917,534,334,646,376,181,095,595
3)把收集起来的数据按第三位排序,依次放到0至9的各桶中得:
桶: 0 1 2 3 4 5 6 7 8 9
95 181 207,209 310,334,376 空 534,595 646 空 809 917
把各桶中的数据收集起来得:
095,181,207,209,310,334,534,595,646,809,917

5.程序如下:
Begin
for i=2 to () do
mark[i]=0;
i=2;
flag=0;
while(flag=0 and ()) do
begin
if mark[i]=0 then
begin
if () then
();
else
begin
s=i+i;
while s≤() do
begin
mark[s]=1;
s=s+i;
end
end
end;
i=i+1;
end;
if () then
writeln(‘n=’,n,素数)
clse
writeln(‘n=’,n,’是合数,以’i,’为因子’);
End.
问题1:在上述程序的空白处填上正确的语句,使程序完整
问题2:在本算法的迭代重复次数是多少?
问题3:计算n=37时,该算法在执行过程中,数组mark[i]值的变化情况
解:问题1:括号里面的答案依次为:1)int(√n);2)i<=int(√n);3)n mod i==0;4)flag=1;5)int(√n);6)flag=0 问题2:本算法的迭代次数是: └√n ┘-1 问题3:当n=37时,数组mark[i]值的变化如下:
Mark[2] Mark[3] Mark[4] Mark[5] Mark[6]
i=1 0 0 0 0 0
i=2 0 0 1 0 1 37 mod 2 ≠0
i=3 0 0 1 0 1 37 mod 3 ≠0
i=4 0 0 1 0 1 37 mod 4 ≠0
i=5 0 0 1 0 1 37 mod 5 ≠0

6.已知数据序列X={3.5,7.0,4.3,5.0,10.0,4.0,6.0,4.8,8.0,1.0}
问题1:写出用分配分块排序算法对其进行排序的过程
问题2:在分配分块排序算法中,何时出现最坏情形?
问题3:最坏情形下分配分块排序的时间复杂度是多少?
答:问题1:用分配分块排序算法对其进行排序的过程如下:
迭代步骤:1)n=10,mix=1.0,max=10.0,median=4.8,
G1={1.0},G2,G3={3.5},G4={4.3,4.0},G5={4.8}
G6={5.0},G7={6.0},G8={7.0},G9={8.0},G10={10.0}
迭代步骤：2）n=2,mix=4.0,max=4.3,median=4.0,
G1={4.0},G2+{4.3}
所以排序如果为：X+{1.0,3.5,4.0,4.3,4.8,5.0,6.0,7.0,8.0,10.0}
问题2:在分配分块排序算法中,每次扫描把输入数据序列分为? ┌n/2┐个元素的非空时,出现我最坏情形. 问题3:最坏情形下分配分块排序的时间复杂度是nlogn