《計算機科學(xué)導(dǎo)論》復(fù)習(xí)資料-楊巨峰

1、課程名稱計算機科學(xué)導(dǎo)論教材信息名稱計算機科學(xué)導(dǎo)論出版社清華大學(xué)出版社作者瞿中、熊安萍、蔣溢版次2010年3月第3版寫給同學(xué)們的幾點說明：1、關(guān)于教材由于計算機科學(xué)導(dǎo)論課程涉及的內(nèi)容廣泛，任何一本教材均無法完全覆蓋所有知識點。所以同學(xué)們在復(fù)習(xí)時應(yīng)該以教學(xué)課件為主，指定教材僅供輔助參考使用。本復(fù)習(xí)資料提供的例題將全部指明其所考知識點在教學(xué)課件中的章節(jié)和頁碼。2、關(guān)于考試題型和試卷結(jié)構(gòu)單項選擇（10道題、每題2分、共20分）；判斷題（5道題、每題2分、共10分）；名詞解釋（6道題、每題5分、共30分）；簡答題（3道題、每題10分、共30分）；分析設(shè)計題（1道題、每題10分、共10分）。3、關(guān)于考試范

2、圍全部試題涉及的知識點在教學(xué)課件中均有體現(xiàn)，在本復(fù)習(xí)資料中也有示例。一、客觀部分：（單項選擇、判斷）（一）、選擇部分1、17世紀(jì),（ ）發(fā)明了第一個數(shù)字計算器A、PascalB、LeibnizC、JacquardD、Babbage考核知識點: 計算硬件的發(fā)展歷程（第1章ppt第21頁）2、內(nèi)存的概念首次出現(xiàn)在（ ）當(dāng)中A、算盤B、分析機C、織布機D、數(shù)字計算器考核知識點: 計算硬件的發(fā)展歷程（第1章ppt第22頁）3、第一代計算機使用（ ）存儲信息A、真空管B、晶體管C、集成電路D、光纖考核知識點: 計算硬件的發(fā)展歷程（第1章ppt第25頁）4、下列哪種語言是面向?qū)ο蟮木幊陶Z言（ ）A、Pas

3、calB、BASICC、CD、C+考核知識點: 計算軟件的發(fā)展歷程（第1章ppt第35-36頁）5、滿足個人應(yīng)用要求，體積小、價格便宜的計算機屬于（ ）A、個人計算機B、小型計算機C、大型計算機D、超級計算機考核知識點: 計算機的類型（第1章ppt第80頁）6、下列選項中不屬于計算機存儲設(shè)備的是（ ）A、內(nèi)存B、光盤C、磁盤驅(qū)動器D、U盤考核知識點:計算機硬件設(shè)備（第1章ppt第83頁）7、在計算機軟件層次結(jié)構(gòu)中，位于匯編語言內(nèi)層的是（ ）A、應(yīng)用軟件B、操作系統(tǒng)C、高級語言D、機器語言考核知識點: 計算機軟件層次（第1章ppt第89頁）8、數(shù)字836的基數(shù)可能是（ ）A、2B、5C、7D、1

4、0考核知識點: 位置計數(shù)法（第2章ppt第5頁）9、下面哪個數(shù)字用來表示任何計數(shù)系統(tǒng)中的基數(shù)值（ ）A、01B、10C、100D、101考核知識點: 位置計數(shù)法（第2章ppt第5頁）10、十三進(jìn)制下的數(shù)字943與十進(jìn)制下的哪個數(shù)含有相同多的實體（ ）A、13B、69C、1576D、943考核知識點: 位值計數(shù)法（第2章ppt第5-6頁）11、二進(jìn)制數(shù)1010110表示為十進(jìn)制數(shù)應(yīng)該是（ ）A、86B、68C、1010110D、0110101考核知識點: 二進(jìn)制向十進(jìn)制轉(zhuǎn)換（第2章ppt第8頁）12、下列哪個句子不屬于命題（ ）A、北京是中國的首都B、1=1=2C、2+2=3dD、幾點了?考核知

5、識點: 命題和邏輯（第3章ppt第5頁）13、半加法器和全加法器的區(qū)別是（ ）A、是否產(chǎn)生進(jìn)位B、是否處理以前的進(jìn)位C、是否產(chǎn)生和位D、是否處理以前的和位考核知識點: 電路設(shè)計（第3章ppt第69-75頁）14、三變元卡諾圖包含幾個方塊（ ）A、3B、6C、8D、9考核知識點: 利用卡諾圖化簡電路（第3章ppt第81-95頁）15、在某些電路中，由于輸入值的一些組合從未出現(xiàn)過，所以對其輸出值可以任意選擇，函數(shù)對于這種組合的值稱為（ ）A、無需在意條件B、無需在意結(jié)果C、最優(yōu)選擇條件D、最優(yōu)選擇結(jié)果考核知識點: 利用卡諾圖化簡電路時無需在意的條件（第3章ppt第96頁）16、下列哪種元件不在中央

