考研復試歷年真題2005年復試題

1、2005 年復試試卷一、集合論與圖論1.簡答設 G 是一個具有 p 個頂點 q 條邊的無向圖。如果 G 的每個頂點的度都為 3 且 q=2p-3，那么對圖 G 回答下列各問題。求p和q 的值。畫出 G 的圖形。你應盡量畫出那些不同構(gòu)的圖。1)2)3)G 必定是偶圖嗎？為什么。4)G 必為圖嗎？為什么？5)G 必為平面圖嗎？為什么？6)G 必有生成樹嗎？為什么？7)G 必有割點嗎？為什么？2.簡答設 N=1,2,3,，R 為 N 上的二元關(guān)系，其定義如下：對任意的 m，nN，mRn 當且僅當m=n 或 n=m+1。1)R 具有以下哪些性質(zhì)？A. 自反的B. 反自反的C. 對稱的D.稱的E.傳遞的

2、求 R 的傳遞閉包 R+，它是你熟知的哪個關(guān)系？R+是否是等價關(guān)系？R+是否是偏序關(guān)系？R+是全序關(guān)系嗎？ R*為 R 的自反傳遞閉包。R*=R+嗎？2)3)4)3.簡答f : N N，其中 N 1, 2, 3,。F 中有多少函數(shù)能用程序計算它的函數(shù)值？說1)設明理由。一個有向圖含n 個頂點，任兩不同頂點間有且僅有一條有向邊。這樣的有向圖有多少個？2)假定各頂點為 1，2，n。二、計算機系統(tǒng)結(jié)構(gòu)1. 填空題1) 提高計算機系統(tǒng)并行性的主要技術(shù)途徑有、和資源共享。2)若浮點數(shù)尾數(shù)長度為 p 位，尾數(shù)的基值為rm ，則可表示的尾數(shù)的最大正數(shù)值為。若通道連接的外設臺數(shù)為 p ，外設i 的數(shù)據(jù)傳輸率為

3、 fi ，那么，字節(jié)多路通道的實際流量3) ，數(shù)組多路通道的實際流量 ，選擇通道的實際流量fbytefselect 。fblock器采用組相聯(lián)映像是指組間采用映像，組內(nèi)各塊之間是映像。4)Cache5)某單功能非線性流水線的預約表如下所示：段號k則這條單功能流水線的延遲表為，初始向量為。2.選擇題1)在不同系列的機器之間實現(xiàn)移植的途徑不包括（）。A.采用的高級語言B.采用的匯編語言C.模擬D.仿真2)RISC 執(zhí)行程序的速度比 CISC 要快的原因是（）。A.RISC 的指令系統(tǒng)的指令數(shù)較少B.RISC 中的指令執(zhí)行時需要的平均機器周期數(shù)較少C.程序在 RISC 上編譯生成的目標程序較短D.R

4、ISC 中包含了一些功能復雜的指令3)設置中斷字可以改變（）。A.多個中斷源的中斷請求優(yōu)先次序B.多個中斷服務程序開始執(zhí)行的次序C.多個中斷服務程序執(zhí)行完的次序D.CPU 對多個中斷請求響應的優(yōu)先次序4)與虛擬器的等效速度無關(guān)的是（）。A.主存的容量B.輔存的容量C.頁面替換算法D.訪存頁面地址流5)異步流水線的特征是（）。A.指令流水線各段的執(zhí)行時間不等123456781234B.指令流水線各段可以實現(xiàn)不同的C.指令流水線各段之間除有串行連接外，還有反饋回路D.指令流出流水線的次序與流入流水線的次序可以不同3.判斷題1)對計算機系統(tǒng)中經(jīng)常使用的基本功能單元宜于用來實現(xiàn)，這樣可以提高功能單元的

5、靈活性。（）2)帶標志符的數(shù)據(jù)表示簡化了指令系統(tǒng)，但是降低了指令的執(zhí)行速度。（）3)流水線細分的段數(shù)越多，實際吞吐率就越接近于最大吞吐率。（）4)當訪存發(fā)生實頁時，就需要進行頁面替換。（）5)通道程序由程序員編寫，并且由通道執(zhí)行。（）4.簡答題1)指令流水線對中斷的處理有哪兩種方法？各有何優(yōu)缺點？2)從設計的目的、實現(xiàn)的方式、速度的差異（第一級比第二級）、CPU 對第二級的方式、典型的塊（頁）大小、失效時 CPU 是否會切換等六個方面，簡述“Cache-主存”層次和“主存-輔存”層次的區(qū)別。三、數(shù)據(jù)庫系統(tǒng)1.填空題1)數(shù)據(jù)庫系統(tǒng)由數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、和計算機基本系統(tǒng)組成。 -連接操作是由關(guān)

6、系代數(shù)的操作和操作組合而成。2)SELECT 語句中，子句用于選擇滿足給定條件的；使用子句可3)按指定列的值分組，同時使用子句可提取滿足條件的組。當 FROM 子句中出現(xiàn)多個基本表時，系統(tǒng)將執(zhí)行這些表的操作。、和。4)數(shù)據(jù)庫系統(tǒng)在運行過程中可能發(fā)生的故障主要有：5)事務的性質(zhì)有、和。選擇題2.1)關(guān)系模型中，一個關(guān)鍵字可由（）組成。A.一個屬性B.一個或多個屬性C.多個屬性D.以上都不是2)關(guān)系數(shù)據(jù)庫規(guī)范化是為了解決關(guān)系數(shù)據(jù)庫中（）問題而引入的。A.數(shù)據(jù)不一致性B.檢索速度C.數(shù)據(jù)操作復雜性D.數(shù)據(jù)安全性3)數(shù)據(jù)庫中的機制是（）的主要方法。A.完整性控制B.安全性控制C.并發(fā)控制D.故障恢復控

7、制4)日志文件是用于（）。A.程序運行過程B.數(shù)據(jù)操作C.程序執(zhí)行結(jié)果D.對數(shù)據(jù)的所有更新操作5)數(shù)據(jù)庫主索引是一種（）的索引。A.對每一，都有一個索引項B.對索引字段上的每一個不同值有一個索引項C.對每一塊有一個索引項D.以上都不對6)如右圖所示 E-R 圖，“保存”是一個聯(lián)系，其指向“圖書”的基數(shù)為（）。A.0.1B.1.1C.0.mD.1.m7)對關(guān)系模式：學生（學號，課程號，課程名，成績），說法正確的是（）。A.不滿足第 2 范式B.滿足第 2 范式但不滿足第 3 范式C.滿足第 3 范式D.都不對8)SQL 語言中的視圖是一種（）。A.全局模式B.子模式C.內(nèi)模式D.物理模式E.其他四、編譯原理1.填空題1)對編譯程序而言，輸入數(shù)據(jù)是，輸出結(jié)果是。文法 G 產(chǎn)生的的全體是該文法描述的語言。自頂向下語法分析方遇到的主要問題有和。在 SLR(1)分析法的名字中，“S”的含義是。編譯程序進行數(shù)據(jù)流分析的目的是為了進行。簡答題2)3)4)5)2.標識符是指字母打頭的字母數(shù)字串，請給出：1)識別標識符的確定的有窮自；書架本資料由王道（）整理發(fā)布，任何組織和個人無權(quán)用于任何商業(yè)活動！2)用于描述標識符的正規(guī)文法；3)用于描述標識符的正則表達式。