(含答案)《計算機(jī)科學(xué)導(dǎo)論》課程復(fù)習(xí)大綱

《(含答案)《計算機(jī)科學(xué)導(dǎo)論》課程復(fù)習(xí)大綱》由會員分享，可在線閱讀，更多相關(guān)《(含答案)《計算機(jī)科學(xué)導(dǎo)論》課程復(fù)習(xí)大綱（14頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、一、名詞解釋 1、位置計數(shù)法：講義第2章ppt第5頁 一種表達(dá)數(shù)字的系統(tǒng)，數(shù)位按順序排列，每個數(shù)位有一個位值，數(shù)字的值是每個數(shù)位和位值的乘積之和 2、模擬數(shù)據(jù)：講義第2章ppt第15頁 是一種連續(xù)表示法，模擬它表示的真實信息 3、數(shù)字?jǐn)?shù)據(jù)：講義第2章ppt第15頁 是一種離散表示法，把信息分割成了獨立的元素 4、原碼： 課本P37，講義第2章ppt第28頁 將數(shù)的符號數(shù)碼化，即用一個二進(jìn)制位表示符號：對整數(shù)，該位取0，對負(fù)數(shù)，該位取1。而數(shù)值部分保持?jǐn)?shù)的原由形式（有時需要在高位部分添幾個0）。這樣所得結(jié)果為該數(shù)的原碼表示。 5、補(bǔ)碼：課本P37 ，講義第2章ppt第32頁，

2、 一個負(fù)數(shù)加模的結(jié)果即是該數(shù)的補(bǔ)碼，它與該負(fù)數(shù)等價，或者說是一對一的，一個正數(shù)的補(bǔ)碼就是它本身 6、反碼：課本P37，講義第2章ppt第37頁 正數(shù)的反碼與其原碼、補(bǔ)碼相同；負(fù)數(shù)的反碼等于原碼除符號位外，按位求反；[X]補(bǔ)= [X]反+1 7、溢出：講義第2章ppt第38頁 當(dāng)運(yùn)算的結(jié)果超出某種數(shù)據(jù)類型所表示的數(shù)的范圍時，機(jī)器不能正確表示，這時要產(chǎn)生溢出；在溢出的情況下，機(jī)器將產(chǎn)生錯誤的結(jié)果 8、字符集：講義第2章ppt第53頁 字符集：字符和表示它們的代碼的清單；常用字符集：ASCII、Unicode 9、RGB表示法：講義第2章ppt第85頁 在計算機(jī)中，顏色通常用RGB(

3、red-green-blue)值表示，其中的三個數(shù)字說明了每種基色的份額 如果用0~255之間的數(shù)字表示一種元素的份額，0：該顏色沒有參與；255：該顏色完全參與其中 10、布爾代數(shù)：講義第3章ppt第22頁 – 提供的是集合{0,1}上的運(yùn)算和規(guī)則 – 這個集合及布爾代數(shù)的規(guī)則被用來研究電子和光學(xué)開關(guān) 主要代數(shù)運(yùn)算：補(bǔ)、和、積 11、布爾函數(shù)：講義第3章ppt第29頁 設(shè)B={0,1}， 則Bn={(x1，x2，……，xn)|xi∈B，1≤i ≤n}是由0和1所能構(gòu)成的所有n元有序列的集合 從Bn到B的函數(shù)稱為n度布爾函數(shù) x稱為布爾變元 12、文字：講義第3章ppt第

4、47頁 – 布爾變元或其補(bǔ) 14、小項：講義第3章ppt第47頁 – 布爾變元x1，x2，……，xn的小項是一個布爾積y1y2……yn，其中yi=xi，或 – 小項是n個文字的積，每個文字對應(yīng)于一個變元 – 一個小項對一個且只對一個變元值的組合取值1 15、積之和展開式：講義第3章ppt第48頁 – 給定一個布爾函數(shù)，可以構(gòu)造小項的布爾和使得：當(dāng)此布爾函數(shù)具有值1時它的值為1，當(dāng)此布爾函數(shù)具有值0時它的值為0 – 此布爾和中的小項與使得此函數(shù)值為1的值的組合對應(yīng) – 表示布爾函數(shù)的小項的和稱為此函數(shù)的積之和展開式或析取范式 16、門：講義第3章p

