算法设计与分析-01345-19日上-新资料

1.n+n*log10n2 = （Θ(n*log n2)）

2.设S={x| x {1,2,…,20} 且 x是素数}，则︱S︱＝（8 ）

3.对算法的分析必须脱离具体的（计算机结构和程序设计语言）

4.如果f(n)和g(n)都是单调递增的，则f(n)+g(n)（单调递增）

5.Log(n!) = （Θ(n*ln n)）

6.可以用来求最优解的是最优解分支界限法常用于求（分支界限法）

7.设S={x| x {1,2,…,30} 且 x是素数}，则︱S︱＝（ 10 ）

8.设S={x| x {1,2,…,200,201} 且x是奇数}，则︱S︱＝（101）

9.EULER函数Ψ(74)的值为（343）

10.属于分配排序技术的是（基数排序）

11.用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451， 526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把 收集好的数据再按第二位排序，依次放到0到9的各桶中，则第6号桶的数据为（865 ）

12. 如果f(n)和g(n)都是加法非负的增函数，则f(n)g(n)（单调递增）

13. 设D是输入的集合，N(I)是I D出现的概率，M(I)是算法在输入I时执行的次数。则算法的最坏情形复杂性为（Max(M(I)) (I D)）

14.同步并行算法是指某些进程（必须等待）别的进程的一类并行算法。

15. 用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照最高位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第2号桶的数据为（526）

16.算法设计方法主要有分治法、回溯法、贪心法、动态规划法、分支界限法。

17.数据压缩是指用较少的信息表示原有较多的信息，已达到节省存储空间的目的。

18. 是指在同一时间间隔内增加操作数量的技术是（并行处理技术）。

19. 序列c(n,0) ,c(n,1),…,c(n,n)对应的毋函数是（(1+x)n）

20. 常用来支持细粒度和中粒度的并行计算是（共享变量通信）

21.同步并行算法是指某些进程必须等待别的进程的一类并行算法。

22.并行算法的加速比为求解相应问题的最快串行算法在最坏情况下的运行时间除以该并行算法在最坏情况下的求解该问题的运行时间。

23. 由程序的控制和数据的相关性决定的是（软件并行性）

24.对算法的分析必须脱离具体的（计算机结构和程序设计语言）

25. 求解有限期的作业调度问题一般应采用（贪心法）

26.EULER函数Ψ(21)的值为（18 ）

27.如果f(n)和g(n)都是单调递减的，则g(g(n))（单调递减 ）

28. 对于并行算法，除了研究所需的运行时间之外还需要研究算法所需（处理器的数目）

29.简单字符串匹配算法在最坏情形下，总共要执行字符的匹配比较操作次数为（(n-m+1)*m）

30.序列(7，10，5，3，8，21，2)的逆序总数为（12 ）

31.下列哪个属性是单向的HASH函数不需要满足的性质（安全性）

32.用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第5号桶的数据为（451）

33.分支限界的本质是（排他方法）

34.采用大整数相乘算法，计算2368×3925所做的一位整数乘法的次数为（9 ）

35.在BM算法中，设模式P=“pattern”,则滑动距离函数dist[n]值为（7 ）

36.设模式Pattern=”aabaaaa”，利用KMP算法计算出的next(7)值为（3 ）

37.衡量算法的优劣通常依据（平均和最坏时间开销）

38.对于算法设计来说，递归是著名的分治策略。

39.函数f(n)=log n和g(n)=log3n这两个函数阶的关系是f(n)=Θ(g(n))。

40在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码10，所需比较的次数是3。

41.Branch and Bound的含义为（分支限界）

42.异步并行算法是指各进程之间无需相互等待的一类并行算法。

43.并行算法的复杂度主要考量两方面，它们是运行时间和处理器数目。

44.设S={x| x {1,2,…,10} 且 x是素数}，则︱S︱＝（4 ）

45. DES密码体制是（非对称密码体制）

46.对于给定的序列，其毋函数（唯一确定）

47.如果f(n)和g(n)都是单调递增的，则f(n)+2g(n)（单调递增）

48.EULER函数Ψ(7)的值为（6 ）

49.处理机的通信模型由所采用的通信算法和（系统结构决定）

