第1章 計(jì)算機(jī)理論基礎(chǔ)概述 課后練習(xí)題答案

3.什么是計(jì)算機(jī)系統(tǒng)？

計(jì)算機(jī)系統(tǒng)是一種能夠按照事先存儲(chǔ)的程序，自動(dòng)、高速地對(duì)數(shù)據(jù)進(jìn)行輸入、處理、輸出

和存儲(chǔ)的系統(tǒng)，由計(jì)算機(jī)硬件系統(tǒng)和計(jì)算機(jī)軟件系統(tǒng)兩大部分組成。

4.簡述計(jì)算機(jī)硬件系統(tǒng)的五大部分。

①運(yùn)算器

運(yùn)算器乂稱算術(shù)邏輯單元(ArithmeticLogicUnit,ALU),是計(jì)算機(jī)對(duì)數(shù)據(jù)進(jìn)行加工處理的

部件，它的主要功能是對(duì)二進(jìn)制數(shù)進(jìn)行加、減、乘、除等算術(shù)運(yùn)算和與、或、非等基本邏輯運(yùn)

算，實(shí)現(xiàn)邏輯判斷。運(yùn)算器是在控制器的控制之下實(shí)現(xiàn)其功能的，運(yùn)算結(jié)果由控制器發(fā)出的指

令送到內(nèi)存儲(chǔ)器中。

②控制器

控制器主要由指令寄存器、譯碼器、程序計(jì)數(shù)器和操作控制器等組成，控制器是用來控制

計(jì)算機(jī)各部件協(xié)調(diào)工作，并使整個(gè)處理過程有條不紊地進(jìn)行。它的基本功能就是從內(nèi)存中取出

指令和執(zhí)行指令，即控制器按程序計(jì)數(shù)器指出的指令地址從內(nèi)存中取出該指令進(jìn)行譯碼，然后

杈據(jù)該指令功能向有關(guān)部件發(fā)出控制命令，執(zhí)行該指令。另外，控制器在工作過程中，還要接

受各部件反饋回來的信息。

通常把運(yùn)算器、控制器集成在一個(gè)大規(guī)模集成電路板上稱為中央處理器，乂稱CPU(Central

ProcessingUnit)。

③存儲(chǔ)器

存儲(chǔ)器是計(jì)算機(jī)的記憶裝置，用于存放原始數(shù)據(jù)、中間數(shù)據(jù)、最終結(jié)果和處理程序。為了

對(duì)存儲(chǔ)的信息進(jìn)行管理，把存儲(chǔ)器劃分成存儲(chǔ)單元，每個(gè)單元的編號(hào)稱為該單元的地址。各種

存儲(chǔ)器基本上都是以1個(gè)字節(jié)作為一個(gè)存儲(chǔ)單元。存儲(chǔ)器內(nèi)的信息是按地址存取的，如要訪問

存儲(chǔ)器中的某個(gè)信息，就必須知道它的地址。向存儲(chǔ)器里存入信息也稱為“寫入”，寫入新的

內(nèi)容將覆蓋原來的內(nèi)容。從存儲(chǔ)器里取出信息也稱為“讀出”，信息讀出后并不破壞原來存儲(chǔ)

的內(nèi)容，因此信息可以重復(fù)讀出，多次利用。

通常把內(nèi)存儲(chǔ)器、運(yùn)算器和控制器合稱為計(jì)算機(jī)主機(jī)，也可以說主機(jī)是由CPU與內(nèi)存儲(chǔ)

器組成的，而主機(jī)以外的裝置稱為外部設(shè)備，外部設(shè)備包括輸入/輸出設(shè)備、外存儲(chǔ)器等。

④輸入和輸出設(shè)備

