吉林大學自考算法設計與分析報告01345復習資料

1、文檔算法設計與分析-01345-19日上-新資料1. n+n*log 10n2 =( (n*log n 2)2. 設S=x| x珂1,2,20且x是素數(shù)，則丨S|=( 8 )3. 對算法的分析必須脫離具體的(計算機結(jié)構(gòu)和程序設計語言)4. 如果f(n)和g(n)都是單調(diào)遞增的，則f(n)+g(n)(單調(diào)遞增)5. Log(n!) =( (n*ln n)6. 可以用來求最優(yōu)解的是最優(yōu)解分支界限法常用于求(分支界限法)7. 設 S=x| x 乏1,2,30且 x 是素數(shù)，貝,S|=( 10)8. 設 S=x| x - 1,2, - ,200,201 且 x 是奇數(shù)，貝,S |=( 101)9. E

2、ULEF函數(shù)(74)的值為(343)10. 屬于分配排序技術的是(基數(shù)排序)11. 用基數(shù)排序法對下面數(shù)據(jù)進行排序：312, 290, 180, 653, 358, 432, 865, 264, 451,526, 239;首先按照第一位的大小依次放到 0到9的桶中，把各桶中的數(shù)據(jù)收集起來，把收集好的數(shù)據(jù)再按第二位排序，依次放到0到9的各桶中，則第6號桶的數(shù)據(jù)為(865 )12. 如果f(n)和g(n)都是加法非負的增函數(shù)，則f(n)g(n)(單調(diào)遞增)13. 設D是輸入的集合，N(l)是L D出現(xiàn)的概率，M(l)是算法在輸入I時執(zhí)行的次數(shù)。 則算法的最壞情形復雜性為(Max(M(I) (I D

3、)14. 同步并行算法是指某些進程(必須等待)別的進程的一類并行算法。15. 用基數(shù)排序法對下面數(shù)據(jù)進行排序：312, 290, 180, 653, 358, 432, 865, 264,451, 526, 239;首先按照最高位的大小依次放到 0到9的桶中，把各桶中的數(shù)據(jù)收集起 來，把收集好的數(shù)據(jù)再按第二位排序，依次放到 0到9的各桶中，則第2號桶的數(shù)據(jù)為(526)16. 算法設計方法主要有分治法、回溯法、貪心法、動態(tài)規(guī)劃法、分支界限法。17. 數(shù)據(jù)壓縮是指用較少的信息表示原有較多的信息，已達到節(jié)省存儲空間的目的。18. 是指在同一時間間隔內(nèi)增加操作數(shù)量的技術是（并行處理技術）。19. 序列

4、 c（n,0） ,c（n,1）,c（n,n）對應的毋函數(shù)是（1+x）n）20. 常用來支持細粒度和中粒度的并行計算是（共享變量通信）21. 同步并行算法是指某些進程必須等待別的進程的一類并行算法。22. 并行算法的加速比為求解相應問題的最快串行算法在最壞情況下的運行時間除以該并行算法在最壞情況下的求解該問題的運行時間。23. 由程序的控制和數(shù)據(jù)的相關性決定的是（軟件并行性）24. 對算法的分析必須脫離具體的（計算機結(jié)構(gòu)和程序設計語言）25. 求解有限期的作業(yè)調(diào)度問題一般應采用（貪心法）26. EULEF函數(shù)（21）的值為（18）27. 如果f（n）和g（n）都是單調(diào)遞減的，則g（g（n）（單調(diào)

5、遞減）28. 對于并行算法，除了研究所需的運行時間之外還需要研究算法所需（處理器的數(shù)目）29. 簡單字符串匹配算法在最壞情形下，總共要執(zhí)行字符的匹配比較操作次數(shù)為（n-m+1）*m）30. 序列（7 , 10, 5, 3, 8, 21, 2）的逆序總數(shù)為（12 ）31. 下列哪個屬性是單向的HASH函數(shù)不需要滿足的性質(zhì)（安全性）32. 用基數(shù)排序法對下面數(shù)據(jù)進行排序：312, 290, 180, 653, 358, 432, 865, 264, 451,526, 239;首先按照第一位的大小依次放到 0到9的桶中，把各桶中的數(shù)據(jù)收集起來， 把收集好的數(shù)據(jù)再按第二位排序，依次放到0到9的各桶中，

6、則第5號桶的數(shù)據(jù)為（451）33. 分支限界的本質(zhì)是（排他方法）34. 采用大整數(shù)相乘算法，計算2368X 3925所做的一位整數(shù)乘法的次數(shù)為（9）35. 在BM算法中，設模式P二“ pattern ” ,則滑動距離函數(shù)distn值為(7 )36. 設模式Pattern二” aabaaaa”，利用KMP算法計算出的next(7)值為(3 )37. 衡量算法的優(yōu)劣通常依據(jù)(平均和最壞時間開銷)38. 對于算法設計來說，遞歸是著名的分治策略。39. 函數(shù)f(n)=log n 和g(n)=log 3n這兩個函數(shù)階的關系是f(n)= & (g(n)。40在順序表(3, 6, 8, 10, 12, 15

7、, 16, 18, 21, 25, 30)中，用二分法查找關鍵碼10, 所需比較的次數(shù)是3。41. Branch and Bound的含義為(分支限界)42. 異步并行算法是指各進程之間無需相互等待的一類并行算法。43. 并行算法的復雜度主要考量兩方面，它們是運行時間和處理器數(shù)目。44. 設 S=x| x w1,2,10且 x 是素數(shù)，則丨 S |=( 4 )45. DES密碼體制是(非對稱密碼體制)46. 對于給定的序列，其毋函數(shù)(唯一確定)47. 如果f(n)和g(n)都是單調(diào)遞增的，則f(n)+2g(n)(單調(diào)遞增)48. EULEF函數(shù)(7)的值為(6 )49. 處理機的通信模型由所采

8、用的通信算法和(系統(tǒng)結(jié)構(gòu)決定)50序列 c(n,0) ,c(n,1),c(n,n-1)對應的毋函數(shù)是(1+x) n - x n)51 設 S=x| x w1,2,20且 x 是合數(shù)，貝,S |=( 12 )51. EULEF函數(shù)(8)的值為(4 )52. ASCII碼壓縮法對純數(shù)據(jù)文本的壓縮率量為(62.5% )53冒泡排序的方式是(數(shù)遍掃描數(shù)據(jù)序列)54對n個元素的線性表進行冒泡排序，最好情況下的時間復雜度為(O(n)55. 利用歸并方法可以實現(xiàn)(數(shù)據(jù)排序)56. RSA密碼體制的困難性是（大數(shù)分解）57. 在討論算法復雜性時必須加以考慮其（同步時間）58. 設模式Pattern二” aab

9、aaaa”，利用KMF算法計算出的next（5）值為（2）59. 通常用來衡量算法的優(yōu)劣的是（平均性態(tài)和最壞情形）60. 結(jié)合KMP算法思想改進后的BM算法速度較快，其不足是需要時間計算（delta函數(shù)）61. 算法分析方法主要有遞歸展開法和毋函數(shù)法。62. 設模式串長為m正文串長為n;則在最壞情況下，BM算法的時間復雜度為（mn）。63. 具有計算機復雜性的里程碑的時間段是（20世紀60年代）64采用大整數(shù)相乘算法，主要依據(jù)是（乘法開銷比加法大）65. 序列 c（n,0） ,c（n,1）,c（n,n）對應的毋函數(shù)是（1+x） n ）66. 并行算法運行的物質(zhì)基礎是（并行計算機體系結(jié)構(gòu)）67.

10、 數(shù)據(jù)壓縮是（可逆或不可逆的）68. 序列（17 , 10, 15, 3, 8, 21, 2）的逆序總數(shù)為（14 ）69. 對n個元素的線性表進行冒泡排序，平均時間復雜度為（0（n2）70. 計算機要充分發(fā)揮作用離不開（計算機軟件）71. 在BM算法中，設模式P二“ pattern ” ,則滑動距離函數(shù)dista值為（5）72. 設模式Pattern二” aabaaaa”，利用KMP算法計算出的next（3）值為（2 ）73. 在順序表（3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30）中，用二分法查找關鍵碼11, 所需比較的次數(shù)是（4 ）74. KMP算法是以下

11、面的人來命名的（Knuth-Morris-Pratt ）75. BM算法在最壞情形下的時間復雜度是（m*n）76. 使用大整數(shù)相乘算法計算兩個n位整數(shù)的乘積，所需的一位數(shù)乘法次數(shù)約為n1.59次77. 并行程序與串行程序有（明顯的差別）78. 設模式串長為m正文串長為n則在最壞情況下，BM算法的時間復雜度為（mn）。 79在順序表（3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30）中，用二分法查找關鍵碼 6, 所需比較的次數(shù)是4。80. 并行算法的復雜度主要考量兩方面，它們是運行時間和處理器數(shù)目。81. 瑞士的N.Wirth教授提出的著名公式是：算法 +數(shù)據(jù)結(jié)構(gòu)二

12、程序。82. 如果f（n）和g（n）都是單調(diào)遞減的，則f（g（f（n）（單調(diào)遞減）83分布式并行算法是指由通訊鏈路連接的多結(jié)點（計算機）并行完成某一計算任務的一 類并行算法。84對于一個m*n的矩陣A和一個n*q的矩陣B, WINOGRAD法中整個算法總的乘法次數(shù) 是（mnp/2）+mn/2+qn/2 ）85. EULERS數(shù)（23）的值為（22 ）86. 下列哪一項不屬于單向HASH數(shù)的應用范圍（加密）87. 第一臺電子計算機產(chǎn)自（美國）88. 序列（7 , 10, 15, 3, 8, 21, 2）的逆序總數(shù)為（11 ）89. 毋函數(shù)的實質(zhì)是（把一個值域變換到另一值域）90. 用基數(shù)排序法對

13、下面數(shù)據(jù)進行排序：312, 290, 180, 653, 358, 432, 865, 264, 451,526, 239;首先按照第一位的大小依次放到 0到9的桶中，把各桶中的數(shù)據(jù)收集起來， 把收集好的數(shù)據(jù)再按第二位排序，依次放到0到9的各桶中，則第0號桶的數(shù)據(jù)為（無數(shù)據(jù)）91. 有助于編譯器更好的發(fā)揮并行性的（硬件處理機）92. 在BM算法中，設模式P二“text ” ,則滑動距離函數(shù)diste值為（2 ）93. 計算機圖靈的評選是（一年一評）94. 對于非對稱密碼體制，每個當事人所需要的密鑰數(shù)是（2 ）95. 簡單字符串匹配算法在最好情形下，進行的匹配比較操作次數(shù)為（n-m+1）96.

14、序列（1，7，10，15，13, 21, 28）經(jīng)起泡排序所需的趟數(shù)為（2）97. 算法分析方法主要有遞歸展開法和毋函數(shù)法。98設模式串長為m正文串長為n;則在最壞情況下，KMP算法的時間復雜度為0（m+n）b99. 在順序表（3, 6, 8，10，12，15，16, 18, 21, 25, 30）中，用二分法查找關鍵碼 1, 所需比較的次數(shù)是3。100. 單向的HASH函數(shù)可應用于（數(shù)字簽名）101. 基于關鍵字比較的排序時間復雜度的下界是（0（n *log n）102. 改進的KMF算法比KMP算法更加有效是因為模式中（重復出現(xiàn)的字符較多）103. 用基數(shù)排序法對下面數(shù)據(jù)進行排序：312,

15、 290, 180, 653, 358, 432, 865, 264,451, 526, 239；首先按照第一位的大小依次放到 0到9的桶中，把各桶中的數(shù)據(jù)收集起來，把收集好的數(shù)據(jù)再按第二位排序，依次放到0到9的各桶中，則第1號桶的數(shù)據(jù)為（312）104. 進程同步所需的時間，是由于進程是（異步并行執(zhí)行的）105. 在BM算法中，設模式P二“ text ” ,則滑動距離函數(shù)distx值為（1）106. 設模式Pattern二” aabaaaa”，利用改進的KMP算法計算出的newnext值為（2 ）107. 計算機算法按數(shù)據(jù)類型可以分為兩類，它們是數(shù)值運算和非數(shù)值運算。108. 在非對稱多處理

16、機系統(tǒng)中，可以被稱為執(zhí)行處理機的是（一個或一組處理機具有執(zhí)行能力）109. 在順序表（3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30）中，用二分法查找關鍵碼21,所需比較的次數(shù)是2。110. RSA密碼體制主要涉及的運算是（模運算）111. 不基于關鍵字比較的排序是（基數(shù)排序）為了提高軟件和硬件的并行性的匹配程度，我們可以通過增加硬件并行性的靈活程度和開發(fā)控制密集程序的（軟件并行性）112. 用基數(shù)排序法對下面數(shù)據(jù)進行排序：312, 290, 180，653, 358, 432, 865, 264,451, 526, 239；首先按照第一位的大小依次放到 0到9

17、的桶中，把各桶中的數(shù)據(jù)收集起 來，把收集好的數(shù)據(jù)再按第二位排序，依次放到 0到9的各桶中，則第3號桶的數(shù)據(jù)為（432）113. 粒度問題的求解既要考慮并行程序中顆粒的數(shù)目還要考慮（顆粒的大?。?14. 在BM算法中，設模式P二“ text ” ,則滑動距離函數(shù)distt 值為（3）115. 設模式Pattern二” aabaaaa”，利用改進的KMP算法計算出的newnext（6）值為（3 ）116. 在多處理機系統(tǒng)上，可以保持也可以不保持程序的狀態(tài)，這取決于（存儲器模型）117. 回溯法屬于（窮舉方法）118. 時間復雜性達到下界的算法稱為最優(yōu)算法119. 算法設計方法主要有分治法、回溯法、

18、貪心法、動態(tài)規(guī)劃法、分支界限法。120. 常見的數(shù)據(jù)壓縮方法主要有 ASCII碼壓縮法、模式置換壓縮法LZ壓縮法。121. 模式置換壓縮多用哪類情況（多次重復出現(xiàn)的信息）122. 分治法常伴隨著（遞歸）123. ASCII碼壓縮法對純數(shù)據(jù)文本的壓縮率量為（62.5%124. 設 S=x| x 1,2,20且 x 是合數(shù)，貝,S|=（ 12 ）125. 在指令級或循環(huán)級上借助于并行化或向量化編譯器來開發(fā)的是（細粒度并行性）126. 設 S=x| x 亡1,2,200且 x 是偶數(shù)，貝,S |=（ 100 ）127. EULEF函數(shù)（9）的值為（6 ）128. 序列（1 , 3, 3, 3, 5,

19、 7, 22）的逆序總數(shù)為（0）130. 在線性表大部分元素已經(jīng)有序的情況下，排序效率較高的算法是（冒泡排序）131. 在BM算法中，設模式P二“ patternern ”，則滑動距離函數(shù)distp值為（9）132. 設 a=23x 521x 75, b=212x 32x 5* 7X 113；貝卩 gcd（a,b）二（23x 54*7 ）133. 設模式Pattern二” aabaaaa”，利用改進的KMP算法計算出的newnext（3）值為（2 ）134. 時間復雜性達到下界的算法稱為最優(yōu)算法。135. 設模式Pattern二” aabaaaa”，利用改進的KMP算法計算出的newnext（

20、6）值為（3）136. 遞歸方程 T（1）=1，T（n）=2T（n）+1 （ n1）的解為 T（n）=0（2）。137. 異步并行算法是指各進程之間相互（無需等待）138. 基數(shù)排序的時間既與待排序數(shù)據(jù)的個數(shù)又與數(shù)據(jù)的位數(shù)及數(shù)據(jù)的基有關。136. 中等粒度所包含的指令數(shù)一般（小于 2000條）137. 對大部分元素已經(jīng)有序的線性表排序需要最多時間的算法是（基數(shù)排序）138. 設數(shù)據(jù)的基為m用基數(shù)排序?qū)個數(shù)據(jù)進行排序。則第一遍基數(shù)排序所需的時間為（O（n+m）139. 在BM算法中，設模式P二“ pattern ” ,則滑動距離函數(shù)distp值為（6）.140. 二維網(wǎng)格結(jié)構(gòu)是一種常用的（并行

21、機）141. ASCII碼壓縮法對純數(shù)據(jù)文本的壓縮率量為（62. 5%）142. 超立方連接機器是一個具有（2k個結(jié)點的網(wǎng)絡）145. 算法的優(yōu)劣通常以平均和最壞兩種性態(tài)結(jié)果來衡量。146. “不論初始狀態(tài)和第一步的判定是什么，其他余下的判定必須相對于前一次判定所產(chǎn)生的新狀態(tài)構(gòu)成一個最優(yōu)序列“，是動態(tài)規(guī)劃法依據(jù)的（最優(yōu)性原理）。147. 在順序表（3，6，8，10，12，15，16，18，21, 25，30）中，用二分法查找關鍵碼12, 所需比較的次數(shù)是4。148. 基數(shù)排序的時間既與待排序數(shù)據(jù)的個數(shù)又與數(shù)據(jù)的位數(shù)及數(shù)據(jù)的基有關。149. 對算法的分析不能脫離的有（技術人員，分析工具）150.

22、 毋函數(shù)與其所對應的序列關系是（一對一的）151. 計算機的速度正比于其價格的（平方）152. 國際象棋騎士巡游算法是應用（回溯法）153. 單向的HASH函數(shù)可應用于（消息摘要）154. 用基數(shù)排序法對下面數(shù)據(jù)進行排序：312，290, 180，653，358, 432, 865, 264,451, 526, 239；首先按照第一位的大小依次放到 0到9的桶中，把各桶中的數(shù)據(jù)收集起 來，把收集好的數(shù)據(jù)再按第二位排序，依次放到 0到9的各桶中，則第7號桶的數(shù)據(jù)為（無數(shù)據(jù)）155. 一般而言，粒度越細（并行性程度越高）156. 算法設計方法主要有分治法、回溯法、貪心法、動態(tài)規(guī)劃法、分支界限法。1

23、57. 在BM算法中，設模式P二“ text ” ,則滑動距離函數(shù)distx值為（1）159. 計算屆的最高獎是圖靈獎。160. 在順序表（3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30）中，用二分法查找關鍵碼15,所需比較的次數(shù)是1。161. 基數(shù)排序的時間既與待排序數(shù)據(jù)的個數(shù)又與數(shù)據(jù)的位數(shù)及數(shù)據(jù)的基有關。162. 二分搜索算法對于有n個數(shù)據(jù)項的有序表L作的比較操作次數(shù)平均約為（Jog n 1/2）163. 在最壞情形下分配分塊排序的時間復雜性為（0（n*logn）164. 基于關鍵字比較的排序時間復雜度的下界是（0（nlog ?n）165. 毋函數(shù)可以用來（

24、解遞歸方程）166. .ASCII碼壓縮法是基于（二極壓縮）171. 求解遞歸函數(shù)就是（推出末函數(shù)顯示公式的過程）172. 簡單字符串匹配算法在最壞情形下，總共要執(zhí)行字符的匹配比較操作次數(shù)為(n-m+1)*m)173. 序列（7, 1, 15, 3, 8, 21, 2）的元素個數(shù)為4的子集的個數(shù)為（35）174. 計算機的發(fā)明人是（馮.諾依曼）175. 基數(shù)排序是（不基于關鍵字比較的排序）176. KMF串匹配算法對正文串的掃描方式是（自左至右無回溯）177. 為節(jié)省硬盤空間對存儲信息進行的壓縮是（全信息壓縮）13178.6 三 6 mod 13179ASCII碼壓縮法對純數(shù)據(jù)文本的壓縮率量為

25、62. 5%180計算機密碼系統(tǒng)主要分為對稱密碼體制和非對稱密碼體制兩種181冒泡排序在最壞情形下得比較次數(shù)是n11 20182.3 X 7 三 3 mod 11和邏輯并行性。183. 開發(fā)問題的并行性包括開發(fā)計算并行性 、搜索并行性184. 可以從不同的角度將并行算法分類，如數(shù)值并行算法和非數(shù)值并行算法；同步并行算法和異步并行算法；SIMD MIMD VLSI并行算法。185. 所謂硬件并行性是指計算機體系結(jié)構(gòu)和硬件多樣性所決定的并行性。186. 我們所構(gòu)造的漢字到整數(shù)的映射應當滿足：映射可逆性，有序性 ， 不可伸縮性，映射函數(shù)計算簡單性。187. 并行計算模型主要有SIMD互聯(lián)網(wǎng)絡模型，共

26、享存儲的SIMD模型，MIMD并行計算 模型。188. 對算法的分析必須脫離具體的計算機結(jié)構(gòu)和程序設計語言。189. 算法設計方法主要有分治法、回溯法、貪心法、動態(tài)規(guī)劃法、分支界限 。190. RSA公開密碼密鑰體制建立在素數(shù)理論和歐拉定理基礎上。191. 冒泡排序的最壞時間復雜度 0（n 2），平均時間復雜度是 0（n 2）。192. 常見的數(shù)據(jù)壓縮方法主要有 ASCII碼壓縮法、模式置換壓縮法、LZ壓縮法 。193. 在最壞情況下，對于具有n個數(shù)據(jù)項的有序表L,二分搜索算法將z與表中的數(shù)據(jù)項進行比較的次數(shù)是ogn 1 。194. 并行算法的 可伸縮性問題對于網(wǎng)絡并行計算環(huán)境顯得尤為重要。1

27、95. 時間復雜性達到下界的算法稱為最優(yōu)算法。196. 在并行算法設計的基本技術中，破對稱技術主要應用于圖論算法技術和隨機算法技術。197. HASH函數(shù)主要應用于數(shù)字簽名和信息認證技術。198. 設模式串長為m待搜索串長為n;則在最壞情況下，KMP算法的時間復雜度0(m+n)199. 簡述LZ壓縮算法的主要思想：答：待編碼(壓縮)得數(shù)據(jù)符號串可能在已經(jīng)編碼的信息結(jié)構(gòu)中，因此整個數(shù)據(jù)源在待 編碼的符號串上呈現(xiàn)冗余程序填空：下面是一個判定素數(shù)的程序，請將程序補全Beg inFlag=O;i=2;while( ) dobegi nif n mod i=0 the nflag=1;i=i+1;ife

28、nd;thenwriteln( n二，n,是素數(shù))elsewriteln（ n二,n,是合數(shù)）En d.答：flag=0 and i=i nt（、n） （2 分） 或者 flag=0 and i=n-1;（2分）flag=0 （2 分）200用于數(shù)字簽名和信息認證技術的 HASH函數(shù)必須滿足那些條件：答：不可逆性；計算簡單；沖突概率??；高度敏感性；201. 在公共總線互聯(lián)SMP系統(tǒng)中，單總線SMP系統(tǒng)具有哪些優(yōu)點？答：成本低，容易實現(xiàn)。擴展性能好202. Flynn分類法，它按照指令流和數(shù)據(jù)流將計算機系統(tǒng)分為哪幾類？答：單指令單數(shù)據(jù)流計算機單指令多數(shù)據(jù)流計算機多指令單數(shù)據(jù)流計算機多指令多數(shù)據(jù)流

29、計算機203. .STRASSEI算法的主要意義是：答：在理論上它突破了矩陣乘法的 O（n3）時間界限以及其他諸如矩陣求逆、計算行列式和解聯(lián)立線性方程組等問題帶來的 O（ n3）時間計算的開銷204. 并行處理的四個級別：答：作業(yè)或程序級的并行。任務或過程級的并行指令之間級的并行 指令內(nèi)部級的并行205. 試敘述設計BM算法的主要考量:答：主要考量是在模式匹配比較過程中，有很多情形是前面許多字符都匹配而最后若干 個字符不匹配206. 數(shù)據(jù)壓縮的經(jīng)濟價值：答：節(jié)省存儲空間，達到一定程度的保密的目的。207.大大減少信息在網(wǎng)絡上傳輸?shù)臅r間208. 并行算法的代價定義：答：并行算法所需的時間和所需的

30、處理器數(shù)目的乘積。209. 程序如下：Beg ini=1;while (i 二n-m+1) dobeg inj=1;while (jm the nwrite In ( Matched, begi ns in positi on: ,i);i=i+1;end;En d.問題：該程序描述了哪種算法？ 答：該程序描述的算法是：簡單的字符串匹配算法210. 基于映射的字符串排序的影射函數(shù)的約束條件答：映射可逆性；有序性(2分)；不可伸縮性(1分)；映射函數(shù)計算的簡單性(1 分)211. “大事化小，小事化了”概括了什么算法設計技術(方法)？分治法212. 分治法：將問題分解為若干個子問題，然后解出這些

31、子問題，最后用某種方法將這些子問題的解 組合成原問題的解。213.列舉出一些字符串匹配算法：答：KMF串匹配算法，BM串匹配算法，KR串匹配算法214. 在公共總線互聯(lián)SMP系統(tǒng)系統(tǒng)中，單SMR總線系統(tǒng)的缺點：答：因為多處理機和其他設備共用一條總線，所以在任一時刻只有一個處理機能夠發(fā)送 信息，故系統(tǒng)效率較低215. 遞歸是由那些部分構(gòu)成的？邊界條件；遞推公式；216. 函數(shù)f(n)是T(n)的上界意味著：存在常數(shù)c0與n。，當nn。時，恒有T(n)遼cf(n)。217. 模式置換壓縮方法：答：是對多次重復的信息構(gòu)造一個模式表，然后根據(jù)此模式表作模式置換來實現(xiàn)數(shù)據(jù)壓 縮。218. 函數(shù)f(n)是

32、T(n)的下界意味著：答：存在常數(shù)c0與n。，當nno時，恒有T(n)cf(n)。219. 試介紹動態(tài)規(guī)劃法的基本思想。答：在每一個判定步上，列出各種可能的局部解，然后按某些條件，舍棄那些肯定不能 得到最優(yōu)解的局部解，經(jīng)過每一步這樣的篩選之后，可以大大減少工作量。220. 歐拉函數(shù)(n)的定義為：(n)=1,2,n中與n互素的數(shù)的個數(shù)221. 寫出用篩法判斷79是否為素數(shù)的步驟：解：求出n= 79=8;有選擇地用2, 3,，8對79進行試除：由于2不整除79,所以4, 6, 8不用再判斷；由于3不整除79,所以6不用再判斷；5不整除79;7不整除79;所以79是素數(shù)；222. 寫出用篩法判斷8

33、3是否為素數(shù)的步驟：解：求出n83=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

34、元；225.已知x=3467,y=4298,取基為10,采用大整數(shù)相乘算法，求解 x*y解：令 x0=67,x1=34 ; y0=98,y1=42 ;則 x0*y0=67*98=6566 x1* y仁34*42=1428(xO-x1)*(y1-yO)+xO*yO+x1* y仁(67-34)*(42-98)+ 67*98+34*42 = -1848 + 6566 + 1428=6146所以 x*y = 6566+6146*10*10+1428*10*10*10*10 設模式P=aabaaaa求改進的KMP算法計算出的nextj和newnextj函數(shù)值。 解：j =1 2

35、 3 4 5 6 7Nextj = 0 1 2 1 2 3 3New nextj = 0 0 2 0 0 3 2227. 解遞歸方程：T (1)=1 ; T(n)=4T(訃(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 (n1)解：對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+2 2+2n-2)= (1+2+2 2+2n-1)=2n-1 ;2

36、29. 用大整數(shù)乘法計算1245*2436;解：設 x=12*102+45; y=24*102+36;則 xy=12*24*10+(12*36+45*24)*10 2+45*36;同理，對于 12*24,設 x=1*10+2; y=2*10+4;貝S xy=1*2*10 2+(1*4+2*2)*10+2*4=288 ;如此下去，最終可得 1245*2436=3032820.230. 請用分治法設計算法：在一個數(shù)組A仁n中(n二2k),同時尋找最大值和最小值請給出你的算法。解：算法如下：min_max(low,high)if high-low=1 the nif Alow1)解：對T(n)展開，

37、得：n1n1T(n )=7T( n-1)=7(7T( n-2)=7(7(7T( n-3)=7T(1)=7的排序過程235. 寫出用冒泡排序法對序列 X=(65,45,23,12,19,18,7,13,44,10)解：1. 第一趟比較并交換后的結(jié)果為：(7.65.45.23.12.19.18.10.13.44)2. 第二趟比較并交換后的結(jié)果為：(7.10.65.45.23.12.19.18.13.44)3. 第三趟比較并交換后的結(jié)果為：(7.10.12.65.45.23.13.19.18.44)4. 第四趟比較并交換后的結(jié)果為：(7.10.12.13.65.45.23.18.19.44)5. 第

38、五趟比較并交換后的結(jié)果為：(7.10.12.13.18.65.45.23.19.44)6. 第六趟比較并交換后的結(jié)果為：(7.10.12.13.18.19.65.45.23.44)7. 第七趟比較并交換后的結(jié)果為：(7,10,12,13,18,19,23,65,45,44)236. 寫出用冒泡排序法對序列 X=(865,451,239,12,192,180,7,123,44,100) 的排序過程: 解：1. 第一趟比較并交換后的結(jié)果為：(7,865,451,239,12,192,180,44,123,100)2. 第二趟比較并交換后的結(jié)果為：(7.12.865.451.239.44.192.1

39、80.100.123)3. 第三趟比較并交換后的結(jié)果為：(7.12.44.865.451.239.100.192.180.123)4. 第四趟比較并交換后的結(jié)果為：(7,12,44,100,865,451,239,123,192,180)5. 第五趟比較并交換后的結(jié)果為：(7.12.44.100.123.865.451.239.180.192)6. 第六趟比較并交換后的結(jié)果為：(7.12.44.100.123.180.865.451.239.192)7. 第七趟比較并交換后的結(jié)果為：(7,12,44,100,123,180,192,865,451,239)8. 第八趟比較并交換后的結(jié)果為：(7

40、,12,44,100,123,180,192,239,865,451)9. 第九趟比較并交換后的結(jié)果為：(7,12,44,100,123,180,192,239,451,865)排序結(jié)束。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 ；且a1)解：對T(

41、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+2 2+2n-2)= (1+2+2 2+2n-1)=2n-1 ；240. 用大整數(shù)乘法計算1245*2436；解：設 x=12*102+45;y=24*102+36;則 xy=12*24*104+(12*36+45*24)*10 2+45*36；同理，對于 12*24,設 x=1*10+2; y=2*10+4;貝S xy=1*2*10 2+(1*4+2*2)*10+2*4=288 ； 如此下去，最終可得 1245*2436=3032820.241. 設數(shù)據(jù)序列 X二3.5, 7.0 , 4.3 , 5.0 , 10.0 , 4.0 , 6.0 , 4.8 , 8.0 , 1.0，寫出用分配分塊排序算法對其進行排序的過程：解：步