50序列c(n,0) ,c(n,1),…,c(n,n-1)对应的毋函数是（ (1+x)n - xn）

51设S={x| x {1,2,…,20} 且 x是合数}，则︱S︱＝（ 12）

51.EULER函数Ψ(8)的值为（4 ）

52.ASCII码压缩法对纯数据文本的压缩率量为（62.5% ）

53冒泡排序的方式是（数遍扫描数据序列）

54对n个元素的线性表进行冒泡排序，最好情况下的时间复杂度为（ O(n)）

55.利用归并方法可以实现（数据排序）

56.RSA密码体制的困难性是（大数分解）

57.在讨论算法复杂性时必须加以考虑其（同步时间）

58.设模式Pattern=”aabaaaa”，利用KMP算法计算出的next(5)值为（ 2）

59.通常用来衡量算法的优劣的是（平均性态和最坏情形）

60.结合KMP算法思想改进后的BM算法速度较快，其不足是需要时间计算（delta函数）

61.算法分析方法主要有递归展开法和毋函数法。

62.设模式串长为m，正文串长为n；则在最坏情况下，BM算法的时间复杂度为Θ(mn)。

63.具有计算机复杂性的里程碑的时间段是（20世纪60年代）

64采用大整数相乘算法，主要依据是（乘法开销比加法大）

65.序列c(n,0) ,c(n,1),…,c(n,n)对应的毋函数是（(1+x)n ）

66.并行算法运行的物质基础是（并行计算机体系结构）

67.数据压缩是（可逆或不可逆的）

68.序列(17，10，15，3，8，21，2)的逆序总数为（14 ）

69.对n个元素的线性表进行冒泡排序，平均时间复杂度为（O(n2) ）

70.计算机要充分发挥作用离不开（计算机软件）

71.在BM算法中，设模式P=“pattern”,则滑动距离函数dist[a]值为（ 5）

72.设模式Pattern=”aabaaaa”，利用KMP算法计算出的next(3)值为（2 ）

73.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码11，所需比较的次数是（4 ）

74.KMP算法是以下面的人来命名的（Knuth-Morris-Pratt ）

75.BM算法在最坏情形下的时间复杂度是（Θ(m*n)）

76.使用大整数相乘算法计算两个n位整数的乘积，所需的一位数乘法次数约为n1.59次

77.并行程序与串行程序有（明显的差别）

78.设模式串长为m，正文串长为n；则在最坏情况下，BM算法的时间复杂度为Θ(mn)。

79在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码6，所需比较的次数是4。

80.并行算法的复杂度主要考量两方面，它们是运行时间和处理器数目。

81.瑞士的N.Wirth教授提出的著名公式是：算法 + 数据结构 = 程序。

82. 如果f(n)和g(n)都是单调递减的，则f(g(f(n)))（单调递减）

83分布式并行算法是指由通讯链路连接的多结点（计算机）并行完成某一计算任务的一类并行算法。

84对于一个m*n的矩阵A和一个n*q的矩阵B，WINOGRAD算法中整个算法总的乘法次数是（(mnp/2)+mn/2+qn/2）

85.EULER函数Ψ(23)的值为（22 ）

86.下列哪一项不属于单向HASH函数的应用范围（加密）

87.第一台电子计算机产自（美国）

88.序列(7，10，15，3，8，21，2)的逆序总数为（11 ）

89.毋函数的实质是（把一个值域变换到另一值域）

90.用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第0号桶的数据为（无数据）

91.有助于编译器更好的发挥并行性的（硬件处理机）

92.在BM算法中，设模式P=“text”,则滑动距离函数dist[e]值为（2 ）

93.计算机图灵的评选是（一年一评）

94.对于非对称密码体制，每个当事人所需要的密钥数是（2 ）

95.简单字符串匹配算法在最好情形下，进行的匹配比较操作次数为（(n-m+1) ）

96.序列(1，7，10，15，13，21，28)经起泡排序所需的趟数为（2）

97.算法分析方法主要有递归展开法和毋函数法。

98设模式串长为m，正文串长为n；则在最坏情况下，KMP算法的时间复杂度为O(m+n)。

99.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码1，所需比较的次数是3。

