考研計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合-24

1、考研計(jì)算機(jī)學(xué)科專(zhuān)業(yè)基礎(chǔ)綜合 -24( 總分： 104.98 ，做題時(shí)間： 90 分鐘 )一、 單項(xiàng)選擇題 ( 總題數(shù)： 40，分?jǐn)?shù)： 80.00)1. 對(duì)于一個(gè)文件的訪問(wèn)，常由 ( ) 共同限制。 A用戶訪問(wèn)權(quán)限和文件屬性 B 用戶訪問(wèn)權(quán)限和用戶優(yōu)先級(jí) C優(yōu)先級(jí)和文件屬性 D 文件屬性和口令A(yù). B.C.D.本題考查文件保護(hù)的概念。2. 下面包含在 TcP頭中而不包含在 UDP頭中的信息是 ( ) 。A目標(biāo)端口號(hào) B序號(hào) C 源端口號(hào) D 校驗(yàn)號(hào)A.B. C.D.本題主要考查 TCP報(bào)文段和 UDP報(bào)文段結(jié)構(gòu)， TCP數(shù)據(jù)報(bào)和 UDP數(shù)據(jù)報(bào)都包含目標(biāo)端口、 源端口、校驗(yàn)號(hào)。 但是由于 UDP是

2、不可靠的傳輸，故數(shù)據(jù)報(bào)不需要編號(hào)，所以不會(huì)有序號(hào)這一字段，而TCP是可靠的傳輸，故需要設(shè)置序號(hào)這一字段，答案是 B。 歸納總結(jié) 注意 UDP數(shù)據(jù)報(bào)有兩個(gè)字段：數(shù)據(jù)字段和首部字段。首部字段有8 個(gè)字節(jié)，由 4 個(gè)字段組成，每個(gè)字段都是兩個(gè)字節(jié) (牢記 )：(1) 源端口，即源端口號(hào) (端口號(hào)用 16bit 來(lái)表示，故需要 2字節(jié)長(zhǎng)度 )。(2) 目的端口，即目的端口號(hào)。(3) 長(zhǎng)度，即 UDP用戶數(shù)據(jù)報(bào)的長(zhǎng)度 (盡管有 2 字節(jié)來(lái)描述 UDP數(shù)據(jù)報(bào)的長(zhǎng)度，但是一般來(lái)說(shuō) UDP協(xié)議限制 其應(yīng)用程序數(shù)據(jù)為 512 字節(jié)或更小 ) 。(4) 檢驗(yàn)和，即檢測(cè) UDP用戶數(shù)據(jù)報(bào)在傳輸中是否有錯(cuò) ( 既檢驗(yàn)

3、首部又檢驗(yàn)數(shù)據(jù)部分 )。而 TCP 報(bào)文段也分為首部和數(shù)據(jù)兩部分， TCP的全部功能也都體現(xiàn)在首部的各個(gè)字段中，其中源端口和目 的端口的意義和 UDP是一致的。3. 一個(gè)完整的計(jì)算機(jī)系統(tǒng)包括 。A主機(jī)、鍵盤(pán)、顯示器 B 主機(jī)及其外部設(shè)備 C主機(jī)與實(shí)用程序 D 硬件系統(tǒng)與軟件系統(tǒng)A.B.C.D. 計(jì)算機(jī)硬件是由主機(jī)和外圍設(shè)備組成，主機(jī)是指CPU和內(nèi)存儲(chǔ)器。通常，把不裝備任何軟件的計(jì)算機(jī)稱為硬件計(jì)算機(jī)或裸機(jī)，裸機(jī)是不能使用的，必須配備一定的軟件，構(gòu)成計(jì)算機(jī)系統(tǒng)才能使用。4. 已知循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組 A0 ， n-1 中，且隊(duì)列非空時(shí) front 和 rear 分別指向?qū)︻^和隊(duì)尾。若 初始時(shí)隊(duì)列

4、為空，且要求第一個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在 A0 處，則初始時(shí) front 和 rear 的值分別為 ( ) A0，0 B0，n-1 C n-1，0 Dn-1，n-1A.B. C.D.在隊(duì)列中插入元素時(shí)，只能在隊(duì)尾進(jìn)行操作。 rear 指針指向隊(duì)尾元素，因此插入時(shí)，要先將 rear 指針向 后移動(dòng)一個(gè)， 然后再將元素插入數(shù)組中。 如果要使得第一個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A0 處，rear 指針初始值應(yīng)該為 n-1 。而插入第一個(gè)元素之后， front 指針不變，隊(duì)尾指針要指向隊(duì)尾元素。因此， rear 指針初 始值應(yīng)該為 n-1 ， front 指針為 0。5. 下列交換方式中， ( ) 一次連接沿著