輸入和出設(shè)備簡稱I/O(Input/Outpu。設(shè)備。用戶通過輸入設(shè)備將程序和數(shù)據(jù)輸入計(jì)算機(jī)，

輸出設(shè)備將計(jì)算機(jī)處理的結(jié)果(如數(shù)字、字母、符號(hào)和圖形)顯示或打印出來。常用的輸入設(shè)備

有：鍵盤、鼠標(biāo)器、掃描儀、數(shù)字化儀等；常用的輸出設(shè)備有：顯示器、打印機(jī)、繪圖儀等。

5.請(qǐng)解釋馮?諾依曼所提出的“存儲(chǔ)程序”概念。

把程序和數(shù)據(jù)都以二進(jìn)制的形式統(tǒng)一存放在存儲(chǔ)器中，由機(jī)器自動(dòng)執(zhí)行。不同的程序解決

不同的問題，實(shí)現(xiàn)了計(jì)算機(jī)通用計(jì)算的功能。

6.控制器的主要功能是什么？

控制器基本功能就是從內(nèi)存中取指令和執(zhí)行指令，即控制器按程序計(jì)數(shù)器指出的指令地址

從內(nèi)存中取出該指令進(jìn)行譯碼，然后根據(jù)該指令功能向有關(guān)部件發(fā)出控制命令，執(zhí)行該指令。

另外，控制器在工作過程中，還要接受各部件反饋回來的信息。

7.簡述CPU和主機(jī)的概念。

通常把運(yùn)算器、控制器做在一個(gè)大規(guī)模集成電路塊上稱為中央處理器，乂稱CPU（Central

ProcessingUnit）。

通常把內(nèi)存儲(chǔ)器、運(yùn)算器和控制器合稱為計(jì)算機(jī)主機(jī)，也可以說主機(jī)是由CPU與內(nèi)存儲(chǔ)

器組成的，而主機(jī)以外的裝置稱為外部設(shè)備，外部設(shè)備包括輸入/輸出設(shè)備，外存儲(chǔ)器等。

8.什么是計(jì)算機(jī)軟件？計(jì)算機(jī)軟件的分類有哪些？

軟件是指用來指揮計(jì)算機(jī)運(yùn)行的各種程序的總和以及開發(fā)、使用和維護(hù)這些程序所需的技

術(shù)文檔。

計(jì)算機(jī)軟件系統(tǒng)分為系統(tǒng)軟件和應(yīng)用軟件。計(jì)算機(jī)系統(tǒng)軟件由操作系統(tǒng)、語言處理系統(tǒng)、

以及各種軟件工具等各種軟件程序組成，指揮、控制計(jì)算機(jī)硬件系統(tǒng)按照預(yù)定的程序運(yùn)行、工

作，從而達(dá)到預(yù)定的目標(biāo)。應(yīng)用軟件是用戶利用計(jì)算機(jī)軟、硬件資源為解決各類應(yīng)用問題而編

寫的軟件，包括用戶程序及其說明性文件資料。

9.計(jì)算機(jī)有哪些主要的特點(diǎn)？

（1）運(yùn)算速度快、精度高

計(jì)算機(jī)的字長越長，其精度越高，現(xiàn)在世界上最快的計(jì)算機(jī)每秒可以運(yùn)算幾十萬億次

以上。般計(jì)算機(jī)可以有I-幾位甚至幾H立（二進(jìn)制）有效數(shù)字，計(jì)算精度可由T分之幾到

百萬分之幾，是任何計(jì)算工具所望塵莫及的。

（2）具有邏輯判斷和記憶能力

計(jì)算機(jī)有準(zhǔn)確的邏輯判斷能力和高超的記憶能力。能夠進(jìn)行各種邏輯判斷，并根據(jù)判

斷的結(jié)果自動(dòng)決定下一步應(yīng)該執(zhí)行的指令。

（3）高度的自動(dòng)化和靈活性

計(jì)算機(jī)采取存儲(chǔ)程序方式工作，即把編好的程序輸入計(jì)算機(jī)，機(jī)器便可依次逐條執(zhí)行，這

就使計(jì)算機(jī)實(shí)現(xiàn)了高度的自動(dòng)化和靈活性。

10.簡述計(jì)算機(jī)系統(tǒng)的主要技術(shù)指標(biāo)。

評(píng)價(jià)計(jì)算機(jī)的性能指標(biāo)有很多，通常人們從計(jì)算機(jī)的字長、時(shí)鐘周期和主頻、運(yùn)算速

度、內(nèi)存容量、數(shù)據(jù)輸入輸出最高速率等技術(shù)指標(biāo)來評(píng)價(jià)計(jì)算機(jī)系統(tǒng)。

1.字長

在計(jì)算機(jī)中，用若干二法制位表示一個(gè)數(shù)或一條指令，前者稱為數(shù)據(jù)字，后者稱為指令字。

字長的直接影響計(jì)算機(jī)的功能強(qiáng)弱、精度高低和速度快慢。計(jì)算機(jī)處理數(shù)據(jù)時(shí)，一次可以運(yùn)算

的數(shù)據(jù)長度稱為一個(gè)“字”（Word）,字的長度稱為字長。一個(gè)字可以是一個(gè)字節(jié)（Byte,簡稱

B）,也可以是多個(gè)字節(jié)。常用的字長有8位（bit）、16位、32位、64位等。如某一類計(jì)算機(jī)

的字由4個(gè)字節(jié)組成，則字的長度為32位，相應(yīng)的計(jì)算機(jī)稱為32位機(jī)。

2.時(shí)鐘周期和主頻

計(jì)算機(jī)的中央處理器對(duì)每條指令的執(zhí)行是通過若干個(gè)微指令操作來完成的，這些微指令操

作是按時(shí)鐘周期的節(jié)拍來“動(dòng)作”的，時(shí)鐘周期的微秒數(shù)反映出計(jì)算機(jī)的運(yùn)算速度。有時(shí)也用

時(shí)鐘周期的倒數(shù)一時(shí)鐘頻率（兆頻），即人們常說的主頻來表示。一般說來，主頻越高（時(shí)鐘周

期越短），計(jì)算機(jī)的運(yùn)算速度越快。但是，主頻并不能全面準(zhǔn)確地反映計(jì)算機(jī)的運(yùn)算速度，而

每秒鐘執(zhí)行百萬條指令數(shù)（MIPS）指標(biāo)則能較全面準(zhǔn)確地反映計(jì)算機(jī)的運(yùn)算速度。近十年來，微

計(jì)算機(jī)的主頻提高很快，例如，IBMPC/XT微機(jī)的CPU主頻為4.77MHz,而Pentium4CPU

的主頻己超過IGMHz,并且在不斷提高。

3.運(yùn)算速度

計(jì)算機(jī)的運(yùn)算速度是衡量計(jì)算機(jī)水平的一項(xiàng)主要指標(biāo)，它取決于指令執(zhí)行時(shí)間。運(yùn)算速度

的計(jì)算方法多種多樣，目前常用單位時(shí)間內(nèi)執(zhí)行多少條指令來表示，而計(jì)算機(jī)執(zhí)行各種指令所

需時(shí)間不同。因此，常根據(jù)在一些典型題目計(jì)算中，各種指令執(zhí)行的頻度以及每種指令的執(zhí)行

時(shí)間來折算出計(jì)算機(jī)的等效速度。

4.內(nèi)存容量

存儲(chǔ)器的容量反映計(jì)算機(jī)記憶信息的能力，它常以字節(jié)為單位表示。存儲(chǔ)器的容量越大，

則存儲(chǔ)的信息越多，計(jì)算機(jī)的功能越強(qiáng)。

計(jì)算機(jī)中的操作大多是與內(nèi)存交換信息，但內(nèi)存的存取速度相對(duì)CPU的算術(shù)和邏輯運(yùn)算

的速度要低1?2個(gè)數(shù)量級(jí)。因此，內(nèi)存的讀寫速度也是影響計(jì)算機(jī)運(yùn)行速度的主要因素之一。

為了度量信息存儲(chǔ)容量，將8位二進(jìn)制位(8bits)稱為1個(gè)字節(jié)，字節(jié)是計(jì)算機(jī)中數(shù)據(jù)處理

和存儲(chǔ)容量的基本單位。1024個(gè)字節(jié)稱為1K字節(jié)(1KB),1024K個(gè)字節(jié)稱1兆字節(jié)(1MB),

1024M個(gè)字節(jié)稱為1G字節(jié)(1GB),1024G個(gè)字節(jié)稱為1T字節(jié)(1TB),現(xiàn)在微型計(jì)算機(jī)主存容

量大多數(shù)在兆字節(jié)以上。

5.數(shù)據(jù)輸入輸出最高速率

主機(jī)與外部設(shè)備之間交換數(shù)據(jù)的速率也是影響計(jì)算機(jī)系統(tǒng)工作速度的重要因素。由于各種

外部設(shè)備本身工作的速度不同，常用主機(jī)所能支持的數(shù)據(jù)輸入輸出最大速率來表示。

11.計(jì)算機(jī)的分類有哪些？

根據(jù)計(jì)算機(jī)工作原理和運(yùn)算方式的不同，以及計(jì)算機(jī)中信息表示形式和處理方式的不同，

計(jì)算機(jī)可分為數(shù)字式電了計(jì)算機(jī)(DigitalComputer)模擬式電了-計(jì)算機(jī)(AnalogComputer)和數(shù)

字模擬混合計(jì)算機(jī)(HybridComputer)。當(dāng)今廣泛應(yīng)用的是數(shù)字計(jì)算機(jī)，因此，常把數(shù)字式電子

計(jì)算機(jī)(ElectronicDigitalComputer)簡稱為電子計(jì)算機(jī)或計(jì)算機(jī)。

按計(jì)算機(jī)的用途可分為通用計(jì)算機(jī)(GeneralPurposeCompuler)和專用計(jì)算機(jī)(Special

PinposeCompuler)兩大類。通用計(jì)算機(jī)能解決多種類型問題，是具有較強(qiáng)通用性的計(jì)算機(jī)，一

般的數(shù)字式電子計(jì)算機(jī)多屬此類；專用計(jì)算機(jī)是為解決某些特定問題而專門設(shè)計(jì)的計(jì)算機(jī)，如

嵌入式系統(tǒng)。

根據(jù)計(jì)算機(jī)的總體規(guī)模對(duì)計(jì)算機(jī)分類，可分為巨型機(jī)(SuperComputer).大/中型計(jì)算機(jī)

(Mainframe)x小型i十算機(jī)(M：nicomputer)>微型it算機(jī)(Microcomputer)和網(wǎng)2各1十算機(jī)(Network

Compuler)五大類。

常見的微型機(jī)還可以分為臺(tái)式機(jī)、便攜機(jī)、筆記本電腦、掌上型電腦等多種類型。

12.簡述計(jì)算機(jī)的基本運(yùn)行方式。

計(jì)算機(jī)的基本運(yùn)作方式可概括為所謂的“IPOS循環(huán)"。IPOS循環(huán)即輸入(Input)、處理

(Processing)輸出(Output)和存儲(chǔ)(Storage),它反映了計(jì)算機(jī)進(jìn)行數(shù)據(jù)處理的基本步驟。

⑴輸入

接受由輸入設(shè)備(如鍵盤、鼠標(biāo)器、掃描儀等)提供的數(shù)據(jù)。

(2)處理

對(duì)數(shù)值、邏輯、字符等各種類型的數(shù)據(jù)進(jìn)行操作，按指定的方式進(jìn)行轉(zhuǎn)換。

(3)輸出

將處理所產(chǎn)生的結(jié)果等數(shù)據(jù)由輸出設(shè)備(如顯示器、打印機(jī)、繪圖儀等)進(jìn)行輸出。

(4)存儲(chǔ)

計(jì)算機(jī)可以存儲(chǔ)程序和數(shù)據(jù)供以后使用。

13.計(jì)算機(jī)有哪些主要的用途？

(1)科學(xué)計(jì)算

使用計(jì)算機(jī)來完成科學(xué)研究和工程技術(shù)中所遇到的數(shù)學(xué)問題的計(jì)算稱為科學(xué)計(jì)算，也

稱為數(shù)值計(jì)算?？茖W(xué)計(jì)算是使用計(jì)算機(jī)完成在科學(xué)研究和工程技術(shù)領(lǐng)域中所提出的大量復(fù)

雜的數(shù)值計(jì)算問題，是計(jì)算機(jī)的傳統(tǒng)應(yīng)用之一。

(2)信息處理

所謂信息處理就是使用計(jì)算機(jī)對(duì)數(shù)據(jù)進(jìn)行輸入、分類、加工、整理.、合并、統(tǒng)計(jì)、制

表、檢索以及存儲(chǔ)等，又稱為數(shù)據(jù)處理。例如座席預(yù)訂與售票系統(tǒng)、零售業(yè)中的應(yīng)用、辦

公自動(dòng)化等。信息處理已成為當(dāng)代計(jì)算機(jī)的主要任務(wù)，是現(xiàn)代化管理的基礎(chǔ)。

(3)實(shí)時(shí)控制(也稱過程控制)

實(shí)時(shí)控制也稱過程控制，實(shí)時(shí)控制能及時(shí)地采集檢測數(shù)據(jù)、使用計(jì)算機(jī)快速地進(jìn)行處

理并自動(dòng)地控制被控對(duì)象的動(dòng)作，實(shí)現(xiàn)生產(chǎn)過程的自動(dòng)化。

(4)計(jì)算機(jī)輔助設(shè)計(jì)/輔助制造/輔助教學(xué)

計(jì)算機(jī)輔助設(shè)計(jì)(ComputerAkledDesignCAD)是使用計(jì)算機(jī)來輔助人們完成產(chǎn)品

或工程的設(shè)計(jì)任務(wù)的一種方法和技術(shù)。計(jì)算機(jī)輔助制造(ComputerAidedManufacturing------

CAM)是使用計(jì)算機(jī)輔助人們完成工業(yè)產(chǎn)品的制造任務(wù)，能通過直接或間接地與工廠生產(chǎn)資

源接口的計(jì)算機(jī)來完成制造系統(tǒng)的計(jì)劃、操作工序控制和管理工作的計(jì)算機(jī)應(yīng)用系統(tǒng)。計(jì)

算機(jī)輔助教學(xué)(ComputerAidedInstiuctionCAI)是把計(jì)算機(jī)用作教學(xué)媒體，使它充當(dāng)指導(dǎo)者、

工具和學(xué)習(xí)者角色，學(xué)生通過與計(jì)算機(jī)的對(duì)話進(jìn)行學(xué)習(xí)的一種新型教學(xué)技術(shù)。

(5)人工智能

人工智能(ArtificialIntelligence-----AI)就是指計(jì)算機(jī)模擬人類某些智力行為的理論、技

術(shù)和應(yīng)用。

(6)多媒體技術(shù)

隨著電子技術(shù)特別是通信和計(jì)算機(jī)技術(shù)的發(fā)展，人們已經(jīng)有能力把文本、音頻、視頻、動(dòng)

畫、圖形和圖像等各種媒體綜合起來，構(gòu)成“多媒體"(Multimedia)的概念。

14.簡述計(jì)算機(jī)的發(fā)展趨勢。

(1)微型化

一方面，隨著計(jì)算機(jī)的應(yīng)用日益廣泛，在一些特定場合，需要很小的計(jì)算機(jī)，計(jì)算機(jī)

的重量、體積都變得越來越小，但功能并不減少。另一方面，隨著計(jì)算機(jī)在世界上日益普

及，個(gè)人電腦正逐步由辦公設(shè)備變?yōu)殡娮酉M(fèi)品。人們要求電腦除了要保留原有的性能之

外，還要有時(shí)尚的外觀、輕便小巧、便于操作等特點(diǎn)，如平板電腦、手持電腦等。今后個(gè)

人計(jì)算機(jī)(PersonalComputer)在計(jì)算機(jī)中所占的比重將會(huì)越來越大，使用也將會(huì)越來越方

便.

(2)巨型化

社會(huì)在不斷發(fā)展，人類對(duì)自然世界的認(rèn)識(shí)活動(dòng)也越來越多，很多情況要求計(jì)算機(jī)對(duì)數(shù)

據(jù)進(jìn)行運(yùn)算。“巨型化”在這里并不是通常意義上的大小，主要是指機(jī)器的性能一一運(yùn)算速

度等。

(3)網(wǎng)絡(luò)化