6、處理器的內(nèi)部（ ）A、運算器B、控制器C、寄存器D、存儲器考核知識點: 馮諾依曼體系（第3章ppt第128、144頁）17、下列選項哪個是用于軟件需求分析的工具（ ）A、數(shù)據(jù)流程圖B、系統(tǒng)結(jié)構(gòu)圖C、程序流程圖D、偽代碼考核知識點: 需求分析（第4章ppt第153頁）18、按傳輸距離劃分，計算機網(wǎng)絡(luò)不包括（ ）A、廣域網(wǎng)B、城域網(wǎng)C、局域網(wǎng)D、無線網(wǎng)考核知識點: 計算機網(wǎng)絡(luò)的分類（第5章ppt第10頁）19、OSI網(wǎng)絡(luò)參考模型中位于第四層的是（ ）A、表示層B、會話層C、傳輸層D、網(wǎng)絡(luò)層考核知識點: OSI參考模型（第5章ppt第24頁）20、在中，cn表示（ ）A、組織B、國家C、網(wǎng)絡(luò)D、主機

7、考核知識點: 域名系統(tǒng)（第5章ppt第35-37頁）（二）、判斷部分1、硬件是計算機系統(tǒng)中有形的裝置和設(shè)備的總稱。（ ）考核知識點: 計算硬件的發(fā)展歷程（第1章ppt第17頁）2、機器語言是內(nèi)置在計算機電路中的指令，用助記碼表示。（ ）考核知識點: 計算軟件的發(fā)展歷程（第1章ppt第30頁）3、如果有三個或更多重復(fù)字符出現(xiàn)，適宜使用行程長度編碼進(jìn)行壓縮。（ ）考核知識點: 行程長度編碼（第2章ppt第64-66頁）4、布爾代數(shù)提供的是在集合0,1上的運算和規(guī)則。（ ）考核知識點: 布爾代數(shù)（第3章ppt第22頁）5、門是對電信號執(zhí)行基礎(chǔ)運算的設(shè)備，用于接受一個輸入信號，生成一個輸出信號。（ ）

8、考核知識點: 門（第3章ppt第53頁）6、編譯器是把用高級語言編寫的程序翻譯成機器碼的程序。（ ）考核知識點: 編譯器（第4章ppt第55頁）7、實體是指某種抽象事物的集合。（ ）考核知識點: E-R模型（第6章ppt第31頁）8、軟件僅指與計算機有關(guān)的程序。（ ）考核知識點: 計算軟件的發(fā)展歷程（第1章ppt第29頁）9、不同數(shù)形的兩個數(shù)字可能表示同等數(shù)量的實體。（ ）考核知識點:等值原理（第2章ppt第6頁）10、視頻中的一幅圖像叫做一幀。（ ）考核知識點: 視頻（第2章ppt第100頁）11、穩(wěn)定排序算法是指占用有限額外空間的算法。（ ）考核知識點: 排序算法（第4章ppt第96頁）1

9、2、軟件危機完全是由軟件自身的特點決定的。（ ）考核知識點: 軟件危機（第4章ppt第135-137頁）13、網(wǎng)絡(luò)協(xié)議就是為網(wǎng)絡(luò)數(shù)據(jù)交換而制定的規(guī)則。（ ）考核知識點: 計算機網(wǎng)絡(luò)協(xié)議（第5章ppt第17頁）二、主觀部分：（名詞解釋、簡答、分析設(shè)計）（一）、名詞解釋1、位置計數(shù)法考核知識點：位置計數(shù)法的概念（第2章ppt第5頁）2、模擬數(shù)據(jù)考核知識點：模擬數(shù)據(jù)的概念（第2章ppt第15頁）3、數(shù)字?jǐn)?shù)據(jù)考核知識點：數(shù)字?jǐn)?shù)據(jù)的概念（第2章ppt第15頁）4、原碼考核知識點：原碼的概念（第2章ppt第28頁）5、補碼考核知識點：補碼的概念（第2章ppt第32頁）6、反碼考核知識點：反碼的概念（第2章