5、一條路由路徑發(fā)送所有的數(shù)據(jù)。A分組交換 B 報(bào)文交換 C 電路交換 D 以上都不是A.B.C. D. 電路交換在數(shù)據(jù)傳送之前需要建立一條物理通路，然后所有數(shù)據(jù)都沿著這條建立的通路發(fā)送。6. 一個(gè)具有 1025 個(gè)結(jié)點(diǎn)的二叉樹(shù)的高度為 ( ) 。A11 B10C11至1025之間 D10至1024之間A.B.C. D.一棵二叉樹(shù)每層只有 1 個(gè)結(jié)點(diǎn)，則具有 1025 個(gè)結(jié)點(diǎn)的二叉樹(shù)的最大高度為 1025。一個(gè)具有 1025 個(gè)結(jié)點(diǎn) 的完全二叉樹(shù)的高度為 11。這一個(gè)具有 1025 個(gè)結(jié)點(diǎn)的二叉樹(shù)的高 h 為 11 至 1025 之間。7. CPU輸出數(shù)據(jù)的速度遠(yuǎn)遠(yuǎn)高于打印機(jī)的打印速度，為解決這一

6、矛盾，可采用的技術(shù)是( ) 。A并行技術(shù) B 通道技術(shù) C 緩沖技術(shù) D 虛存技術(shù)A.B.C. D.緩沖技術(shù)的引入主要解決 CPU速度和外設(shè)速度不匹配的問(wèn)題，它同時(shí)減少了通道數(shù)量上的占用，提高了CPU、IO 和通道的并發(fā)性， 減少了中斷的次數(shù)，放寬了 CPU對(duì)中斷響應(yīng)的時(shí)間要求， 例如打印、 文件訪問(wèn)， 網(wǎng)絡(luò)收發(fā)等場(chǎng)合，均要用到緩沖技術(shù)。8. 為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問(wèn)題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依 次寫(xiě)入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是 ( ) 。 A棧 B 隊(duì)列 C樹(shù) D圖A.B. C.D.9. 若一棵二叉樹(shù)具有 10

7、個(gè)度為 2的結(jié)點(diǎn)， 5個(gè)度為 1的結(jié)點(diǎn)，則度為 0的結(jié)點(diǎn)個(gè)數(shù)是 。A9 B11 C15 D不確定A.B. C.D.對(duì)任何一棵二叉樹(shù)，如果終端結(jié)點(diǎn)數(shù)為n0，度為 2 的結(jié)點(diǎn)數(shù)為 n2，則一定有 n0 =n2+1。所以 n0 =10+1=11，而與 n1 無(wú)關(guān)。10. 數(shù)據(jù)鏈路層采用了后退 N幀(GBN)協(xié)議，發(fā)送方已經(jīng)發(fā)送了編號(hào)為 07的幀。當(dāng)計(jì)時(shí)器超時(shí)時(shí)， 若發(fā)送 方只收到 0、2、3 號(hào)幀的確認(rèn)，則發(fā)送方需要重發(fā)的幀數(shù)是 ( )A2 B3 C4 D5A.B.C. D.考查后退 N 幀協(xié)議的工作原理。在后退 N 幀協(xié)議中，發(fā)送方可以連續(xù)發(fā)送若干個(gè)數(shù)據(jù)幀，如果收到接收方的確認(rèn)幀，則可以繼續(xù)發(fā)送。

8、若 某個(gè)幀出錯(cuò)，接收方只是簡(jiǎn)單地丟棄該幀及其后所有的后續(xù)幀，發(fā)送方超時(shí)后需重傳該數(shù)據(jù)幀及其后續(xù)的 所有數(shù)據(jù)幀。這里要注意，連續(xù) ARQ協(xié)議中，接收方一般采用累積確認(rèn)的方式，即接收方對(duì)按序到達(dá)的最后一個(gè)分組發(fā) 送確認(rèn)，因此題目中收到 3 的確認(rèn)幀就代表編號(hào)為 0、1、 2、3 的幀已接收，而此時(shí)發(fā)送方未收到 1 號(hào)幀的 確認(rèn)只能代表確認(rèn)幀在返回的過(guò)程中丟失了，而不代表 1 號(hào)幀未到達(dá)接收方。因此需要重傳的幀為編號(hào)是 4、5、6、7 的幀，答案為 C。其發(fā)送過(guò)程如下頁(yè)圖所示：11. 文件系統(tǒng)中，文件訪問(wèn)控制信息存儲(chǔ)的合理位置是( )A文件控制塊 B 文件分配表C用戶口令表 D 系統(tǒng)注冊(cè)表A. B.

9、C.B. 考查文件控制塊的內(nèi)容。 在文件控制塊中，通常含有以下 3 類(lèi)信息，即基本信息、存取訪問(wèn)控制信息及使用信息。本題中，文件訪 問(wèn)控制信息存儲(chǔ)的合理存儲(chǔ)位置是文件控制塊。12. 某操作系統(tǒng)的文件管理采用直接索引和多級(jí)索引混合方式，文件索引表共有10 項(xiàng)，其中前 8 項(xiàng)是直接索引項(xiàng)，第 9 項(xiàng)是一次間接索引項(xiàng)，第 10 項(xiàng)是二次間接索引項(xiàng)，假定物理塊的大小是1K，每個(gè)索引項(xiàng)占用4 個(gè)字節(jié)，則該文件系統(tǒng)中最大的文件可以達(dá)到( ) 。A 65793K B32768K C65536K D34000KA. B.C.D.多級(jí)索引的邏輯并不復(fù)雜，二級(jí)間接索引表最多有256張，但是并沒(méi)有用滿。只用了 25