因特網(wǎng)(Internet)的建立正在改變我們的世界，改變我們的生活。網(wǎng)絡(luò)具有虛擬和真實(shí)

兩種特性，網(wǎng)上聊天和網(wǎng)絡(luò)游戲等具有虛擬特性，而網(wǎng)絡(luò)通信、電子商務(wù)、網(wǎng)絡(luò)資源共享

則具有真實(shí)的特性。

(4)智能化

今后，計(jì)算機(jī)在生活中扮演的角色將會(huì)更加重要，計(jì)算機(jī)應(yīng)用將具有更多的智能特性，

能夠幫助用戶解決一些自己不熟悉或不愿意做的事，如智能家電、烹調(diào)等。

(5)新型計(jì)算機(jī)

目前新一代計(jì)算機(jī)正處在設(shè)想和研制階段。新一代計(jì)算機(jī)是把信息采集、存儲(chǔ)處理、通信

和人工智能結(jié)合在一起的計(jì)算機(jī)系統(tǒng)。

15.簡述計(jì)算學(xué)科的定義、計(jì)算學(xué)科的本質(zhì)、計(jì)算學(xué)科的三個(gè)過程。

計(jì)算學(xué)科是對(duì)描述和變換信息的算法過程，包括對(duì)理論分析、設(shè)計(jì)、效率、實(shí)現(xiàn)和應(yīng)用等

進(jìn)行的系統(tǒng)研究。計(jì)算學(xué)科的研究包括了從算法與可計(jì)算性的研究到根據(jù)可計(jì)算硬件和軟件的

實(shí)際實(shí)現(xiàn)問題的研究。

計(jì)算學(xué)科的根本問題是“什么能被有效地自動(dòng)進(jìn)行？計(jì)算學(xué)科的根本問題討論的是能

行性的有關(guān)內(nèi)容，而凡是與能行性有關(guān)的討論都是處理離散對(duì)象的。

計(jì)算學(xué)科的實(shí)質(zhì)是學(xué)科方法論的思想，其關(guān)鍵問題是抽象、理論和設(shè)計(jì)三個(gè)過程相互

作用的問題。

(1)理論

理論是數(shù)學(xué)科學(xué)的根本。應(yīng)用數(shù)學(xué)家們都認(rèn)為，科學(xué)的進(jìn)展都是基于純數(shù)學(xué)的。應(yīng)用

數(shù)學(xué)用數(shù)學(xué)的方法推動(dòng)經(jīng)驗(yàn)科學(xué)和工程學(xué)的發(fā)展，同時(shí)乂不斷刺激對(duì)新數(shù)學(xué)的需要，為純

理論數(shù)學(xué)提出新的問題。

(2)抽象

抽象(模型化)是自然科學(xué)的根本?？茖W(xué)家們相信，科學(xué)進(jìn)展的過程基本上都是形成假設(shè),

然后用模型化過程去求證。

(3)設(shè)計(jì)

設(shè)計(jì)是工程的根本。工程師們認(rèn)為，工程進(jìn)展基本上都是提出問題，然后通過設(shè)計(jì)去構(gòu)造

系統(tǒng)，以解決問題。

16.簡述計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的定義。

計(jì)算機(jī)科學(xué)技術(shù)是研究計(jì)算機(jī)的設(shè)計(jì)與制造和利用計(jì)算機(jī)進(jìn)行信息獲取、表示、存儲(chǔ)、處

理、控制等的理論、原則、方法和技術(shù)的學(xué)科，包括科學(xué)與技術(shù)兩方面?？茖W(xué)側(cè)重于講究現(xiàn)象、

揭示規(guī)律；技術(shù)則側(cè)重于研制計(jì)算機(jī)和研究使用計(jì)算機(jī)進(jìn)行信息處理的方法與技術(shù)手段?？茖W(xué)

是技術(shù)的依據(jù)，技術(shù)是科學(xué)的體現(xiàn)；技術(shù)得益于科學(xué)，它又向科學(xué)提出新的課題。

17.簡述計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的根本問題及研究范疇。

計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的根本問題是什么能被有效地自動(dòng)化。問題的符號(hào)表示及其處理過

程的機(jī)械化、嚴(yán)格化的固有特性，決定了數(shù)學(xué)是計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的重要基礎(chǔ)之一，數(shù)學(xué)

及其形式化描述、嚴(yán)密的表達(dá)和計(jì)算是計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科所用的重要工具，建立物理符號(hào)

系統(tǒng)并對(duì)其實(shí)施變換是計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科進(jìn)行問題描述和求解的重要手段。

計(jì)算機(jī)科學(xué)與技術(shù)的研究范疇包括計(jì)算機(jī)理論、硬件、軟件、網(wǎng)絡(luò)及應(yīng)用等，按照研究的

內(nèi)容，也可以劃分為基礎(chǔ)理論、專業(yè)基礎(chǔ)和應(yīng)用三個(gè)層面。

計(jì)算機(jī)理論的研究包括離散數(shù)學(xué)、算法分析理論、形式語言與自動(dòng)機(jī)理論、程序設(shè)計(jì)語言

理論、程序設(shè)計(jì)方法學(xué)；計(jì)算機(jī)硬件的研究包括元器件與存儲(chǔ)介質(zhì)、微電子技術(shù)、計(jì)算機(jī)組成

原理、微型計(jì)算機(jī)技術(shù)、計(jì)篁機(jī)體系結(jié)構(gòu)：計(jì)算機(jī)軟件的研究包括程序設(shè)計(jì)語言的設(shè)計(jì)、數(shù)據(jù)

結(jié)構(gòu)與算法、程序設(shè)計(jì)語言翻譯系統(tǒng)、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)、算法設(shè)計(jì)與分析、軟件工程學(xué)、

可視化技術(shù)；計(jì)算機(jī)網(wǎng)絡(luò)的研究包括網(wǎng)絡(luò)結(jié)構(gòu)、數(shù)據(jù)通信與網(wǎng)絡(luò)協(xié)議、網(wǎng)絡(luò)服務(wù)、網(wǎng)絡(luò)安全；

計(jì)算機(jī)應(yīng)用的研究及人一機(jī)工程包括計(jì)算機(jī)應(yīng)用的研究、軟件開發(fā)工具、完善既有的應(yīng)用系統(tǒng)、

開拓新的應(yīng)用領(lǐng)域、人一機(jī)工程、研究人與計(jì)算機(jī)的交互和協(xié)同技術(shù)。

18.簡述計(jì)算機(jī)科學(xué)課程體系的核心內(nèi)容。

計(jì)算學(xué)科課程體系的教學(xué)內(nèi)容歸結(jié)為14個(gè)知識(shí)體，包括：

(1)離散結(jié)構(gòu)(PS)

計(jì)算學(xué)科是以離散型變量為研究對(duì)象，離散數(shù)學(xué)對(duì)計(jì)算技術(shù)的發(fā)展起著I?分重要的作

用。隨著計(jì)算技術(shù)的迅猛發(fā)展，離散數(shù)學(xué)越來越受到重視。

(2)程序設(shè)計(jì)基礎(chǔ)(PF)

《計(jì)算作為一門學(xué)科》報(bào)告指出了程序設(shè)計(jì)在計(jì)算學(xué)科的正確地位：程序設(shè)計(jì)是計(jì)算

學(xué)科課程中固定練習(xí)的一部分，是每一個(gè)計(jì)算學(xué)科專業(yè)的學(xué)生應(yīng)具備的能力，是計(jì)算學(xué)科

核心科目的一部分，程序設(shè)計(jì)語言還是獲得計(jì)算機(jī)重要特性的有力工具。

(3)算法與復(fù)雜性(AL)

算法是計(jì)算機(jī)科學(xué)和軟件工程的基礎(chǔ)，現(xiàn)實(shí)世界中，任何軟件系統(tǒng)的性能僅依賴于兩

個(gè)基本點(diǎn)方面，一方面是所選擇的算法；另一方面是各不同層次實(shí)現(xiàn)的適宜性和效率。

(4)組織與體系結(jié)構(gòu)(AR)

計(jì)算機(jī)在計(jì)算中處于核心地位，如果沒有計(jì)算機(jī)，計(jì)算學(xué)科只是理論數(shù)學(xué)的一個(gè)分支,

應(yīng)該對(duì)計(jì)算機(jī)系統(tǒng)的功能構(gòu)件、以及他們的特點(diǎn)/性能和相互作用有一定的理解。

(5)操作系統(tǒng)(OS)

操作系統(tǒng)定義了對(duì)硬件行為的抽象，程序員用它來對(duì)硬件進(jìn)行控制。操作系統(tǒng)還管理

計(jì)算機(jī)用戶間的資源共享。

(6)網(wǎng)絡(luò)計(jì)算(NC)

計(jì)算機(jī)和通信網(wǎng)絡(luò)的發(fā)展，尤其是基于TCP/IP的網(wǎng)絡(luò)的發(fā)展使得網(wǎng)絡(luò)技術(shù)在計(jì)算學(xué)科

中更加重要。

(7)程序設(shè)計(jì)語言(PL)

程序設(shè)計(jì)語言是程序員與計(jì)算機(jī)交流的主要工具。一個(gè)程序員不僅要知道如何使用一

種語言進(jìn)行程序設(shè)計(jì)，還應(yīng)理解不同語言的程序設(shè)計(jì)風(fēng)格。

(8)人-機(jī)交互(HL)

人機(jī)交互重點(diǎn)在于理解人對(duì)交互式對(duì)象的交互行為，知道如何使用以人為中心的方法

開發(fā)和評(píng)價(jià)交互軟件系統(tǒng)，以及人機(jī)交互設(shè)計(jì)問題的一般知識(shí)°

(9)圖形學(xué)和可視化計(jì)算(GV)

該主領(lǐng)域的主要內(nèi)容包括：計(jì)算機(jī)圖形學(xué)、可視化、虛擬現(xiàn)實(shí)、計(jì)算機(jī)視覺等4個(gè)學(xué)

科子領(lǐng)域的研究內(nèi)容。

(10)智能系統(tǒng)(IS)

人工智能領(lǐng)域關(guān)心的問題是自主代理的設(shè)計(jì)和分析。智能系統(tǒng)必須干知其環(huán)境，合理