10、ppt第37頁）7、溢出考核知識點：溢出的概念（第2章ppt第38頁）8、字符集考核知識點：字符集的概念（第2章ppt第53頁）9、RGB表示法考核知識點：RGB表示法的概念（第2章ppt第85頁）10、布爾代數(shù)考核知識點：布爾代數(shù)的概念（第3章ppt第22頁）11、布爾函數(shù)考核知識點：布爾函數(shù)的概念（第3章ppt第29頁）12、文字考核知識點：文字的概念（第3章ppt第47頁）13、小項考核知識點：小項的概念（第3章ppt第47頁）14、積之和展開式考核知識點：積之和展開式的概念（第3章ppt第48頁）15、門考核知識點：門的概念（第3章ppt第53頁）16、電路考核知識點：電路的概念（第3

11、章ppt第53頁）17、無需在意的條件考核知識點：無需在意的條件的概念（第3章ppt第96頁）18、指令考核知識點：指令的概念（第3章ppt第131頁）19、程序考核知識點：程序的概念（第3章ppt第132頁）20、驅(qū)動程序考核知識點：驅(qū)動程序的概念（第3章ppt第198頁）21、算法考核知識點：算法的概念（第4章ppt第8頁）22、編譯器考核知識點：編譯器的概念（第4章ppt第55頁）23、基本操作考核知識點：基本操作的概念（第4章ppt第76頁）24、T(n)考核知識點：T(n)的概念（第4章ppt第77頁）25、排序問題考核知識點：排序問題的概念（第4章ppt第96頁）26、穩(wěn)定排序算法

12、考核知識點：穩(wěn)定排序算法的概念（第4章ppt第96頁）27、原址排序算法考核知識點：原址排序算法的概念（第4章ppt第96頁）28、計算機網(wǎng)絡(luò)考核知識點：計算機網(wǎng)絡(luò)的概念（第5章ppt第7頁）29、數(shù)據(jù)庫考核知識點：數(shù)據(jù)庫的概念（第6章ppt第24頁）（二）、簡答題1、請以圖形的形式敘述計算硬件的發(fā)展歷程考核知識點：計算硬件的發(fā)展歷程（第1章ppt第17頁）附2.2.1：（考核知識點解釋）繪制該圖時應(yīng)力求完整，即從計算硬件的雛形、發(fā)展、成熟一直繪制到當(dāng)前的情況，其中時間軸及各時間段圖形可以適當(dāng)簡化。2、請以圖形的形式敘述計算軟件的發(fā)展歷程考核知識點：計算軟件的發(fā)展歷程（第1章ppt第29頁）【

13、參考答案】附2.2.2：（考核知識點解釋）繪制該圖時應(yīng)力求完整，即從計算軟件的雛形、發(fā)展、成熟一直繪制到當(dāng)前的情況，其中時間軸及各時間段圖形可以適當(dāng)簡化。3、簡述計算機的四種類型及各自的特點考核知識點：計算機的類型和特點（第1章ppt第80頁）【參考答案】個人計算機 滿足個人應(yīng)用要求，體積小、價格便宜 臺式機（Desktop）、便攜式計算機（Laptop、Notebook）小型計算機 體積比個人計算機大一點，計算與存儲能力更強 適用于中小型企業(yè)和科研機構(gòu)的計算處理要求大型計算機 體積更大，需要專門的機房和維護(hù)環(huán)境 系統(tǒng)性能更高，數(shù)據(jù)存儲空間更大 一般用于大型企業(yè)和科研機構(gòu)的數(shù)據(jù)中心和計算服務(wù)平

14、臺超級計算機 擁有遠(yuǎn)勝于其他計算機的計算能力和存儲能力 用于國家戰(zhàn)略服務(wù)和專項的超級數(shù)據(jù)計算4、請解釋等值原理并說明其應(yīng)用領(lǐng)域考核知識點：等值原理（第2章ppt第6頁）【參考答案】不同數(shù)形的兩個數(shù)字可能表示同等數(shù)量的實體 Base=10 1576(10) Base=13 943(13)=9*132+4*131+3*130=1521+52+3散列法 是一種將字符串轉(zhuǎn)換為更短長度數(shù)值的方法，廣泛應(yīng)用于索引、加密等領(lǐng)域 其中一種散列算法就是進(jìn)行基數(shù)轉(zhuǎn)換5、二進(jìn)制數(shù)1010110、八進(jìn)制數(shù)754、十六進(jìn)制數(shù)ABC轉(zhuǎn)換為十進(jìn)制后各是多少考核知識點：其他進(jìn)制向十進(jìn)制的轉(zhuǎn)換（第2章ppt第8頁）【參考答案】

