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

《《計(jì)算機(jī)科學(xué)導(dǎo)論》課程復(fù)習(xí)大綱.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《《計(jì)算機(jī)科學(xué)導(dǎo)論》課程復(fù)習(xí)大綱.doc（12頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

一、名詞解釋 1、位置計(jì)數(shù)法：講義第2章ppt第5頁(yè) 一種表達(dá)數(shù)字的系統(tǒng)，數(shù)位按順序排列，每個(gè)數(shù)位有一個(gè)位值，數(shù)字的值是每個(gè)數(shù)位和位值的乘積之和 2、模擬數(shù)據(jù)：講義第2章ppt第15頁(yè) 是一種連續(xù)表示法，模擬它表示的真實(shí)信息 3、數(shù)字?jǐn)?shù)據(jù)：講義第2章ppt第15頁(yè) 是一種離散表示法，把信息分割成了獨(dú)立的元素 4、原碼： 課本P37，講義第2章ppt第28頁(yè) 將數(shù)的符號(hào)數(shù)碼化，即用一個(gè)二進(jìn)制位表示符號(hào)：對(duì)整數(shù)，該位取0，對(duì)負(fù)數(shù)，該位取1。而數(shù)值部分保持?jǐn)?shù)的原由形式（有時(shí)需要在高位部分添幾個(gè)0）。這樣所得結(jié)果為該數(shù)的原碼表示。 5、補(bǔ)碼：課本P37 ，講義第2章ppt第32頁(yè)， 一個(gè)負(fù)數(shù)加模的結(jié)果即是該數(shù)的補(bǔ)碼，它與該負(fù)數(shù)等價(jià)，或者說是一對(duì)一的，一個(gè)正數(shù)的補(bǔ)碼就是它本身 6、反碼：課本P37，講義第2章ppt第37頁(yè) 正數(shù)的反碼與其原碼、補(bǔ)碼相同；負(fù)數(shù)的反碼等于原碼除符號(hào)位外，按位求反；[X]補(bǔ)= [X]反+1 7、溢出：講義第2章ppt第38頁(yè) 當(dāng)運(yùn)算的結(jié)果超出某種數(shù)據(jù)類型所表示的數(shù)的范圍時(shí)，機(jī)器不能正確表示，這時(shí)要產(chǎn)生溢出；在溢出的情況下，機(jī)器將產(chǎn)生錯(cuò)誤的結(jié)果 8、字符集：講義第2章ppt第53頁(yè) 字符集：字符和表示它們的代碼的清單；常用字符集：ASCII、Unicode 9、RGB表示法：講義第2章ppt第85頁(yè) 在計(jì)算機(jī)中，顏色通常用RGB(red-green-blue)值表示，其中的三個(gè)數(shù)字說明了每種基色的份額 如果用0~255之間的數(shù)字表示一種元素的份額，0：該顏色沒有參與；255：該顏色完全參與其中 10、布爾代數(shù)：講義第3章ppt第22頁(yè) – 提供的是集合{0,1}上的運(yùn)算和規(guī)則 – 這個(gè)集合及布爾代數(shù)的規(guī)則被用來研究電子和光學(xué)開關(guān) 主要代數(shù)運(yùn)算：補(bǔ)、和、積 11、布爾函數(shù)：講義第3章ppt第29頁(yè) 設(shè)B={0,1}， 則Bn={(x1，x2，……，xn)|xi∈B，1≤i ≤n}是由0和1所能構(gòu)成的所有n元有序列的集合 從Bn到B的函數(shù)稱為n度布爾函數(shù) x稱為布爾變?cè)? 12、文字：講義第3章ppt第47頁(yè) – 布爾變?cè)蚱溲a(bǔ) 14、小項(xiàng)：講義第3章ppt第47頁(yè) – 布爾變?cè)獂1，x2，……，xn的小項(xiàng)是一個(gè)布爾積y1y2……yn，其中yi=xi，或 – 小項(xiàng)是n個(gè)文字的積，每個(gè)文字對(duì)應(yīng)于一個(gè)變?cè)? – 一個(gè)小項(xiàng)對(duì)一個(gè)且只對(duì)一個(gè)變?cè)档慕M合取值1 15、積之和展開式：講義第3章ppt第48頁(yè) – 給定一個(gè)布爾函數(shù)，可以構(gòu)造小項(xiàng)的布爾和使得：當(dāng)此布爾函數(shù)具有值1時(shí)它的值為1，當(dāng)此布爾函數(shù)具有值0時(shí)它的值為0 – 此布爾和中的小項(xiàng)與使得此函數(shù)值為1的值的組合對(duì)應(yīng) – 表示布爾函數(shù)的小項(xiàng)的和稱為此函數(shù)的積之和展開式或析取范式 16、門：講義第3章ppt第53頁(yè) – 對(duì)電信號(hào)執(zhí)行基礎(chǔ)運(yùn)算的設(shè)備，接受一個(gè)或者多個(gè)輸入信號(hào)，生成一個(gè)輸出信號(hào) – 門是構(gòu)成數(shù)字邏輯電路的基元，基本的門電路包括與、或、非、異或、與非、或非 17、電路：講義第3章ppt第53頁(yè) – 相互關(guān)聯(lián)的門的組合，用于實(shí)現(xiàn)特定的邏輯函數(shù) – 計(jì)算機(jī)的所有硬件都是使用不同的電路復(fù)合而成 – 電路主要分為組合電路和時(shí)序電路 邏輯框圖與真值表：講義第3章ppt第53頁(yè) – 邏輯框圖：電路的圖形化表示，不同類型的門有專用符號(hào) – 真值表：列出了所有可能的輸入值和相關(guān)輸出值的表，用于分析電路的輸入輸出規(guī)律 18、無(wú)需在意條件：講義第3章ppt第96頁(yè) – 在某些電路中，由于輸入值的一些組合從未出現(xiàn)過，所以對(duì)其輸出值可以任意選擇，函數(shù)對(duì)于這種組合的值稱為無(wú)需在意條件 – 在卡諾圖中，用d作其記號(hào) 19、指令：講義第3章ppt第131頁(yè) ? 將計(jì)算機(jī)看成是一臺(tái)信息處理機(jī) ? 處理只能一步一步地進(jìn)行，一次進(jìn)行一項(xiàng)基本操作 ? 指令：人給機(jī)器下達(dá)的完成一項(xiàng)基本操作的命令 ? 指令只能由1和0來編寫 20、程序：講義第3章ppt第132頁(yè) ? 完成一項(xiàng)任務(wù)需要將其分解成一系列能由指令實(shí)現(xiàn)的基本操作，即一系列指令 ? 程序：完成一項(xiàng)任務(wù)所需的并且按照一定順序排列起來的一系列指令 21、驅(qū)動(dòng)程序：講義第3章ppt第198頁(yè) ? 是一種可以使計(jì)算機(jī)和設(shè)備通信的特殊程序，可以說相當(dāng)于硬件的接口，操作系統(tǒng)只有通過這個(gè)接口，才能控制硬件設(shè)備的工作 ? 底層硬件是設(shè)備管理和操作的最終執(zhí)行者，驅(qū)動(dòng)程序則體現(xiàn)系統(tǒng)的設(shè)備控制能力，也是硬件設(shè)備存在的基本條件 ? 越高級(jí)的操作系統(tǒng)需要安裝的驅(qū)動(dòng)程序越少 22、算法：講義第4章ppt第8頁(yè) – 在有限的時(shí)間內(nèi)用有限的數(shù)據(jù)解決問題或子問題的明確指令集合 23、編譯器：講義第4章ppt第55頁(yè) 編譯器：把用高級(jí)語(yǔ)言編寫的程序翻譯成機(jī)器碼的程序 24、基本操作：講義第4章ppt第76頁(yè) 指算法運(yùn)行中起主要作用且花費(fèi)最多時(shí)間的操作 – 兩個(gè)實(shí)數(shù)矩陣的乘法問題中，矩陣的實(shí)數(shù)元素之間的數(shù)乘 – 對(duì)N個(gè)整數(shù)進(jìn)行排序的算法中，整數(shù)間的比較和交換 25、T(n)：講義第4章ppt第77頁(yè) – 算法的時(shí)間復(fù)雜度，用問題實(shí)例長(zhǎng)度的函數(shù)表示 – 也就是用該算法用于問題長(zhǎng)度為n的實(shí)例所需要的基本操作次數(shù)來刻畫 26、排序問題：講義第4章ppt第95頁(yè) – 是人們對(duì)數(shù)據(jù)集合最常用的基本操作之一 – 通訊錄或電話本中記錄一般按照人名的字典順序排列 – 打牌時(shí)按牌色和點(diǎn)數(shù)排列 – 體育比賽的獲獎(jiǎng)情況按實(shí)際成績(jī)排序 – 所有計(jì)算機(jī)工作中，排序占25%以上 27、穩(wěn)定排序算法：講義第4章ppt第96頁(yè) – 相同大小的元素不被交換的算法 28、原址排序算法：講義第4章ppt第96頁(yè) – 占用有限額外空間或者說額外空間與n無(wú)關(guān) 29、計(jì)算機(jī)網(wǎng)絡(luò)：講義第5章ppt第7頁(yè) 計(jì)算機(jī)網(wǎng)絡(luò)是為了通信和共享資源而以各種方式連在一起的一組計(jì)算設(shè)備。 30、數(shù)據(jù)庫(kù)：講義第6章ppt第27頁(yè) 按照數(shù)據(jù)結(jié)構(gòu)來組織、存儲(chǔ)和管理數(shù)據(jù)的倉(cāng)庫(kù)，綜合管理多個(gè)實(shí)體眾多記錄和字段，更加靈活實(shí)用 二、簡(jiǎn)答題 1、請(qǐng)敘述計(jì)算硬件的發(fā)展歷程 講義第1章ppt第17頁(yè) 1936年圖靈機(jī)是計(jì)算機(jī)的理論模型，計(jì)算機(jī)的發(fā)展到目前為止共經(jīng)歷了四個(gè)時(shí)代，從1946年到1959年這段時(shí)期我們稱之為“電子管計(jì)算機(jī)時(shí)代”。第一代計(jì)算機(jī)的內(nèi)部元件使用的是電子管。從1960年到1964年，由于在計(jì)算機(jī)中采用了比電子管更先進(jìn)的晶體管，所以我們將這段時(shí)期稱為“晶體管計(jì)算機(jī)時(shí)代”。晶體管比電子管小得多，不需要暖機(jī)時(shí)間，消耗能量較少，處理更迅速、更可靠。從1965年到1970年，集成電路被應(yīng)用到計(jì)算機(jī)中來，因此這段時(shí)期被稱為“中小規(guī)模集成電路計(jì)算機(jī)時(shí)代”。集成電路（Integrated Circuit，簡(jiǎn)稱r）是做在晶片上的一個(gè)完整的電子電路，這個(gè)晶片比手指甲還小，卻包含了幾千個(gè)晶體管元件。從1971年到現(xiàn)在，被稱之為“大規(guī)模集成電路計(jì)算機(jī)時(shí)代”。第四代計(jì)算機(jī)使用的元件依然是集成電路，不過，這種集成電路已經(jīng)大大改善，它包含著幾十萬(wàn)到上百萬(wàn)個(gè)晶體管，人們稱之為大規(guī)模集成電路（LargeScale lntegrated Circuit，簡(jiǎn)稱LSI）和超大規(guī)模集成電路（Very Large Scale lntegrated Circuit，簡(jiǎn)稱VLSI）。 2、請(qǐng)敘述計(jì)算軟件的發(fā)展歷程 講義第1章ppt第29頁(yè) 1946年第一臺(tái)電子計(jì)算機(jī)問世以來，計(jì)算機(jī)已被廣泛地應(yīng)用于生產(chǎn)、生活的各個(gè)領(lǐng)域，推動(dòng)著社會(huì)的進(jìn)步與發(fā)展。計(jì)算機(jī)科學(xué)的發(fā)展依賴于計(jì)算機(jī)硬件和軟件技術(shù)的發(fā)展，軟件是用計(jì)算機(jī)語(yǔ)言編寫的。計(jì)算機(jī)語(yǔ)言的發(fā)展經(jīng)歷了從機(jī)器語(yǔ)言、匯編語(yǔ)言到高級(jí)語(yǔ)言的歷程。 20世紀(jì)50年代初（1951-1959年），計(jì)算機(jī)發(fā)明之初，科學(xué)家只能用二進(jìn)制數(shù)編制的指令控制計(jì)算機(jī)運(yùn)行。機(jī)器語(yǔ)言是計(jì)算機(jī)唯一能識(shí)別并直接執(zhí)行的語(yǔ)言，每一條計(jì)算機(jī)指令均由一組“0”、“1”數(shù)字，按一定的規(guī)則排列組成，若要計(jì)算機(jī)執(zhí)行一項(xiàng)簡(jiǎn)單的任務(wù)，需要編寫大量的這種指令。這種有規(guī)則的二進(jìn)制數(shù)組成的指令集，就是機(jī)器語(yǔ)言（也稱為指令系統(tǒng)）。 20世紀(jì)50年代末（1959-1965年），出現(xiàn)了匯編語(yǔ)言。匯編語(yǔ)言用比較容易識(shí)別、記憶的助記符替代特定的二進(jìn)制串。匯編語(yǔ)言是符號(hào)化的機(jī)器語(yǔ)言，執(zhí)行效率仍接近于機(jī)器語(yǔ)言。 1970年，瑞士計(jì)算機(jī)科學(xué)家Niklaus.Wirth開發(fā)了第一個(gè)結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言—Pascal語(yǔ)言，標(biāo)志著結(jié)構(gòu)化程序設(shè)計(jì)時(shí)期的開始。Pascal語(yǔ)言的簡(jiǎn)潔明了以及豐富的數(shù)據(jù)結(jié)構(gòu)，為程序員提供了極大的方便性與靈活性，同時(shí)它特別適合微計(jì)算機(jī)系統(tǒng)。結(jié)構(gòu)化程序設(shè)計(jì)方法也在整個(gè)20世紀(jì)70年代的軟件開發(fā)中占絕對(duì)統(tǒng)治地位。除Pascal語(yǔ)言外，常見的結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言還有C、FORTRAN、True BASIC等。 1990年以來，面向?qū)ο蠓治觥y(cè)試、度量和管理等研究得到了長(zhǎng)足的發(fā)展，并在全世界掀起了一股面向?qū)ο鬅岢?，至今盛行不衰。面向?qū)ο蟪绦蛟O(shè)計(jì)在軟件開發(fā)領(lǐng)域掀起了巨大的變革，極大地提高了軟件開發(fā)效率。 3、簡(jiǎn)述計(jì)算機(jī)的四種類型及各自的特點(diǎn) 講義第1章ppt第80頁(yè) ? 個(gè)人計(jì)算機(jī) – 滿足個(gè)人應(yīng)用要求，體積小、價(jià)格便宜 – 臺(tái)式機(jī)（Desktop）、便攜式計(jì)算機(jī)（Laptop、Notebook） ? 小型計(jì)算機(jī) – 體積比個(gè)人計(jì)算機(jī)大一點(diǎn)，計(jì)算與存儲(chǔ)能力更強(qiáng) – 適用于中小型企業(yè)和科研機(jī)構(gòu)的計(jì)算處理要求 ? 大型計(jì)算機(jī) – 體積更大，需要專門的機(jī)房和維護(hù)環(huán)境 – 系統(tǒng)性能更高，數(shù)據(jù)存儲(chǔ)空間更大 – 一般用于大型企業(yè)和科研機(jī)構(gòu)的數(shù)據(jù)中心和計(jì)算服務(wù)平臺(tái) ? 超級(jí)計(jì)算機(jī) – 擁有遠(yuǎn)勝于其他計(jì)算機(jī)的計(jì)算能力和存儲(chǔ)能力 – 用于國(guó)家戰(zhàn)略服務(wù)和專項(xiàng)的超級(jí)數(shù)據(jù)計(jì)算 4、請(qǐng)解釋等值原理并說明其應(yīng)用領(lǐng)域 講義第2章ppt第6頁(yè) 是一種將字符串轉(zhuǎn)換為更短長(zhǎng)度數(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)制后各是多少 講義第2章ppt第8頁(yè) 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頁(yè) 43(10)=101011(2) 43(10)=53(8) 43(10)=2B(16) 7、說明字符表示的基本思想并列舉兩種常用的字符集 講義第2章ppt第52頁(yè) ? 基本思想： 列出所有字符，賦予每個(gè)字符一個(gè)二進(jìn)制字符串 要存儲(chǔ)一個(gè)特定的字母，保存它對(duì)應(yīng)的串即可 ? 需要表示和保存的字符 英語(yǔ)字母，阿拉伯?dāng)?shù)字，標(biāo)點(diǎn)符號(hào)，空格 8、比較關(guān)鍵字編碼和行程長(zhǎng)度編碼的基本思想及特點(diǎn) 講義第2章ppt第58頁(yè) 關(guān)鍵字編碼（特點(diǎn)：用單個(gè)字符代替常用的單詞） 在文本中有一些常見詞匯 the，and，which，that，what 如果這些單詞占用更少的空間，文檔就會(huì)減小 即使每個(gè)單詞節(jié)省的空間有限，但是整個(gè)文檔節(jié)省的總空間仍可能非?？捎^ 行程長(zhǎng)度編碼（重復(fù)字符的序列用標(biāo)志字符，后面加重復(fù)字符和說明字符重復(fù)次數(shù)的數(shù)字替換） 迭代編碼 把一系列重復(fù)字符替換為它們重復(fù)出現(xiàn)的次數(shù) 常用于一些大規(guī)模數(shù)據(jù)流中 9、說明赫夫曼編碼的基本思想和編碼規(guī)則 講義第2章ppt第67頁(yè) 基本思想 在常規(guī)字符集中，每個(gè)字符都由定長(zhǎng)的位串表示 文本中很少使用字母“X”，為什么要讓它占用的位數(shù)與其他常用字符一樣呢？ 為了解決這一問題，應(yīng)該用不同長(zhǎng)度的位串表示每個(gè)字符 令較少的位表示經(jīng)常出現(xiàn)的字符，而將較長(zhǎng)的位串留給不經(jīng)常出現(xiàn)的字符，這樣文檔的整體大小將比較小 編碼規(guī)則 列出要編碼的字符出現(xiàn)的頻率 編碼令出現(xiàn)頻率最高的字符擁有最短位串 同時(shí)保證表示一個(gè)字符的位串不會(huì)是表示另一個(gè)字符的位串的前綴 10、列舉幾種常見的音頻格式 講義第2章ppt第77頁(yè) .wav （Microsoft公司用于Windows平臺(tái)的音頻文件格式） .cda（音質(zhì)最好的音頻格式） .mp3（目前處于統(tǒng)治地位的音頻數(shù)據(jù)格式，動(dòng)態(tài)影像專家壓縮標(biāo)準(zhǔn)音頻層面3） .mid（可供數(shù)字合成器和其他設(shè)備交換信息） .wma（既有較好的音質(zhì)，又適合于在網(wǎng)絡(luò)傳播） .ra，.rm，.rmx（主要用于在低速?gòu)V域網(wǎng)上實(shí)時(shí)傳輸音頻信息、質(zhì)量較差） 11、列舉幾種常見的圖像格式 講義第2章ppt第95頁(yè)以后 .jpg（對(duì)色彩的信息保留較好） .bmp（不采用任何壓縮，文件較大） .gif（一個(gè)gif文件中可以存多幅彩色圖像，從而形成動(dòng)畫） .tif（占用空間大，較完整的保留原有信息） .png（經(jīng)常用于Java程序，特別是Java手機(jī)程序中） 12、列舉幾種常見的視頻格式 講義第2章ppt第95頁(yè) .avi（兼容好，調(diào)用方便，圖像質(zhì)量好、文件較大） ASF、MPEG、DIVX、MOV、RMVB 13、列舉色彩三要素及其含義 講義第2章ppt第103頁(yè) ? 亮度 描述光作用于人眼時(shí)引起的明暗程度感覺 彩色光輻射的功率越大，亮度越高 彩色光輻射的功率越小，亮度越低 ? 色調(diào) 描述人眼看到光時(shí)產(chǎn)生的彩色感覺 顏色的類別 不同波長(zhǎng)的光呈現(xiàn)不同的顏色 ? 色飽和度 某一顏色的深淺程度（濃度） 高飽和度的深色光可摻入白色光被沖淡 14、說明顯示分辨率和圖像分辨率的異同 講義第2章ppt第91-92頁(yè) 顯示分辨率 顯示屏上能夠顯示出的像素?cái)?shù)目 如果顯示分辨率為1024*768 ? 顯示屏分成768行 ? 每行顯示1024個(gè)像素 ? 整個(gè)顯示屏含有796432個(gè)像素點(diǎn) 顯示分辨率越高，顯示的圖像質(zhì)量越高 圖像分辨率 組成一幅圖像的像素密度，表示為每英寸多少點(diǎn) 如果用200dpi掃描一幅2*2.5英寸的彩色照片，則得到一幅400*500個(gè)像素點(diǎn)的圖像 對(duì)于同樣大小的一幅圖像 ? 組成的像素?cái)?shù)目越多，則分辨率越高，圖像越逼真 ? 組成的像素?cái)?shù)目越少，則分辨率越低，圖像越粗糙 15、說明視頻壓縮的常用方法及適用范圍 講義第2章ppt第102頁(yè) ? 時(shí)間壓縮—根據(jù)連續(xù)幀之間的差別壓縮電影的技術(shù) ? 空間壓縮—基于靜態(tài)圖像的壓縮方法的電影壓縮技術(shù) 16、設(shè)計(jì)并繪制三人多數(shù)表決器電路 講義第3章ppt第62頁(yè) 某個(gè)組織的一切事務(wù)都由一個(gè)三人委員會(huì)決定，每個(gè)委員對(duì)提出的建議可以投贊成票或反對(duì)票。一個(gè)建議如果得到了至少兩張贊成票就獲通過。設(shè)計(jì)一個(gè)電路，來判斷建議是否獲得通過 ? 分析 – 如果第一個(gè)委員投贊成票，則令x=1，否則為0 – 如果第二個(gè)委員投贊成票，則令y=1，否則為0 – 如果第三個(gè)委員投贊成票，則令z=1，否則為0 – 必須設(shè)計(jì)一個(gè)電路使得對(duì)于輸入x、y、z，如果其中至少有兩個(gè)為1，則此電路產(chǎn)生輸出1 17、設(shè)計(jì)并繪制兩路開關(guān)電路 講義第3章ppt第64頁(yè) – 某盞燈需要由兩個(gè)開關(guān)控制，當(dāng)燈是關(guān)閉時(shí)，按下任何一個(gè)開關(guān)都可以打開此燈；當(dāng)燈是打開時(shí)，按下任何一個(gè)開關(guān)都可以關(guān)閉此燈。 ? 分析 – 當(dāng)?shù)谝粋€(gè)開關(guān)關(guān)閉時(shí)，令x=1，否則為0 – 當(dāng)?shù)诙€(gè)開關(guān)關(guān)閉時(shí)，令y=1，否則為0 – 當(dāng)燈是打開時(shí)，令F(x,y)=1，否則為0 – 假設(shè)當(dāng)兩個(gè)開關(guān)都是關(guān)閉時(shí)，燈是打開的 18、設(shè)計(jì)并繪制三路開關(guān)電路 講義第3章ppt第66頁(yè) – 某盞燈需要由三個(gè)開關(guān)控制，當(dāng)燈是關(guān)閉時(shí)，按下任何一個(gè)開關(guān)都可以打開此燈；當(dāng)燈是打開時(shí)，按下任何一個(gè)開關(guān)都可以關(guān)閉此燈。 ? 分析 – 當(dāng)?shù)谝粋€(gè)開關(guān)關(guān)閉時(shí)，令x=1，否則為0 – 當(dāng)?shù)诙€(gè)開關(guān)關(guān)閉時(shí)，令y=1，否則為0 – 當(dāng)?shù)谌齻€(gè)開關(guān)關(guān)閉時(shí)，令z=1，否則為0 – 當(dāng)燈是打開時(shí)，令F(x,y,z)=1，否則為0 – 假設(shè)當(dāng)三個(gè)開關(guān)都是關(guān)閉時(shí)，燈是打開的 19、設(shè)計(jì)并繪制半加法器電路 講義第3章ppt第68頁(yè) 20、簡(jiǎn)述布爾函數(shù)最小化的作用 講義第3章ppt第79頁(yè) – 產(chǎn)生布爾積的布爾和，使其包含的文字之積的個(gè)數(shù)最少，這個(gè)過程稱作布爾函數(shù)的最小化。 – 相應(yīng)的電路含有最少的門和最少的輸入。 ? 作用 – 降低成本 – 提高電路可靠性 – 在一塊芯片上設(shè)計(jì)更合適的電路 – 減少電路計(jì)算時(shí)間 21、繪制馮諾依曼體系結(jié)構(gòu)并說明其核心部件的功能 講義第3章ppt第128頁(yè) 22、請(qǐng)說明鼠標(biāo)的基本構(gòu)件 講義第3章ppt第173頁(yè) 23、請(qǐng)說明驅(qū)動(dòng)程序和應(yīng)用程序的異同 講義第3章ppt第198-201頁(yè) ? 每個(gè)位于總線上的設(shè)備必須包含系統(tǒng)設(shè)備管理器下的驅(qū)動(dòng)程序，但不一定都包含應(yīng)用程序 ? 驅(qū)動(dòng)程序位于操作系統(tǒng)下層，提供設(shè)備的存取操作 ? 應(yīng)用程序位于操作系統(tǒng)上層，不需要直到設(shè)備所用地址、信號(hào)種類或者通信協(xié)議 ? Windows\system下存放著一些驅(qū)動(dòng)程序 24、你是如何理解自頂向下和面向?qū)ο髢煞N設(shè)計(jì)方法的？它們有何異同？講義第4章ppt第28-40頁(yè) 自頂向下設(shè)計(jì) 一種程序開發(fā)技術(shù)，其中問題被分解為更容易處理的子問題，這些子問題的解決方案組合起來構(gòu)成整體問題的解決方案，面向過程設(shè)計(jì)是一種自頂向下逐步求精的設(shè)計(jì)方法,是單入口單出口的程序結(jié)構(gòu).設(shè)計(jì)者用一個(gè)main函數(shù)概括出整個(gè)應(yīng)用程序需要做的事,而main函數(shù)由對(duì)一系列子函數(shù)的調(diào)用組成.其特征是以函數(shù)為中心,用函數(shù)來作為劃分程序的基本單位,數(shù)據(jù)在過程式設(shè)計(jì)中往往處于從屬的位置. ? 模塊—一個(gè)用于解決問題或子問題的封閉步驟集合 ? 抽象步驟—細(xì)節(jié)仍未明確的算法步驟 ? 具體步驟—細(xì)節(jié)完全明確的算法步驟 面向?qū)ο? 面向?qū)ο蟮某绦蛟O(shè)計(jì)的基本思想是使用對(duì)象、類、繼承、封裝、消息等基本概念來進(jìn)行程序設(shè)計(jì),允許開發(fā)者從問題的局部開始,一點(diǎn)一點(diǎn)地構(gòu)建出整個(gè)程序,在開發(fā)過程中逐步加深對(duì)系統(tǒng)的理解.面向?qū)ο笤O(shè)計(jì)以數(shù)據(jù)為中心,類作為表現(xiàn)數(shù)據(jù)的工具,是劃分程序的基本單位. ? 對(duì)象—在問題背景中具有意義的事物或?qū)嶓w ? 類—描述了一組類似的對(duì)象，它們有一些共同的屬性和行為 ? 方法—處理對(duì)象中數(shù)據(jù)的指定算法，定義了類的某種行為 25、請(qǐng)繪圖說明算法復(fù)雜度的漸進(jìn)性質(zhì) 講義第4章ppt第78頁(yè) 如果解決問題P的算法A和算法B，其時(shí)間復(fù)雜度分別是TA(n)和TB(n)，則判斷A、B性能優(yōu)劣的標(biāo)準(zhǔn)是查看在n足夠大時(shí)TA(n)和TB(n)的大小關(guān)系 26、請(qǐng)說明冒泡排序算法的原理 講義第4章ppt第100頁(yè) 對(duì)尚未排序的各元素從頭到尾依次比較相鄰的兩個(gè)元素是否逆序（與欲排順序相反），若逆序就交換這兩元素，經(jīng)過第一輪比較排序后便可把最大（或最?。┑脑嘏藕?，然后再用同樣的方法把剩下的元素逐個(gè)進(jìn)行比較，就得到了你所要的順序?？梢钥闯鋈绻?n 個(gè)元素，那么一共要進(jìn)行 n-1 輪比較，第 i 輪要進(jìn)行 j=n-i 次比較。（如：有5個(gè)元素，則要進(jìn)行5-1輪比較。第3輪則要進(jìn)行5-3次比較）經(jīng)過優(yōu)化后的算法根據(jù)不同的情況有可能減小排序的次數(shù) 27、請(qǐng)說明快速排序算法的原理 講義第4章ppt第105頁(yè) 快速排序是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是：通過一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按次方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。 28、請(qǐng)列舉計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的主要類型 講義第5章ppt第13頁(yè) 網(wǎng)狀拓?fù)? 星型拓?fù)? 樹狀拓?fù)? 環(huán)狀拓?fù)? 29、請(qǐng)對(duì)比操作系統(tǒng)與應(yīng)用軟件的異同 講義第6章ppt第3-4頁(yè) 按與硬件相關(guān)的密切程度, 通常將計(jì)算機(jī)的軟件分為系統(tǒng)軟件和應(yīng)用軟件。用戶直接使用的軟件通常為應(yīng)用軟件, 而應(yīng)用軟件通常是通過系統(tǒng)軟件來指揮計(jì)算機(jī)的硬件完成其功能的。最重要的系統(tǒng)軟件是操作系統(tǒng)(Operation System,OS),它完成指揮計(jì)算機(jī)運(yùn)行的各個(gè)細(xì)節(jié), 亦即, 操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)中用于指揮和管理其自身的軟件。 操作系統(tǒng)是一管理電腦硬件與軟件資源的程序，同時(shí)也是計(jì)算機(jī)系統(tǒng)的內(nèi)核與基石。操作系統(tǒng)是一個(gè)龐大的管理控制程序，大致包括5個(gè)方面的管理功能:進(jìn)程與處理機(jī)管理、作業(yè)管理、存儲(chǔ)管理、設(shè)備管理、文件管理。有效地組織和管理系統(tǒng)中的各種軟硬件資源，合理地組織計(jì)算機(jī)系統(tǒng)工作流程，控制程序的執(zhí)行，并向用戶提供一個(gè)良好的工作環(huán)境和友好的接口。 應(yīng)用軟件通常是由計(jì)算機(jī)專業(yè)人員為滿足人們完成特定任務(wù)的要求開發(fā)的, 這些軟件通常以特定的操作系統(tǒng)作為其運(yùn)行基礎(chǔ)（稱應(yīng)用平臺(tái)）。 30、請(qǐng)說明數(shù)據(jù)庫(kù)建模與實(shí)現(xiàn)過程 講義第6章ppt第29頁(yè) 在設(shè)計(jì)數(shù)據(jù)庫(kù)時(shí)，對(duì)現(xiàn)實(shí)世界進(jìn)行分析、抽象、并從中找出內(nèi)在聯(lián)系，進(jìn)而確定數(shù)據(jù)庫(kù)的結(jié)構(gòu)，這一過程就稱為數(shù)據(jù)庫(kù)建模。它主要包括兩部分內(nèi)容：確定最基本的數(shù)據(jù)結(jié)構(gòu)；對(duì)約束建模。 1.需求分析階段：通過調(diào)查分析，確定用戶的功能需求和信息需求，綜合各個(gè)用戶的應(yīng)用需求，描述出數(shù)據(jù)流圖和數(shù)據(jù)字典。 　2.概念設(shè)計(jì)階段：對(duì)需求分析階段得到的結(jié)果經(jīng)行綜合、歸納與抽象，形成一個(gè)獨(dú)立于具體DBMS的概念模式，通常指得到一個(gè)E-R模型。 　3.邏輯設(shè)計(jì)階段：將概念模型按照一定的轉(zhuǎn)換規(guī)則轉(zhuǎn)換為DBMS所支持的數(shù)據(jù)模式，并對(duì)其經(jīng)行優(yōu)化。首先將E-R圖轉(zhuǎn)換成具體的數(shù)據(jù)庫(kù)產(chǎn)品支持的數(shù)據(jù)模型，如關(guān)系模型，形成數(shù)據(jù)庫(kù)邏輯模式；然后根據(jù)用戶處理的要求、安全性的考慮，在基本表的基礎(chǔ)上再建立必要的視圖(View)，形成數(shù)據(jù)的外模式 　4.數(shù)據(jù)庫(kù)物理設(shè)計(jì)階段：為邏輯數(shù)據(jù)模型確定最適合于應(yīng)用環(huán)境的物理結(jié)構(gòu)，包括存儲(chǔ)結(jié)構(gòu)和存取方法。根據(jù)DBMS特點(diǎn)和處理的需要，進(jìn)行物理存儲(chǔ)安排，建立索引，形成數(shù)據(jù)庫(kù)內(nèi)模式 5、數(shù)據(jù)庫(kù)實(shí)施：利用DBMS提供的數(shù)據(jù)語(yǔ)言和平臺(tái)、根據(jù)邏輯設(shè)計(jì)和物理設(shè)計(jì)的結(jié)果建立數(shù)據(jù)庫(kù)，編制并調(diào)試程序運(yùn)行，組織數(shù)據(jù)的輸入，并試運(yùn)行。 6、運(yùn)行與維護(hù)：調(diào)試運(yùn)行后的數(shù)據(jù)庫(kù)應(yīng)用系統(tǒng)正式運(yùn)行，并在運(yùn)行過程中，按照軟件工程的方法經(jīng)行不斷地測(cè)試、維護(hù)。 三、分析與設(shè)計(jì)題 1、利用卡諾圖方法化簡(jiǎn) 講義第3章ppt第94頁(yè) 原式= 2、利用奎因-莫可拉斯基方法化簡(jiǎn) 講義第3章ppt第99頁(yè) 3、已知整型數(shù)組NUM長(zhǎng)度為N，設(shè)計(jì)算法求得其最大元和最小元。請(qǐng)說明算法的基本思想并繪制對(duì)應(yīng)的程序流程圖 講義第4章ppt第89頁(yè) – 求n元中的最大元MAX(n)和最小元MIN(n) 4、已知整型數(shù)組NUM={8,9,2,6,3,1,7,5}，設(shè)計(jì)算法將NUM按照從大到小的順序排列。請(qǐng)說明算法的基本思想并繪制對(duì)應(yīng)的程序流程圖 講義第4章ppt第90頁(yè)以后的許多算法 5、設(shè)計(jì)一個(gè)E-R圖，記錄球隊(duì)、隊(duì)員和球迷的信息。包括球隊(duì)的名稱、隊(duì)員、隊(duì)長(zhǎng)、隊(duì)服顏色；隊(duì)員名字；球迷名字、喜歡的球隊(duì)、喜歡的隊(duì)員、最喜歡的顏色等。講義第6章ppt第30頁(yè)以后的許多算法 由"每個(gè)球隊(duì)有一個(gè)教練負(fù)責(zé)管理球隊(duì)，一個(gè)教練僅負(fù)責(zé)一個(gè)球隊(duì)。"知球隊(duì)與教練間為1∶1聯(lián)系；球隊(duì)與隊(duì)員之間應(yīng)為1∶N聯(lián)系；多個(gè)球隊(duì)使用多個(gè)訓(xùn)練場(chǎng)地，球隊(duì)與場(chǎng)地之間為M∶M聯(lián)系；比賽是球隊(duì)、場(chǎng)地與裁判之間的聯(lián)系，一個(gè)球隊(duì)會(huì)與同組的其他多個(gè)隊(duì)之間比賽，有多個(gè)場(chǎng)地和裁決，一位裁判會(huì)對(duì)多場(chǎng)比賽判罰，一個(gè)場(chǎng)地會(huì)有多場(chǎng)比賽，涉及多個(gè)球隊(duì)和裁判，因此球隊(duì)、場(chǎng)地與裁判之間的比賽關(guān)系為M∶N∶P聯(lián)系。 根據(jù)補(bǔ)充后的E-R圖，球隊(duì)與球員之間的1∶N聯(lián)系應(yīng)通過將1端實(shí)體（球員）的主碼（球隊(duì)名稱）加入到N端實(shí)體（球員）對(duì)應(yīng)的關(guān)系中來表達(dá)。這類聯(lián)系也可通過獨(dú)立的一個(gè)關(guān)系來表達(dá)，如球隊(duì)-球員（球隊(duì)名稱，隊(duì)員編號(hào)），這樣會(huì)對(duì)查詢?cè)黾佣嘤嗟倪B接操作，因此一般不采用這種方法。 同樣，球隊(duì)與教練之間的1∶1聯(lián)系也應(yīng)通過將一方的主碼增加到另一方實(shí)體對(duì)應(yīng)的關(guān)系中，來表達(dá)聯(lián)系。 訓(xùn)練和比賽為多對(duì)多聯(lián)系，只能獨(dú)立成一個(gè)關(guān)系模式，取該聯(lián)系相關(guān)連的各實(shí)體的碼及聯(lián)系自有的屬性構(gòu)成。如比分和分組應(yīng)該是比賽的屬性，再加上球隊(duì)、裁判、場(chǎng)地的碼，即構(gòu)成"比賽記錄"的關(guān)系模式。同理，訓(xùn)練是球隊(duì)和場(chǎng)地的多對(duì)多聯(lián)系，訓(xùn)練開始時(shí)間和結(jié)束時(shí)間為訓(xùn)練的屬性，加上球隊(duì)的碼和場(chǎng)地的碼，構(gòu)成"訓(xùn)練記錄"關(guān)系模式。 參考答案 【問題1】（圖中的M、N、P可表示為*，對(duì)聯(lián)系名稱可不做要求，但不能出現(xiàn)重名。） 【問題2】 填空：（a）球隊(duì)名稱（b）教練編號(hào)（c）球隊(duì)名稱，場(chǎng)地名稱，開始時(shí)間，結(jié)束時(shí)間（d）甲隊(duì)，乙隊(duì)，比賽時(shí)間，場(chǎng)地名稱，比分，裁判，分組 主鍵：訓(xùn)練記錄（球隊(duì)，開始時(shí)間）或訓(xùn)練記錄（場(chǎng)地名稱，開始時(shí)間） 或 訓(xùn)練記錄（球隊(duì)，結(jié)束時(shí)間）或訓(xùn)練記錄（場(chǎng)地名稱，結(jié)束時(shí)間） 比賽記錄（場(chǎng)地名稱，比賽時(shí)間）或比賽記錄（裁判，比賽時(shí)間） 或 比賽記錄（甲隊(duì)，比賽時(shí)間）或比賽記錄（乙隊(duì)，比賽時(shí)間） 外鍵：訓(xùn)練記錄的外鍵：球隊(duì)名稱，場(chǎng)地名稱 比賽記錄的外鍵：甲隊(duì)，乙隊(duì)，場(chǎng)地名稱，裁判 【問題3】關(guān)系模式： 熱心球迷（球迷編號(hào)，姓名，住址，俱樂部） 支持球隊(duì)（球迷編號(hào)，球隊(duì)）