算法設計與分析--01345--19日上-復習資料一、填空1.解遞歸方程可利用（毋函數法） 2.設S={x|x{1,2,…,20}且x是素數}，則︱S︱＝（8）3.對算法的分析必須脫離具體的（計算機結構和程序設計語言）4.如果f(n)和g(n)都是單調遞增的，則f(n)+g(n)（單調遞增）5.EULER函數Ψ(17)的值為（16）6.設S={x|x?{1,2,…,10}且x是合數}，則︱S︱＝（6）7.如果f(n)和g(n)都是單調遞增的，則f(2g(n))（單調遞增）8.EULER函數Ψ(16)的值為（8）9.序列(7，10，15，3，18，21，2)的逆序總數為（9）10.屬于分配排序技術的是（基數排序）11.用基數排序法對下面數據進行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的數據收集起來，把收集好的數據再按第二位排序，依次放到0到9的各桶中，則第6號桶的數據為（865）12.在BM算法中，設模式P=“pattern”,則滑動距離函數dist[e]值為（2）13.設模式Pattern=”aabaaaa”，利用KMP算法計算出的next(6)值為（3）14.同步并行算法是指某些進程（必須等待）別的進程的一類并行算法。15.在最壞情況下，分配分塊排序的復雜性為（O(nlogn)）16.算法設計方法主要有分治法、回溯法、貪心法、動態規劃法、分支界限法。17.數據壓縮是指用較少的信息表示原有較多的信息，已達到節省存儲空間的目的。18.字符串模式匹配操作是字符串所有運算的基礎。19.在順序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找關鍵碼11，所需比較的次數是4。20. 可以從不同的角度將并行算法分類，如數值并行算法和非數值并行算法；同步并行算法和異步并行算法；SIMD、MIMD并行算法；VLSI并行算法。21.同步并行算法是指某些進程必須等待別的進程的一類并行算法。22.并行算法的加速比為求解相應問題的最快串行算法在最壞情況下的運行時間除以該并行算法在最壞情況下的求解該問題的運行時間。23.圖的深度優先遍歷一般應采用（回溯法）24.對算法的分析必須脫離具體的（計算機結構和程序設計語言）25.廣泛應用于數據安全與加密領域的算法是（大整數相乘算法）26.EULER函數Ψ(21)的值為（18）27.如果f(n)和g(n)都是單調遞減的，則g(g(n))（單調遞減）28.設S={x|x{1,2,…,10}且x是素數}，則︱S︱＝（4 ）29.簡單字符串匹配算法在最壞情形下，總共要執行字符的匹配比較操作次數為（(n-m+1)*m）30.序列(7，10，5，3，8，21，2)的逆序總數為（12）31.不屬于分配排序技術的是（冒泡排序）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. Flynn分類法將并行計算機分為（4）類。38.對于算法設計來說，遞歸是著名的分治策略。39.函數f(n)=logn和g(n)=log3n這兩個函數階的關系是f(n)=Θ(g(n))。40.在順序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找關鍵碼10，所需比較的次數是3。41.并行計算機上的分類主要有兩類方法：Flynn分類法和Handler分類法。42.異步并行算法是指各進程之間無需相互等待的一類并行算法。43.并行算法的復雜度主要考量兩方面，它們是運行時間和處理器數目。44.設S={x|x{1,2,…,10}且x是素數}，則︱S︱＝（4）45.分支界限法常用于求（最優解）46.對于給定的序列，其毋函數（唯一確定）47.如果f(n)和g(n)都是單調遞增的，則f(n)+2g(n)（單調遞增）48.EULER函數Ψ(7)的值為（6）49.EULER函數Ψ(19)的值為（18）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）52.EULER函數Ψ(8)的值為（4）53.ASCII碼壓縮法對純數據文本的壓縮率量為（62.5%）54.序列(7，10，3，3，8，21，2)的逆序總數為（11）55.對n個元素的線性表進行冒泡排序，最好情況下的時間復雜度為（O(n)）56.用基數排序法對下面數據進行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的數據收集起來，把收集好的數據再按第二位排序，依次放到0到9的各桶中，則第2號桶的數據為（526）57.分配和歸并混合排序算法在最壞情形下的時間復雜性為（O(n*logn)）58.在BM算法中，設模式P=“abcdae”,則滑動距離函數dist[a]值為（1）59.設模式Pattern=”aabaaaa”，利用KMP算法計算出的next(5)值為（2）60.Strassen方法的思想是將相乘的A、B矩陣分成（4）個矩陣塊。61.結合KMP算法思想改進后的BM算法速度較快，其不足是需要時間計算（delta函數）62.算法分析方法主要有遞歸展開法和毋函數法。63.設模式串長為m，正文串長為n；則在最壞情況下，BM算法的時間復雜度為Θ(mn)。64.在順序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找關鍵碼30，所需比較的次數是4。65.設S={x|x{1,2,…,200}且x是偶數}，則︱S︱＝（100）66.序列c(n,0),c(n,1),…,c(n,n)對應的毋函數是（(1+x)n）67.EULER函數Ψ(18)的值為（6）68.數據壓縮是（可逆或不可逆的）69.序列(17，10，15，3，8，21，2)的逆序總數為（14）70.對n個元素的線性表進行冒泡排序，平均時間復雜度為（O(n2)）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.設模式串長為m，正文串長為n；1970年，S.A.Cook在理論上證明了字符串模式匹配問題可在時間（O(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.可以從不同的角度將并行算法分類，如數值并行算法和非數值并行算法；同步并行算法和異步并行算法；SIMD、MIMD、VLSI并行算法。83.分布式并行算法是指由通訊鏈路連接的多結點（計算機）并行完成某一計算任務的一類并行算法。84.序列c(n,1),c(n,2),…,c(n,n)對應的毋函數是（(1+x)n–1）85. EULER函數Ψ(23)的值為（22）86.下列哪一項不屬于單向HASH函數的應用范圍（加密）87.設S={x|x{1,2,…,20}且x是素數}，則︱S︱＝（8）88.序列(7，10，15，3，8，21，2)的逆序總數為（11）89.對n個元素的線性表進行冒泡排序，最壞情況下的時間復雜度為（O(n2)）90.BM算法對待搜索串的掃描方式是（自右至左無回溯）91.在BM算法中，設模式P=“text”,則滑動距離函數dist[e]值為（2）92.設模式Pattern=”aabaaaa”，利用改進的KMP算法計算出的newnext(4)值為（0）93. 對于非對稱密碼體制，每個當事人所需要的密鑰數是（2）94.簡單字符串匹配算法在最好情形下，進行的匹配比較操作次數為（(n-m+1)）95.計算機算法按數據類型可以分為兩類，它們是數值運算和非數值運算96.算法分析方法主要有遞歸展開法和毋函數法。97.設模式串長為m，正文串長為n；則在最壞情況下，KMP算法的時間復雜度為O(m+n)。98.在順序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找關鍵碼1，所需比較的次數是3。99. 單向的HASH函數可應用于（數字簽名）單向的HASH函數可應用于（消息摘要）100.設S={x|x{1,2,…,10}且x是合數}，則︱S︱＝（6）101.基于關鍵字比較的排序時間復雜度的下界是（O(n*logn)）102.序列(7，1，15，3，8，21，2)的逆序總數為（9103.用基數排序法對下面數據進行排序：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.改進的冒泡法對n個數據進行排序，在最壞的情況下，該算法所需的數據比較次數為n(n-1)/2。110.設模式串長為m，待搜索串長為n；則在最壞情況下，KMP算法的時間復雜度為O(m+n)。111.在順序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找關鍵碼21，所需比較的次數是2。112.RSA密碼體制主要涉及的運算是（模運算）113.不基于關鍵字比較的排序是（基數排序）114.序列(7，10，15，3，8，1，2)的逆序總數為（15）115.用基數排序法對下面數據進行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的數據收集起來，把收集好的數據再按第二位排序，依次放到0到9的各桶中，則第3號桶的數據為（432）116.KMP算法對待搜索串的掃描方式是（自左至右無回溯）117.在BM算法中，設模式P=“text”,則滑動距離函數dist[t]值為（3）118.設模式Pattern=”aabaaaa”，利用改進的KMP算法計算出的newnext(6)值為（3）119.基數排序屬于（分配排序）120.回溯法屬于（窮舉方法）121.時間復雜性達到下界的算法稱為最優算法122.算法設計方法主要有分治法、回溯法、貪心法、動態規劃法、分支界限法。123.常見的數據壓縮方法主要有ASCII碼壓縮法、模式置換壓縮法LZ壓縮法。124.在順序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找關鍵碼8，所需比較的次數是2。125.分治法常伴隨著（遞歸）126.解遞歸方程可利用（遞歸展開法）127.設S={x|x{1,2,…,20}且x是合數}，則︱S︱＝（12）128.ASCII碼壓縮法是基于（二極壓縮）129.設S={x|x{1,2,…,200}且x是偶數}，則︱S︱＝（100）130.EULER函數Ψ(9)的值為（6）131.求解最短路徑問題一般應采用（動態規劃）132.RSA密碼體制要用到（兩個大素數）133.在線性表大部分元素已經有序的情況下，排序效率較高的算法是（冒泡排序）134.用基數排序法對下面數據進行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的數據收集起來，把收集好的數據再按第二位排序，依次放到0到9的各桶中，則第9號桶的數據為（290）135.在BM算法中，設模式P=“pattern”,則滑動距離函數dist[r]值為（1）136.設模式Pattern=”aabaaaa”，利用改進的KMP算法計算出的newnext(3)值為（2）137.時間復雜性達到下界的算法稱為最優算法。138.算法設計方法主要有分治法、回溯法、貪心法、動態規劃法、分支界限法。139.遞歸方程T(1)=1，T(n)=2T(n)+1(n>1)的解為T(n)=O(2n)。140.在順序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找關鍵碼25，所需比較的次數是3。141.基數排序的時間既與待排序數據的個數又與數據的位數及數據的基有關。142.序列(7，10，15，13，8，21，2)的逆序總數為（10）143.對大部分元素已經有序的線性表排序需要最多時間的算法是（基數排序）144.用基數排序法對下面數據進行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的數據收集起來，把收集好的數據再按第二位排序，依次放到0到9的各桶中，則第8號桶的數據為（180）145.在BM算法中，設模式P=“pattern”,則滑動距離函數dist[p]值為（6）.146.設模式Pattern=”aabaaaa”，利用改進的KMP算法計算出的newnext(5)值為（0）147.ASCII碼壓縮法對純數據文本的壓縮率量為（62.5%）148.序列c(n,0),c(n,1),…,c(n,n)對應的毋函數是（(1+x)n）149.算法的優劣通常以平均和最壞兩種性態結果來衡量。150.遞歸方程T(1)=1，T(n)=4T(n/2)+n(n>1)的解為T(n)=O(n2)。151.在順序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找關鍵碼12，所需比較的次數是4。152.基數排序的時間既與待排序數據的個數又與數據的位數及數據的基有關。153.RSA密碼體制的困難性是基于（大整數分解）154.LZ數據壓縮算法是基于（字符串匹配）155.ASCII碼壓縮法對純數據文本的壓縮率量為（62.5%）156.序列(7，10，15，3，8，21，22)的逆序總數為（5）157.使用冒泡排序對線性表排序，需要最多時間的線性表是（逆序）158.用基數排序法對下面數據進行排序：312，290，180，653，358，432，865，264，451，526，239；首先按照第一位的大小依次放到0到9的桶中，把各桶中的數據收集起來，把收集好的數據再按第二位排序，依次放到0到9的各桶中，則第7號桶的數據為（無數據）159.異步并行算法是指各進程之間相互（無需等待）160.算法設計方法主要有分治法、回溯法、貪心法、動態規劃法、分支界限法。161.基于關鍵字比較的排序算法的時間復雜性的下界為（O(n*logn)）。162.計算屆的最高獎是圖靈獎。163.在順序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找關鍵碼15，所需比較的次數是1。164.基數排序的時間既與待排序數據的個數又與數據的位數及數據的基有關。165.“大事化小，小事化了”概括了什么算法設計技術（方法）？166.設S={x|x{1,2,…,30}且x是素數}，則︱S︱＝（10）167.設S={x|x{1,2,…,200,201}且x是奇數}，則︱S︱＝（101）168.EULER函數Ψ(74)的值為（343）169.設D是輸入的集合，N(I)是ID出現的概率，M(I)是算法在輸入I時執行的次數。則算法的最壞情形復雜性為（Max(M(I))(ID)）毋函數與其所對應的序列關系是（一對一的）170.一般而言，粒度越細（并行性程度越高）171.求解有限期的作業調度問題一般應采用（貪心法）172.可以用來求最優解的是最優解分支界限法常用于求（分支界限法）173.常用來支持細粒度和中粒度的并行計算是（共享變量通信）174.由程序的控制和數據的相關性決定的是（軟件并行性）175.對于并行算法，除了研究所需的運行時間之外還需要研究算法所需（處理器的數目）176.下列哪個屬性是單向的HASH函數不需要滿足的性質（安全性）177.分支限界的本質是（排他方法）178.BranchandBound的含義為（分支限界）179.DES密碼體制是（非對稱密碼體制）180.處理機的通信模型由所采用的通信算法和（系統結構決定）181.冒泡排序的方式是（數遍掃描數據序列）182.利用歸并方法可以實現（數據排序）183.RSA密碼體制的困難性是（大數分解）184.在討論算法復雜性時必須加以考慮其（同步時間）185.具有計算機復雜性的里程碑的時間段是（20世紀60年代）186.采用大整數相乘算法，主要依據是（乘法開銷比加法大）187.并行算法運行的物質基礎是（并行計算機體系結構）188.計算機要充分發揮作用離不開（計算機軟件）189.n+n*log10n2=（Θ(n*logn2)）190.Log(n!)=（Θ(n*lnn)）191.并行程序與串行程序有（明顯的差別）192.如果f(n)和g(n)都是單調遞減的，則f(g(f(n)))（單調遞減）193.對于一個m*n的矩陣A和一個n*q的矩陣B，WINOGRAD算法中整個算法總的乘法次數是（(mnp/2)+mn/2+qn/2）194.第一臺電子計算機產自（美國）195.毋函數的實質是（把一個值域變換到另一值域）196.有助于編譯器更好的發揮并行性的（硬件處理機）197.計算機圖靈的評選是（一年一評）198.序列(1，7，10，15，13，21，28)經起泡排序所需的趟數為（2）199.改進的KMP算法比KMP算法更加有效是因為模式中（重復出現的字符較多）200.進程同步所需的時間，是由于進程是（異步并行執行的）201.在非對稱多處理機系統中，可以被稱為執行處理機的是（一個或一組處理機具有執行能力）202.為了提高軟件和硬件的并行性的匹配程度，我們可以通過增加硬件并行性的靈活程度和開發控制密集程序的（軟件并行性）203.在多處理機系統上，可以保持也可以不保持程序的狀態，這取決于（存儲器模型）204.粒度問題的求解既要考慮并行程序中顆粒的數目還要考慮（顆粒的大小）205.模式置換壓縮多用哪類情況（多次重復出現的信息）206.在指令級或循環級上借助于并行化或向量化編譯器來開發的是（細粒度并行性）207.序列(1，3，3，3，5，7，22)的逆序總數為（0）208.在BM算法中，設模式P=“patternern”,則滑動距離函數dist[p]值為（9）209.設a=23×521×75，b=212×32×54×7×113；則gcd(a,b)=（23×54*7）210.基數排序的時間既與待排序數據的個數又與數據的位數及數據的基有關。211.中等粒度所包含的指令數一般（小于2000條）212.對大部分元素已經有序的線性表排序需要最多時間的算法是（基數排序）213.設數據的基為m，用基數排序對n個數據進行排序。則第一遍基數排序所需的時間為（O(n+m)）214.二維網格結構是一種常用的（并行機）215.超立方連接機器是一個具有（2k個結點的網絡）216.“不論初始狀態和第一步的判定是什么，其他余下的判定必須相對于前一次判定所產生的新狀態構成一個最優序列“，是動態規劃法依據的（最優性原理）217.對算法的分析不能脫離的有（技術人員，分析工具）218.計算機的速度正比于其價格的（平方）219.國際象棋騎士巡游算法是應用（回溯法）220.基數排序的時間既與待排序數據的個數又與數據的位數及數據的基有關。221.二分搜索算法對于有n個數據項的有序表L作的比較操作次數平均約為（）222.毋函數可以用來（解遞歸方程）223.求解遞歸函數就是（推出末函數顯示公式的過程）224.序列(7，1，15，3，8，21，2)的元素個數為4的子集的個數為（35）225.計算機的發明人是（馮.諾依曼）226.為節省硬盤空間對存儲信息進行的壓縮是（全信息壓縮）227.613≡6mod13228.計算機密碼系統主要分為對稱密碼體制和非對稱密碼體制兩種。229.冒泡排序在最壞情形下得比較次數是n2。230.311×720≡3mod11231.開發問題的并行性包括開發計算并行性、搜索并行性和邏輯并行性。232.所謂硬件并行性是指計算機體系結構和硬件多樣性所決定的并行性。233.我們所構造的漢字到整數的映射應當滿足：映射可逆性，有序性，不可伸縮性，映射函數計算簡單性。234.并行計算模型主要有SIMD互聯網絡模型，共享存儲的SIMD模型，MIMD并行計算模型。235.RSA公開密碼密鑰體制建立在素數理論和歐拉定理基礎上。236.冒泡排序的最壞時間復雜度O(n2)，平均時間復雜度是O(n2)。237.在最壞情況下，對于具有n個數據項的有序表L，二分搜索算法將z與表中的數據項進行比的次數是。238.并行算法的可伸縮性問題對于網絡并行計算環境顯得尤為重要。239.在并行算法設計的基本技術中，破對稱技術主要應用于圖論算法技術和隨機算法技術。240.HASH函數主要應用于數字簽名和信息認證技術。241.簡述LZ壓縮算法的主要思想：答：待編碼（壓縮）得數據符號串可能在已經編碼的信息結構中，因此整個數據源在待編碼的符號串上呈現冗余242.用于數字簽名和信息認證技術的HASH函數必須滿足那些條件：答：不可逆性；計算簡單；沖突概率小；高度敏感性；243.KMP算法是以下面的人來命名的（Knuth-Morris-Pratt）244.BM算法在最壞情形下的時間復雜度是（Θ(m*n)）245.基數排序的時間既與待排序數據的個數又與數據的位數及數據的基有關。二、名詞解釋1.分治法：將問題分解為若干個子問題，然后解出這些子問題，最后用某種方法將這些子問題的解組合成原問題的解。2.回朔法：是一種逐步試探以求出問題解的方法3.并行處理技術：是指在同一時間間隔內增加操作數量的技術。4.分布式并行算法：是指由通訊鏈路連接的多結點（計算機）并行完成某一計算任務的一類并行算法。5.異步并行算法：是指各進程之間無需相互等待的一類并行算法6.同步并行算法：是指某些進程必須等待別的進程的一類并行算法。7.并行計算機：是為并行處理所設計的計算機系統。8.并行算法的加速比：為求解相應問題的最快串行算法在最壞情況下的運行時間除以該并行算法在最壞情況下的求解該問題的運行時間9.分配排序：是通過散列的方法將數據分配定位到不同的組中，然后對每組排序并重新組合出來。10. 模式置換壓縮方法：是對多次重復的信息構造一個模式表，然后根據此模式表作模式置換來實現數據壓縮。11. 并行算法的代價：并行算法所需的時間和所需的處理器數目的乘積。三、簡答1.基于映射的字符串排序的影射函數的約束條件答：映射可逆性；有序性（2分）；不可伸縮性（1分）；映射函數計算的簡單性（1分）2.評價算法的優劣主要考慮哪些因素？主要考量平均復雜性和最壞情形下的復雜性。3.計算機程序與算法的區別：一步一步解問題的過程稱為算法；程序必須在指定的計算機上執行，而算法是抽象的，它凌駕于一切具體的計算機之上。4.KMP算法與簡單串匹配算法的最大區別是什么？無回溯；和預先計算next函數；5.試舉出兩例動態規劃法的具體應用答：求最短路徑算法；背包最優化問題；6.遞歸是由那些部分構成的？邊界條件；遞推公式；7.函數f(n)是T(n)的上界意味著：存在常數c>0與n0，當n>n0時，恒有T(n)cf(n)。8.函數f(n)是T(n)的下界意味著：答：存在常數c>0與n0，當n>n0時，恒有T(n)cf(n)。9.試介紹動態規劃法的基本思想。答：在每一個判定步上，列出各種可能的局部解，然后按某些條件，舍棄那些肯定不能得到最優解的局部解，經過每一步這樣的篩選之后，可以大大減少工作量。10. 歐拉函數Ψ(n)的定義為：Ψ(n)={1,2,…,n}中與n互素的數的個數11. 在公共總線互聯SMP系統中，單總線SMP系統具有哪些優點？答：成本低，容易實現。擴展性能好12. 在公共總線互聯SMP系統系統中，單SMP總線系統的缺點：答：因為多處理機和其他設備共用一條總線，所以在任一時刻只有一個處理機能夠發送信息，故系統效率較低13. .Flynn分類法，它按照指令流和數據流將計算機系統分為哪幾類？單指令單數據流計算機；單指令多數據流計算機；多指令單數據流計算機；多指令多數據流計算機14. STRASSEN算法的主要意義是：答：在理論上它突破了矩陣乘法的O（n3）時間界限以及其他諸如矩陣求逆、計算行列式和解聯立線性方程組等問題帶來的O（n3）時間計算的開銷15. 并行處理的四個級別：答：作業或程序級的并行。任務或過程級的。并行指令之間級的并行。指令內部級的并行16. 試敘述設計BM算法的主要考量：答：主要考量是在模式匹配比較過程中，有很多情形是前面許多字符都匹配而最后若干個字符不匹配17. 數據壓縮的經濟價值：節省存儲空間，達到一定程度的保密的目的。大大減少信息在網絡上傳輸的時間18. 列舉出一些字符串匹配算法：答：KMP串匹配算法，BM串匹配算法，KR串匹配算法19. 用于數字簽名和信息認證技術的HASH函數必須滿足那些條件：答：不可逆性；計算簡單；沖突概率小；高度敏感性；20. 在公共總線互聯SMP系統中，單總線SMP系統具有哪些優點？答：成本低，容易實現。擴展性能好21. .在公共總線互聯SMP系統系統中，單SMP總線系統的缺點：答：因為多處理機和其他設備共用一條總線，所以在任一時刻只有一個處理機能夠發送信息，故系統效率較低22. 遞歸是由那些部分構成的？邊界條件；遞推公式；23. 函數f(n)是T(n)的上界意味著：存在常數c>0與n0，當n>n0時，恒有T(n)cf(n)。24. 模式置換壓縮方法：答：是對多次重復的信息構造一個模式表，然后根據此模式表作模式置換來實現數據壓縮。25. 函數f(n)是T(n)的下界意味著：答：存在常數c>0與n0，當n>n0時，恒有T(n)cf(n)。26. 試介紹動態規劃法的基本思想。答：在每一個判定步上，列出各種可能的局部解，然后按某些條件，舍棄那些肯定不能得到最優解的局部解，經過每一步這樣的篩選之后，可以大大減少工作量。四、解答1.寫出用篩法判斷79是否為素數的步驟：解：求出n==8；有選擇地用2，3，…，8對79進行試除： 由于2不整除79，所以4，6，8不用再判斷； 由于3不整除79，所以6不用再判斷； 5不整除79； 7不整除79； 所以79是素數； 2. 寫出用篩法判斷83是否為素數的步驟：解：求出n==9；有選擇地用2，3，…，9對83進行試除： 由于2不整除83，所以4，6，8不用再判斷； 由于3不整除83，所以6，9不用再判斷； 3. 設集合S={1，2，6，8，10，12，100}，求S的子集，要求該子集的元素之和d=9。i. 滿足要求的子集有：{1，2，6}；{1，8}；4. 所謂“平方貨幣體制”，是指一共有17種面值的貨幣，面值分別從1的平方到17的平方(298)，也就是：1元，4元，9元，…，298元。求10元共有多少種支付方法。解：10元錢共有4種支付方法：10個1元；6個1元和一個4元；2個1元和2個4元；1個1元和一個9元；5. 已知x=3467,y=4298,取基為10，采用大整數相乘算法，求解x*y解：令x0=67,x1=34；y0=98,y1=42；則x0*y0=67*98=6566x1*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=149011666. 設模式P=aabaaaa；求改進的KMP算法計算出的next[j]和newnext[j]函數值。解：j=1234567Next[j]=0121233 Newnext[j]=0020032 7. 解遞歸方程：T(1)=1；T(n)=4T()+n2(n﹥1)解：因為D(n)=n2，D(b)=4=a；所以T(n)=O(n2logn)8. 解遞歸公式：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；9. 用大整數乘法計算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.10. 請用分治法設計算法：在一個數組A[1..n]中（n=2k），同時尋找最大值和最小值。請給出你的算法。解：算法如下：min_max(low,high){ifhigh-low=1then ifA[low]<A[high]thenreturn(A[low],A[high]); elsereturn(A[high],A[low]); endifelsemid=(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); endif}11. 設模式P=“pattern”，求dist[c]的值（c是模式P中的任意字符）解：dist[p]=6;dist[a]=5;dist[t]=3;dist[e]=2;dist[r]=1;dist[n]=712. 設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)}；13. 用基數排序法對序列X=(865,451,239,12,192,180,7,123,44,100)進行排序：解：1.按第一位依次放到下面0至9的桶中：0123456789180,10045112,1921234486572392.從0到9依次把各桶中的數據收集起來得：180，100，451，12，192，123，44，865，7，2393.按第二位依次放到下面0至9的桶中：0123456789100,712123239444518651801924.從0到9依次把各桶中的數據收集起來得：100，7，12，123，239，44，451，865，180，1925.按第三位依次放到下面0至9的桶中：01234567897,12,44100,123,180,192239451865最后從0到9依次把各桶中的數據收集起來，排序完畢；結果為：7，12，44，100，123，180，192，239，451，86514. 解遞歸公式：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-115. 寫出用冒泡排序法對序列X=(65,45,23,12,19,18,7,13,44,10)的排序過程解：第一趟比較并交換后的結果為：(7,65,45,23,12,19,18,10,13,44)第二趟比較并交換后的結果為：(7,10,65,45,23,12,19,18,13,44)第三趟比較并交換后的結果為：(7,10,12,65,45,23,13,19,18,44)第四趟比較并交換后的結果為：(7,10,12,13,65,45,23,18,19,44)第五趟比較并交換后的結果為：(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)16. 寫出用冒泡排序法對序列X=(865,451,239,12,192,180,7,123,44,100)的排序過程：解：第一趟比較并交換后的結果為：(7,865,451,239,12,192,180,44,123,100)第二趟比較并交換后的結果為：(7,12,865,451,239,44,192,180,100,123)第三趟比較并交換后的結果為：(7,12,44,865,451,239,100,192,180,123)第四趟比較并交換后的結果為：(7,12,44,100,865,451,239,123,192,180)第五趟比較并交換后的結果為：(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)排序結束。17.求遞歸方程：T(1)=1；T(n)=4T()+n3(n﹥1)的復雜度解：因為D(n)=n3，D(b)=8；且a<D(b),其特解是O(n3)所以T(n)=O(n3)18.解遞歸公式：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；19.用大整數乘法計算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.20.設數據序列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.8G1={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五、 應用題1.假設有一個需要使用某一資源的n個活動組成的集合A={1，2，3，……，n}。該資源一次只能被一個活動占用。每個活動i有其開始時間Si和結束時間Fi，而且Si≤Fi。一旦被選擇，活動i就占據時間