15、1010110(2)=1*26+1*24+1*22+1*21=86(10)754(8)=7*82+5*81+4*80=448+40+4=492(10) ABC(16)=10*162+11*161+12*160=2560+176+12=2748(10) 附2.2.5：（考核知識點解釋）解決其他進(jìn)制向十進(jìn)制的轉(zhuǎn)換問題關(guān)鍵是掌握位置計數(shù)法的原理，將待轉(zhuǎn)換數(shù)字的每一位的數(shù)值和位值相乘，然后在求其累加和即可。以八進(jìn)制數(shù)754為例，右起第1位的位值是80=1，數(shù)值是4，乘積是4；第2位的位值是81=8，數(shù)值是5，乘積是40；第3位的位值是82=64，數(shù)值是7，乘積是448，所以最后轉(zhuǎn)換得到的十進(jìn)制數(shù)是44

16、8+40+4=492。6、十進(jìn)制數(shù)43轉(zhuǎn)換為二進(jìn)制、八進(jìn)制、十六進(jìn)制各是多少考核知識點：十進(jìn)制向其他進(jìn)制的轉(zhuǎn)換（第2章ppt第12-13頁）【參考答案】43(10)=32+8+2+1=101011(2)43(10)=5*8+3*1=53(8)43(10)=2*16+11*1=2B(16)附2.2.6：（考核知識點解釋）解決十進(jìn)制向其他進(jìn)制的轉(zhuǎn)換問題關(guān)鍵是找到該十進(jìn)制數(shù)中含有多少個待轉(zhuǎn)換進(jìn)制的整數(shù)冪。以十進(jìn)制數(shù)43轉(zhuǎn)換為八進(jìn)制為例，數(shù)制8的整數(shù)冪是1、8、64、，顯然43中包含了5個8和3個1，所以結(jié)果是53(8)。7、列舉幾種常見的音頻格式考核知識點：音頻格式（第2章ppt第76-81頁）【參

17、考答案】wav、cda、mp3、mid、wma8、列舉幾種常見的圖像格式考核知識點：圖像格式（第2章ppt第94-98頁）【參考答案】jpg、bmp、gif、tif、png9、列舉幾種常見的視頻格式考核知識點：視頻格式（第2章ppt第102-103頁）【參考答案】avi、asf、divx、mov、rmvb10、列舉色彩三要素及其含義考核知識點：計算機的顏色系統(tǒng)（第2章ppt第83頁）【參考答案】亮度 描述光作用于人眼時引起的明暗程度感覺 彩色光輻射的功率越大，亮度越高 彩色光輻射的功率越小，亮度越低 色調(diào) 描述人眼看到光時產(chǎn)生的彩色感覺 顏色的類別 不同波長的光呈現(xiàn)不同的顏色 色飽和度 某一顏

18、色的深淺程度（濃度） 高飽和度的深色光可摻入白色光被沖淡11、說明顯示分辨率和圖像分辨率的異同考核知識點：分辨率（第2章ppt第91-93頁）【參考答案】顯示分辨率 顯示屏上能夠顯示出的像素數(shù)目 顯示分辨率越高，顯示的圖像質(zhì)量越高圖像分辨率 組成一幅圖像的像素密度，表示為每英寸多少點 對于同樣大小的一幅圖像 Ø 組成的像素數(shù)目越多，則分辨率越高，圖像越逼真 Ø 組成的像素數(shù)目越少，則分辨率越低，圖像越粗糙顯示分辨率 VS 圖像分辨率 前者確定顯示圖像的區(qū)域大小 后者確定組成一幅圖像的像素數(shù)目 圖像分辨率>顯示分辨率時，屏幕上顯示部分圖像 圖像分辨率<顯示分辨率時

19、，圖像只占屏幕的一部分12、說明視頻壓縮的常用方法考核知識點：視頻壓縮（第2章ppt第101頁）【參考答案】時間壓縮 根據(jù)連續(xù)幀之間的差別壓縮電影的技術(shù) 空間壓縮 基于靜態(tài)圖像的壓縮方法的電影壓縮技術(shù)13、簡述布爾函數(shù)最小化的作用考核知識點：布爾函數(shù)最小化的作用（第3章ppt第79頁）【參考答案】作用 降低成本 提高電路可靠性 在一塊芯片上設(shè)計更合適的電路 減少電路計算時間 14、繪制馮諾依曼體系結(jié)構(gòu)考核知識點：馮諾依曼體系（第3章ppt第128頁）【參考答案】附2.2.14：（考核知識點解釋）馮諾依曼體系的結(jié)構(gòu)示意圖是本課程的一個重點，繪制該圖有兩個要點：一是準(zhǔn)確繪制計算機的三大核心模塊，即

