計算機導論 第五章測驗題答案

1、第五章測驗題答案1.計算機程序設計語言的分類：(1)機器語言：由機器指令構成的語言稱機器語言，即用二進制編碼組成。(如：onioioi)特點：費時費事；難懂容易錯；只能在一種型號計算機上運行；可以直接在計算機上運行。(2)匯編語言：用容易記憶的符號來代替機器指令中操作碼和地址碼的一種 語言。(如:ADD代表“+” SUB代表 MOV代表“傳遞”)優(yōu)點：程序直觀容易閱讀；編程工作量相對小。缺點：只能在一種型號機器上運行；不能直接在計算機上運行。(3)高級程序設計語言：高級程序設計語言是一種面向過程或者面向?qū)ο蟮?語言，不面向機器，用一些符號或者數(shù)字對求解的問題或者現(xiàn)實世界進行描 述。特點： 直觀

2、、易寫、易讀、工作量小；不依賴于具體的機器；便于程序交流；不可直接在計算機上運行，經(jīng)編譯程序編譯成機器語言后方可運行。.算法(Algorithm)是對特定問題求解步驟準確而完整的描述，它的表現(xiàn) 形式是計算機指令的有序系列，執(zhí)行這些指令就可解決特定問題。一個好的算 法應當具有以下5個重要特性。(1)有限性：算法在執(zhí)行有限步之后必須終止，且每一步都應在有限的時間 內(nèi)完成；(2)確定性：算法的每一步必須要有確切的含義，不能存在二義性；(3)可行性：算法的每一步都是可執(zhí)行的，可以通過有限次操作來完成其功 能；(4)輸入：一個算法具有。個或多個輸入；(5)輸出：一個算法具有1個或多個輸出。.常用算法的描

3、述方法有：自然語言法、流程圖法、N-S流程圖法、偽代 碼法等。(1)自然語言:就是采用人們?nèi)粘Ｊ褂玫恼Z言，來描述解決問題的方法和步 驟；這種描述方法通俗易懂，即使是不熟悉計算機語言的用戶也很容易理解程 序。(2)流程圖:流程圖是以特定的圖形符號加上說明來表示算法，通常是用一 些圖框來表示各種操作。(3)N-S圖是在流程圖的基礎上完全去掉流程線，并將全部算法寫在一個矩 形框內(nèi)，且框內(nèi)還可以包含其他框的表示形式。N-S圖包括順序、選擇和循環(huán)3 種基本結構，如下列圖所示：當條件為真時循環(huán)體循環(huán)結構(4)偽代碼:偽代碼是介于自然語言和計算機語言之間的文字和符號.偽代碼 通常采用自然語言、數(shù)學公式和符號

4、來描述算法的操作步驟，同時采用計算機 高級語言的控制結構來描述算法步驟的執(zhí)行順序。在程序開發(fā)期間，偽代碼經(jīng) 常用于“規(guī)劃” 一個程序，然后再轉換成某種高級語言程序。.計算機技術所涉及的算法比擬多，常用的算法有枚舉法、遞推法、遞歸 法、貪心算法、分治法、回溯法等.(1)枚舉法，或稱為窮舉法，其基本思路是：對于要解決的問題，列舉出它 所有可能的情況，逐個判斷哪些是符合問題所要求的條件，從而得到問題的 解；(2)遞推法:是按照一定的規(guī)律來計算序列中的某個項，通常是通過計算前 面的一些項來得出序列中指定項的值；(3)遞歸法:程序直接或間接自己調(diào)用自己的方法簡稱為遞歸，它通常是把 一個大型的、復雜的問題

5、層層轉化為一個個與原問題相似的、規(guī)模較小的問題 來進行求解；(4)貪心算法:貪心算法采用自頂向下，以迭代的方式做出相繼的貪心選 擇，每做一次貪心選擇就將所求解問題簡化為一個規(guī)模更小的子問題，通過每 一步貪心選擇，就可得到問題的一個最優(yōu)解。貪心算法的每一步都能獲得局部 最優(yōu)解，但由此產(chǎn)生的全局解有時不一定是最優(yōu)解，所以貪婪法不能回溯。(5)分治法：分治法是把一個復雜的問題分解成兩個或更多個相同或相似的 子問題，再把子問題分解成更小的子問題，直到最后的子問題可以進行簡單的 直接求解，合并所有子問題的解就可得到原問題的解。(6)回溯法：回溯法的基本思想是，在包含問題所有解的解空間樹中，按照 深度優(yōu)先搜索的策略，從根結點出發(fā)深度搜索解空間樹；當搜索到某一結點 時，要先判斷該結點是否包含問題的解，如果包含就從該結點出發(fā)繼續(xù)搜索下 去，否那么就逐層向其祖先結點