算法设计与分析

1

算法设计 一、

n+n*log 10

n 2 = （Θ(n*log n 2)）

设S={x| x ∈{1,2,…,20} 且 x 是素数}，则︱S ︱＝（8 ） 对算法的分析必须脱离具体的（计算机结构和程序设计语言） 如果f(n)和g(n)都是单调递增的，则f(n)+g(n)（单调递增） 1． Log(n!) = （Θ(n*l n n)）

2． 可以用来求最优解的是最优解分支界限法常用于求（分支界限法） 3． 设S={x| x ∈{1,2,…,30} 且 x 是素数}，则︱S ︱＝（ 10 ） 4． 设S={x| x ∈{1,2,…,200,201} 且x 是奇数}，则︱S ︱＝（101） 5．

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)=log 3n 这两个函数阶的关系是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 - x n ） 51. 设S={x| x ∈{1,2,…,20} 且 x 是合数}，则︱S ︱＝（ 12） 52. EULER 函数Ψ(8)的值为（4 ） 53. ASCII 码压缩法对纯数据文本的压缩率量为（62.5% ） 54.

冒泡排序的方式是（数遍扫描数据序列） 55. 对n 个元素的线性表进行冒泡排序，最好情况下的时间复杂度为（ O(n)）

56. 利用归并方法可以实现（数据排序） 57. RSA 密码体制的困难性是（大数分解）

58.

在讨论算法复杂性时必须加以考虑其（同步时间） 59. 设模式Pattern=”aabaaaa”，利用KMP 算法计算出的next(5)值为（ 2）

60.

通常用来衡量算法的优劣的是（平均性态和最坏情形） 61. 结合KMP 算法思想改进后的BM 算法速度较快，其不足是需要时间计算（delta 函数） 62. 算法分析方法主要有递归展开法和毋函数法。 63. 设模式串长为m ，正文串长为n ；则在最坏情况下，BM 算法的时间复杂度为Θ(mn)。

64. 具有计算机复杂性的里程碑的时间段是（20世纪60年代） 65. 采用大整数相乘算法，主要依据是（乘法开销比加法大） 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(n 2) ） 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 位整数的乘积，所需的一位数乘

法次数约为n 1.59

次

77.

并行程序与串行程序有（明显的差别） 78. 设模式串长为m ，正文串长为n ；则在最坏情况下，BM 算法的时间复杂度为Θ(mn)。 79. 在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码6，所需比较的次数是4。 80. 并行算法的复杂度主要考量两方面，它们是运行时间和处理器数目。

82.瑞士的N.Wirth 教授提出的著名公式是：算法 + 数据结构 = 程序。 83. 如果f(n)和g(n)都是单调递减的，则f(g(f(n)))（单调递减） 84.

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

的一类并行算法。

86.

对于一个m*n 的矩阵A 和一个n*q 的矩阵B ，WINOGRAD 算法中整个

算法总的乘法次数是（(mnp/2)+mn/2+qn/2） 87. EULER 函数Ψ(23)的值为（22 ） 88. 下列哪一项不属于单向HASH 函数的应用范围（加密） 89. 第一台电子计算机产自（美国） 90. 序列(7，10，15，3，8，21，2)的逆序总数为（11 ） 91. 毋函数的实质是（把一个值域变换到另一值域） 92. 用基数排序法对下面数据进行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第0号桶的数据为（无数据） 93. 有助于编译器更好的发挥并行性的（硬件处理机） 94. 在BM 算法中，设模式P=“text”,则滑动距离函数dist[e]值为（2 ） 95. 计算机图灵的评选是（一年一评） 96. 对于非对称密码体制，每个当事人所需要的密钥数是（2 ） 97. 简单字符串匹配算法在最好情形下，进行的匹配比较操作次数为（(n-m+1) ） 98. 序列(1，7，10，15，13，21，28)经起泡排序所需的趟数为（2） 99. 算法分析方法主要有递归展开法和毋函数法。 100. 设模式串长为m ，正文串长为n ；则在最坏情况下，KMP 算法的时间复杂度为O(m+n)。 101. 在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码1，所需比较的次数是3。 102.单向的HASH 函数可应用于（数字签名）

102. 基于关键字比较的排序时间复杂度的下界是（O(n*log n) ） 103. 改进的KMP 算法比KMP 算法更加有效是因为模式中（重复出现的字符较多） 104. 用基数排序法对下面数据进行排序：312，290，180，653，358，

432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第1号桶的数据为（312 ） 105. 进程同步所需的时间，是由于进程是（异步并行执行的）

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

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

108. 计算机算法按数据类型可以分为两类，它们是数值运算和非数值运算。 111．在非对称多处理机系统中，可以被称为执行处理机的是（一个或一

组处理机具有执行能力） 109. 在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码21，所需比较的次数是2。 114.RSA 密码体制主要涉及的运算是（模运算） 115.不基于关键字比较的排序是（基数排序） 116.

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

117. 用基数排序法对下面数据进行排序：312，290，180，653，358，

432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第3号桶的数据为（432 ） 118. 粒度问题的求解既要考虑并行程序中颗粒的数目还要考虑（颗粒

的大小）

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

（3 ）

120. 设模式Pattern=”aabaaaa”，利用改进的KMP 算法计算出的

newnext(6)值为（3 ）

121. 在多处理机系统上，可以保持也可以不保持程序的状态，这取决

于（存储器模型）

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

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

124. 算法设计方法主要有分治法、回溯法、贪心法、动态规划法、分

支界限法。

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

压缩法。

126．模式置换压缩多用哪类情况（多次重复出现的信息） 127.分治法常伴随着（递归）

