算法設(shè)計(jì)與分析-01345-19日上-復(fù)習(xí)資料

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