10、5 張，而且第 255張中也沒(méi)有全部用足 256 條表項(xiàng)。計(jì)算時(shí)加以仔細(xì)小心，一般不會(huì)有太多變化，但是對(duì)多級(jí)索引的方法一 定要掌握。(1) 直接索引為 8*1K=8K，一級(jí)間接索引為 (1K/4B)*1K=256K ； 二級(jí)間接索引為 (1K/4B)*(1K/4B)*1K=64M 。(2) 64M 的文件需要 64M/1K=64K=65536個(gè)磁盤(pán)塊，所以其占用直接索引 8 塊，一級(jí)間接索引 256 塊，二級(jí) 間接索引 65272 塊，還要加上一級(jí)間接索引表 1 塊，二級(jí)間接索引表 1 塊+255 塊，所以一共占有磁盤(pán)空間 65793 塊。13. 設(shè)磁盤(pán)的 IO 請(qǐng)求隊(duì)列中所要訪問(wèn)的磁道號(hào)為：

11、 96，184， 25，120，12，126，73，75，當(dāng)前磁頭在 96， 前一次在 90。當(dāng)采用最短尋道時(shí)間優(yōu)先算法 (SSTF)和電梯算法所要移動(dòng)的距離是 ( ) 。A 618， 418 B 306， 260 C 306， 418 D 618， 260A.B. C.D.本題考查考生對(duì)最短尋道時(shí)間優(yōu)先算法和電梯算法的理解。最短尋道時(shí)間優(yōu)先算法(SSTF)：96 75 731201261842512 共計(jì) 306 道。電梯算法，前一次在 90，當(dāng)前在 96，表示移動(dòng)方向?yàn)榇诺涝龃蠓?向，故： 9612012618475732512 共計(jì) 260 道。計(jì)算時(shí)注意磁頭的當(dāng)前位置和運(yùn)行方向。14.

12、 UDP的報(bào)文頭部不包括 ( ) 。A目的地址 B 報(bào)文長(zhǎng)度 C目的 UDP端口 D源 UDP端口A. B.C.D.UDP是傳輸層的協(xié)議，不需要包括目的地址，尋址是網(wǎng)絡(luò)層的功能。15. 在請(qǐng)求分頁(yè)存儲(chǔ)管理中，若采用 FIFO 的頁(yè)面淘汰算法，當(dāng)分配的頁(yè)面數(shù)增加時(shí)，缺頁(yè)中斷的次數(shù) ( ) A減少 B 增加C無(wú)影響 D 可能增加也可能減少A.B.C.D. 為 FIFO 算法存在 Belady 現(xiàn)象，所以可能增加也可能減少。16. 對(duì)某一給定的程序，具有最高命中率的Cache替換算法是 ( ) 。A先進(jìn)先出替換算法 B 最近最少使用替換算法C隨機(jī)替換算法 D 無(wú)法確定A.B.C.D. 選項(xiàng)中三種替換

13、算法，平均來(lái)說(shuō) LRU替換算法命中率最高，但對(duì)于某一個(gè)特定的程序，無(wú)法確定哪種替換 算法命中率最高。17. 下列說(shuō)法中正確的是 ( ) 。 A微處理器的程序稱為微程序 B微指令控制器的執(zhí)行速度比硬布線控制器快 C存放微程序的控制存儲(chǔ)器可用 ROM或 EPROM來(lái)實(shí)現(xiàn) D在微程序控制器中，微指令使用機(jī)器指令來(lái)解釋執(zhí)行A.B.C. D.A選項(xiàng)所述顯然錯(cuò)誤； 機(jī)器指令使用微指令構(gòu)成的微程序來(lái)解釋執(zhí)行，D 錯(cuò)誤；硬布線控制器的速度要比微程序控制器快， B 錯(cuò)誤；微程序控制器根據(jù)其指令是否可以修改，分為靜態(tài)微程序控制器和動(dòng)態(tài)微程序控 制器分別可用 ROM、EPROM來(lái)實(shí)現(xiàn)。故 C 為正確選項(xiàng)。18. 下

14、列有關(guān)散列查找的敘述正確的是 ( ) 。 A散列存儲(chǔ)法只能存儲(chǔ)數(shù)據(jù)元素的值，不能存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系 B散列沖突是指同一個(gè)關(guān)鍵字對(duì)應(yīng)多個(gè)不同的散列地址 C用線性探測(cè)法解決沖突的散列表中，散列函數(shù)值相同的關(guān)鍵字總是存放在一片連續(xù)的存儲(chǔ)單元中 D若散列表的裝填因子 a 1，則可避免沖突的產(chǎn)生A. B.C.D.在散列表中， 每個(gè)元素的存儲(chǔ)位置通過(guò)散列函數(shù)和解決沖突的方法得到， 散列存儲(chǔ)法只存儲(chǔ)數(shù)據(jù)元素的值， 不能存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系，所以選項(xiàng)A 正確；散列沖突是指多個(gè)不同關(guān)鍵字對(duì)應(yīng)相同的散列地址，選項(xiàng) B 錯(cuò)誤；用線性探測(cè)法解決沖突的散列表中，散列函數(shù)值相同的關(guān)鍵字不一定總是存放在一片連續(xù)的存