20、CPU、存儲器、輸入輸出設(shè)備；二是準(zhǔn)確繪制上述設(shè)備之間傳遞數(shù)據(jù)、指令、控制信號的路徑。15、請說明驅(qū)動程序和應(yīng)用程序的異同考核知識點：驅(qū)動程序和應(yīng)用程序的異同（第3章ppt第198-201頁）【參考答案】每個位于總線上的設(shè)備必須包含系統(tǒng)設(shè)備管理器下的驅(qū)動程序，但不一定都包含應(yīng)用程序；驅(qū)動程序位于操作系統(tǒng)下層，提供設(shè)備的存取操作；應(yīng)用程序位于操作系統(tǒng)上層，不需要直到設(shè)備所用地址、信號種類或者通信協(xié)議16、請繪圖說明算法復(fù)雜度的漸進(jìn)性質(zhì)考核知識點：算法復(fù)雜度（第4章ppt第78頁）【參考答案】如果解決問題P的算法A和算法B，其時間復(fù)雜度分別是TA(n)和TB(n)，則判斷A、B性能優(yōu)劣的標(biāo)準(zhǔn)是查看

21、在n足夠大時TA(n)和TB(n)的大小關(guān)系17、請說明冒泡排序算法的原理考核知識點：冒泡排序（第4章ppt第100頁）【參考答案】比較表中的相鄰元素，如果它們是逆序的話就交換它們的位置；重復(fù)多次以后，最小的元素就像氣泡一樣升到了列表的第一個位置；第二遍操作將第二小的元素升起來；這樣一直做，直到n-1遍以后，該列表就排好序了18、請說明快速排序算法的原理考核知識點：快速排序（第4章ppt第105頁）【參考答案】按照元素的值進(jìn)行劃分；對給定數(shù)組中的元素進(jìn)行重新排列，以得到一個快速排序的分區(qū)；在一個分區(qū)中，所有在s下標(biāo)之前的元素都小于等于As，所有在s下標(biāo)之后的元素都大于等于As；建立了一個分區(qū)以

22、后，As已經(jīng)位于它在有序數(shù)組中的最終位置。接下來使用同樣的方法繼續(xù)對As前和As后的子數(shù)組分別進(jìn)行排序19、請對比操作系統(tǒng)與應(yīng)用軟件的異同考核知識點：操作系統(tǒng)和應(yīng)用軟件的異同（第6章ppt第3-4頁）【參考答案】應(yīng)用軟件是計算機用戶利用計算機的軟件、硬件資源為某一專門的應(yīng)用目的而開發(fā)的軟件；操作系統(tǒng)則負(fù)責(zé)有效地組織和管理系統(tǒng)中的各種軟硬件資源，合理地組織計算機系統(tǒng)工作流程，控制程序的執(zhí)行，并向用戶提供一個良好的工作環(huán)境和友好的接口20、請繪圖說明數(shù)據(jù)庫建模與實現(xiàn)過程考核知識點：數(shù)據(jù)庫（第6章ppt第29頁）【參考答案】（三）、分析與設(shè)計題1、設(shè)計一個兩路開關(guān)電路并繪制其電路圖考核知識點：面向應(yīng)

23、用的簡單電路設(shè)計（第3章ppt第64-65頁）【參考答案】第一步：由題意分析當(dāng)?shù)谝粋€開關(guān)關(guān)閉時，令x=1，否則為0當(dāng)?shù)诙€開關(guān)關(guān)閉時，令y=1，否則為0當(dāng)燈是打開時，令F(x,y)=1，否則為0假設(shè)當(dāng)兩個開關(guān)都是關(guān)閉時，燈是打開的 因此，該問題對應(yīng)的真值表是：x y F(x,y) 1 1 1 1 0 0 0 0 1 0 1 0 第二步：滿足上述要求輸出值的一個布爾表達(dá)式是：所求的電路是：附2.3.1：（考核知識點解釋）由一個實際問題設(shè)計對應(yīng)電路是第3章的一個重要知識點，其基本步驟是：首先分析題意，了解所要求解的問題，做出合理假設(shè)；其次根據(jù)題意列出對應(yīng)的真值表，然后找到真值表中函數(shù)值取1的行，提取這些情況下各自變量的取值（真或假），