算法設(shè)計(jì)
算法設(shè)計(jì)
一、n+n*log10n2 = （Θ(n*log n2)）
1． 設(shè)S={x| x?{1,2,…,20} 且 x是素?cái)?shù)}，則︱S︱＝ （8 ）
2． 對(duì)算法的分析必須脫離具體的（計(jì)算機(jī)結(jié)構(gòu)和程序設(shè)計(jì)語言）
3． 如果f(n)和g(n)都是單調(diào)遞增的，則f(n)+g(n)（單調(diào)遞增 ）
4． Log(n!) = （Θ(n*ln n)）
5． 可以用來求最優(yōu)解的是最優(yōu)解分支界限法常用于求（分支界限法）
6． 設(shè)S={x| x?{1,2,…,30} 且 x是素?cái)?shù)}，則︱S︱＝（ 10 ）
7． 設(shè)S={x| x?{1,2,…,200,201} 且x是奇數(shù)}，則︱S︱＝（101）
8． EULER函數(shù)Ψ(74)的值為（343）
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. 如果f(n)和g(n)都是加法非負(fù)的增函數(shù)，則f(n)g(n)（單調(diào)遞增）
13. 設(shè)D是輸入的集合，N(I)是I?D出現(xiàn)的概率，M(I)是算法在輸入I時(shí)執(zhí)行的次數(shù)。則算法的最壞情形復(fù)雜性為（Max(M(I)) (I?D)）
14.同步并行算法是指某些進(jìn)程（必須等待）別的進(jìn)程的一類并行算法。
15. 用基數(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）
16.算法設(shè)計(jì)方法主要有分治法、回溯法、貪心法、動(dòng)態(tài)規(guī)劃法、分支界限法。
17.數(shù)據(jù)壓縮是指用較少的信息表示原有較多的信息，已達(dá)到節(jié)省存儲(chǔ)空間的目的。
18. 是指在同一時(shí)間間隔內(nèi)增加操作數(shù)量的技術(shù)是（并行處理技術(shù)）。
19. 序列c(n,0) ,c(n,1),…,c(n,n)對(duì)應(yīng)的毋函數(shù)是（(1+x)n）
20. 常用來支持細(xì)粒度和中粒度的并行計(jì)算是（共享變量通信）
21.同步并行算法是指某些進(jìn)程必須等待別的進(jìn)程的一類并行算法。
22.并行算法的加速比為求解相應(yīng)問題的最快串行算法在最壞情況下的運(yùn)行時(shí)間除以該并行算法在最壞情況下的求解該問題的運(yùn)行時(shí)間。
23. 由程序的控制和數(shù)據(jù)的相關(guān)性決定的是（軟件并行性）
24.對(duì)算法的分析必須脫離具體的（計(jì)算機(jī)結(jié)構(gòu)和程序設(shè)計(jì)語言）
25. 求解有限期的作業(yè)調(diào)度問題一般應(yīng)采用（貪心法）
26.EULER函數(shù)Ψ(21)的值為（18 ）
27.如果f(n)和g(n)都是單調(diào)遞減的，則g(g(n))（單調(diào)遞減 ）
28. 對(duì)于并行算法，除了研究所需的運(yùn)行時(shí)間之外還需要研究算法所需（處理器的數(shù)目）
29.簡(jiǎn)單字符串匹配算法在最壞情形下，總共要執(zhí)行字符的匹配比較操作次數(shù)為（(n-m+1)*m）
30． 序列(7，10，5，3，8，21，2)的逆序總數(shù)為（12 ）
31． 下列哪個(gè)屬性是單向的HASH函數(shù)不需要滿足的性質(zhì)（安全性）
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． 分支限界的本質(zhì)是（排他方法）
34． 采用大整數(shù)相乘算法，計(jì)算2368×3925所做的一位整數(shù)乘法的次數(shù)為（9）
35． 在BM算法中，設(shè)模式P=“pattern”,則滑動(dòng)距離函數(shù)distn值為（7）
36． 設(shè)模式Pattern=”aabaaaa”，利用KMP算法計(jì)算出的next(7)值為（3）
37． 衡量算法的優(yōu)劣通常依據(jù)（平均和最壞時(shí)間開銷）
38． 對(duì)于算法設(shè)計(jì)來說，遞歸是著名的分治策略。
39． 函數(shù)f(n)=log n和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． Branch and Bound的含義為（分支限界）
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. DES密碼體制是（非對(duì)稱密碼體制）
46.對(duì)于給定的序列，其毋函數(shù)（唯一確定）
47.如果f(n)和g(n)都是單調(diào)遞增的，則f(n)+2g(n)（單調(diào)遞增）
48.EULER函數(shù)Ψ(7)的值為（6 ）
49.處理機(jī)的通信模型由所采用的通信算法和（系統(tǒng)結(jié)構(gòu)決定）
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. 冒泡排序的方式是（數(shù)遍掃描數(shù)據(jù)序列）
55. 對(duì)n個(gè)元素的線性表進(jìn)行冒泡排序，最好情況下的時(shí)間復(fù)雜度為（ O(n)）
56. 利用歸并方法可以實(shí)現(xiàn)（數(shù)據(jù)排序）
57. RSA密碼體制的困難性是（大數(shù)分解）
58. 在討論算法復(fù)雜性時(shí)必須加以考慮其（同步時(shí)間）
59. 設(shè)模式Pattern=”aabaaaa”，利用KMP算法計(jì)算出的next(5)值為（ 2）
60. 通常用來衡量算法的優(yōu)劣的是（平均性態(tài)和最壞情形）
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. 具有計(jì)算機(jī)復(fù)雜性的里程碑的時(shí)間段是（20世紀(jì)60年代）
65. 采用大整數(shù)相乘算法，主要依據(jù)是（乘法開銷比加法大）
65. 序列c(n,0) ,c(n,1),…,c(n,n)對(duì)應(yīng)的毋函數(shù)是（(1+x)n ）
66. 并行算法運(yùn)行的物質(zhì)基礎(chǔ)是（并行計(jì)算機(jī)體系結(jié)構(gòu)）
67. 數(shù)據(jù)壓縮是（可逆或不可逆的）
68. 序列(17，10，15，3，8，21，2)的逆序總數(shù)為（14 ）
69. 對(duì)n個(gè)元素的線性表進(jìn)行冒泡排序，平均時(shí)間復(fù)雜度為（O(n2) ）
70. 計(jì)算機(jī)要充分發(fā)揮作用離不開（計(jì)算機(jī)軟件）
71. 在BM算法中，設(shè)模式P=“pattern”,則滑動(dòng)距離函數(shù)dista值為（ 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. BM算法在最壞情形下的時(shí)間復(fù)雜度是（Θ(m*n)）
76. 使用大整數(shù)相乘算法計(jì)算兩個(gè)n位整數(shù)的乘積，所需的一位數(shù)乘法次數(shù)約為n1.59次
77. 并行程序與串行程序有（明顯的差別）
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ù)目。
82.瑞士的N.Wirth教授提出的著名公式是：算法 + 數(shù)據(jù)結(jié)構(gòu) = 程序。
83. 如果f(n)和g(n)都是單調(diào)遞減的，則f(g(f(n)))（單調(diào)遞減）
84. 分布式并行算法是指由通訊鏈路連接的多結(jié)點(diǎn)（計(jì)算機(jī)）并行完成某一計(jì)算任務(wù)
的一類并行算
......詳細(xì)資料請(qǐng)下載
下一篇： 多媒體