15、儲(chǔ)單元中，選項(xiàng) C錯(cuò)誤；裝填因子 a 越小，發(fā)生沖突的概率越小，但仍有可能發(fā)生沖突。19. 下列序列中，滿足堆定義的是 ( ) 。A (100 ，86，48，73，35，39，42，57，66，21)B (12 ， 70， 33， 65， 24， 56， 48， 92， 86， 33)C (103 ，97，56，38，66，23，42，12，30，52，6，26)D(5 ，56，20，23，40，38，29，61，36，76，28，100)A. B.C.D.依據(jù)堆的定義， 將選項(xiàng)中的每個(gè)數(shù)列分別看成是一棵完全二叉樹(shù)， 則堆或是空樹(shù)或是滿足下列特性的完全 二叉樹(shù)：其左、右子樹(shù)分別是堆，并且當(dāng)左

16、/右子樹(shù)不空時(shí)，根結(jié)點(diǎn)的值小于 (或大于)左/ 右子樹(shù)根結(jié)點(diǎn)的 值。20. 如果一個(gè)文件系統(tǒng)使用兩級(jí)索引管理文件，物理塊大小為2KB，每塊索引地址占 4B，該文件系統(tǒng)管理文件的最大尺寸為 。A2GB B1GB C512MB D都不對(duì)A.B.C. D.每塊索引地址占 4B，物理塊大小為 2KB，則一個(gè)索引物理塊可存放 512 個(gè)物理塊的索引，兩級(jí)索引則可存 放 512*512 個(gè)物理塊的索引，每個(gè)物理塊大小為 2KB，則文件的最大尺寸為 512*512*2KB=512MB。21. 軟件與硬件在 ( ) 上可以是等級(jí)的，在 ( ) 上是不等級(jí)的 。A效率功能 B 功能效率 C方法結(jié)構(gòu) D結(jié)構(gòu)方法A

17、.B. C.D.隨著 VLSI 技術(shù)的發(fā)展， 任何操作 ( 功能)可以由軟件來(lái)實(shí)現(xiàn)， 也可以由硬件來(lái)實(shí)現(xiàn)， 軟硬件在功能上是等級(jí) 的，但是軟件實(shí)現(xiàn)和硬件實(shí)現(xiàn)在方法、結(jié)構(gòu)和效率上都不等級(jí)。22. 簡(jiǎn)單無(wú)向圖的鄰接矩陣是對(duì)稱的， 可以對(duì)其進(jìn)行壓縮存儲(chǔ)。 若無(wú)向圖 G有 n 個(gè)結(jié)點(diǎn)，其鄰接矩陣為 A1.n ，1.n ，且壓縮存儲(chǔ)在 B1.n(n-1)/2 。若按行壓縮存儲(chǔ)對(duì)稱矩陣的上三角元素， 則當(dāng) n 等于 10 時(shí)，邊(v6 ， v3) 的信息存儲(chǔ)在 ( ) 。A B18 B B19 C B20 D B21A.B.C. D.邊(v6 ， v3)與邊(v3 ， v3)是同一條邊。原第 i 行第 j

18、 列元素在矩陣 B(上三角形式 )中的下標(biāo)為：(n-1)+(n-2)+ +(n-(i-1)+(j-i)。本題中將數(shù)值代入， (10-1)+(10-2)+(6-3)=20 。所以邊 (v6 ， v3) 的信息存儲(chǔ)在 B20 中。23. 局域網(wǎng)中訪問(wèn)沖突的根源是 ( ) 。A獨(dú)占介質(zhì) B 共享介質(zhì)C引入 MAC子層 D 規(guī)則的拓?fù)浣Y(jié)構(gòu)A.B. C.D.本題考查以太網(wǎng) CSMA/CD協(xié)議的原理，由于采用隨機(jī)訪問(wèn)和競(jìng)爭(zhēng)技術(shù)，CS-MA/CD只用于總線拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)，因此答案為 B。 歸納總結(jié) CSMA/CD 改進(jìn)其它 CSMA協(xié)議的地方是，當(dāng)發(fā)送節(jié)點(diǎn)檢測(cè)到?jīng)_突后立即停止發(fā)送，并進(jìn)入沖突 解決過(guò)程。也就是

19、說(shuō)，僅當(dāng)檢測(cè)到?jīng)_突時(shí)仍未結(jié)束發(fā)送，才能節(jié)省時(shí)間和帶寬。節(jié)點(diǎn)從開(kāi)始發(fā)送至檢測(cè)到 沖突，所需的最長(zhǎng)時(shí)間等于信號(hào)在相距最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)之間的來(lái)回傳輸時(shí)間(2 ) 。沖突的檢測(cè)是通過(guò)將監(jiān)聽(tīng)到的信號(hào)與發(fā)送出去的信號(hào)相比較而實(shí)現(xiàn)的，因此物理層上需要使用便于檢測(cè)沖突的信號(hào)編碼方案。24. 以太網(wǎng)交換機(jī)中的端口 /MAC地址映射表是 ( ) 。 A是由交換機(jī)的生產(chǎn)廠商建立的B是交換機(jī)在數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程中通過(guò)學(xué)習(xí)動(dòng)態(tài)建立的 C是由網(wǎng)絡(luò)管理員建立的D是由網(wǎng)絡(luò)用戶利用特殊的命令建立的A.B. C.D.本題考查交換機(jī)中地址映射表的原理， 主要與路由器的路由表進(jìn)行區(qū)分， 路由表可以由人為配置靜態(tài)路由， 也可以通過(guò)動(dòng)態(tài)協(xié)議建立