100.单向的HASH函数可应用于（数字签名）

101.基于关键字比较的排序时间复杂度的下界是（O(n*log n) ）

102.改进的KMP算法比KMP算法更加有效是因为模式中（重复出现的字符较多）

103.用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第1号桶的数据为（312 ）

104.进程同步所需的时间，是由于进程是（异步并行执行的）

105.在BM算法中，设模式P=“text”,则滑动距离函数dist[x]值为（1 ）

106.设模式Pattern=”aabaaaa”，利用改进的KMP算法计算出的newnext(7)值为（2 ）

107.计算机算法按数据类型可以分为两类，它们是数值运算和非数值运算。

108.在非对称多处理机系统中，可以被称为执行处理机的是（一个或一组处理机具有执行能力）

109.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码21，所需比较的次数是2。

110.RSA密码体制主要涉及的运算是（模运算）

111.不基于关键字比较的排序是（基数排序）

为了提高软件和硬件的并行性的匹配程度，我们可以通过增加硬件并行性的灵活程度和开发控制密集程序的（软件并行性）

112.用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第3号桶的数据为（432 ）

113.粒度问题的求解既要考虑并行程序中颗粒的数目还要考虑（颗粒的大小）

114.在BM算法中，设模式P=“text”,则滑动距离函数dist[t]值为（3 ）

115.设模式Pattern=”aabaaaa”，利用改进的KMP算法计算出的newnext(6)值为（3 ）

116.在多处理机系统上，可以保持也可以不保持程序的状态，这取决于（存储器模型）

117.回溯法属于（穷举方法）

118.时间复杂性达到下界的算法称为最优算法

119.算法设计方法主要有分治法、回溯法、贪心法、动态规划法、分支界限法。

120.常见的数据压缩方法主要有ASCII码压缩法、模式置换压缩法LZ压缩法。

121.模式置换压缩多用哪类情况（多次重复出现的信息）

122.分治法常伴随着（递归）

123. ASCII码压缩法对纯数据文本的压缩率量为（62.5%）

124.设S={x| x {1,2,…,20} 且 x是合数}，则︱S︱＝（12 ）

125. 在指令级或循环级上借助于并行化或向量化编译器来开发的是（细粒度并行性）

126.设S={x| x {1,2,…,200} 且x是偶数}，则︱S︱＝（100 ）

127.EULER函数Ψ(9)的值为（6 ）

128.序列(1，3，3，3，5，7，22)的逆序总数为（0）

130.在线性表大部分元素已经有序的情况下，排序效率较高的算法是（冒泡排序 ）

131.在BM算法中，设模式P=“patternern”,则滑动距离函数dist[p]值为（9）

132.设a=23×521×75，b=212×32×54×7×113；则gcd(a,b)=（23×54*7）

133.设模式Pattern=”aabaaaa”，利用改进的KMP算法计算出的newnext(3)值为（2 ）

134.时间复杂性达到下界的算法称为最优算法。

135.设模式Pattern=”aabaaaa”，利用改进的KMP算法计算出的newnext(6)值为（3）

136.递归方程T(1)=1，T(n)=2T(n)+1 ( n>1) 的解为T(n)=O(2n)。

137.异步并行算法是指各进程之间相互（无需等待）

138.基数排序的时间既与待排序数据的个数又与数据的位数及数据的基有关。

136.中等粒度所包含的指令数一般（小于2000条）

137.对大部分元素已经有序的线性表排序需要最多时间的算法是（基数排序）

138.设数据的基为m，用基数排序对n个数据进行排序。则第一遍基数排序所需的时间为（O(n+m)）

139.在BM算法中，设模式P=“pattern”,则滑动距离函数dist[p]值为（6 ）.

140.二维网格结构是一种常用的（并行机）

141.ASCII码压缩法对纯数据文本的压缩率量为（62.5% ）

142.超立方连接机器是一个具有（2k个结点的网络）

145.算法的优劣通常以平均和最坏两种性态结果来衡量。

146.“不论初始状态和第一步的判定是什么，其他余下的判定必须相对于前一次判定所产生的新状态构成一个最优序列“，是动态规划法依据的（最优性原理）。

147.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码12，所需比较的次数是4 。