地朝著指定的任務(wù)行動(dòng)，并與其它代理和人進(jìn)行交互。

(11)信息管理(IM)

信息系統(tǒng)幾乎在所有使用計(jì)算機(jī)的場合都發(fā)揮著重要的作用°

(12)軟件工程(SE)

軟件工程是關(guān)于如何有效地利用建立滿足用戶和客戶需求的軟件系統(tǒng)理論/知識(shí)和實(shí)

踐的學(xué)科，可以應(yīng)用于小型、中型、大型系統(tǒng)。

(13)數(shù)值計(jì)算科學(xué)(CN)

從計(jì)算學(xué)科的誕生之日起，科學(xué)計(jì)算的數(shù)值方法和技術(shù)就構(gòu)成了計(jì)算機(jī)科學(xué)研究的一

個(gè)主要領(lǐng)域。

(14)社會(huì)和職業(yè)問題(SP)

大學(xué)生需要懂得計(jì)算學(xué)科本身基本的文化、社會(huì)、法律和道德問題。還需要培養(yǎng)學(xué)生提出

有關(guān)計(jì)算的社會(huì)影響這樣嚴(yán)肅問題以及對(duì)這些問題的可能答案進(jìn)行評(píng)價(jià)的能力。學(xué)生還需要認(rèn)

識(shí)到軟硬件銷售商和用戶的基本法律權(quán)利，也應(yīng)意識(shí)到這些權(quán)利的基本基礎(chǔ)——道德價(jià)值觀。

三.討論題

1.計(jì)算機(jī)的產(chǎn)生是世紀(jì)最偉大的成就之一，具體體現(xiàn)在哪些方面？根據(jù)你的觀察，請(qǐng)列

出計(jì)算機(jī)的應(yīng)用。

答案略。

2.在信息社會(huì)，如何才能在計(jì)算機(jī)產(chǎn)業(yè)中做出自己的貢獻(xiàn)，有所作為？

答案略。

3.計(jì)算機(jī)提供了無限的機(jī)會(huì)和挑戰(zhàn)。利用它可以更快更好地完成許多事情，可以方便地

和全世界的人們聯(lián)系和通信。但是，是否想過事情的反面呢？所有的變化都是積極的么？計(jì)算

機(jī)的廣泛使用會(huì)產(chǎn)生什么負(fù)面的影響嗎？討論這些問題和其他所能想到的問題。

答案略。

第2章計(jì)算機(jī)體系結(jié)構(gòu)與組織

習(xí)題(答案)

一.選擇題

1.D2.D3.D4.D5.C

6.B7.A8.C9.A10.C

11.A12.C13.C14.C15.A

16.A17.B18.A

二.簡答題

1.試簡單敘述計(jì)算機(jī)采用二進(jìn)制的原因。

答：計(jì)算機(jī)只認(rèn)識(shí)二進(jìn)制編碼形式的指令和數(shù)據(jù)。因此，包括數(shù)字、字符、聲音、圖

形、圖像等信息都必須經(jīng)過某種方式轉(zhuǎn)換成二進(jìn)制的形式，才能提供給計(jì)算機(jī)進(jìn)行識(shí)別和

處理。在計(jì)算機(jī)中采用二進(jìn)制，是因?yàn)槲锢砩蠈?shí)現(xiàn)容易。由于二進(jìn)制只有兩個(gè)狀態(tài)。和1,

這正好與物理器件的兩種狀態(tài)相對(duì)應(yīng)，例如電壓信號(hào)的高與低，門電路的導(dǎo)通與截止等；

而十進(jìn)制電路則需要用十種狀態(tài)來描述，這將使得電路十分復(fù)雜，處理也十分困難。因此,

采用二進(jìn)制將使得計(jì)算機(jī)在物理上實(shí)現(xiàn)簡單，且具有可靠性高、處理簡單、抗干擾能力強(qiáng)

等優(yōu)點(diǎn)。

2.什么是定點(diǎn)數(shù)，它分為哪些種類？

答：所謂定點(diǎn)數(shù)，就是指計(jì)算機(jī)在運(yùn)算過程中，數(shù)據(jù)中小數(shù)點(diǎn)的位置固定不變。其中

小數(shù)點(diǎn)的位置是由計(jì)算機(jī)設(shè)計(jì)者在機(jī)器的結(jié)構(gòu)中指定一個(gè)不變的位置，而不?定都必須具

有小數(shù)點(diǎn)的指示裝置。定點(diǎn)數(shù)一般有小數(shù)和整數(shù)兩種表示形式。定點(diǎn)小數(shù)是把小數(shù)點(diǎn)固定

在數(shù)據(jù)數(shù)值部分的左邊，符號(hào)位的右邊；定點(diǎn)整數(shù)則把小數(shù)點(diǎn)固定在數(shù)據(jù)數(shù)值部分的右邊。

3.簡要敘述聲音的編碼過程。

答：計(jì)算機(jī)獲取聲音信息的過程即是聲音信號(hào)數(shù)字化的處理過程。經(jīng)過數(shù)字化處理后

的數(shù)字聲音信息才能被計(jì)算機(jī)所識(shí)別和處理。聲音被計(jì)算機(jī)處理的過程主要經(jīng)過音頻信號(hào)

的采樣、量化和編碼幾個(gè)過程。

4.簡述計(jì)算機(jī)軟件系統(tǒng)的分類。（系統(tǒng)軟件和應(yīng)用軟件兩方面）

軟件是指能在計(jì)算機(jī)上運(yùn)行的各種程序，包括各種有關(guān)的文檔。通常將軟件分為系統(tǒng)

軟件和應(yīng)用軟件兩大類。

1.系統(tǒng)軟件

可以把軟件分成若干層，最內(nèi)層是對(duì)硬件的擴(kuò)充與完善，而外層則是對(duì)內(nèi)層的再次擴(kuò)

充與完善。一般把靠近內(nèi)層、為方便使用和管理計(jì)算機(jī)資源的軟件，稱為系統(tǒng)軟件。系統(tǒng)

軟件通常是負(fù)責(zé)管理、控制和維護(hù)計(jì)算機(jī)的各種軟硬件資源，并為用戶提供一個(gè)友好的操

作界面，以及服務(wù)于一般目的的上機(jī)環(huán)境。系統(tǒng)軟件包括操作系統(tǒng)、計(jì)算機(jī)的監(jiān)控管理程

序、高級(jí)程序設(shè)計(jì)語言的編譯和解釋程序以及系統(tǒng)服務(wù)程序等。操作系統(tǒng)在系統(tǒng)軟件中處

于核心地位，其他的系統(tǒng)軟件在操作系統(tǒng)的支持下工作；高級(jí)程序設(shè)計(jì)語言的編譯和解釋

程序，將軟件工程師編寫的軟件“翻譯”成為計(jì)算機(jī)能夠“理解”的機(jī)器語言；系統(tǒng)服務(wù)

程序?yàn)橛?jì)算機(jī)系統(tǒng)的正常運(yùn)行提供服務(wù)。

2.應(yīng)用軟件

應(yīng)用軟件是針對(duì)某個(gè)應(yīng)用領(lǐng)域的具體問題而開發(fā)和研制的程序，它由專業(yè)人員為各種

應(yīng)用目的而開發(fā)。應(yīng)用軟件必須在系統(tǒng)軟件的支持下才能工作，它具有很強(qiáng)的實(shí)用性和專

業(yè)性，正是由于應(yīng)用軟件的開發(fā)和使用，才使得計(jì)算機(jī)的應(yīng)用日益滲透到社會(huì)的各行各業(yè)。

應(yīng)用軟件可以由用戶自己開發(fā)，也可在市場上購買。

常用的應(yīng)用軟件有：文字處理軟件，如WPS、Word等；電子表格軟件，如Excel、Lotus

等；圖形處理軟件，如3DMAX等；課件制作軟件，如PowerPoint、Authorware等；多媒

體處理軟件，如RealPlay、Medi埋layer等。

5.存儲(chǔ)器的功能是什么？

答：現(xiàn)代計(jì)算機(jī)是以存儲(chǔ)器為中心的計(jì)算機(jī)系統(tǒng)，存儲(chǔ)器是計(jì)算機(jī)的重要組成部分。

當(dāng)利用計(jì)算機(jī)完成某項(xiàng)任務(wù)時(shí)，首先把解決問題的程序和所需數(shù)據(jù)存于存儲(chǔ)器中，在執(zhí)行

程序時(shí)再由存儲(chǔ)器快速地提供給處理機(jī).顯然，存儲(chǔ)器的功能是存儲(chǔ)信息，被存儲(chǔ)的信息

包括程序信息和數(shù)據(jù)信息等。

6.存儲(chǔ)器的主要指標(biāo)是什么？

答：存儲(chǔ)器作為計(jì)算機(jī)系統(tǒng)的核心部件之一，有必要對(duì)其性能進(jìn)行描述。描述一個(gè)存

儲(chǔ)器性能優(yōu)劣的主要指標(biāo)有存儲(chǔ)容量、存儲(chǔ)周期和存取時(shí)間、可靠性、性能價(jià)格比、功耗、

可靠性等。

7.簡述存儲(chǔ)器的三級(jí)存儲(chǔ)體系分層結(jié)構(gòu)。

三級(jí)結(jié)構(gòu)的存儲(chǔ)器系統(tǒng)，是圍繞讀寫速度尚可、存儲(chǔ)容量適中的主存儲(chǔ)器來組織和運(yùn)

行的，并由高速緩沖存儲(chǔ)器緩解主存讀寫速度慢、不能滿足CPU運(yùn)行速度需耍的矛盾；用

虛擬存儲(chǔ)器更大的存儲(chǔ)空間來解決主存容量小、存不下規(guī)模更大的程序與更多數(shù)據(jù)的難題,

從而達(dá)到使整修存儲(chǔ)器系統(tǒng)有更高的讀寫速度、更大的存儲(chǔ)空間、相對(duì)較低的制造與運(yùn)行

成本的要求。追求整修存儲(chǔ)器系統(tǒng)有更高的性能價(jià)格比是三級(jí)存儲(chǔ)體系結(jié)構(gòu)的核心思想。