5、pt第53頁 – 對電信號執(zhí)行基礎(chǔ)運(yùn)算的設(shè)備，接受一個或者多個輸入信號，生成一個輸出信號 – 門是構(gòu)成數(shù)字邏輯電路的基元，基本的門電路包括與、或、非、異或、與非、或非 17、電路：講義第3章ppt第53頁 – 相互關(guān)聯(lián)的門的組合，用于實現(xiàn)特定的邏輯函數(shù) – 計算機(jī)的所有硬件都是使用不同的電路復(fù)合而成 – 電路主要分為組合電路和時序電路 邏輯框圖與真值表：講義第3章ppt第53頁 – 邏輯框圖：電路的圖形化表示，不同類型的門有專用符號 – 真值表：列出了所有可能的輸入值和相關(guān)輸出值的表，用于分析電路的輸入輸出規(guī)律 18、無需在意條件：講義第3章ppt第96頁 – 在某些電路

6、中，由于輸入值的一些組合從未出現(xiàn)過，所以對其輸出值可以任意選擇，函數(shù)對于這種組合的值稱為無需在意條件 – 在卡諾圖中，用d作其記號 19、指令：講義第3章ppt第131頁 ? 將計算機(jī)看成是一臺信息處理機(jī) ? 處理只能一步一步地進(jìn)行，一次進(jìn)行一項基本操作 ? 指令：人給機(jī)器下達(dá)的完成一項基本操作的命令 ? 指令只能由1和0來編寫 20、程序：講義第3章ppt第132頁 ? 完成一項任務(wù)需要將其分解成一系列能由指令實現(xiàn)的基本操作，即一系列指令 ? 程序：完成一項任務(wù)所需的并且按照一定順序排列起來的一系列指令 21、驅(qū)動程序：講義第3章ppt第198頁 ? 是一種可以使計算機(jī)

7、和設(shè)備通信的特殊程序，可以說相當(dāng)于硬件的接口，操作系統(tǒng)只有通過這個接口，才能控制硬件設(shè)備的工作 ? 底層硬件是設(shè)備管理和操作的最終執(zhí)行者，驅(qū)動程序則體現(xiàn)系統(tǒng)的設(shè)備控制能力，也是硬件設(shè)備存在的基本條件 ? 越高級的操作系統(tǒng)需要安裝的驅(qū)動程序越少 22、算法：講義第4章ppt第8頁 – 在有限的時間內(nèi)用有限的數(shù)據(jù)解決問題或子問題的明確指令集合 23、編譯器：講義第4章ppt第55頁 編譯器：把用高級語言編寫的程序翻譯成機(jī)器碼的程序 24、基本操作：講義第4章ppt第76頁 指算法運(yùn)行中起主要作用且花費(fèi)最多時間的操作 – 兩個實數(shù)矩陣的乘法問題中，矩陣的實數(shù)元素之間的數(shù)乘 – 對

8、N個整數(shù)進(jìn)行排序的算法中，整數(shù)間的比較和交換 25、T(n)：講義第4章ppt第77頁 – 算法的時間復(fù)雜度，用問題實例長度的函數(shù)表示 – 也就是用該算法用于問題長度為n的實例所需要的基本操作次數(shù)來刻畫 26、排序問題：講義第4章ppt第95頁 – 是人們對數(shù)據(jù)集合最常用的基本操作之一 – 通訊錄或電話本中記錄一般按照人名的字典順序排列 – 打牌時按牌色和點數(shù)排列 – 體育比賽的獲獎情況按實際成績排序 – 所有計算機(jī)工作中，排序占25%以上 27、穩(wěn)定排序算法：講義第4章ppt第96頁 – 相同大小的元素不被交換的算法 28、原址排序算法：講義第4章ppt第96頁 –

9、 占用有限額外空間或者說額外空間與n無關(guān) 29、計算機(jī)網(wǎng)絡(luò)：講義第5章ppt第7頁 計算機(jī)網(wǎng)絡(luò)是為了通信和共享資源而以各種方式連在一起的一組計算設(shè)備。 30、數(shù)據(jù)庫：講義第6章ppt第27頁 按照數(shù)據(jù)結(jié)構(gòu)來組織、存儲和管理數(shù)據(jù)的倉庫，綜合管理多個實體眾多記錄和字段，更加靈活實用 二、簡答題 1、請敘述計算硬件的發(fā)展歷程 講義第1章ppt第17頁 1936年圖靈機(jī)是計算機(jī)的理論模型，計算機(jī)的發(fā)展到目前為止共經(jīng)歷了四個時代，從1946年到1959年這段時期我們稱之為“電子管計算機(jī)時代”。第一代計算機(jī)的內(nèi)部元件使用的是電子管。從1960年到1964年，由于在計算機(jī)中采用了比電子管