20、，而對(duì)于交換機(jī)，映射表只能在數(shù)據(jù)轉(zhuǎn)發(fā)中進(jìn)行動(dòng)態(tài)學(xué)習(xí)建立，并且每個(gè)表項(xiàng)都 有定時(shí)器， 具體是收到一幀后先進(jìn)行自學(xué)習(xí)。 查找轉(zhuǎn)發(fā)表中與收到幀的源地址有無(wú)相匹配的項(xiàng)目。 如沒(méi)有， 就在轉(zhuǎn)發(fā)表中增加一個(gè)項(xiàng)目 (源地址、進(jìn)入的接口和時(shí)間 ) 。如有，則把原有的項(xiàng)目進(jìn)行更新，因此答案為B。25. 為提高散列表的查找效率，可以采取的正確措施有( )增大裝填因子設(shè)計(jì)沖突少的散列函數(shù) 處理沖突時(shí)，避免產(chǎn)生聚集現(xiàn)象 A僅 B 僅 C 僅， D 僅，A.B. C.D.填滿因子 的定義是：由于表長(zhǎng)是定值， 與“填入表中的元素個(gè)數(shù)”成正比，所以， 越大，填入表中的元素越多，產(chǎn)生沖突 的可能性就越大； 越小，填入表中的元

21、素越少，產(chǎn)生沖突的可能性就越小。如果增大裝填因子，則查找 時(shí)，產(chǎn)生沖突的可能性就越大；查找的效率會(huì)降低；設(shè)計(jì)沖突少的散列函數(shù)，是可行的方案； 處理沖突時(shí)，避免產(chǎn)生聚集現(xiàn)象，錯(cuò)在“避免”兩個(gè)字上。26. 設(shè) A是一個(gè)已有 10個(gè)元素的棧，棧中依次是 A1，A2， A10，棧頂是 A10；B是一個(gè)已有 10個(gè)元素 的循環(huán)隊(duì)列，隊(duì)列中元素依次為 B1， B2， B10，隊(duì)頭元素為 B1。A、B 均采用順序結(jié)構(gòu)，現(xiàn)要將棧中元 素全部移入隊(duì)列中，需 ( ) 次基本操作才能使得隊(duì)列中元素與棧中元素交替排列，即 B中排列后的元素為 B1， A1， B2， A2， B10，A10。( 不必考慮存儲(chǔ)空間 )A1

22、00 B 1000 C50 D20A. B.C.D.操作如下：（1）先將棧中所有元素出棧 （10 次） ，入隊(duì)列（10 次） ，棧為空，隊(duì)列中的元素為 B1，B2， B10， A10， A9， A1；（2）將 B1，B2，B3， B10出隊(duì)列（10 次） ，入隊(duì)列 （10 次） ，則隊(duì)列變?yōu)?A10，A2，A1，B1，B2， B10；（3）將A10，A9， A1出隊(duì)列 （10 次） ，入棧（10 次） ，棧中自棧底至棧頂依次為 A10， A3，A2， A1， 隊(duì)列中剩下 B1，B2， B10；（4）重復(fù)執(zhí)行 10 次 Bi 出隊(duì)列 （1 次） ，入隊(duì)列 （1 次），Ai 出棧（1 次） ，入隊(duì)

23、（1 次） ，則最終得至 B1，A1，B2， A2， B10， A10。27. 下列關(guān)于圖的敘述中正確的是 （ ） 回路是簡(jiǎn)單路徑 存儲(chǔ)稀疏圖，用鄰接矩陣比鄰接表更省空間 若有向圖中存在拓?fù)湫蛄?，則該圖不存在回路 A僅 B 僅， C僅 D 僅，A.B.C. D.幾個(gè)概念的描述如下： 回路：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路（環(huán)） ；簡(jiǎn)單路徑：在一條路徑中，若沒(méi)有重復(fù)相同的頂點(diǎn)，該路徑稱為簡(jiǎn)單路徑； 簡(jiǎn)單回路： 在一個(gè)回路中， 若除第一個(gè)與最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡(jiǎn)單回路 （ 簡(jiǎn)單 環(huán)） ?；芈穼?duì)應(yīng)于路徑，簡(jiǎn)單回路對(duì)應(yīng)于簡(jiǎn)單路徑； 存儲(chǔ)稀疏圖時(shí)，使用鄰接表比鄰接矩陣更

24、省空間。 若有向圖中存在拓?fù)湫蛄?，則說(shuō)明該圖不存在回路。通過(guò)以上分析可知只有的描述是正確的。28. 互聯(lián)網(wǎng)上的服務(wù)通常都是基于某一種協(xié)議，www是基于下面的 協(xié)議。A SNMP BSMTP CHTTP DTELNETA.B.C. D.本題目主要考查了“ WW”W服務(wù)。WWW是基于超文本的信息查詢系統(tǒng)，而超文本的傳輸是通過(guò)HTTP協(xié)議進(jìn)行傳輸?shù)摹?HTTP是 Hypertexttransfer prototcol ，即超文本的傳輸。SNMP是專(zhuān)門(mén)設(shè)計(jì)用于在 IP 網(wǎng)絡(luò)管理網(wǎng)絡(luò)節(jié)點(diǎn) （服務(wù)器、工作站、路由器、交換機(jī)及 HUBS等） 的一種標(biāo)準(zhǔn)協(xié) 議，它是一種應(yīng)用層協(xié)議。 SNMP使網(wǎng)絡(luò)管理員能夠管