128. ASCII 码压缩法对纯数据文本的压缩率量为（62.5%） 129.设S={x| x ∈{1,2,…,20} 且 x 是合数}，则︱S ︱＝（12 ） 130. 在指令级或循环级上借助于并行化或向量化编译器来开发的是（细粒度并行性）

131．

设S={x| x ∈{1,2,…,200} 且x 是偶数}，则︱S ︱＝（100 ） 132． EULER 函数Ψ(9)的值为（6 ）

133．

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

134． 在线性表大部分元素已经有序的情况下，排序效率较高的算法是

（冒泡排序 ）

135． 在BM 算法中，设模式P=“pattern ern ”,则滑动距离函数dist[p]值

为（9）

136． 设a=23×521×75，b=212×32×54×7×113；则gcd(a,b)=（23×54

*7） 137． 设模式Pattern=”aabaaaa”，利用改进的KMP 算法计算出的

newnext(3)值为（2 ）

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

139． 设模式Pattern=”aabaaaa”，利用改进的KMP 算法计算出的

newnext(6)值为（3）

140． 递归方程T(1)=1，T(n)=2T(n)+1 ( n>1) 的解为T(n)=O(2n )。 141． 异步并行算法是指各进程之间相互（无需等待）

142． 基数排序的时间既与待排序数据的个数又与数据的位数及数据

的基有关。

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

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

146． 设数据的基为m ，用基数排序对n 个数据进行排序。则第一遍基数

排序所需的时间为（O(n+m)）

147． 在BM 算法中，设模式P=“pattern”,则滑动距离函数dist[p]值

为（6 ）.

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

149． ASCII 码压缩法对纯数据文本的压缩率量为（62.5% ） 150． 超立方连接机器是一个具有（2k 个结点的网络）

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

152． “不论初始状态和第一步的判定是什么，其他余下的判定必须相

对于前一次判定所产生的新状态构成一个最优序列“，是动态规划法依据的（最优性原理）。

153． 在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，

用二分法查找关键码12，所需比较的次数是4 。

154． 基数排序的时间既与待排序数据的个数又与数据的位数及数据

的基有关。

156. 对算法的分析不能脱离的有（技术人员，分析工具） 157. 毋函数与其所对应的序列关系是（一对一的）

158.

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

158. 国际象棋骑士巡游算法是应用（回溯法） 159. 单向的HASH 函数可应用于（消息摘要）

160. 用基数排序法对下面数据进行排序：312，290，180，653，358，

432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的数据收集起来，把收集好的数据再按第二位排序，依次放到0到9的各桶中，则第7号桶的数据为（无数据）

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

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

163. 在BM 算法中，设模式P=“text”,则滑动距离函数dist[x]值为（1） 164. 计算届的最高奖是图灵奖。

165. 在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，

用二分法查找关键码15，所需比较的次数是1 。

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

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

2

/1log +n ）

168.在最坏情形下分配分块排序的时间复杂性为（O(n*logn)） 169.基于关键字比较的排序时间复杂度的下界是（O(nlog 2

n)）

170.毋函数可以用来（解递归方程） 171.ASCII 码压缩法是基于（二极压缩）

180.求解递归函数就是（推出末函数显示公式的过程） 181.简单字符串匹配算法在最坏情形下，总共要执行字符的匹配比较操作次数为（(n-m+1)*m ）

182.序列(7，1，15，3，8，21，2)的元素个数为4的子集的个数为（35） 183.计算机的发明人是（冯.诺依曼）

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

185.KMP 串匹配算法对正文串的扫描方式是（自左至右无回溯） 186.为节省硬盘空间对存储信息进行的压缩是（全信息压缩） 189． 613

≡ 6 mod 13

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

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

192． 冒泡排序在最坏情形下得比较次数是 n 2 。 193．

311×720≡ 3 mod 11

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

195． 可以从不同的角度将并行算法分类，如数值并行算法和非数值并行算法；同步 并行算法和异步并行算法；SIMD 、MIMD 、VLSI 并行算法。 196． 所谓硬件并行性是指 计算机体系结构 和硬件多样性所决定的并行性。

197．

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

198．

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

199．

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

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

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

202．

冒泡排序的最坏时间复杂度 O(n 2) ，平均时间复杂度是 O(n 2) 。 203． 常见的数据压缩方法主要有ASCII 码压缩法、模式置换压缩法 、 LZ 压缩法 。

204．

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

1

log +n 。

205． 并行算法的 可伸缩性问题 对于网络并行计算环境显得尤为重要。 206． 时间复杂性 达到下界的算法称为最优算法。 207．

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

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

209． 设模式串长为m ，待搜索串长为n ；则在最坏情况下，KMP 算法的时间复杂度为

O(m+n) 。

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

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

1． 程序填空：下面是一个判定素数的程序，请将程序补全 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(

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

flag=0（2分）

2.用于数字签名和信息认证技术的HASH 函数必须满足那些条件： 答：不可逆性；计算简单；冲突概率小；高度敏感性；

3.在公共总线互联SMP 系统中，单总线SMP 系统具有哪些优点？ 答：成本低，容易实现。

扩展性能好

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

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

答：在理论上它突破了矩阵乘法的O （n 3

）时间界限以及其他诸如矩阵求逆、计算行列式和解联立线性方程组等问题带来的O （n 3）时间计算的开销

6.并行处理的四个级别： 答：作业或程序级的并行。 任务或过程级的并行 指令之间级的并行

指令内部级的并行

7.试叙述设计BM 算法的主要考量： 答：主要考量是在模式匹配比较过程中，有很多情形是前面许多字符都匹配而最后若干个字符不匹配 8.数据压缩的经济价值：

答：节省存储空间，达到一定程度的保密的目的。 大大减少信息在网络上传输的时间 9.并行算法的代价定义：

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

10.程序如下：

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.

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

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

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

第1页下一页