10、更先進(jìn)的晶體管，所以我們將這段時期稱為“晶體管計算機(jī)時代”。晶體管比電子管小得多，不需要暖機(jī)時間，消耗能量較少，處理更迅速、更可靠。從1965年到1970年，集成電路被應(yīng)用到計算機(jī)中來，因此這段時期被稱為“中小規(guī)模集成電路計算機(jī)時代”。集成電路（Integrated Circuit，簡稱r）是做在晶片上的一個完整的電子電路，這個晶片比手指甲還小，卻包含了幾千個晶體管元件。從1971年到現(xiàn)在，被稱之為“大規(guī)模集成電路計算機(jī)時代”。第四代計算機(jī)使用的元件依然是集成電路，不過，這種集成電路已經(jīng)大大改善，它包含著幾十萬到上百萬個晶體管，人們稱之為大規(guī)模集成電路（LargeScale lntegrate

11、d Circuit，簡稱LSI）和超大規(guī)模集成電路（Very Large Scale lntegrated Circuit，簡稱VLSI）。 2、請敘述計算軟件的發(fā)展歷程 講義第1章ppt第29頁 1946年第一臺電子計算機(jī)問世以來，計算機(jī)已被廣泛地應(yīng)用于生產(chǎn)、生活的各個領(lǐng)域，推動著社會的進(jìn)步與發(fā)展。計算機(jī)科學(xué)的發(fā)展依賴于計算機(jī)硬件和軟件技術(shù)的發(fā)展，軟件是用計算機(jī)語言編寫的。計算機(jī)語言的發(fā)展經(jīng)歷了從機(jī)器語言、匯編語言到高級語言的歷程。 20世紀(jì)50年代初（1951-1959年），計算機(jī)發(fā)明之初，科學(xué)家只能用二進(jìn)制數(shù)編制的指令控制計算機(jī)運(yùn)行。機(jī)器語言是計算機(jī)唯一能識別并直接執(zhí)行的語言

12、，每一條計算機(jī)指令均由一組“0”、“1”數(shù)字，按一定的規(guī)則排列組成，若要計算機(jī)執(zhí)行一項簡單的任務(wù)，需要編寫大量的這種指令。這種有規(guī)則的二進(jìn)制數(shù)組成的指令集，就是機(jī)器語言（也稱為指令系統(tǒng)）。 20世紀(jì)50年代末（1959-1965年），出現(xiàn)了匯編語言。匯編語言用比較容易識別、記憶的助記符替代特定的二進(jìn)制串。匯編語言是符號化的機(jī)器語言，執(zhí)行效率仍接近于機(jī)器語言。 1970年，瑞士計算機(jī)科學(xué)家Niklaus.Wirth開發(fā)了第一個結(jié)構(gòu)化程序設(shè)計語言—Pascal語言，標(biāo)志著結(jié)構(gòu)化程序設(shè)計時期的開始。Pascal語言的簡潔明了以及豐富的數(shù)據(jù)結(jié)構(gòu)，為程序員提供了極大的方便性與靈活性，同時它特別適合微

13、計算機(jī)系統(tǒng)。結(jié)構(gòu)化程序設(shè)計方法也在整個20世紀(jì)70年代的軟件開發(fā)中占絕對統(tǒng)治地位。除Pascal語言外，常見的結(jié)構(gòu)化程序設(shè)計語言還有C、FORTRAN、True BASIC等。 1990年以來，面向?qū)ο蠓治?、測試、度量和管理等研究得到了長足的發(fā)展，并在全世界掀起了一股面向?qū)ο鬅岢?，至今盛行不衰。面向?qū)ο蟪绦蛟O(shè)計在軟件開發(fā)領(lǐng)域掀起了巨大的變革，極大地提高了軟件開發(fā)效率。 3、簡述計算機(jī)的四種類型及各自的特點 講義第1章ppt第80頁 ? 個人計算機(jī) – 滿足個人應(yīng)用要求，體積小、價格便宜 – 臺式機(jī)（Desktop）、便攜式計算機(jī)（Laptop、Notebook） ? 小型計算機(jī)