148.基数排序的时间既与待排序数据的个数又与数据的位数及数据的基有关。

149. 对算法的分析不能脱离的有（技术人员，分析工具）

150.毋函数与其所对应的序列关系是（一对一的）

151.计算机的速度正比于其价格的（平方）

152.国际象棋骑士巡游算法是应用（回溯法）

153.单向的HASH函数可应用于（消息摘要）

154.用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第7号桶的数据为（无数据）

155.一般而言，粒度越细（并行性程度越高）

156.算法设计方法主要有分治法、回溯法、贪心法、动态规划法、分支界限法。

157.在BM算法中，设模式P=“text”,则滑动距离函数dist[x]值为（1）

159.计算届的最高奖是图灵奖。

160.在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码15，所需比较的次数是1 。

161.基数排序的时间既与待排序数据的个数又与数据的位数及数据的基有关。

162.二分搜索算法对于有n个数据项的有序表L作的比较操作次数平均约为（）

163.在最坏情形下分配分块排序的时间复杂性为（O(n*logn)）

164.基于关键字比较的排序时间复杂度的下界是（O(nlog2n)）

165.毋函数可以用来（解递归方程）

166..ASCII码压缩法是基于（二极压缩）

171..求解递归函数就是（推出末函数显示公式的过程）

172.简单字符串匹配算法在最坏情形下，总共要执行字符的匹配比较操作次数为（(n-m+1)*m）

173.序列(7，1，15，3，8，21，2)的元素个数为4的子集的个数为（35）

174.计算机的发明人是（冯.诺依曼）

175.基数排序是（不基于关键字比较的排序）

176.KMP串匹配算法对正文串的扫描方式是（自左至右无回溯）

177.为节省硬盘空间对存储信息进行的压缩是（全信息压缩）

178.613≡ 6 mod 13

179ASCII码压缩法对纯数据文本的压缩率量为 62.5% 。

180计算机密码系统主要分为 对称密码体制 和 非对称密码体制 两种。

181冒泡排序在最坏情形下得比较次数是 n2 。

182.311×720≡ 3 mod 11

183.开发问题的并行性包括开发 计算并行性 、搜索并行性 和逻辑并行性。

184.可以从不同的角度将并行算法分类，如数值并行算法和非数值并行算法；同步 并行算法和异步并行算法；SIMD、MIMD、VLSI并行算法。

185.所谓硬件并行性是指 计算机体系结构 和硬件多样性所决定的并行性。

186.我们所构造的汉字到整数的映射应当满足：映射可逆性， 有序性 ， 不可伸缩性 ，映射函数计算简单性。

187.并行计算模型主要有SIMD互联网络模型，共享存储的SIMD模型， MIMD并行计算模型 。

188.对算法的分析必须脱离具体的 计算机结构和程序设计语言 。

189.算法设计方法主要有分治法、回溯法 、 贪心法、动态规划法、 分支界限 。

190.RSA公开密码密钥体制建立在 素数理论 和欧拉定理基础上。

191.冒泡排序的最坏时间复杂度 O(n2) ，平均时间复杂度是 O(n2) 。

192.常见的数据压缩方法主要有ASCII码压缩法、模式置换压缩法 、 LZ压缩法 。

193.在最坏情况下，对于具有n个数据项的有序表L，二分搜索算法将z与表中的数据项进行比较的次数是 。

194.并行算法的 可伸缩性问题 对于网络并行计算环境显得尤为重要。

195. 时间复杂性 达到下界的算法称为最优算法。

196.在并行算法设计的基本技术中，破对称技术主要应用于 图论算法技术和随机算法技术。

197.HASH函数主要应用于数字签名和 信息认证技术 。

198.设模式串长为m，待搜索串长为n；则在最坏情况下，KMP算法的时间复杂度 O(m+n)。

199.简述LZ压缩算法的主要思想：

答：待编码（压缩）得数据符号串可能在已经编码的信息结构中，因此整个数据源在待编码的符号串上呈现冗余

程序填空：下面是一个判定素数的程序，请将程序补全

Begin

Flag=0;

i=2;

while( ) do

begin

if n mod i=0 then

flag=1;

i=i+1;

end;

if then