25、理網(wǎng)絡(luò)效能， 發(fā)現(xiàn)并解決網(wǎng)絡(luò)問(wèn)題以及規(guī)劃網(wǎng)絡(luò)增長(zhǎng)。 SMTP是因特網(wǎng)電子郵件中主要的應(yīng)用層協(xié)議，它使用TCP可靠數(shù)據(jù)傳輸服務(wù)，從發(fā)送方的郵件服務(wù)器向接收方的郵件服務(wù)器發(fā)送郵件，默認(rèn)使用TCP端口為 25。 POP3是接收郵件協(xié)議，端口號(hào)是 110。Telnet 協(xié)議是 TCP/IP 協(xié)議族中的一員，是 Internet 遠(yuǎn)程登錄服務(wù)的標(biāo)準(zhǔn)協(xié)議和主要方式。它為用戶提供 了在本地計(jì)算機(jī)上完成遠(yuǎn)程主機(jī)工作的能力。29. 下列說(shuō)法中錯(cuò)誤的是 （ ） 。 程序中斷過(guò)程是由硬件和中斷服務(wù)程序共同完成的 在每條指令的執(zhí)行過(guò)程中，每個(gè)總線周期要檢查一次有無(wú)中斷請(qǐng)求 檢測(cè)有無(wú) DMA請(qǐng)求，一般安排在一條指令執(zhí)行

26、過(guò)程的末尾 中斷服務(wù)程序的最后指令是無(wú)條件轉(zhuǎn)移指令A(yù)、 B 、 C、 D 、A.B. C.D.程序中斷過(guò)程是由硬件執(zhí)行中斷隱指令和中斷服務(wù)程序共同完成的，其余說(shuō)法都是錯(cuò)誤的。 歸納總結(jié) 中斷系統(tǒng)是計(jì)算機(jī)實(shí)現(xiàn)中斷功能的軟、硬件總稱。一般在CPU中配置中斷機(jī)構(gòu)，在外設(shè)接口中配置中斷控制器，在軟件上設(shè)計(jì)相應(yīng)的中斷服務(wù)程序。30. 甲乙兩臺(tái)主機(jī)通過(guò) TCP的進(jìn)行通信，甲方發(fā)送了一個(gè)帶有 FIN 標(biāo)志的數(shù)據(jù)段，所表示的含義是 ( ) 。 A將斷開(kāi)通信雙方的 TCP連接B單方面釋放連接，表示本方已經(jīng)無(wú)數(shù)據(jù)發(fā)送，但是可以接受對(duì)方的數(shù)據(jù) C中止數(shù)據(jù)發(fā)送，雙方都不能發(fā)送數(shù)據(jù)D連接被重新建立A.B. C.D.本題

27、考查 TCP首部 FIN 標(biāo)志位和 TCP的連接管理。 TCP采用對(duì)稱釋放法釋放連接。任何一方想要釋放連接 時(shí)，發(fā)送一個(gè) FIN=1 的 TCP段，當(dāng)這個(gè)段被確認(rèn)后，這個(gè)方向的連接就釋放了。當(dāng)雙方都發(fā)送了FIN=1 的TCP段并得到了確認(rèn)時(shí)，這條 TCP連接就釋放了。通常釋放 TCP連接需要 4 個(gè) TCP段，但第一個(gè) FIN 的確 認(rèn)可以和第二個(gè) FIN 合并，從而只需要 3 個(gè)段。當(dāng)雙方同時(shí)向?qū)Ψ桨l(fā)送 FIN=1 的段時(shí)，按正常方法響應(yīng)， 事實(shí)上同時(shí)釋放和順序釋放沒(méi)有什么不同。因此本題中，甲方單方面釋放連接，但乙方有數(shù)據(jù)還可以繼續(xù) 發(fā)送，因此答案是 B。31. 主存地址寄存器 MAR的位數(shù)

28、與下列哪個(gè)寄存器相同 ?( ) 。A主存數(shù)據(jù)寄存器 MDR B程序計(jì)數(shù)器 PCC指令寄存器 IR D 累加器 ACA.B. C.D.主存地址寄存器 MAR和程序計(jì)數(shù)器 PC 的位數(shù)都取決于主存儲(chǔ)器的容量，二者位數(shù)相等，選B。32. 字長(zhǎng) 16 位的補(bǔ)碼定點(diǎn)小數(shù)的表示范圍是 ( ) 。A 01-2 -15 B -(1-2 -15 ) 1-2 -15C-1 1-2 -15 D-1 1A.B.C. D.表示定點(diǎn)小數(shù)時(shí)，補(bǔ)碼可比原碼、反碼多表示一個(gè)-1 ，選 C。33. 關(guān)于 FTP的工作過(guò)程，下面那種說(shuō)法錯(cuò)誤的是 ( ) 。A在傳輸數(shù)據(jù)前， FTP服務(wù)器用 TCP 21 端口與客戶端建立連接B建立連