14、 – 體積比個人計算機(jī)大一點，計算與存儲能力更強(qiáng) – 適用于中小型企業(yè)和科研機(jī)構(gòu)的計算處理要求 ? 大型計算機(jī) – 體積更大，需要專門的機(jī)房和維護(hù)環(huán)境 – 系統(tǒng)性能更高，數(shù)據(jù)存儲空間更大 – 一般用于大型企業(yè)和科研機(jī)構(gòu)的數(shù)據(jù)中心和計算服務(wù)平臺 ? 超級計算機(jī) – 擁有遠(yuǎn)勝于其他計算機(jī)的計算能力和存儲能力 – 用于國家戰(zhàn)略服務(wù)和專項的超級數(shù)據(jù)計算 4、請解釋等值原理并說明其應(yīng)用領(lǐng)域 講義第2章ppt第6頁 是一種將字符串轉(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)換

15、為十進(jìn)制后各是多少 講義第2章ppt第8頁 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 6、十進(jìn)制數(shù)43轉(zhuǎn)換為二進(jìn)制、八進(jìn)制、十六進(jìn)制各是多少 講義第2章ppt第12頁 43(10)=101011(2) 43(10)=53(8) 43(10)=2B(16) 7、說明字符表示的基本思想并列舉兩種常用的字符集 講義第2章ppt第52頁 ? 基本思想： 列出所有字

16、符，賦予每個字符一個二進(jìn)制字符串 要存儲一個特定的字母，保存它對應(yīng)的串即可 ? 需要表示和保存的字符 英語字母，阿拉伯?dāng)?shù)字，標(biāo)點符號，空格 8、比較關(guān)鍵字編碼和行程長度編碼的基本思想及特點 講義第2章ppt第58頁 關(guān)鍵字編碼（特點：用單個字符代替常用的單詞） 在文本中有一些常見詞匯 the，and，which，that，what 如果這些單詞占用更少的空間，文檔就會減小 即使每個單詞節(jié)省的空間有限，但是整個文檔節(jié)省的總空間仍可能非?？捎^ 行程長度編碼（重復(fù)字符的序列用標(biāo)志字符，后面加重復(fù)字符和說明字符重復(fù)次數(shù)的數(shù)字替換） 迭代編碼 把一系列重復(fù)字符替

17、換為它們重復(fù)出現(xiàn)的次數(shù) 常用于一些大規(guī)模數(shù)據(jù)流中 9、說明赫夫曼編碼的基本思想和編碼規(guī)則 講義第2章ppt第67頁 基本思想 在常規(guī)字符集中，每個字符都由定長的位串表示 文本中很少使用字母“X”，為什么要讓它占用的位數(shù)與其他常用字符一樣呢？ 為了解決這一問題，應(yīng)該用不同長度的位串表示每個字符 令較少的位表示經(jīng)常出現(xiàn)的字符，而將較長的位串留給不經(jīng)常出現(xiàn)的字符，這樣文檔的整體大小將比較小 編碼規(guī)則 列出要編碼的字符出現(xiàn)的頻率 編碼令出現(xiàn)頻率最高的字符擁有最短位串 同時保證表示一個字符的位串不會是表示另一個字符的位串的前綴 10、列舉幾種常見的音頻格式 講

18、義第2章ppt第77頁 .wav （Microsoft公司用于Windows平臺的音頻文件格式） .cda（音質(zhì)最好的音頻格式） .mp3（目前處于統(tǒng)治地位的音頻數(shù)據(jù)格式，動態(tài)影像專家壓縮標(biāo)準(zhǔn)音頻層面3） .mid（可供數(shù)字合成器和其他設(shè)備交換信息） .wma（既有較好的音質(zhì)，又適合于在網(wǎng)絡(luò)傳播） .ra，.rm，.rmx（主要用于在低速廣域網(wǎng)上實時傳輸音頻信息、質(zhì)量較差） 11、列舉幾種常見的圖像格式 講義第2章ppt第95頁以后 .jpg（對色彩的信息保留較好） .bmp（不采用任何壓縮，文件較大） .gif（一個gif文件中可以存多幅彩色圖像，從而形成動畫） .t