writeln(‘n=’,n,’是素数’)

else

writeln(‘n=’,n,’是合数’)

End.

答： flag=0 and i<=int() (2分) 或者 flag=0 and i<=n-1;(2分)

　　　flag=0（2分）

200用于数字签名和信息认证技术的HASH函数必须满足那些条件：

答：不可逆性；计算简单；冲突概率小；高度敏感性；

201.在公共总线互联SMP系统中，单总线SMP系统具有哪些优点？

答：成本低，容易实现。

扩展性能好

202.Flynn分类法，它按照指令流和数据流将计算机系统分为哪几类？

答： 单指令单数据流计算机

单指令多数据流计算机

多指令单数据流计算机

多指令多数据流计算机

203..STRASSEN算法的主要意义是：

答：在理论上它突破了矩阵乘法的O（n3）时间界限以及其他诸如矩阵求逆、计算行列式和解联立线性方程组等问题带来的O（n3）时间计算的开销

204.并行处理的四个级别：

答：作业或程序级的并行。

任务或过程级的并行

指令之间级的并行

指令内部级的并行

205..试叙述设计BM算法的主要考量：

答：主要考量是在模式匹配比较过程中，有很多情形是前面许多字符都匹配而最后若干个字符不匹配

206..数据压缩的经济价值：

答：节省存储空间，达到一定程度的保密的目的。

207.大大减少信息在网络上传输的时间

208..并行算法的代价定义：

答：并行算法所需的时间和所需的处理器数目的乘积。

209.程序如下：

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.

问题：该程序描述了哪种算法？

答：该程序描述的算法是：简单的字符串匹配算法

210.基于映射的字符串排序的影射函数的约束条件

答：映射可逆性；有序性（2分）；不可伸缩性（1分）；映射函数计算的简单性（1分）

211..“大事化小，小事化了”概括了什么算法设计技术（方法）？

分治法

212..分治法：

将问题分解为若干个子问题，然后解出这些子问题，最后用某种方法将这些子问题的解组合成原问题的解。

213.列举出一些字符串匹配算法：

答：KMP串匹配算法，BM串匹配算法，KR串匹配算法

214..在公共总线互联SMP系统系统中，单SMP总线系统的缺点：

答：因为多处理机和其他设备共用一条总线，所以在任一时刻只有一个处理机能够发送信息，故系统效率较低

215..递归是由那些部分构成的？

边界条件；递推公式；

216..函数f(n)是T(n)的上界意味着：

存在常数c>0与n0，当n>n0时，恒有T(n) cf(n)。

217..模式置换压缩方法：

答：是对多次重复的信息构造一个模式表，然后根据此模式表作模式置换来实现数据压缩。

218..函数f(n)是T(n)的下界意味着：

答：存在常数c>0与n0，当n>n0时，恒有T(n) cf(n)。

219..试介绍动态规划法的基本思想。

答：在每一个判定步上，列出各种可能的局部解，然后按某些条件，舍弃那些肯定不能得到最优解的局部解，经过每一步这样的筛选之后，可以大大减少工作量。

220..欧拉函数Ψ(n)的定义为：

Ψ(n)={1,2,…,n}中与n互素的数的个数

221..写出用筛法判断79是否为素数的步骤：

解：求出n==8；有选择地用2，3，…，8对79进行试除：

由于2不整除79，所以4，6，8不用再判断；

由于3不整除79，所以6不用再判断；

5不整除79；

7不整除79；

所以79是素数；

222.写出用筛法判断83是否为素数的步骤：

解：求出n==9；有选择地用2，3，…，9对83进行试除：

由于2不整除83，所以4，6，8不用再判断；

由于3不整除83，所以6，9不用再判断；

223.设集合S={1，2，6，8，10，12，100}，求S的子集，要求该子集的元素之和d=9。

满足要求的子集有：{1，2，6}；{1，8}；

224..所谓“平方货币体制”，是指一共有17种面值的货币，面值分别从1的平方到17的平方(298)，也就是：1元，4元，9元，…，298元。求10元共有多少种支付方法。

解：10元钱共有4种支付方法：

10个1元；

6个1元和一个4元；

2个1元和2个4元；

1个1元和一个9元；

225.已知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

