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