19、if（占用空間大，較完整的保留原有信息） .png（經(jīng)常用于Java程序，特別是Java手機(jī)程序中） 12、列舉幾種常見的視頻格式 講義第2章ppt第95頁 .avi（兼容好，調(diào)用方便，圖像質(zhì)量好、文件較大） ASF、MPEG、DIVX、MOV、RMVB 13、列舉色彩三要素及其含義 講義第2章ppt第103頁 ? 亮度 描述光作用于人眼時引起的明暗程度感覺 彩色光輻射的功率越大，亮度越高 彩色光輻射的功率越小，亮度越低 ? 色調(diào) 描述人眼看到光時產(chǎn)生的彩色感覺 顏色的類別 不同波長的光呈現(xiàn)不同的顏色 ? 色飽和度 某一顏色的深淺程度（濃度）

20、 高飽和度的深色光可摻入白色光被沖淡 14、說明顯示分辨率和圖像分辨率的異同 講義第2章ppt第91-92頁 顯示分辨率 顯示屏上能夠顯示出的像素數(shù)目 如果顯示分辨率為1024*768 ? 顯示屏分成768行 ? 每行顯示1024個像素 ? 整個顯示屏含有796432個像素點 顯示分辨率越高，顯示的圖像質(zhì)量越高 圖像分辨率 組成一幅圖像的像素密度，表示為每英寸多少點 如果用200dpi掃描一幅2*2.5英寸的彩色照片，則得到一幅400*500個像素點的圖像 對于同樣大小的一幅圖像 ? 組成的像素數(shù)目越多，則分辨率越高，圖像越逼真 ? 組成的像素數(shù)目越少

21、，則分辨率越低，圖像越粗糙 15、說明視頻壓縮的常用方法及適用范圍 講義第2章ppt第102頁 ? 時間壓縮—根據(jù)連續(xù)幀之間的差別壓縮電影的技術(shù) ? 空間壓縮—基于靜態(tài)圖像的壓縮方法的電影壓縮技術(shù) 16、設(shè)計并繪制三人多數(shù)表決器電路 講義第3章ppt第62頁 某個組織的一切事務(wù)都由一個三人委員會決定，每個委員對提出的建議可以投贊成票或反對票。一個建議如果得到了至少兩張贊成票就獲通過。設(shè)計一個電路，來判斷建議是否獲得通過 ? 分析 – 如果第一個委員投贊成票，則令x=1，否則為0 – 如果第二個委員投贊成票，則令y=1，否則為0 – 如果第三個委員投贊成票，則令z=1，否則

22、為0 – 必須設(shè)計一個電路使得對于輸入x、y、z，如果其中至少有兩個為1，則此電路產(chǎn)生輸出1 17、設(shè)計并繪制兩路開關(guān)電路 講義第3章ppt第64頁 – 某盞燈需要由兩個開關(guān)控制，當(dāng)燈是關(guān)閉時，按下任何一個開關(guān)都可以打開此燈；當(dāng)燈是打開時，按下任何一個開關(guān)都可以關(guān)閉此燈。 ? 分析 – 當(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)閉時，燈是打開的 18、設(shè)計并繪制三路開關(guān)電路 講義第3章ppt第66頁 – 某盞燈需要由三個開關(guān)控制，當(dāng)燈是關(guān)閉時，按下任何一個開

23、關(guān)都可以打開此燈；當(dāng)燈是打開時，按下任何一個開關(guān)都可以關(guān)閉此燈。 ? 分析 – 當(dāng)?shù)谝粋€開關(guān)關(guān)閉時，令x=1，否則為0 – 當(dāng)?shù)诙€開關(guān)關(guān)閉時，令y=1，否則為0 – 當(dāng)?shù)谌齻€開關(guān)關(guān)閉時，令z=1，否則為0 – 當(dāng)燈是打開時，令F(x,y,z)=1，否則為0 – 假設(shè)當(dāng)三個開關(guān)都是關(guān)閉時，燈是打開的 19、設(shè)計并繪制半加法器電路 講義第3章ppt第68頁 20、簡述布爾函數(shù)最小化的作用 講義第3章ppt第79頁 – 產(chǎn)生布爾積的布爾和，使其包含的文字之積的個數(shù)最少，這個過程稱作布爾函數(shù)的最小化。 – 相應(yīng)的電路含有最少的門和最少的輸入。 ? 作用 – 降低成本

