1、算法是指解決問題的方法或過程，它包含一系列步驟，用來將輸入數(shù)據(jù)轉(zhuǎn)換成輸出結(jié)果。
A:對 B:錯
答案：對

2、使用偽代碼描述算法具有（ ）等優(yōu)點。
A、簡單易懂
B、容易修改
C、格式統(tǒng)一規(guī)范
D、易于轉(zhuǎn)化為程序語言代碼
答案：易于轉(zhuǎn)化為程序語言代碼;
容易修改;
簡單易懂

3、算法通常具有（ ）的性質(zhì)。
A、輸入：有零個或多個輸入
B、輸出：至少有一個輸出
C、確定性：組成算法的每條指令清晰、無歧義
D、有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時間也有限
答案：輸入：有零個或多個輸入;
輸出：至少有一個輸出;
確定性：組成算法的每條指令清晰、無歧義;
有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時間也有限

4、程序是算法用某種程序設(shè)計語言的具體實現(xiàn)，程序需滿足算法的所有性質(zhì)。
答案：錯

5、常用的描述算法的形式有（ ）。
A、自然語言
B、機器語言
C、偽代碼
D、程序流程圖
答案：機器語言

6、函數(shù)f(n)=20log3^n的漸進表達式是（ ）。
A、O(n)
B、0（n^2）
C、0(1)
D、0(log(n))
答案：O(n)

7、一個算法的優(yōu)劣由（ ）決定。
A、空間復(fù)雜度
B、代碼長度
C、時間復(fù)雜度
D、使用的編程語言
答案：空間復(fù)雜度
時間復(fù)雜度