29、接后， FTP服務(wù)器用 TCP 20 端口傳輸數(shù)據(jù)C數(shù)據(jù)傳輸結(jié)束后， FTP服務(wù)器同時(shí)釋放 21 和 20 端口D FTP客戶端的端口是動(dòng)態(tài)分配的A.B.C. D.本題考查 FTP 的工作原理， FTP使用兩條 TCP連接完成文件傳輸，一條是控制連接，另一條是數(shù)據(jù)連接。 平時(shí) FTP服務(wù)器總在端口 21 上等待客戶的連接請(qǐng)求，當(dāng)用戶需要傳輸文件時(shí)，F(xiàn)TP 客戶與 FTP服務(wù)器的端口 21 建立一個(gè)控制連接， 用來(lái)傳送客戶的命令和服務(wù)器的響應(yīng)。 當(dāng)客戶在控制連接上發(fā)出數(shù)據(jù)傳輸命令時(shí)， 服務(wù)器在另一個(gè)端口上主動(dòng)與客戶建立一條數(shù)據(jù)連接，然后在數(shù)據(jù)連接上傳輸文件。當(dāng)一個(gè)文件傳輸結(jié)束 時(shí)，關(guān)閉數(shù)據(jù)連接。

30、如果用戶請(qǐng)求另一個(gè)文件的傳輸，則服務(wù)器和客戶再建立一個(gè)數(shù)據(jù)連接，用于傳輸新 的文件。雖然數(shù)據(jù)連接頻繁地建立和釋放，但控制連接在整個(gè)會(huì)話期間一直保持，直到客戶與服務(wù)器通信 結(jié)束為止，因此答案為 C。34. 設(shè)樹(shù) T的度為 4，其中度為 1，2，3 和4 的結(jié)點(diǎn)個(gè)數(shù)分別為 4，2，1，1則 T中的葉子數(shù)為 A5 B6 C7 D8A.B.C. D.n=n0+n1+n2+n3+n4， n=1*4+2*2+3*1+4*1 ，所以 n0=7。35. 一次分配所有資源的方法可以預(yù)防死鎖的發(fā)生，它破壞的死鎖四個(gè)必要條件中的( ) 。A互斥條件 B 占有并請(qǐng)求 C 非剝奪條件 D 循環(huán)等待A.B. C.C. 發(fā)

31、生死鎖的四個(gè)必要條件如下：互斥條件；占有并請(qǐng)求資源；非剝奪條件和循環(huán)等待條件。一次分配所有 資源的方法是當(dāng)進(jìn)程需要資源時(shí)，一次性提出所有的請(qǐng)求，若請(qǐng)求的所有資源均滿足則分配，只要有一項(xiàng) 不滿足，那么不分配任何資源，該進(jìn)程阻塞，直到所有的資源空閑后，滿足了進(jìn)程的所有需求時(shí)再分配。 這種分配方法不會(huì)部分占有資源，所以就打破了死鎖的四個(gè)必要條件之一，實(shí)現(xiàn)了對(duì)死鎖的預(yù)防。但是， 這種分配方式需要湊齊所有資源，所以，當(dāng)一個(gè)進(jìn)程所需的資源比較多時(shí)，資源的利用率會(huì)比較低，甚至 會(huì)造成進(jìn)程的饑餓。正確答案為 B。36. 設(shè) n是描述問(wèn)題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是( ) 。2 2 5 3 A O

32、(n2log 2n) B O(nlog 5n) C O(n2log 5n) D O(n3)A.B.C. D. 基本運(yùn)算語(yǔ)句是 k=5*k ，設(shè)其執(zhí)行時(shí)間為 T(n) 。對(duì)于 j 每循環(huán)一次，該語(yǔ)句的執(zhí)行次數(shù)為 m，有： 5m n，即 m log 5n 。所以 :37. 馮·諾依曼機(jī)中指令和數(shù)據(jù)均以二進(jìn)制形式存放在存儲(chǔ)器中，CPU區(qū)分它們的依據(jù)是 ( ) 。A指令操作碼的譯碼結(jié)果 B 指令和數(shù)據(jù)的尋址方式C指令周期的不同階段 D 指令和數(shù)據(jù)所在的存儲(chǔ)單元A.B.C. D.馮·諾依曼機(jī)中根據(jù)指令周期的不同階段來(lái)區(qū)分從存儲(chǔ)器取出的是指令還是數(shù)據(jù)： 取指周期取出的是指令； 執(zhí)行周期

33、取出的是數(shù)據(jù)。此外，也可根據(jù)取數(shù)和取指令時(shí)的地址來(lái)源不同來(lái)區(qū)分：指令地址來(lái)源于程序計(jì) 數(shù)器 PC；數(shù)據(jù)地址來(lái)源于地址形成部件。38. 指令流水線將一條指令的執(zhí)行過(guò)程分為四步，其中第1、2 和 4 步的經(jīng)過(guò)時(shí)間為 t ，如下圖所示。若該流水線順序執(zhí)行， 50條指令共用 153t ，并且不考慮相關(guān)問(wèn)題，則該流水線的瓶頸第3 步的時(shí)間是 ( ) 。A2t B 3t C 4t D 5tA.B. C.D.第 3 個(gè)流水段的執(zhí)行時(shí)間沒(méi)有給出， 顯然這是一個(gè)瓶頸段， 設(shè)它的執(zhí)行時(shí)間為 X。通過(guò)列方程 (3+X) t+49X t=153 t ，可以求得 X=3。 歸納總結(jié) 對(duì)于包含瓶頸段的指令流水線，完成n