24、 – 提高電路可靠性 – 在一塊芯片上設(shè)計更合適的電路 – 減少電路計算時間 21、繪制馮諾依曼體系結(jié)構(gòu)并說明其核心部件的功能 講義第3章ppt第128頁 22、請說明鼠標(biāo)的基本構(gòu)件 講義第3章ppt第173頁 23、請說明驅(qū)動程序和應(yīng)用程序的異同 講義第3章ppt第198-201頁 ? 每個位于總線上的設(shè)備必須包含系統(tǒng)設(shè)備管理器下的驅(qū)動程序，但不一定都包含應(yīng)用程序 ? 驅(qū)動程序位于操作系統(tǒng)下層，提供設(shè)備的存取操作 ? 應(yīng)用程序位于操作系統(tǒng)上層，不需要直到設(shè)備所用位置、信號種類或者通信協(xié)議 ? Windows\system下存放著一些驅(qū)動程序 24、你是如何理

25、解自頂向下和面向?qū)ο髢煞N設(shè)計方法的？它們有何異同？講義第4章ppt第28-40頁 自頂向下設(shè)計 一種程序開發(fā)技術(shù)，其中問題被分解為更容易處理的子問題，這些子問題的解決方案組合起來構(gòu)成整體問題的解決方案，面向過程設(shè)計是一種自頂向下逐步求精的設(shè)計方法,是單入口單出口的程序結(jié)構(gòu).設(shè)計者用一個main函數(shù)概括出整個應(yīng)用程序需要做的事,而main函數(shù)由對一系列子函數(shù)的調(diào)用組成.其特征是以函數(shù)為中心,用函數(shù)來作為劃分程序的基本單位,數(shù)據(jù)在過程式設(shè)計中往往處于從屬的位置. ? 模塊—一個用于解決問題或子問題的封閉步驟集合 ? 抽象步驟—細(xì)節(jié)仍未明確的算法步驟 ? 具體步驟—細(xì)節(jié)完全明確的算法步驟

26、 面向?qū)ο? 面向?qū)ο蟮某绦蛟O(shè)計的基本思想是使用對象、類、繼承、封裝、消息等基本概念來進(jìn)行程序設(shè)計,允許開發(fā)者從問題的局部開始,一點一點地構(gòu)建出整個程序,在開發(fā)過程中逐步加深對系統(tǒng)的理解.面向?qū)ο笤O(shè)計以數(shù)據(jù)為中心,類作為表現(xiàn)數(shù)據(jù)的工具,是劃分程序的基本單位. ? 對象—在問題背景中具有意義的事物或?qū)嶓w ? 類—描述了一組類似的對象，它們有一些共同的屬性和行為 ? 方法—處理對象中數(shù)據(jù)的指定算法，定義了類的某種行為 25、請繪圖說明算法復(fù)雜度的漸進(jìn)性質(zhì) 講義第4章ppt第78頁 如果解決問題P的算法A和算法B，其時間復(fù)雜度分別是TA(n)和TB(n)，則判斷A、B性能優(yōu)劣的標(biāo)準(zhǔn)是查看

27、在n足夠大時TA(n)和TB(n)的大小關(guān)系 26、請說明冒泡排序算法的原理 講義第4章ppt第100頁 對尚未排序的各元素從頭到尾依次比較相鄰的兩個元素是否逆序（與欲排順序相反），若逆序就交換這兩元素，經(jīng)過第一輪比較排序后便可把最大（或最小）的元素排好，然后再用同樣的方法把剩下的元素逐個進(jìn)行比較，就得到了你所要的順序。可以看出如果有 n 個元素，那么一共要進(jìn)行 n-1 輪比較，第 i 輪要進(jìn)行 j=n-i 次比較。（如：有5個元素，則要進(jìn)行5-1輪比較。第3輪則要進(jìn)行5-3次比較）經(jīng)過優(yōu)化后的算法根據(jù)不同的情況有可能減小排序的次數(shù) 27、請說明快速排序算法的原理 講義第4