226..设模式P=aabaaaa；求改进的KMP算法计算出的next[j]和newnext[j]函数值。

解：

j = 1 2 3 4 5 6 7

Next[j] = 0 1 2 1 2 3 3

Newnext[j] = 0 0 2 0 0 3 2

227..解递归方程：T (1)=1；T(n)=4T()+n2 (n﹥1)

解：因为D(n)=n2，

D(b)=4=a；

所以T(n)=O(n2 log n)

228.解递归公式：T(1)=1；T(n)=2T(n-1)+1 (n>1)

解：对T(n)展开，得：

T(n)=2T(n-1)+1=2(2T(n-2)+1)+1=2(2(2T(n-3)+1)+1)+1=23T(n-3)+1+2+22

=2n-1T(1)+(1+2+22+…+2n-2)= (1+2+22+…+2n-1)=2n-1；

229.用大整数乘法计算1245*2436；

解：设 x=12*102+45; y=24*102+36;则xy=12*24*104+(12*36+45*24)*102+45*36；

同理，对于12*24，设x=1*10+2; y=2*10+4;则xy=1*2*102+(1*4+2*2)*10+2*4=288；

如此下去，…，最终可得 1245*2436=3032820.

230.请用分治法设计算法：在一个数组A[1..n]中（n=2k），同时寻找最大值和最小值。请给出你的算法。

解：算法如下：

min_max(low,high)

{

if  high-low=1 then

if A[low]

return(A[low],A[high]);

else

return(A[high],A[low]);

end if

else

mid=(low+high)/2;

(x1,y1)=min_max(low,mid);

(x2,y2)=min_max(mid+1,high);

x=min(x1,x2);

y=max(y1,y2);

return(x,y);

end if

}

231.设模式P=“pattern”，求dist[c]的值（c是模式P中的任意字符）

解：

dist[p]=6;

dist[a]=5;

dist[t]=3;

dist[e]=2;

dist[r]=1;

dist[n]=7

232..设R=(1, 2, .., n)，给出利用分治法求解R的全排列的算法思想。

解：分治法求解全排列的算法思想：

设R=(1, 2, .., n)的全排列为P(R)；

若R=(a)，则P(R)=(a)；

否则，P(R)={(1)P(2, 3, .., n)，(2)P(1, 3, .., n)，…，(n)P(1,2, .., n-1)}；