這種三級(jí)結(jié)構(gòu)的存儲(chǔ)器系統(tǒng)的運(yùn)行原理是建立在程序運(yùn)行的局部性原理之上的。程序運(yùn)行

的局部性原理體現(xiàn)在：

(1)時(shí)間的局部性原理。在一小段時(shí)間內(nèi)，最近被訪問過的程序和數(shù)據(jù)很可能再次被

訪問。

(2)空間局部性原理。即最近被往往集中在一小片存儲(chǔ)區(qū)域中。

(3)指令執(zhí)行順序的局部性原理。指令順序執(zhí)行比轉(zhuǎn)移執(zhí)行的可能性要大。

在三級(jí)結(jié)構(gòu)的存儲(chǔ)器系統(tǒng)中，所存儲(chǔ)的信息必須滿足如下原則：

?一致性原則

即同一個(gè)信息會(huì)同時(shí)存放在幾個(gè)級(jí)別的存儲(chǔ)器中，此時(shí)，這一信息在兒個(gè)級(jí)別的存儲(chǔ)

器中必須保持相同的值。

?包含性原則

處在內(nèi)層(即靠近CPU)存儲(chǔ)器中的信息一定被包含在各外層的存儲(chǔ)器中，即內(nèi)層存儲(chǔ)

器中的全部信息一定是各外層存儲(chǔ)器中所存信息中一小部分的副本，這是保證程序正常運(yùn)

行、實(shí)現(xiàn)信息共享、提高系統(tǒng)資源利用率所必需的，反之則不成立。

8.簡述多核的關(guān)鍵技術(shù)。

與單核處理器相比，多核處理器在體系結(jié)構(gòu)、軟件、功耗和安全性設(shè)計(jì)等方面面臨著

巨大的挑戰(zhàn)，但也蘊(yùn)含著巨大的潛能。

1.核結(jié)構(gòu)研究

CMP的構(gòu)成分成同構(gòu)和異構(gòu)兩類，同構(gòu)是指內(nèi)部咳的結(jié)構(gòu)是相同的，而異構(gòu)是指內(nèi)部

的核結(jié)構(gòu)是不同的。為此，面對(duì)不同的應(yīng)用研究核結(jié)構(gòu)的實(shí)現(xiàn)對(duì)未來微處理器的性能至關(guān)

重要。核本身的結(jié)構(gòu)，關(guān)系到整個(gè)芯片的面積、功耗和性能。怎樣繼承和發(fā)展傳統(tǒng)處理器

的成果，直接影響多核的性能和實(shí)現(xiàn)周期。同時(shí)，根據(jù)Amdahl定理，程序的加速比決定

于串行部分的性能，所以，從理論上來看似乎異構(gòu)微處理器的結(jié)構(gòu)具有更好的性能。

多核所用的指令系統(tǒng)對(duì)系統(tǒng)的實(shí)現(xiàn)也是很重要的，采用多核之間采用相同的指令系統(tǒng)

還是不同的指令系統(tǒng)，能否運(yùn)行操作系統(tǒng)等，也將是研究的內(nèi)容之一。

2.程序執(zhí)行模型

多核處理器設(shè)計(jì)的首要問題是選擇程序執(zhí)行模型。程序執(zhí)行模型的適用性決定多核處

理器能否以最低的代價(jià)提供最高的性能。程序執(zhí)行模型是編譯器設(shè)計(jì)人員與系統(tǒng)實(shí)現(xiàn)人員

之間的接口。編譯器設(shè)計(jì)人員決定如何將一種高級(jí)語言程序按一種程序執(zhí)行模型轉(zhuǎn)換成一

種目標(biāo)機(jī)器語言程序；系統(tǒng)實(shí)現(xiàn)人員則決定該程序執(zhí)行模型在具體目標(biāo)機(jī)器上的有效實(shí)

現(xiàn)。當(dāng)目標(biāo)機(jī)器是多核體系結(jié)構(gòu)時(shí)，產(chǎn)生的問題是：多核體系結(jié)構(gòu)如何支持重要的程序執(zhí)

行模型？是否有其他的程序執(zhí)行模型更適于多核的體系結(jié)構(gòu)？這些程序執(zhí)行模型能多大程

度上滿足應(yīng)用的需要并為用戶所接受？

3.Cache設(shè)“：多級(jí)Cache設(shè)與一致性問題

處理器和主存間的速度差距對(duì)CMP來說是個(gè)突出的矛盾，因此必須使用多級(jí)Cache

來緩解。目前有共享一級(jí)Cache的CMP、共享二級(jí)Cache的CMP以及共享主存的CMP。

通常，CMP采用共享二級(jí)Cache的CMP結(jié)構(gòu)，即每個(gè)處理器核心擁有私有的一級(jí)Cache,

且所有處理器核心共享二級(jí)CacheoCache自身的體系結(jié)構(gòu)設(shè)計(jì)也直接關(guān)系到系統(tǒng)整體性

能。但是在CMP結(jié)構(gòu)中，共享Cache或獨(dú)有Cache孰優(yōu)孰劣、需不需要在一塊芯片上建立

多級(jí)Cache,以及建立幾級(jí)Cache等等，由于對(duì)整個(gè)芯片的尺寸、功耗、布局、性能以及

運(yùn)行效率等都有很大的影響，因而這些都是需要認(rèn)真研究和探討的問題。另一方面，多級(jí)

Cache又引發(fā)一致性問題。采用何種Cache一致性模型和機(jī)制都將對(duì)CMP整體性能產(chǎn)生重

要影響。在傳統(tǒng)多處理器系統(tǒng)結(jié)構(gòu)中廣泛采用的Cache一致性模型有：順序一致性模型、

弱一致性模型、釋放一致性模型等。與之相關(guān)的Cache一致性機(jī)制主要有總線的偵聽協(xié)議

和基于目錄的目錄協(xié)議。目前的CMP系統(tǒng)大多采用基于總線的偵聽協(xié)議。

4.核間通信技術(shù)

CMP處理器的各CPU核心執(zhí)行的程序之間有時(shí)需要進(jìn)行數(shù)據(jù)共享與同步，因此其硬

件結(jié)構(gòu)必須支持核間通信。高效的通信機(jī)制是CMP處理器高性能的重要保障，目前比較主

流的片上高效通信機(jī)制有兩種，一種是基于總線共享的Cache結(jié)構(gòu)，一種是基于片上的互

連結(jié)構(gòu)。總線共享Cache結(jié)構(gòu)是指每個(gè)CPU內(nèi)核擁有共享的二級(jí)或三級(jí)Cache,用于保

存比較常用的數(shù)據(jù)，并通過連接核心的總線進(jìn)行通信。這種系統(tǒng)的優(yōu)點(diǎn)是結(jié)構(gòu)簡單，通信

速度高，缺點(diǎn)是基于總線的結(jié)構(gòu)可擴(kuò)展性較差。

基于片上互連的結(jié)構(gòu)是指每個(gè)CPU核心具有獨(dú)立的處理單元和Cache,各個(gè)CPU核

心通過交叉開關(guān)或片上網(wǎng)絡(luò)等方式連接在一起。各個(gè)CPU核心間通過消息通信。這種結(jié)構(gòu)

的優(yōu)點(diǎn)是可擴(kuò)展性好，數(shù)據(jù)帶寬有保證；缺點(diǎn)是硬件結(jié)構(gòu)復(fù)雜，且軟件改動(dòng)較大。也許這

兩者的競爭結(jié)果不是互相取代而是互相合作，例如在全局范圍采用片上網(wǎng)絡(luò)而局部采用總

線方式，來達(dá)到性能與復(fù)雜性的平衡。

5.總線設(shè)計(jì)

傳統(tǒng)微處理器中，Cache不命中或訪存事件都會(huì)對(duì)CPU的執(zhí)行效率產(chǎn)生負(fù)面影響，而

總線接口單元（BIU）的工作效率會(huì)決定此影響的程度。當(dāng)多個(gè)CPU核心同時(shí)要求訪問內(nèi)

存或多個(gè)CPU核心內(nèi)私有Cache同時(shí)出現(xiàn)Cache不命中事件時(shí)，BIU對(duì)這多個(gè)訪問請(qǐng)求的

仲裁機(jī)制以及對(duì)外存儲(chǔ)訪問的轉(zhuǎn)換機(jī)制的效率決定了CMP系統(tǒng)的整體性能。因此尋找高效

的多端口總線接口單元（BRJ）結(jié)構(gòu)，將多核心對(duì)主存的單字訪問轉(zhuǎn)為更為高效的猝發(fā)

（burst）訪問，同時(shí)尋找對(duì)CMP處理器整體效率最佳的一次Burst訪問字的數(shù)量模型以及

高效多端口BIU訪問的仲裁機(jī)制將是CMP處理器研究的重要內(nèi)容。

6.操作系統(tǒng)設(shè)計(jì)：任務(wù)調(diào)度、中斷處理、同步互斥

對(duì)于多核CPU,優(yōu)化操作系統(tǒng)任務(wù)調(diào)度算法是保證效率的關(guān)鍵。一般任務(wù)謊度算法有

全局隊(duì)列調(diào)度和局部隊(duì)列調(diào)度。前者是指操作系統(tǒng)維護(hù)一個(gè)全局的任務(wù)等待隊(duì)列，當(dāng)系統(tǒng)

中有一個(gè)CPU核心空閑時(shí)，操作系統(tǒng)就從全局任務(wù)等待隊(duì)列中選取就緒任務(wù)開始在此核心

上執(zhí)行。這種方法的優(yōu)點(diǎn)是CPU核心利用率較高。后者是指操作系統(tǒng)為每個(gè)CPU內(nèi)核維

護(hù)一個(gè)局部的任務(wù)等待隊(duì)列，當(dāng)系統(tǒng)中有一個(gè)CPU內(nèi)核空閑時(shí)，便從該核心的任務(wù)等待隊(duì)

列中選取恰當(dāng)?shù)娜蝿?wù)執(zhí)行，這種方法的優(yōu)點(diǎn)是任務(wù)基本上無需在多個(gè)CPU核心間切換，