28、章ppt第105頁 快速排序是對冒泡排序的一種改進(jìn)。它的基本思想是：通過一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按次方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。 28、請列舉計算機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的主要類型 講義第5章ppt第13頁 網(wǎng)狀拓?fù)? 星型拓?fù)? 樹狀拓?fù)? 環(huán)狀拓?fù)? 29、請對比操作系統(tǒng)與應(yīng)用軟件的異同 講義第6章ppt第3-4頁 按與硬件相關(guān)的密切程度, 通常將計算機(jī)的軟件分為系統(tǒng)軟件和應(yīng)用軟件。用戶直接使用的軟件通常為應(yīng)用軟件, 而應(yīng)用軟件通常是通過系

29、統(tǒng)軟件來指揮計算機(jī)的硬件完成其功能的。最重要的系統(tǒng)軟件是操作系統(tǒng)(Operation System,OS),它完成指揮計算機(jī)運(yùn)行的各個細(xì)節(jié), 亦即, 操作系統(tǒng)是計算機(jī)系統(tǒng)中用于指揮和管理其自身的軟件。 操作系統(tǒng)是一管理電腦硬件與軟件資源的程序，同時也是計算機(jī)系統(tǒng)的內(nèi)核與基石。操作系統(tǒng)是一個龐大的管理控制程序，大致包括5個方面的管理功能:進(jìn)程與處理機(jī)管理、作業(yè)管理、存儲管理、設(shè)備管理、文件管理。有效地組織和管理系統(tǒng)中的各種軟硬件資源，合理地組織計算機(jī)系統(tǒng)工作流程，控制程序的執(zhí)行，并向用戶提供一個良好的工作環(huán)境和友好的接口。 應(yīng)用軟件通常是由計算機(jī)專業(yè)人員為滿足人們完成特定任務(wù)的要求開發(fā)的,

30、這些軟件通常以特定的操作系統(tǒng)作為其運(yùn)行基礎(chǔ)（稱應(yīng)用平臺）。 30、請說明數(shù)據(jù)庫建模與實現(xiàn)過程 講義第6章ppt第29頁 在設(shè)計數(shù)據(jù)庫時，對現(xiàn)實世界進(jìn)行分析、抽象、并從中找出內(nèi)在了解，進(jìn)而確定數(shù)據(jù)庫的結(jié)構(gòu)，這一過程就稱為數(shù)據(jù)庫建模。它主要包括兩部分內(nèi)容：確定最基本的數(shù)據(jù)結(jié)構(gòu)；對約束建模。 1.需求分析階段：通過調(diào)查分析，確定用戶的功能需求和信息需求，綜合各個用戶的應(yīng)用需求，描述出數(shù)據(jù)流圖和數(shù)據(jù)字典。 　2.概念設(shè)計階段：對需求分析階段得到的結(jié)果經(jīng)行綜合、歸納與抽象，形成一個獨立于具體DBMS的概念模式，通常指得到一個E-R模型。 　3.邏輯設(shè)計階段：將概念模型按照一定的轉(zhuǎn)換規(guī)

31、則轉(zhuǎn)換為DBMS所支持的數(shù)據(jù)模式，并對其經(jīng)行優(yōu)化。首先將E-R圖轉(zhuǎn)換成具體的數(shù)據(jù)庫產(chǎn)品支持的數(shù)據(jù)模型，如關(guān)系模型，形成數(shù)據(jù)庫邏輯模式；然后根據(jù)用戶處理的要求、安全性的考慮，在基本表的基礎(chǔ)上再建立必要的視圖(View)，形成數(shù)據(jù)的外模式 　4.數(shù)據(jù)庫物理設(shè)計階段：為邏輯數(shù)據(jù)模型確定最適合于應(yīng)用環(huán)境的物理結(jié)構(gòu)，包括存儲結(jié)構(gòu)和存取方法。根據(jù)DBMS特點和處理的需要，進(jìn)行物理存儲安排，建立索引，形成數(shù)據(jù)庫內(nèi)模式 5、數(shù)據(jù)庫實施：利用DBMS提供的數(shù)據(jù)語言和平臺、根據(jù)邏輯設(shè)計和物理設(shè)計的結(jié)果建立數(shù)據(jù)庫，編制并調(diào)試程序運(yùn)行，組織數(shù)據(jù)的輸入，并試運(yùn)行。 6、運(yùn)行與維護(hù)：調(diào)試運(yùn)行后的數(shù)據(jù)庫應(yīng)用系統(tǒng)正式