233..用基数排序法对序列X=(865,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. 从0到9依次把各桶中的数据收集起来得：

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. 从0到9依次把各桶中的数据收集起来得：

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

最后从0到9依次把各桶中的数据收集起来，排序完毕；结果为：

7，12，44，100，123，180，192，239，451，865

234.解递归公式：T(1)=1；T(n)=7T(n-1) (n>1)

解：对T(n)展开，得：

T(n)=7T(n-1)=7(7T(n-2))=7(7(7T(n-3))=7n-1T(1)=7n-1

235..写出用冒泡排序法对序列X=(65,45,23,12,19,18,7,13,44,10)的排序过程

解：

1.第一趟比较并交换后的结果为：

(7,65,45,23,12,19,18,10,13,44)

2. 第二趟比较并交换后的结果为：

(7,10,65,45,23,12,19,18,13,44)

3. 第三趟比较并交换后的结果为：

(7,10,12,65,45,23,13,19,18,44)

4. 第四趟比较并交换后的结果为：

(7,10,12,13,65,45,23,18,19,44)

5. 第五趟比较并交换后的结果为：

(7,10,12,13,18,65,45,23,19,44)

6．第六趟比较并交换后的结果为：

(7,10,12,13,18,19,65,45,23,44)

7．第七趟比较并交换后的结果为：

(7,10,12,13,18,19,23,65,45,44)

236..写出用冒泡排序法对序列X=(865,451,239,12,192,180,7,123,44,100)的排序过程：

解：

1.第一趟比较并交换后的结果为：

(7,865,451,239,12,192,180,44,123,100)

2. 第二趟比较并交换后的结果为：

(7,12,865,451,239,44,192,180,100,123)

3. 第三趟比较并交换后的结果为：

(7,12,44,865,451,239,100,192,180,123)

4. 第四趟比较并交换后的结果为：

(7,12,44,100,865,451,239,123,192,180)

5. 第五趟比较并交换后的结果为：

(7,12,44,100,123,865,451,239,180,192)

6．第六趟比较并交换后的结果为：

(7,12,44,100,123,180,865,451,239,192)

7．第七趟比较并交换后的结果为：

(7,12,44,100,123,180,192,865,451,239)

8．第八趟比较并交换后的结果为：

(7,12,44,100,123,180,192,239,865,451)

9．第九趟比较并交换后的结果为：

(7,12,44,100,123,180,192,239,451,865)

排序结束。

237.所谓“平方货币体制”，是指一共有17种面值的货币，面值分别从1的平方到17的平方(298)，也就是：1元，4元，9元，…，298元。求10元共有多少种支付方法。

解：10元钱共有4种支付方法：

10个1元；

6个1元和一个4元；

2个1元和2个4元；

1个1元和一个9元；

238.求递归方程：T (1)=1；T(n)=4T()+n3 (n﹥1)的复杂度

解：因为D(n)=n3，

D(b)=8；

且a其特解是O(n3)

所以T(n)=O(n3)

239.解递归公式：T(1)=1；T(n)=2T(n-1)+1(n>1)

解：对T(n)展开，得：

T(n)=2T(n-1)+1=2(2T(n-2)+1)+1=2(2(2T(n-3)+1)+1)+1=23T(n-3)+1+2+22

=2n-1T(1)+(1+2+22+…+2n-2)= (1+2+22+…+2n-1)=2n-1；

240.用大整数乘法计算1245*2436；

解：设 x=12*102+45; y=24*102+36;则xy=12*24*104+(12*36+45*24)*102+45*36；

同理，对于12*24，设x=1*10+2; y=2*10+4;则xy=1*2*102+(1*4+2*2)*10+2*4=288；

如此下去，…，最终可得 1245*2436=3032820.

241.设数据序列X={3.5，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},G2,G3={3.5},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,min=4.0,max=4.3,median=4.0,G1={4.0},G2={4.3}

步骤3、n=2,min=7.0,max=8.0,median=7.0, G1={7.0},G2={8.0}

所以排序结果为X={1.0，3.5，4.0，4.3，4.8，5.0，6.0，7.0，8.0，10.0

242.假设有一个需要使用某一资源的n个活动组成的集合A={1，2，3，……，n}。该资源一次只能被一个活动占用。每个活动i有其开始时间Si和结束时间Fi，而且Si≤Fi。一旦被选择，活动i就占据时间区间[Si,Fi〕。如果时间区间[Si,Fi〕和[Sj,Fj〕互不重叠，那么称活动i和活动j是兼容的。假设输入的活动按结束时间的递增顺序排序，使用贪心算法描述：

答：

Begin

A={1};

j=1;

for i = 2 to n do

if S[i]>=F[j] then　

begin

A = A +{i};　

j=I;

end

End.

243.编写一个常规的矩阵相乘算法（矩阵A是m*n,矩阵B是n*q）

解：

Begin

for i=1 to m do

for j=1 to q do

begin

C[i,j]=0;

for k=1 to n do

C[i,j]=C[i,j]+A[i,k]*B[k,j];

end;

End

244.遍写简单的冒泡排序的算法

解：

Begin

k=n;

flag=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;

flag=1;

end

end

End

245.请用分治法设计算法：在一个数组A[1..n]中（n=2k），同时寻找最大值和最小值。请给出你的算法。

解：算法如下：

min_max(low,high)

{

if  high-low=1 then

if A[low]

return(A[low],A[high]);

else

return(A[high],A[low]);

end if

else

mid=(low+high)/2;

(x1,y1)=min_max(low,mid);

(x2,y2)=min_max(mid+1,high);

x=min(x1,x2);

y=max(y1,y2);

return(x,y);

end if

}

246.用基数排序法对序列X=(865,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)从0到9依次把各桶中的数据收集起来得：

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)从0到9依次把各桶中的数据收集起来得：

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

最后从0到9依次把各桶中的数据收集起来，排序完毕；结果为：

7，12，44，100，123，180，192，239，451，865

吉林大学自考算法设计与分析报告01345复习资料