有利于提高CPU核心局部Cache命中率。目前多數(shù)多核CPU操作系統(tǒng)采用的是基于全局

隊(duì)列的任務(wù)調(diào)度算法。

多核的中斷處理和單核有很大不同。多核的各處理器之間需要通過中斷方式進(jìn)行通信,

所以多個(gè)處理器之間的本地中斷控制器和負(fù)責(zé)仲裁各核之間中斷分配的全局中斷控制器也

需要封裝在芯片內(nèi)部。另外，多核CPU是一個(gè)多任務(wù)系統(tǒng)。由于不同任務(wù)會(huì)競爭共享資

源，因此需要系統(tǒng)提供同步與互斥機(jī)制。而傳統(tǒng)的用于單核的解決機(jī)制并不能滿足多核，

需要利用硬件提供的“讀一修改一寫”的原子操作或其他同步互斥機(jī)制來保證。

7.低功耗設(shè)計(jì)

半導(dǎo)體工藝的迅速發(fā)展使微處理器的集成度越來越高，同時(shí)處理器表面溫度也變得越

來越高并呈指數(shù)級(jí)增長，每三年處理器的功耗密度就能翻一番。目前，低功耗和熱優(yōu)化設(shè)

計(jì)已經(jīng)成為微處理器研究中的核心問題。CMP的多核心結(jié)構(gòu)決定了其相關(guān)的功耗研究是一

個(gè)至關(guān)重要的課題。低功耗設(shè)計(jì)是一個(gè)多層次問題，需要同時(shí)在操作系統(tǒng)級(jí)、算法級(jí)、結(jié)

構(gòu)級(jí)、電路級(jí)等多個(gè)層次上進(jìn)行研究。每個(gè)層次的低功耗設(shè)計(jì)方法實(shí)現(xiàn)的效果不同——抽

象層次越高，功耗和溫度降低的效果越明顯。

8.存儲(chǔ)器

為了使芯片內(nèi)核充分地工作，最起碼的要求是芯片能提供與芯片性能相匹配的存儲(chǔ)器

帶寬，雖然內(nèi)部Cache的容量能解決一些問題，但隨著性能的進(jìn)一步提高，必須有其他一

些手段來提高存儲(chǔ)器接口的帶寬，如增加單個(gè)管腳帶寬的DDR、DDR2、QDR、XDR等。

同樣，系統(tǒng)也必須有能提供高帶寬的存儲(chǔ)器。所以，芯片對(duì)封裝的要求也越來越高，雖然

封裝的管腳數(shù)每年以20%的數(shù)目提升，但還不能完全解決問題，而且還帶來了成本提高的

問題，為此，怎樣提供一個(gè)高帶寬，低延遲的接口帶寬，是必須解決的一個(gè)重要問題。

9.可靠性及安全性設(shè)計(jì)

隨著技術(shù)革新的發(fā)展，處理器的應(yīng)用滲透到現(xiàn)代社會(huì)的各個(gè)層面，但是在安全性方面

卻存在著很大的隱患。一方面，處理器結(jié)構(gòu)自身的可靠性低下，由于超微細(xì)化與時(shí)鐘設(shè)計(jì)

的高速化、低電源電壓化，設(shè)計(jì)上的安全系數(shù)越來越難以保證，故障的發(fā)生率逐漸走高。

另一方面，來自第三方的惡意攻擊越來越多，手段越來越先進(jìn)，已成為具有普遍性的社會(huì)

問題?，F(xiàn)在，可靠性與安全性的提高在計(jì)算機(jī)體系結(jié)構(gòu)研究領(lǐng)域備受注目。

今后，CMP這類處理器芯片內(nèi)有多個(gè)進(jìn)程同時(shí)執(zhí)行的結(jié)構(gòu)將成為主流，再加上硬件復(fù)

雜性、設(shè)計(jì)時(shí)的失誤增加，使得處理器芯片內(nèi)部也未必是安全的，因此，安全與可靠性設(shè)

計(jì)任重而道遠(yuǎn)。

9.什么是高性能計(jì)算機(jī)？

答：高性能計(jì)算機(jī)的概念并無明確的定義，一般認(rèn)為運(yùn)算速度非?？斓挠?jì)算機(jī)就可以

認(rèn)為是高性能計(jì)算機(jī)。嚴(yán)格地講，高性能計(jì)算機(jī)是一個(gè)擁有最先進(jìn)的硬件、軟件、網(wǎng)絡(luò)和

算法的綜合概念，“高性能”的標(biāo)準(zhǔn)是隨著技術(shù)的發(fā)展而發(fā)展的。

10.什么是接口？它的主要功能是什么？

答：在主機(jī)與外設(shè)進(jìn)行數(shù)據(jù)交換時(shí)必領(lǐng)引入相應(yīng)的邏輯部件解決兩者之間的同步與協(xié)

調(diào)、數(shù)據(jù)格式轉(zhuǎn)換等問題，這些邏輯部件就稱為輸入輸出接口，簡稱為接口。輸入輸出接

口的基本功能有：

(1)實(shí)現(xiàn)數(shù)據(jù)緩沖，提供主機(jī)和設(shè)備交換信息過程中的數(shù)據(jù)緩沖機(jī)構(gòu)，使主機(jī)與外設(shè)在

工作速度上達(dá)到匹配。

(2)實(shí)現(xiàn)數(shù)據(jù)格式的轉(zhuǎn)換，例如，當(dāng)主機(jī)和設(shè)備的信號(hào)同謀不同時(shí)的信號(hào)電平轉(zhuǎn)換功能、

數(shù)據(jù)傳送中的格式(串行、并行)轉(zhuǎn)換功能、直接內(nèi)存訪問中的額外需求等。

(3)提供外設(shè)和接口的狀態(tài)，為CPU更好地控制各種外設(shè)提供有效的幫助，交換主機(jī)

和外圍設(shè)備的狀態(tài)信息。

(4)實(shí)現(xiàn)主機(jī)與外設(shè)之間的通訊聯(lián)絡(luò)控制，實(shí)現(xiàn)主機(jī)與設(shè)備之間的數(shù)據(jù)交換。

11.簡述并行算法的基本內(nèi)容。

并行算法是在給定并行模型下的一種具體明確的計(jì)算方法和步驟，其分類有不同的分

類方法。

根據(jù)并行計(jì)算任務(wù)的大小分類，可以分為粗粒度并行算法、中粒度并行算法和細(xì)粒度

并行算法三類。粗粒度并行算法所含的計(jì)算任務(wù)有較大的計(jì)算量和較復(fù)雜的計(jì)算程序；中

粒度并行算法所含的計(jì)算任務(wù)的大小和計(jì)算程序的長短在粗粒度和細(xì)粒度兩種類型的算法

之間：細(xì)粒度并行算法所含的計(jì)算任務(wù)有較小的計(jì)算曾和較短的計(jì)算程序。

根據(jù)并行計(jì)算的基本對(duì)象可分為數(shù)值并行計(jì)算和非數(shù)值并行計(jì)算。非數(shù)值計(jì)算也會(huì)用

于高精度數(shù)值計(jì)算，數(shù)值計(jì)算中也會(huì)有查找、匹配等非數(shù)值計(jì)算成分，這兩者之間并無嚴(yán)

格的界限。實(shí)際分類時(shí)，主要是根據(jù)主要的計(jì)算量所屬范疇以及宏觀的計(jì)算方法來判斷。

根據(jù)并行計(jì)算進(jìn)程間的依賴關(guān)系可以分為同步并行算法和異步并行算法。前者是通過

一個(gè)全局的時(shí)鐘來控制各部分的步伐，將任務(wù)中的各個(gè)部分計(jì)算同步地向前推進(jìn)；而后者

執(zhí)行的各部分計(jì)算步伐之間沒有關(guān)聯(lián)，互不同步，在操作中，它們根據(jù)計(jì)算過程的不同階

段決定等待、繼續(xù)或終止。同步并行算法適合于SIMD并行計(jì)算機(jī)，異步并行算法適合于

MIMD并行計(jì)算機(jī)。

一個(gè)高效的并行算法設(shè)計(jì)過程比較復(fù)雜。一般編程設(shè)計(jì)過程可以分為任務(wù)劃分、通信

分析、任務(wù)組合和處理器映射四步。任務(wù)劃分階段主要將整個(gè)使用域或功能分解成一些小

的計(jì)算任務(wù)，它的目的是要揭示和開拓并行執(zhí)行的機(jī)會(huì)；通信分析則檢測在任務(wù)劃分階段

劃分的合理性；任務(wù)組合按照性能要求和實(shí)現(xiàn)的代價(jià)來考察前兩個(gè)階段的結(jié)果，必要時(shí)可

以將一些小的任務(wù)組合成更大的任務(wù)以提高執(zhí)行效率和減少通信開銷；處理器映射決定將

每一個(gè)任務(wù)分配到哪個(gè)處理器上去執(zhí)行，目的是要最小化全局執(zhí)行時(shí)間和通訊成本，并最

天化處理器的利用率。

12.什么是網(wǎng)絡(luò)計(jì)算機(jī)?它有什么優(yōu)點(diǎn)？

答：網(wǎng)絡(luò)計(jì)算機(jī)(NETWORKCOMPUTER)簡稱NC,是專用于高速網(wǎng)絡(luò)環(huán)境下的計(jì)算機(jī)終

端設(shè)備。是基于處理器芯片和網(wǎng)絡(luò)基礎(chǔ)的新一代計(jì)算機(jī)產(chǎn)品，是一種新的桌面計(jì)算機(jī)。NC

除了有人機(jī)交互必需的顯示器，鍵盤鼠標(biāo)外，它沒有硬盤，軟盤，光驅(qū)等外部存儲(chǔ)設(shè)備，

是一種瘦客戶機(jī)。網(wǎng)絡(luò)計(jì)算機(jī)具有以下優(yōu)點(diǎn)：

(1)易管理，維護(hù)簡單，使用方便。

(2)網(wǎng)絡(luò)計(jì)算機(jī)沒有硬盤，軟盤和光盤，也沒有風(fēng)扇，在硬件方面沒有什么可維護(hù)的地