8、如果存在正的常數(shù)C和自然數(shù)N0,使得當N≥N0時有f(N)≤Cg(N),則稱函數(shù)f(N)當N充分大時上有界，且g(N)是它的一個上界，記為f(N)=O(g(N)),即f(N)的階不高于g(N）的階。
答案：對

9、分析以下代碼的時間復(fù)雜度： int func(int n) { int i=1, k=0; while(i<=n) { k++; i=i*2; } return k; }
A、O(n)
B、O(logn)
C、O(n^2)
D、O(n/2)
答案：O(logn)

10、對于f(n)=n，下列說確的是（ ）。
聽錄音，選出正確的字母填在題前括號內(nèi)。
(????) 1. z?d?p?r?
(????) 2. f?g?e?c??
(????) 3. o?m?n?b?
(????) 4. g?k??i??b????
(????) 5. u?m?w?v?
(????) 6. R?A?Q?S????
(????) 7. L?N?G?J????
(????) 8. B?R?T?N??????????????????????????????????????????????
(????) 9. Z?U?Y?W???????
(????) 10. J?T?I?L??
答案：1. d?? ?2. e?? 3. n?? 4. g?? 5. v? ?6. Q?? 7. J? ?8. R? ?9. Y?? 10. I

1、遞歸函數(shù)是指在一個函數(shù)體中出現(xiàn)直接或間接調(diào)用該函數(shù)自身的函數(shù)。
答案：對

2、已知f(1)=1，f(n)=f(n-1)+n，那么f(50)的作用是( )。
A、計算50個1的和。
B、計算1到50的乘積。
C、計算1到50的和。
D、計算斐波拉契數(shù)列的第50個元素的值。
答案：計算1到50的和。

3、遞歸的優(yōu)點包括( )。
A、結(jié)構(gòu)清晰
B、可讀性強
C、容易用數(shù)學(xué)歸納法來證明算法的正確性
D、運行效率高
答案：結(jié)構(gòu)清晰;
可讀性強;
容易用數(shù)學(xué)歸納法來證明算法的正確性

4、在經(jīng)典的漢諾塔問題中，如果有5個圓盤需要從A柱移至C柱，最少需要移動( )步。
A、31
B、41
C、32
D、28
答案：31

5、分治法能解決的問題一般具有（ ）等特征。
A、該問題縮小到一定程度時可以容易地解決
B、最優(yōu)子結(jié)構(gòu)
C、分解出的子問題的解可以合并為原問題的解
D、子問題相互獨立
答案：該問題縮小到一定程度時可以容易地解決 最優(yōu)子結(jié)構(gòu) 分解出的子問題的解可以合并為原問題的解 子問題相互獨立

6、在使用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同，即將一個問題分成大小相等的多個子問題的處理方法是行之有效的。
答案：正確

7、給定遞歸公式T(n)=4T(n/2)+O(n),由主定理可以得知T(n)=( )。
A、O(logn)
B、O(nlogn)
C、O(n^2)
D、O(n)
答案：O(n^2)

8、已知某樓房共20層，如果采用二分查找，請問最多猜( )次就能猜出任意一個樓層。
A、3
B、4
C、5
D、6
答案：5

9、關(guān)于快速排序的時間復(fù)雜度，( )是正確的。
A、在最壞情況下時間復(fù)雜度為O(n^2)
B、在最好情況下時間復(fù)雜度為O(nlogn)
C、在平均情況下時間復(fù)雜度為O(n^2)
D、在平均情況下時間復(fù)雜度為O(nlogn)
答案：在最壞情況下時間復(fù)雜度為O(n^2);
在最好情況下時間復(fù)雜度為O(nlogn);
在平均情況下時間復(fù)雜度為O(nlogn)

10、快速排序是對傳統(tǒng)排序算法( )的一種改進。
A、冒泡排序
B、選擇排序
C、插入排序
D、歸并排序
答案：冒泡排序

1、能夠使用動態(tài)規(guī)劃算法來求解的問題通常需要具備兩個重要的性質(zhì)，它們分別是( )。
A、貪心選擇性質(zhì)
B、遞歸調(diào)用
C、最優(yōu)子結(jié)構(gòu)
D、重疊子問題
答案：最優(yōu)子結(jié)構(gòu);
重疊子問題

2、關(guān)于備忘錄法，以下說確的是( )。
A、備忘錄法的控制結(jié)構(gòu)與直接使用遞歸方法的控制結(jié)構(gòu)相同。
B、備忘錄法為每個解過的子問題建立備忘錄以備需要時查看，又稱查表法。
C、備忘錄法又稱為記憶化搜索，它采用一種自底向上的方式求解問題。
D、備忘錄法可以避免相同子問題的重復(fù)求解。
答案：備忘錄法的控制結(jié)構(gòu)與直接使用遞歸方法的控制結(jié)構(gòu)相同。;
備忘錄法為每個解過的子問題建立備忘錄以備需要時查看，又稱查表法。;
備忘錄法可以避免相同子問題的重復(fù)求解。

3、字符序列abcde與字符序列abdge的最長公共子序列長度為( )，最長公共子串長度為( )。
A、4,2
B、4,6
C、4,1
D、3,5
答案：4,2

4、使用動態(tài)規(guī)劃算法求兩條長度分別為m和n的序列的最長公共子序列，其時間復(fù)雜度為( )。
A、O(n^2)
B、O(m^n)
C、O(nlogm)
D、O(n*m)
答案：O(n*m)

5、輸入數(shù)組（-1, 0, 1, -2, 3），它的最大子段和是( )。
A、1
B、2
C、3
D、4
答案：3

6、序列（1，7，3，4，9，2，3）的最長遞增子序列的長度為( )。
A、1
B、2
C、3
D、4
答案：4

7、使用窮舉法求解最長遞增子序列的時間復(fù)雜度為( )。
A、O(n^2)
B、O(nlogn)
C、O(n*2^n)
D、O(n^n)
答案：O(n*2^n)

8、使用動態(tài)規(guī)劃算法求最大子段和的時間復(fù)雜度為( )。
A、O(logn)
B、O(n)
C、O(nlogn)
D、O(2^n)
答案：O(n)

9、某工廠預(yù)計明年有A,B,C,D四個新建項目，每個項目的投資額分別為15,10,12,8（萬元），投資收益分別為12,8,9,5（萬元），投資總額為30萬元，選擇項目( )可以使總收益最大。（不允許部分投資某個項目）
A、A
B、B
C、C
D、D
答案：B
C
D

10、在使用動態(tài)規(guī)劃算法求解0-1背包問題時，若m[i][j]=m[i+1][j-w[i]]+v[i]，說明第i個物品在剩余背包容量為j時可以裝入，并且裝入比不裝入的背包總價值更大，裝入后，背包剩余容量減少w[i]，價值增加v[i]。
答案：正確