32、運(yùn)行，并在運(yùn)行過程中，按照軟件工程的方法經(jīng)行不斷地測試、維護(hù)。 三、分析與設(shè)計題 1、利用卡諾圖方法化簡 講義第3章ppt第94頁 原式= 2、利用奎因-莫可拉斯基方法化簡 講義第3章ppt第99頁 3、已知整型數(shù)組NUM長度為N，設(shè)計算法求得其最大元和最小元。請說明算法的基本思想并繪制對應(yīng)的程序流程圖 講義第4章ppt第89頁 – 求n元中的最大元MAX(n)和最小元MIN(n) 4、已知整型數(shù)組

33、NUM={8,9,2,6,3,1,7,5}，設(shè)計算法將NUM按照從大到小的順序排列。請說明算法的基本思想并繪制對應(yīng)的程序流程圖 講義第4章ppt第90頁以后的許多算法 5、設(shè)計一個E-R圖，記錄球隊、隊員和球迷的信息。包括球隊的名稱、隊員、隊長、隊服顏色；隊員名字；球迷名字、喜歡的球隊、喜歡的隊員、最喜歡的顏色等。講義第6章ppt第30頁以后的許多算法 由"每個球隊有一個教練負(fù)責(zé)管理球隊，一個教練僅負(fù)責(zé)一個球隊。"知球隊與教練間為1∶1了解；球隊與隊員之間應(yīng)為1∶N了解；多個球隊使用多個訓(xùn)練場地，球隊與場地之間為M∶M了解；比賽是球隊、場地與裁判之間的了解，一個球隊會與同組的其他

34、多個隊之間比賽，有多個場地和裁決，一位裁判會對多場比賽判罰，一個場地會有多場比賽，涉及多個球隊和裁判，因此球隊、場地與裁判之間的比賽關(guān)系為M∶N∶P了解。 根據(jù)補(bǔ)充后的E-R圖，球隊與球員之間的1∶N了解應(yīng)通過將1端實體（球員）的主碼（球隊名稱）加入到N端實體（球員）對應(yīng)的關(guān)系中來表達(dá)。這類了解也可通過獨立的一個關(guān)系來表達(dá)，如球隊-球員（球隊名稱，隊員編號），這樣會對查詢增加多余的連接操作，因此一般不采用這種方法。 同樣，球隊與教練之間的1∶1了解也應(yīng)通過將一方的主碼增加到另一方實體對應(yīng)的關(guān)系中，來表達(dá)了解。 訓(xùn)練和比賽為多對多了解，只能獨立成一個關(guān)系模式，取該了解

35、相關(guān)連的各實體的碼及了解自有的屬性構(gòu)成。如比分和分組應(yīng)該是比賽的屬性，再加上球隊、裁判、場地的碼，即構(gòu)成"比賽記錄"的關(guān)系模式。同理，訓(xùn)練是球隊和場地的多對多了解，訓(xùn)練開始時間和結(jié)束時間為訓(xùn)練的屬性，加上球隊的碼和場地的碼，構(gòu)成"訓(xùn)練記錄"關(guān)系模式。 參考答案 【問題1】（圖中的M、N、P可表示為*，對了解名稱可不做要求，但不能出現(xiàn)重名。） 【問題2】 填空：（a）球隊名稱（b）教練編號（c）球隊名稱，場地名稱，開始時間，結(jié)束時間（d）甲隊，乙隊，比賽時間，場地名稱，比分，裁判，分組 主鍵：訓(xùn)練記錄（球隊，開始時間）或訓(xùn)練記錄（場地名稱，開始時間） 或 訓(xùn)練記錄（球隊，結(jié)束時間）或訓(xùn)練記錄（場地名稱，結(jié)束時間） 比賽記錄（場地名稱，比賽時間）或比賽記錄（裁判，比賽時間） 或 比賽記錄（甲隊，比賽時間）或比賽記錄（乙隊，比賽時間） 外鍵：訓(xùn)練記錄的外鍵：球隊名稱，場地名稱 比賽記錄的外鍵：甲隊，乙隊，場地名稱，裁判 【問題3】關(guān)系模式： 熱心球迷（球迷編號，姓名，住址，俱樂部） 支持球隊（球迷編號，球隊） 友情提示：部分文檔來自網(wǎng)絡(luò)整理，供您參考！文檔可復(fù)制、編制，期待您的好評與關(guān)注！ 14 / 14