一、 選擇題
1.應用johnson法則的流水作業排程採用的演算法是（d）
a. 貪心演算法 b. 分支限界法c.分治法 d. 動態規劃演算法
塔問題如下圖所示。現要求將塔座a上的的所有圓盤移到塔座b上，並仍按同樣順序疊置。移動圓盤時遵守hanoi塔問題的移動規則。由此設計出解hanoi塔問題的遞迴演算法正確的為：（b）
3. 動態規劃演算法的基本要素為（c）
a. 最優子結構性質與貪心選擇性質
b．重疊子問題性質與貪心選擇性質
c．最優子結構性質與重疊子問題性質
d. 預排序與遞迴呼叫
4. 演算法分析中，記號o表示（b）， 記號表示（a）， 記號表示（d）。
a.漸進下界
b.漸進上界
c.非緊上界
d.緊漸進界
e.非緊下界
5. 以下關於漸進記號的性質是正確的有：（a）
a. b.
c. o(f(n))+o(g(n)) = o(min)
d.6. 能採用貪心演算法求最優解的問題，一般具有的重要性質為：（a）
a. 最優子結構性質與貪心選擇性質
b．重疊子問題性質與貪心選擇性質
c．最優子結構性質與重疊子問題性質
d. 預排序與遞迴呼叫
7. 回溯法在問題的解空間樹中，按（d）策略，從根結點出發搜尋解空間樹。
a． 廣度優先 b. 活結點優先 c.擴充套件結點優先 d. 深度優先
8. 分支限界法在問題的解空間樹中，按（a）策略，從根結點出發搜尋解空間樹。
a． 廣度優先 b. 活結點優先 c.擴充套件結點優先 d. 深度優先
9. 程式塊（a）是回溯法中遍歷排列樹的演算法框架程式。
a.b.
c.d.10. 回溯法的效率不依賴於以下哪乙個因素？（c ）
a. 產生x[k]的時間；
b. 滿足顯約束的x[k]值的個數；
c. 問題的解空間的形式；
d. 計算上界函式bound的時間；
e. 滿足約束函式和上界函式約束的所有x[k]的個數。
f. 計算約束函式constraint的時間；
11. 常見的兩種分支限界法為（d）
a. 廣度優先分支限界法與深度優先分支限界法；
b. 佇列式（fifo）分支限界法與堆疊式分支限界法；
c. 排列樹法與子集樹法；
d. 佇列式（fifo）分支限界法與優先佇列式分支限界法；
12. k帶圖靈機的空間複雜性s(n)是指（b）
a. k帶圖靈機處理所有長度為n的輸入時，在某條帶上所使用過的最大方格數。
b. k帶圖靈機處理所有長度為n的輸入時，在k條帶上所使用過的方格數的總和
c. 。
c. k帶圖靈機處理所有長度為n的輸入時，在k條帶上所使用過的平均方格數。
d. k帶圖靈機處理所有長度為n的輸入時，在某條帶上所使用過的最小方格數。
13. np類語言在圖靈機下的定義為（d）
a. np=；
b. np=；
c. np=；
d. np=；
14. 記號o的定義正確的是（a）。
a. o(g(n)) = ；
b. o(g(n)) = ；
c. o(g(n)) = ；
15. 記號的定義正確的是（b）。
a. o(g(n)) = ；
b. o(g(n)) = ；
c. (g(n)) = ；
二、 填空題
1. 下面程式段的所需要的計算時間為
2. 有11個待安排的活動，它們具有下表所示的開始時間與結束時間，如果以貪心演算法求解這些活動的最優安排（即為活動安排問題：在所給的活動集合中選出最大的相容活動子集合），得到的最大相容活動子集合為活動（ ）。
3. 所謂貪心選擇性質是指（所求問題的整體最優解可以通過一系列區域性最優的選擇，即貪心選擇來達到）。
4. 所謂最優子結構性質是指（問題的最優解包含了其子問題的最優解）。
5. 回溯法是回溯法是指（具有限界函式的深度優先生成法）。
6. 用回溯法解題的乙個顯著特徵是在搜尋過程中動態產生問題的解空間。在任何時刻，演算法只儲存從根結點到當前擴充套件結點的路徑。
如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為（o(h(n))
）。7. 回溯法的演算法框架按照問題的解空間一般分為（子集樹）演算法框架與（排列樹）演算法框架。
8. 用回溯法解0/1揹包問題時，該問題的解空間結構為（子集樹）結構。
9.用回溯法解批處理作業排程問題時，該問題的解空間結構為（排列樹）結構。
10.用回溯法解0/1揹包問題時，計算結點的上界的函式如下所示，請在空格中填入合適的內容：
11. 用回溯法解佈線問題時，求最優解的主要程式段如下。如果佈線區域劃分為的方格陣列，擴充套件每個結點需o(1)的時間，l為最短佈線路徑的長度，則演算法共耗時 ( o(mn) )，構造相應的最短距離需要（o(l)）時間。
期末考試複習題
一 填空 1 單位時間內通過橫截面的叫做電流強度，簡稱公式為 導體 電荷量 電流 2 電流的換算 1amaa。1000 103 1000000 106 3 電壓就是的差。電位4 電壓的換算 1vmvkv。1000 103 0.001 10 3 5 電路的三種狀態為和 通路 斷路 短路 6 電壓源內阻...
Linux期末考試複習題
一 填空題 1.在linux系統中，以檔案方式訪問裝置 2.linux核心引導時，從檔案 etc fstab 中讀取要載入的檔案系統。3.linux檔案系統中每個檔案用 i節點來標識。4.全部磁碟塊由四個部分組成，分別為引導塊 專用塊 i節點表塊和資料儲存塊。5.鏈結分為 硬鏈結和符號鏈結 6.超級...
vhdl期末考試複習題大全
vhdl複習 一 問答題 1訊號賦值語句在什麼情況下作為並行語句？在什麼情況下作順序語句？訊號賦值和變數賦值符號分別是什麼？兩種賦值符號有什麼區別？訊號賦值語句在程序外作並行語句，併發執行，與語句所處的位置無關。訊號賦值語句在程序內或子程式內做順序語句，按順序執行，與語句所處的位置有關。訊號賦值符號...