方，大大減少了計(jì)算機(jī)網(wǎng)絡(luò)的維護(hù)工作，成本低廉。

(3)安全性強(qiáng)，無論是防止病毒的侵犯，還是資料維護(hù)的安全，NC都比PC耍好的多。

(4)靜音節(jié)能，高可靠網(wǎng)絡(luò)計(jì)算機(jī)沒有任何噪音，非常安靜。網(wǎng)絡(luò)計(jì)算機(jī)的功耗非常小。

三,討論題

1.為什么計(jì)算機(jī)使用二進(jìn)制，而不使用人們生活中的十進(jìn)制來表示數(shù)據(jù)信息。

答案略。

2.計(jì)算機(jī)系統(tǒng)的存儲(chǔ)器分為哪幾個(gè)層次？(原題已刪除)

答案略。

3.網(wǎng)絡(luò)計(jì)算機(jī)有許多優(yōu)點(diǎn)，請(qǐng)結(jié)合其特點(diǎn)談?wù)勎覈l(fā)展網(wǎng)絡(luò)計(jì)算機(jī)的前途。

答案略。

第3章程序設(shè)計(jì)語言

習(xí)題

一、選擇題

1.A2.A3.D4.A5.AB

6.C7.D8.D9.ABCD1().B

11.A12.A

二、簡答題

1.簡述程序的概念。

答：一個(gè)程序就是能夠?qū)崿F(xiàn)特定功能的一組指令序列的集合。或者程序=算法+數(shù)據(jù)

結(jié)構(gòu)。

2.簡述程序設(shè)計(jì)過程的一般步驟。

程序設(shè)計(jì)的過程一般有四個(gè)步驟。

1.分析問題

在著手解決問題之前，應(yīng)該通過分析，充分理解問題，明確原始數(shù)據(jù)、解題要求、需

要輸出的數(shù)據(jù)及形式等。

2.設(shè)計(jì)算法

算法是解題的過程。首先集中精力于算法的總體規(guī)劃，然后逐層降低問題的抽象性，

逐步充實(shí)細(xì)節(jié)，直到最終把抽象的問題具體化成可用程序語句表達(dá)的算法。這是一個(gè)自上

而下、逐步細(xì)化的過程。

3.編碼

利用程序設(shè)計(jì)語言表示算法的過程稱為編碼。

4.調(diào)試程序

調(diào)試程序包括編譯和連接等操作。編譯程序?qū)⒃闯绦蜣D(zhuǎn)換為目標(biāo)程序，它對(duì)程序員編

寫的源程序進(jìn)行語法檢查，程序員根據(jù)編譯過程中的錯(cuò)誤提示信息，查找并改正源程序的

錯(cuò)誤后再重新編譯，直到?jīng)]有語法錯(cuò)誤為止。大多數(shù)程序設(shè)計(jì)語言還要使用連接程序把目

標(biāo)程序與系統(tǒng)提供的庫文件進(jìn)行連接以得到最終的可執(zhí)行文件。在連接過程中若程序使用

了錯(cuò)誤的內(nèi)部函數(shù)名，將會(huì)引起連接錯(cuò)誤。對(duì)于經(jīng)過編譯和連接，并最終運(yùn)行結(jié)束的程序,

程序員還要對(duì)程序執(zhí)行的結(jié)果進(jìn)行分析，只有得到正確結(jié)果的程序才是所需的程序。

3.簡述機(jī)器語言和匯編語言的共同特點(diǎn)。

匯編語言具有一個(gè)木質(zhì)上與機(jī)器語言一一對(duì)應(yīng)的指令系統(tǒng)。大多數(shù)情況下,

一條匯編指令直接對(duì)應(yīng)一條機(jī)器指令，少數(shù)匯編指令對(duì)應(yīng)幾條機(jī)器指令，所以,

匯編語言的實(shí)質(zhì)和機(jī)器語言是相同的。與機(jī)器指令一樣，匯編指令直接針對(duì)計(jì)

算機(jī)硬件進(jìn)行操作，要求程序員具有較為深厚的計(jì)算機(jī)專業(yè)知識(shí)；每一條指令

只能實(shí)現(xiàn)一個(gè)非常細(xì)微的操作(例如移動(dòng)、自增)，因而源程序一般比較冗長、

復(fù)雜、容易出錯(cuò)。

4.簡述高級(jí)語言程序的運(yùn)行過程。

使用高級(jí)語言編寫程序的一般過程可以歸納為以下幾個(gè)步驟：

(1)使用文本編輯工具，逐條編寫源程序的語句。保存源程序的文件時(shí)，文件的后綴

名與所用的高級(jí)語言有關(guān)。

(2)編譯源程序文件，生成目標(biāo)文件，文件后綴名通常為obj。

(3)鏈接目標(biāo)文件，生成可執(zhí)行文件，文件后綴名通常為exe。

(4)在計(jì)算機(jī)上運(yùn)行可執(zhí)行程序，并進(jìn)行調(diào)試和維護(hù)。

程序的執(zhí)行環(huán)境由操作系統(tǒng)提供，一般分為命令行環(huán)境和圖形用戶界面環(huán)境。在DOS

與大多數(shù)Unix類操作系統(tǒng)中，提供的就是命令行用戶界面，用戶需要在系統(tǒng)命令提示符后

面輸入各種操作命令以實(shí)現(xiàn)需要的功能；在Windows操作系統(tǒng)中，提供的是圖形用戶界面,

用戶可以通過點(diǎn)擊鼠標(biāo)等操作完成希望的功能。“界面就是程序”反映了在程序設(shè)計(jì)中為用

戶提供良好的操作界面的重要性。用戶使用界面的好壞直接影響著程序的質(zhì)量，要樹立以

人為本的思想，盡量為用戶提供便利。

5.簡述編譯程序的概念。

編譯程序是把高級(jí)語言程序（源程序）作為一個(gè)整體來處理，在應(yīng)用源程序執(zhí)行之前，

就將程序源代碼“翻譯”成目標(biāo)代碼（機(jī)器語言），編譯后與系統(tǒng)提供的代碼庫鏈接，形成

一個(gè)完整的可執(zhí)行的機(jī)器語言程序（目標(biāo)程序代碼）。

6.用圖示法表示編譯程序的框架。

答：編譯程序的框架如圖所示:

表格管理

口

M三

或

SM2百

煉

大

尢

與

夕

宸

百S

本

燈

舞6

然

運(yùn)

運(yùn)

7.詞法分析的任務(wù)是什么？

答：作為編譯過程的第一個(gè)階段，其任務(wù)是從左到右一個(gè)字符，一個(gè)字符地對(duì)源程序

進(jìn)行掃描，讀入源程序，對(duì)構(gòu)成源程序的字符流進(jìn)行掃描和分解，通過詞法分析從而識(shí)別

出一個(gè)個(gè)單詞（也稱單詞符號(hào)或符號(hào)）。

8.語法分析的任務(wù)是什么？

答：語法分析是編譯過程的第二個(gè)階段，任務(wù)是在詞法分析的基礎(chǔ)上將單

詞序列分解成各類語法短語，如“程序”、“語句”、“表達(dá)式”等等。

9.簡述語義處理的功能。

答：編譯過程中的語義處理實(shí)現(xiàn)兩個(gè)功能：

（1）審查每個(gè)語法結(jié)構(gòu)的靜態(tài)語義，即驗(yàn)證語法結(jié)構(gòu)合法的程序是否真正有

意義，有時(shí)把這個(gè)工作稱為靜態(tài)語義分析或靜態(tài)審查。

（2）如果靜態(tài)語義正確，則語義處理要執(zhí)行真正的翻譯，要么生成程序的一種中間表

示形式（中間代碼），要么生成實(shí)際的目標(biāo)代碼。

10.簡述中間代碼的概念。

答：所謂“中間代碼”是一種結(jié)構(gòu)簡單、含義明確的記號(hào)系統(tǒng)，這種記號(hào)

系統(tǒng)可以設(shè)計(jì)為多種多樣的形式，重要的設(shè)計(jì)原則為兩點(diǎn)：一是容易生成；二

是容易將它翻譯成目標(biāo)代碼。

H.目標(biāo)代碼生成階段的任務(wù)是什么？

答：目標(biāo)代碼生成階段的任務(wù)是把中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重

定位的指令代碼或匯編指令代碼。這是編譯的最后階段，它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令

含義有關(guān)，這個(gè)階段的工作很復(fù)雜，涉及到硬件系統(tǒng)功能部件的運(yùn)用、機(jī)器指令的選擇、

各種數(shù)據(jù)類型變量的存儲(chǔ)空間分配以及寄存器和后援寄存器的調(diào)度等。

三、討論題

1.作為一個(gè)計(jì)算機(jī)專業(yè)的學(xué)生，程序設(shè)計(jì)是大學(xué)學(xué)習(xí)的重要內(nèi)容之一，程序設(shè)計(jì)的內(nèi)

容很多，語言的更新也很快，如何才能更好地掌握程序設(shè)計(jì)？如何利用語言編程？怎樣才

能克服害怕編程的思想？

答案略。

2.根據(jù)你的理解，學(xué)習(xí)程序設(shè)計(jì)語言的過程中，最重要的注意事項(xiàng)是什么？

答案略。

第4章程序設(shè)計(jì)基礎(chǔ)

習(xí)題

一、選擇題

I.C2.A3B4.D5.A

6.B7.C8.D9.B10.D

二、簡答題

1.結(jié)構(gòu)化程序設(shè)計(jì)的思想是什么？

答：結(jié)構(gòu)化程序設(shè)計(jì)的基本思想就是采用白頂向下、逐步求精的設(shè)計(jì)方法和單入口單

日口的控制結(jié)構(gòu)。

2.結(jié)構(gòu)化程序設(shè)計(jì)的原則是什么？

答：結(jié)構(gòu)化程序設(shè)計(jì)的原則是：

(1)使用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)表示程序邏輯。

(2)程序語句組織成容易識(shí)別的語句模塊，每個(gè)模塊都是單入口、單出口。

(3)嚴(yán)格控制GOTO語句的使用。