34、個(gè)任務(wù)的解釋共需時(shí)間 (n-1)max t i， ，其中k 為流水線段數(shù)。 解題技巧 首先要列方程，然后才能求出瓶頸段的執(zhí)行時(shí)間。39. 數(shù)據(jù)鏈路層采用選擇重傳 (SR)協(xié)議，發(fā)送方已經(jīng)發(fā)送了編號(hào)為 03的幀。當(dāng)計(jì)時(shí)器超時(shí)時(shí)若發(fā)送方 只收到 023 號(hào)幀的確認(rèn)，則發(fā)送方此時(shí)需要重發(fā)的幀數(shù)是 。A1 B2 C3 D4A. B.C.B. 本題目主要考查了“多幀滑動(dòng)窗口與選擇重傳協(xié)議(SR) ”。當(dāng)管道化技術(shù)建立在不可靠的信道上時(shí)會(huì)有一些問(wèn)題。比如，如果位于幀流中的某個(gè)幀丟失或損壞了，另 外在發(fā)送進(jìn)程發(fā)現(xiàn)出錯(cuò)前，大量的后繼幀會(huì)到達(dá)接收方；也可能當(dāng)一個(gè)壞幀到達(dá)接收方時(shí)，會(huì)被接收方丟 棄，這些又如何處理

35、呢 ?處理以上問(wèn)題，其中一種方法稱之為“ GO-BACK-N”協(xié)議，即 GBN，接收進(jìn)程丟棄 所有的后繼幀，并且不通知發(fā)送進(jìn)程。該策略對(duì)應(yīng)接收窗口為 l 的情況，即只能按順序接收幀，當(dāng)發(fā)送進(jìn) 程超時(shí)后，必須按順序重傳所有未被確認(rèn)的幀。如果錯(cuò)誤率高的話，這種方法會(huì)浪費(fèi)很多帶寬，但對(duì)內(nèi)存 需求不大。為了進(jìn)一步提高信道的利用率，可設(shè)法只重傳出現(xiàn)差錯(cuò)的數(shù)據(jù)幀或是計(jì)時(shí)器超時(shí)的數(shù)據(jù)幀。但 這時(shí)必須加大接收窗口，以便先收下發(fā)送序號(hào)不連續(xù)但仍處在接收窗口中的那些數(shù)據(jù)幀。等到所缺序號(hào)的 數(shù)據(jù)幀收到后再一并送交主機(jī)。這就是選擇重傳協(xié)議。題目告知已經(jīng)發(fā)送了編號(hào)為 03 的幀，當(dāng)計(jì)時(shí)器超時(shí)時(shí)，發(fā)送方只收到 號(hào)幀的確認(rèn)

36、。這表示，對(duì)方 已經(jīng)正確接收到了 0、 2、3 號(hào)幀，只有 1 號(hào)幀沒(méi)有被正確接收，此時(shí)，發(fā)生了超時(shí)問(wèn)題，所以發(fā)送方需要 重發(fā)的幀數(shù)是 1。40. 一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿足 。A所有的結(jié)點(diǎn)均無(wú)左孩子 B 所有的結(jié)點(diǎn)均無(wú)右孩子C只有一個(gè)葉子結(jié)點(diǎn) D 是任意一棵二叉樹(shù)A.B.C. D.前序序列是“根左右”，后序序列是“左右根”，若要這兩個(gè)序列相反，只有單支樹(shù)，所以本題的 A 和 B 均對(duì)，單支樹(shù)的特點(diǎn)是只有一個(gè)葉子結(jié)點(diǎn)，故C是最合適的，選 C。A或 B 都不全。二、 綜合應(yīng)用題 ( 總題數(shù)： 3，分?jǐn)?shù)： 25.00)已知有 6 個(gè)頂點(diǎn)(頂點(diǎn)編號(hào)為 0 5)的有向帶權(quán)圖 G，其鄰接矩陣 4為上三角陣，按行為主序 (行優(yōu)先 )保存 在下面的一維數(shù)組中：要求：(分?jǐn)?shù)： 9.99 )(1) . 寫(xiě)出圖 G的鄰接矩陣 A；(分?jǐn)?shù)： 3.33 )正確答案： （ 將一位數(shù)組中的內(nèi)容填充到二維數(shù)組中，頂點(diǎn)0頂點(diǎn) 0 的位置用 0 填充；得到圖 G的鄰接矩陣如下：（2）. 畫(huà)出有向帶權(quán)圖；（分?jǐn)?shù)： 3.33 ）正確答案： （ 根據(jù)各個(gè)頂點(diǎn)之間的關(guān)系，可知有向帶權(quán)圖G如下圖所示）（3）. 求圖 G 的關(guān)鍵路徑，并計(jì)算該關(guān)鍵路徑的長(zhǎng)度。（分?jǐn)?shù)：3.33 ） 正確答案： （ 關(guān)鍵路徑：從起點(diǎn)到終點(diǎn)的最長(zhǎng)路徑長(zhǎng)度 （