3.結(jié)構(gòu)化程序設(shè)計(jì)語言采用自頂向下的方法進(jìn)行程序設(shè)計(jì)的特點(diǎn)是什么？

答：利用結(jié)構(gòu)化程序設(shè)計(jì)語言采用自頂向下的方法進(jìn)行程序設(shè)計(jì)的特點(diǎn)是:

(1)問題分解成子問題的結(jié)構(gòu)必須與3種基本程序結(jié)構(gòu)之一相對(duì)應(yīng)。

(2)問題的劃分決定了程序的結(jié)構(gòu)。一方面，子問題的劃分決定了這一層次

的程序是3種基本結(jié)構(gòu)中的哪一種結(jié)構(gòu)；另一方面，一個(gè)問題該如何劃分成子

問題是靈活的，并不是只有一種分解方法。分解的好壞就決定了設(shè)計(jì)的質(zhì)量，

也決定了程序的不同結(jié)構(gòu)。

(3)問題的邊界應(yīng)該清晰明確。只有這樣才能精確地解決這些子問題，否則

就會(huì)模棱兩可，無從下手。

4.簡述面向?qū)ο蠛徒Y(jié)構(gòu)化程序設(shè)計(jì)的區(qū)別。

答：面向?qū)ο笫菑谋举|(zhì)上區(qū)別于傳統(tǒng)的結(jié)構(gòu)化方法的一種新方法、新思路。它吸收了

結(jié)構(gòu)化程序設(shè)計(jì)的全部優(yōu)點(diǎn)，同時(shí)又考慮到現(xiàn)實(shí)世界與計(jì)算機(jī)之間的關(guān)系，認(rèn)為現(xiàn)實(shí)世界

是由一系列彼此相關(guān)并且能夠相互通信的實(shí)體組成，這些實(shí)體就是面向?qū)ο蠓椒ㄖ械膶?duì)象,

每個(gè)對(duì)象都有自己的自然屬性和行為特征，而一類相似對(duì)象的共性的抽象描述，就是面向

對(duì)象方法中的核心——類。

5.什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)的物理結(jié)構(gòu)有哪些？

答：數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)元素之間的相互關(guān)系的集合，包括了數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)

構(gòu)以及數(shù)據(jù)的運(yùn)算。

數(shù)據(jù)的物理結(jié)構(gòu)主要有四種，分別是順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)及散列結(jié)構(gòu)。

(1)順序結(jié)構(gòu)：是把所有元素存放在一片連續(xù)的存儲(chǔ)單元中，邏輯上相鄰的元素存儲(chǔ)在

物理位置相鄰的存儲(chǔ)單元中，由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。

(2)鏈表結(jié)構(gòu)：對(duì)邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過附

設(shè)的指針域來表示，由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

(3)索引結(jié)構(gòu)：每個(gè)數(shù)據(jù)結(jié)構(gòu)建立索引表，每個(gè)數(shù)據(jù)元素占用表中的一項(xiàng)，每個(gè)表項(xiàng)通

常包含關(guān)鍵字和地址指針。其中的關(guān)鍵字是能夠惟一標(biāo)志一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。

(4)散列結(jié)構(gòu)：通過構(gòu)造相應(yīng)的散列函數(shù)，由散列函數(shù)的值來確定元素存放的地址。

三、討論題

題目已變

1.在進(jìn)行程序設(shè)計(jì)時(shí)，語言的選擇尤為重要，根據(jù)你對(duì)程序設(shè)計(jì)語言的了解，談?wù)勀?/p>

對(duì)程序設(shè)計(jì)的認(rèn)識(shí)。

答案略。

2.如何才能選擇一個(gè)好的數(shù)據(jù)結(jié)構(gòu)進(jìn)行程序設(shè)計(jì)。

答案略。

第5章算法與復(fù)雜性

習(xí)題

一、選擇題

1.B2.D3.C4.A5.B

6.B7.D8.C9.A10.A

二、簡答題

i.什么是算法，算法的特性有哪些?

答：“算法(Algorithm)是一組明確的、可以執(zhí)行的步驟的有序集合，它在有限的時(shí)間內(nèi)

終止并產(chǎn)生結(jié)果”。算法的特性有：

(1)有窮性(可終止性)：一個(gè)算法必須在有限個(gè)操作步驟內(nèi)以及合理的有限

時(shí)間內(nèi)執(zhí)行完成。

(2)確定性：算法中的每一個(gè)操作步驟都必須有明確的含義，不允許存在二

義性。

(3)有效性(可執(zhí)行性)：算法中描述的操作步驟都是可執(zhí)行的，并能最終得

到確定的結(jié)果。

(4)輸入及輸出：一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入數(shù)據(jù)、有1個(gè)或多個(gè)輸出數(shù)據(jù)。

2.什么是算法的時(shí)間復(fù)雜度和空間復(fù)雜度，如何表示？

答：時(shí)間復(fù)雜度是與求解問題規(guī)模、算法輸入相關(guān)的函數(shù)，該函數(shù)表示算法運(yùn)行所花

費(fèi)的時(shí)間。記為，7(〃)，其中，n代表求解問題的規(guī)模。

算法的空間復(fù)雜度(Spacecomplexity)度量算法的空間復(fù)雜性、即執(zhí)行算法的程序在計(jì)算

機(jī)中運(yùn)行所占用空間的大小。簡單講，空間復(fù)雜度也是與求解問題規(guī)模、算法輸入相關(guān)的

函數(shù)。記為，SS),其中，n代表求解問題的規(guī)模。

時(shí)間夏雜度和空間豆雜度同樣，引入符號(hào)來表示丁(〃)、5(〃)與求解問題規(guī)模nZ

間的數(shù)量級(jí)關(guān)系。

3.用圖示法表示語言處理的過程。

答：語言處理的過程如圖所示：

骨架程序

絕對(duì)機(jī)器碼

4.簡述算法設(shè)計(jì)的策略。

答：作為實(shí)現(xiàn)計(jì)算機(jī)程序?qū)崿F(xiàn)時(shí)解決問題的方法，算法研究的內(nèi)容是解決問題的方法，

而不是計(jì)算機(jī)程序的本身。一個(gè)優(yōu)秀的算法可以運(yùn)行在比較慢的計(jì)算機(jī)上，但一個(gè)劣質(zhì)的

算法在一臺(tái)性能很強(qiáng)的計(jì)算機(jī)上也不一定能滿足應(yīng)用的需要，因此在計(jì)算機(jī)程序設(shè)計(jì)中，

算法設(shè)計(jì)往往處于核心地位。

要想充分理解算法并有效地應(yīng)用于實(shí)際問題，關(guān)鍵是對(duì)算法的分析。通?？梢岳脤?shí)

驗(yàn)對(duì)比分析?、數(shù)學(xué)方法來分析算法。實(shí)驗(yàn)對(duì)比分析很簡單，兩個(gè)算法相互比較，它們都能

解決同一問題，在相同環(huán)境下，一般就會(huì)認(rèn)為哪個(gè)算法的速度快這個(gè)算法性能更好。在算

法設(shè)計(jì)中，通常采用能近似表達(dá)性能的方法來展示某個(gè)算法的性能指標(biāo)例如，計(jì)算機(jī)對(duì)〃2

和〃2+2〃的響應(yīng)速度，當(dāng)n比較大的時(shí)?，沒什么區(qū)別，便可直接認(rèn)為后者算法的復(fù)雜度為

基于算法復(fù)雜度簡化表達(dá)的思想基礎(chǔ)上，通常會(huì)對(duì)算法進(jìn)行最壞情況分析和平均情況

分析。對(duì)于一個(gè)給定的算法，如果能保證它的最壞情況下的性能依然很好，但是在某些情

況下，程序的最壞情況算法的運(yùn)行時(shí)間和實(shí)際情況的運(yùn)行時(shí)間相差很大，在實(shí)際應(yīng)用中幾

乎不會(huì)碰到最壞情況下的輸入，那么此時(shí)進(jìn)行最壞情況分析顯得有些畫蛇添足，特別是分

析最壞情況算法會(huì)花費(fèi)大量精力的時(shí)候。算法的平均情況分析可以幫助估計(jì)程序的性能，

作為算法分析的基本指標(biāo)之一，但是平均情況和實(shí)際情況仍然會(huì)有相差很大的時(shí)候，這時(shí)

便可以使用隨機(jī)法來盡量模擬現(xiàn)實(shí)中的情況，這樣可以得到在嚴(yán)格的概率意義上的預(yù)測運(yùn)

行時(shí)間。另外，對(duì)于一個(gè)經(jīng)典算法，沒有必要再去對(duì)該算法進(jìn)行改進(jìn)，研究它的上界和下

界，只需要了解該算法的特性，然后在合適的時(shí)候使月它。

5.簡述并行算法研究的內(nèi)容。

答：(1)并行計(jì)算模型并行算法作為一門學(xué)科，首先研究的是并行計(jì)算模型。并行計(jì)

算模型是算法設(shè)II者與體系結(jié)構(gòu)研究者之間的一個(gè)橋梁，是并行算法設(shè)訂和分析的基礎(chǔ)。

它屏蔽了并行機(jī)之間的差異，從并行機(jī)中抽取若干個(gè)能反映計(jì)算特性的可計(jì)算或可測量的

參數(shù)，并按照模型所定義的計(jì)算行為構(gòu)造成本函數(shù)，以此進(jìn)行算法的復(fù)雜度分析。

并行計(jì)算模型的第一代是共享存儲(chǔ)模型，如SIMD-SM和MIMD-SM的一些計(jì)算模型，模

型參數(shù)主要是CPU的單位計(jì)算時(shí)間，這樣科學(xué)家可以忽略一些細(xì)節(jié)，集中精力設(shè)計(jì)算法。

第二代是分布存儲(chǔ)模型。在這個(gè)階段，人們逐漸意識(shí)到對(duì)并行計(jì)算機(jī)性能帶來影響的不僅

僅是CPU,還有通信。因此如何把不同的通信性能抽象成模型參數(shù)，是這個(gè)階段的研究重

點(diǎn)。第三代是分布共享存儲(chǔ)模