2009-2010計(jì)算機(jī)考研真題及答案(含選擇題解析)WORD高清晰版

1、2009年統(tǒng)考計(jì)算機(jī)考研真題 1一.單項(xiàng)選擇題，每小題2分，共80分。 1二.綜合應(yīng)用題。共70分。 588202009年計(jì)算機(jī)統(tǒng)考真題參考答案 1 . 選擇題2 .綜合應(yīng)用題2010年全國研究生考試計(jì)算機(jī)統(tǒng)考試題及答案242009年統(tǒng)考計(jì)算機(jī)考研真題單項(xiàng)選擇題，每小題 2分，共80分。1 .為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依 次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是A.棧B.隊(duì)列C.樹D.圖2 .設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q,且7個(gè)元素

2、出隊(duì)的順序是 bdcfeag,則棧S的容量至少是 A. 1 B.2 C.3 D.43 .給定二叉樹圖所示。設(shè) N代表二叉機(jī)勺根，L代表根結(jié)點(diǎn)的左子樹， R代 表根結(jié)點(diǎn)的右子樹。若遍歷后的結(jié)點(diǎn)序列為3, 1, 7, 5, 6, 2, 4,則其遍歷方式是 A. LRN B.NRL C.RLN D.RNL4 .下列二叉排序樹中，滿足平衡二叉樹定義的是5.已知一棵完全二叉樹的第 6層（設(shè)根為第1層）有8個(gè)葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是A. 39 B.52 C.111 D.1196 .將森林轉(zhuǎn)換為對應(yīng)的二叉樹，若在二叉樹中，結(jié)點(diǎn) u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在原來的森林中,u和v可能具有的關(guān)系是

3、I .父子關(guān)系II.兄弟關(guān)系III. u的父結(jié)點(diǎn)與v的父結(jié)點(diǎn)是兄弟關(guān)系A(chǔ).只有 II B.I 和 II C.I 和 III D.I 、II 和 III7 .下列關(guān)于無向連通圖特性的敘述中，正確的是I .所有頂點(diǎn)的度之和為偶數(shù)II.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1 III.至少有一個(gè)頂點(diǎn)的度為 1A.只有I B.只有II C.I和II D.I和III8 .下列敘述中，不符合 m階B樹定義要求的是A.根節(jié)點(diǎn)最多有m棵子樹 B.所有葉結(jié)點(diǎn)都在同一層上C.各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D.葉結(jié)點(diǎn)之間通過指針鏈接9 .已知關(guān)鍵序列5, 8, 12, 19, 28, 20, 15, 22是小根堆（最小堆），插入關(guān)鍵字

4、3,調(diào)整后得到的小根 堆是A. 3, 5, 12, 8, 28, 20, 15, 22, 19B. 3, 5, 12, 19, 20, 15, 22, 8, 28C. 3, 8, 12, 5, 20, 15, 22, 28, 19D. 3, 12, 5, 8, 28, 20, 15, 22, 1910 .若數(shù)據(jù)元素序列 11, 12, 13, 7, 8, 9, 23, 4, 5是采用下列排序方法之一得到的第二趟排序后的結(jié) 果，則該排序算法只能是A.起泡排序B.插入排序C.選擇排序D.二路歸并排序11 .馮諾依曼計(jì)算機(jī)中指令和數(shù)據(jù)均以二進(jìn)制形式存放在存儲(chǔ)器中，CPU區(qū)分它們的依據(jù)是 A.指令操作

5、碼的譯碼結(jié)果 B.指令和數(shù)據(jù)的尋址方式C.指令周期的不同階段D.指令和數(shù)據(jù)所在的存儲(chǔ)單元12 .一個(gè)C語言程序在一臺(tái) 32位機(jī)器上運(yùn)行。程序中定義了三個(gè)變量 xyz,其中x和z是int型，y為short 型。當(dāng)x=127, y=-9時(shí)，執(zhí)行賦值語句 z=x+y后，xyz的值分別是A. X=0000007FH , y=FFF9H , z=00000076HA. X=0000007FH , y=FFF9H , z=FFFF0076HA. X=0000007FH , y=FFF7H , z=FFFF0076HA. X=0000007FH , y=FFF7H , z=00000076H13 .浮點(diǎn)數(shù)加

6、減運(yùn)算過程一般包括對階、尾數(shù)運(yùn)算、規(guī)格化、舍入和判溢出等步驟。設(shè)浮點(diǎn)數(shù)的階碼和尾 數(shù)均采用補(bǔ)碼表示， 且位數(shù)分別為5位和7位（均含2位符號位）。若有兩個(gè)數(shù)X=27 X 29/32, 丫=25 X 5/8 , 則用浮點(diǎn)加法計(jì)算 X+Y的最終結(jié)果是A. 00111 1100010 B.00111 0100010C. 01000 0010001 D.發(fā)生溢出14 .某計(jì)算機(jī)的Cache共有16塊，采用2路組相聯(lián)映射方式（即每組2塊）。每個(gè)主存塊大小為32字節(jié)，按字節(jié)編址。主存 129號單元所在主存塊應(yīng)裝入到的Cache組號是A. 0 B.2 C.4 D.615 .某計(jì)算機(jī)主存容量為 64KB ,其中

7、ROM區(qū)為4KB ,其余為RAM區(qū)，按字節(jié)編址?，F(xiàn)要用 2K X 8位 的ROM芯片和4K X 4位的RAM芯片來設(shè)計(jì)該存儲(chǔ)器， 則需要上述規(guī)格的 ROM芯片數(shù)和RAM芯片數(shù) 分別是A. 1、15 B, 2、15 C . 1、30 D , 2、3016 .某機(jī)器字長16位，主存按字節(jié)編址，轉(zhuǎn)移指令采用相對尋址，由兩個(gè)字節(jié)組成，第一字節(jié)為操作碼字段，第二字節(jié)為相對位移量字段。假定取指令時(shí)，每取一個(gè)字節(jié)PC自動(dòng)加1。若某轉(zhuǎn)移指令所在主存地址為2000H ,相對位移量字段的內(nèi)容為06H,則該轉(zhuǎn)移指令成功轉(zhuǎn)以后的目標(biāo)地址是A.2006H B.2007H C.2008H D.2009H17 .下列關(guān)于R

8、ISC的敘述中，錯(cuò)誤的是A. RISC普遍采用微程序控制器B. RISC大多數(shù)指令在一個(gè)時(shí)鐘周期內(nèi)完成C. RISC的內(nèi)部通用寄存器數(shù)量相對CISC多D. RISC的指令數(shù)、尋址方式和指令格式種類相對CISC少18 .某計(jì)算機(jī)的指令流水線由四個(gè)功能段組成，指令流經(jīng)各功能段的時(shí)間（忽略各功能段之間的緩存時(shí)間）分別是90ns、80ns、70ns和60ns,則該計(jì)算機(jī)的 CPU時(shí)鐘周期至少是A. 90ns B.80ns C.70ns D.60ns19 .相對于微程序控制器，硬布線控制器的特點(diǎn)是A.指令執(zhí)行速度慢，指令功能的修改和擴(kuò)展容易B .指令執(zhí)行速度慢，指令功能的修改和擴(kuò)展難C.指令執(zhí)行速度快，

9、指令功能的修改和擴(kuò)展容易D.指令執(zhí)行速度快，指令功能的修改和擴(kuò)展難20 .假設(shè)某系統(tǒng)總線在一個(gè)總線周期中并行傳輸4字節(jié)信息，一個(gè)總線周期占用2個(gè)時(shí)鐘周期，總線時(shí)鐘頻率為10MHz ,則總線帶寬是A. 10MB/s B.20MB/S C.40MB/S D.80MB/S21 .假設(shè)某計(jì)算機(jī)的存儲(chǔ)系統(tǒng)由Cache和主存組成，某程序執(zhí)行過程中訪存1000次，其中訪問 Cache缺失（未命中）50次，則Cache的命中率是A. 5% B.9.5% C.50% D.95%22 .下列選項(xiàng)中，能引起外部中斷的事件是A.鍵盤輸入 B.除數(shù)為0 C.浮點(diǎn)運(yùn)算下溢 D.訪存缺頁23 .單處理機(jī)系統(tǒng)中，可并行的是I

10、進(jìn)程與進(jìn)程II處理機(jī)與設(shè)備III處理機(jī)與通道IV設(shè)備與設(shè)備A. I、 II 和 III B. I 、 II 和 IV C. I 、 III 和 IV D. II 、 III 和 IV24 .下列進(jìn)程調(diào)度算法中，綜合考慮進(jìn)程等待時(shí)間和執(zhí)行時(shí)間的是A.時(shí)間片輪轉(zhuǎn)調(diào)度算法B短進(jìn)程優(yōu)先調(diào)度算法C.先來先服務(wù)調(diào)度算法D.高響應(yīng)比優(yōu)先調(diào)度算法25 .某計(jì)算機(jī)系統(tǒng)中有8臺(tái)打印機(jī)，有K個(gè)進(jìn)程競爭使用，每個(gè)進(jìn)程最多需要3臺(tái)打印機(jī)。該系統(tǒng)可能會(huì)發(fā)生死鎖的 K的最小值是（）不死鎖需要2K+1V8,最多支持3個(gè)進(jìn)程并發(fā)。注意問的如果是“不會(huì)發(fā)生死鎖 的最大值”就選B。4個(gè)以上就死鎖，所以會(huì)死鎖的最小值是 4。別看錯(cuò)了

11、。A . 2 B.3C.4D.526 .分區(qū)分配內(nèi)存管理方式的主要保護(hù)措施是A.界地址保護(hù)B.程序代碼保護(hù) C.數(shù)據(jù)保護(hù) D.棧保護(hù)27 .一個(gè)分段存儲(chǔ)管理系統(tǒng)中，地址長度為32位，其中段號占8位，則段長最大 A.2的8次方字節(jié) B.2的16次方字節(jié) C.2的24次方字節(jié) D.2的32次方字節(jié)28 .下列文件物理結(jié)構(gòu)中，適合隨機(jī)訪問且易于文件擴(kuò)展的是A.連續(xù)結(jié)構(gòu)B.索引結(jié)構(gòu)C.鏈?zhǔn)浇Y(jié)構(gòu)且磁盤塊定長 D.鏈?zhǔn)浇Y(jié)構(gòu)且磁盤塊變長29 .假設(shè)磁頭當(dāng)前位于第105道，正在向磁道序號增加的方向?yàn)鮿?dòng)。現(xiàn)有一個(gè)磁 道訪問請求序列為35, 45, 12, 68, 110, 180, 170, 195,采用SCA

12、N調(diào)度（電梯調(diào)度）算法得到的磁道訪問序列是A. 110, 170, 180, 195, 68, 45, 35, 12B.110, 68, 45, 35, 12, 170, 180, 195C.110, 170, 180, 195, 12, 35, 45, 68D.12, 35, 45, 68, 110, 170, 180, 19530 .文件系統(tǒng)中，文件訪問控制信息存儲(chǔ)的合理位置是A.文件控制塊B.文件分配表C.用戶口令表D.系統(tǒng)注冊表31 .設(shè)文件F1的當(dāng)前引用計(jì)數(shù)值為1,先建立F1的符號鏈接（軟鏈接）文件 F2,再建立F1的硬鏈接文件F3,然后刪除F1。此時(shí)，F(xiàn)2和F3的引用計(jì)數(shù)值 分別是

13、A . 0、 1 B.1、 1 C.1、 2 D.2、 132 .程序員利用系統(tǒng)調(diào)用打開I/O設(shè)備時(shí)，通常使用的設(shè)備標(biāo)識(shí)是A.邏輯設(shè)備名B.物理設(shè)備名C.主設(shè)備號D.從設(shè)備號33 .在OSI參考模型中，自下而上第一個(gè)提供端到端服務(wù)的層次是A.數(shù)據(jù)鏈路層 B.傳輸層 C.會(huì)話層D.應(yīng)用層34 .在無噪聲情況下，若某通信鏈路的帶寬為3kHz,采用4個(gè)相位，每個(gè)相位具有4種振幅的QAM調(diào)制技術(shù)，則該通信鏈路的最大數(shù)據(jù)傳輸速率是A. 12kbps B.24 kbps C.48 kbps D.96 kbps35 .數(shù)據(jù)鏈路層采用了后退N幀（GBN）協(xié)議，發(fā)送方已經(jīng)發(fā)送了編號為07的幀。當(dāng)計(jì)時(shí)器超時(shí)時(shí)，若

14、發(fā)送方只收到0、2、3號幀的確認(rèn)，則發(fā)送方需要重發(fā)的幀數(shù)是A. 2 B.3 C.4 D.536 .以太網(wǎng)交換機(jī)進(jìn)行轉(zhuǎn)發(fā)決策時(shí)使用的PDU地址是A.目的物理地址 B.目的IP地址 C.源物理地址 D.源IP地址1Gbps,電纜中的信37 .在一個(gè)采用 CSMA/CD協(xié)議的網(wǎng)絡(luò)中，傳輸介質(zhì)是一根完整的電纜，傳輸速率為 號傳播速度是200 000km/s o若最小數(shù)據(jù)幀長度減少 800比特，則最遠(yuǎn)的兩個(gè)站點(diǎn)之間的距離至少需要A,增加160m B.增加80m C.減少160m D.減少80m38 .主機(jī)甲和主機(jī)乙間已建立一個(gè)TCP連接，主機(jī)甲向主機(jī)乙發(fā)送了兩個(gè)連續(xù)的 TCP段，分別包含 300字節(jié)和5

15、00字節(jié)的有效載荷，第一個(gè)段的序列號為200,主機(jī)乙正確接收到兩個(gè)段后，發(fā)送給主機(jī)甲的確認(rèn)序列號是 A. 500 B.700 C.800 D.100039 .一個(gè)TCP連接總是以1KB的最大段發(fā)送 TCP段，發(fā)送方有足夠多的數(shù)據(jù)要發(fā)送。 當(dāng)擁塞窗口為16KB 時(shí)發(fā)生了超時(shí)，如果接下來的 4個(gè)RTT （往返時(shí)間）時(shí)間內(nèi)的 TCP段的傳輸都是成功的，那么當(dāng)?shù)?4個(gè) RTT時(shí)間內(nèi)發(fā)送的所有 TCP段都得到肯定應(yīng)答時(shí)，擁塞窗口大小是A. 7KB B. 8KB C. 9KB D. 16KB 40.FTP客戶和服務(wù)器間傳遞 FTP命令時(shí)，使用的連接是A.建立在 TCP之上的控制連接 B.建立在TCP之上的

16、數(shù)據(jù)連接 C.建立在 UDP之上的控制連接 D.建立在 UDP之上的數(shù)據(jù)連接二.綜合應(yīng)用題。共70分。41. （10分）帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離）的最短路徑問題是找出從初始頂點(diǎn)到目 標(biāo)頂點(diǎn)之間的一條最短路徑。假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一種解決該問題的方法： 設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn)，令當(dāng)前頂點(diǎn)u為初始頂點(diǎn)；選擇離u最近且尚未在最短路徑中的一個(gè)頂點(diǎn)V,加入到最短路徑中，修改當(dāng)前頂點(diǎn)u=v;重復(fù)步驟，直到 u是目標(biāo)頂點(diǎn)時(shí)為止。請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則，請舉例說明。42. （15分）已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)為d

17、atalink假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第 k個(gè)位置上的結(jié)點(diǎn)（k為正整數(shù)）。若查找成功，算法輸出該結(jié)點(diǎn)的 data 值，并返回1;否則，只返回 0。要求：（1）描述算法的基本設(shè)計(jì)思想（2）描述算法的詳細(xì)實(shí)現(xiàn)步驟（3）根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語言描述算法（使用 C或C+或JAVA語言實(shí)現(xiàn)），關(guān)鍵 之處請給出簡要注釋。43. （8分）某計(jì)算機(jī)的 CPU主頻為500MHz , CPI為5 （即執(zhí)行每條指令平均需 5個(gè)時(shí)鐘周期）。假定某 外設(shè)的數(shù)據(jù)傳輸率為 0.5MB/S,采用中斷方式與主機(jī)進(jìn)行數(shù)據(jù)傳送，以 32位為傳

18、輸單位，對應(yīng)的中斷服 務(wù)程序包含18條指令，中斷服務(wù)的其他開銷相當(dāng)于2條指令的執(zhí)行時(shí)間。請回答下列問題，要求給出計(jì)算過程。（1）在中斷方式下， CPU用于該外設(shè)I/O的時(shí)間占整個(gè) CPU時(shí)間的百分比是多少？（2）當(dāng)該外設(shè)的數(shù)據(jù)傳輸率達(dá)到 5MB/S時(shí)，改用DMA方式傳送數(shù)據(jù)。假設(shè)每次DMA傳送大小為5000B, 且DMA預(yù)處理和后處理的總開銷為 500個(gè)時(shí)鐘周期，則CPU用于該外設(shè)I/O的時(shí)間占整個(gè) CPU時(shí)間的 百分比是多少？（假設(shè) DMA與CPU之間沒有訪存沖突）44. （13分）某計(jì)算機(jī)字長16位，采用16位定長指令字結(jié)構(gòu)，部分?jǐn)?shù)據(jù)通路結(jié)構(gòu)如圖所示。圖中所有控 制信號為1時(shí)表示有效、為

19、0時(shí)表示無效。例如控制信號MDRinE為1表示允許數(shù)據(jù)從 DB打入MDR ,MDRin為1表示允許數(shù)據(jù)從內(nèi)總線打入MDR 。假設(shè)MAR的輸出一直處于使能狀態(tài)。加法指令“ADD(R1), R0”的功能為(R0) + (R1) 一( R1),即將R0中的數(shù)據(jù)與R1的內(nèi)容所指主存單元的數(shù)據(jù)相 加，并將結(jié)果送入 R1的內(nèi)容所指主存單元中保存。AddrCB ,R1 白 utRlin» R1 A J d* 1R * I RinACinACout至指令律碼 部件存儲(chǔ)器Mr !|iABrcoutPC p- PCinROoutROirt敢一數(shù)據(jù)通路結(jié)構(gòu)下表給出了上述指令取值和譯碼階段每個(gè)節(jié)拍(時(shí)鐘周期

20、)的功能和有效控制信號，請按表中描 述方式用表格列出指令執(zhí)行階段每個(gè)節(jié)拍的功能和有效控制信號。功能和控制信號時(shí)鐘功能有效控制信號C1MAR (PC)PCout,MARinC2MDR M(MAR) PC(PC)+1MemR,MDRinE PC+1C3IR (MDR)MDRout,IRinC4指令譯碼無45. (7分)三個(gè)進(jìn)程P1、P2、P3互斥使用一個(gè)包含N (N>0)個(gè)單元的緩沖區(qū)。P1每次用 produce。生成一個(gè)正整數(shù)并用 put ()送入緩沖區(qū)某一空單元中；P2每次用getodd ()從該緩沖區(qū)中取出一個(gè)奇數(shù)并用 countodd ()統(tǒng)計(jì)奇數(shù)個(gè)數(shù)；P3每次用geteven()從

21、該緩 沖區(qū)中取出一個(gè)偶數(shù)并用 counteven ()統(tǒng)計(jì)偶數(shù)個(gè)數(shù)。請用信號量機(jī)制實(shí)現(xiàn)這三個(gè)進(jìn)程的 同步與互斥活動(dòng)，并說明所定義的信號量的含義。要求用偽代碼描述。46. （8分）請求分頁管理系統(tǒng)中，假設(shè)某進(jìn)程的頁表內(nèi)容如下表所示頁號頁框號后效位（存在包）0101H11-02254H1頁面大小為4KB, 一次內(nèi)存的訪問時(shí)間是100ns,一 次快表（TLB）的訪問時(shí)間是10ns,處理一次缺頁的平均 時(shí)間為108ns （已含更新TLB和頁表的時(shí)間），進(jìn)程的駐 留集大小固定為2,采用最近最少使用置換算法（LRU） 和局部淘汰策略。假設(shè)TLB初始為空；地址轉(zhuǎn)換時(shí)先訪問TLB,若TLB未命中，再訪問頁表（

22、忽略訪問頁表之后的TLB更新時(shí)間）；有效位為0表示頁面不在內(nèi)存，產(chǎn)生缺頁中斷，缺頁中斷處理后，返回到產(chǎn)生缺頁中斷的 指令處重新執(zhí)行。設(shè)有虛地址訪問序列2362H、1565H、25A5H,請問：（1）依次訪問上述三個(gè)虛地址，各需多少時(shí)間？給出計(jì)算過程（2）基于上述訪問序列，虛地址 1565H的物理地址是多少？請說明理由。47. （9分）某公司網(wǎng)絡(luò)拓?fù)鋱D如下圖所示，路由器 R1通過接口 E1、E2分別連接局域網(wǎng)1、局域網(wǎng)2, 通過接口 L0連接路由器 R2,并通過路由器 R2連接域名服務(wù)器與互聯(lián)網(wǎng)。R1的L0接口的IP地址是48. .118.2.1; R2 的 L0 接口的 IP 地址是 202.

23、118.2.2, L1 接口的 IP 地址是 , E0 接口的 IP地址是;域名服務(wù)器的 IP地址是。f互聯(lián)網(wǎng)）/tlHlk 、R1和R2舊居由我"網(wǎng)為:目組網(wǎng)絡(luò)】產(chǎn)地址子網(wǎng)推碼下二喔II地址修口將IP地址空間/24劃分為兩個(gè)子網(wǎng)，分配給局域網(wǎng)1、局域網(wǎng)2,每個(gè)局域網(wǎng)分配的地址數(shù)不少于120個(gè)，請給出子網(wǎng)劃分結(jié)果。說明理由或給出必要的計(jì)算過程。請給出R1的路由表，使其明確包括到局域網(wǎng)1的路由、局域網(wǎng)2的路由、域名服務(wù)器的主機(jī)路由和互聯(lián)網(wǎng)的路由。請采用路由聚合技術(shù)，給出R2到局域網(wǎng)1和局域網(wǎng)2的路

24、由。如09年計(jì)算機(jī)統(tǒng)考真題參考答案選擇題123J5&789wBCDBCBA叵*HII12B141517INI"2UCDhl>CAA【）B2122232425珀272S29劉11Ann-CAeAA31523334353637伸4(1HAHCAD1>cA1 2 3 4 5 6 7 8 9 10B C D B C B A D A B11 12 13 14 15 16 17 18 19 20C D D C D C A A D B21 22 23 24 25 26 27 28 29 30D A D D C A C B A A31 32 33 34 35 36 37 38 3

25、9 40B A B B C A D D C A1 .為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（隊(duì)列）棧的定義：棧是只準(zhǔn)在表尾進(jìn)行插入和刪除的線性表，稱為 LIOFO （即后進(jìn)先出表）。允許插入和刪除的 一端叫棧頂，另一端叫棧底。隊(duì)列的定義：隊(duì)列是允許在一端進(jìn)行插入而在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。隊(duì)列也稱為先進(jìn)先出表（ FIFO ）樹的定義：樹是包含 n個(gè)結(jié)點(diǎn)的有限集合（n>0）圖的定義：圖（Graph）是由非空的頂點(diǎn)集合和一個(gè)描述頂點(diǎn)之間關(guān)系一一邊（或者?。┑募辖M成。其形式化定義為：G=（

26、V ,E ）其中G表一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中邊的集合。2 .設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q,且7個(gè)元素出隊(duì)的順序是 bdcfeagMU棧S的容量？ ？ ？ （3）3 .給定二叉樹圖，若遍歷后的結(jié)點(diǎn)序列為XXX ,則其遍歷方式是? ? ?設(shè)N代表二叉樹的根，L代表根結(jié)點(diǎn)的左子樹，R代表根結(jié)點(diǎn)的右子樹。4 .平衡二叉樹定義：若一棵二叉樹中每個(gè)結(jié)點(diǎn)的左、右子樹的高度至多相差1,則稱此樹為平衡二叉樹。我們把二叉樹中每個(gè)結(jié)點(diǎn)的左子樹高度減去右子樹高度定義為該結(jié)點(diǎn)的平衡因子（balance factor）o因此，平衡樹中每個(gè)結(jié)

27、點(diǎn)的平衡因子只能是1、0或-1。5 .已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個(gè)葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù) 最多是? ? ?（111）二叉樹：二叉樹是一種重要的樹形結(jié)構(gòu)，它是 n （n>=0）個(gè)結(jié)點(diǎn)的有限集，其子樹分為互不相交的兩個(gè)集 合，分別稱為左子樹和右子樹，左子樹和右子樹也是如上定義的二叉樹。左子樹和右子樹的順序不能互換。滿二叉樹：深度為k結(jié)點(diǎn)數(shù)為2”-1的二叉樹。完全二叉樹：若對滿二叉樹的結(jié)點(diǎn)從上到下從左到右進(jìn)行編號,則深度為k且有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹的編號從 1到n 一一對應(yīng)時(shí)，稱為完全二叉樹。6 .將森林轉(zhuǎn)換為對應(yīng)的二叉樹 ，

28、若在 二叉樹 中,結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在 原來的森林中， u和v可能具有的關(guān)系是：父子關(guān)系或兄弟關(guān)系。森林轉(zhuǎn)換為對應(yīng)的二叉樹 ：兄弟之間連線，父只與長子連線。（左孩子右兄弟）7 .無向連通圖特性 的敘述:所有頂點(diǎn)的度 之和為 偶數(shù)。頂點(diǎn)的度 定義:與定點(diǎn)v相關(guān)聯(lián)的邊數(shù)（每個(gè)環(huán)計(jì)算兩次）。度為零的頂點(diǎn)稱為孤立頂點(diǎn)，度為奇數(shù)的頂點(diǎn)稱為奇點(diǎn)，度為偶數(shù)的頂點(diǎn)稱為偶點(diǎn)。8 .一棵 m階B樹（1970年，R.Bayer和E.mccreight提出了一種適用于 外杳找的樹,它是一種平衡多叉樹）定義：樹中每個(gè)結(jié)點(diǎn)至多有 m個(gè)孩子； 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有m/2個(gè)孩子；若根結(jié)點(diǎn)不

29、是葉子結(jié)點(diǎn)，則至少有2個(gè)孩子（除非B樹只有一個(gè)結(jié)點(diǎn)）；（4）所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層，葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息；有k個(gè)孩子的非終端結(jié)點(diǎn)恰好包含有k-1個(gè)關(guān)鍵字（各節(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列）.9 .堆（Heap）分為小根堆和大根堆兩種，對于一個(gè)小根堆，它是具有如下特性的一棵完全二叉樹：（1）若樹根結(jié)點(diǎn)存在左孩子，則根結(jié)點(diǎn)的值（或某個(gè)域的值）小于等于左孩子結(jié)點(diǎn)的值（或某個(gè)域的值）；（2）若樹根結(jié)點(diǎn)存在右孩子，則根結(jié)點(diǎn)的值（或某個(gè)域的值）小于等于右孩子結(jié)點(diǎn)的值（或某個(gè)域的值）；（3）以左、右孩子為根的子樹又各是一個(gè)堆。大根堆的定義與上述類似，只要把小于等于改為大于等于就得到了。由堆的定義可

30、知，若一棵完全二叉樹是堆，則該樹中以每個(gè)結(jié)點(diǎn)為根的子樹也都是一個(gè)堆。分別為一個(gè)小根堆和一個(gè)大根堆。根據(jù)堆的定義可知，堆頂結(jié)點(diǎn)，即整個(gè)完全二叉樹的根結(jié)點(diǎn)，對于小根堆來說具有最小值，對于大根堆來說具有最大值。堆排序利用了大根堆（或小根堆）堆頂記錄的關(guān)鍵字最大（或最?。┻@一特征，使得在當(dāng)前無序區(qū)中選取最大 （或最?。╆P(guān)鍵字的記錄變得簡單。當(dāng)向一個(gè)小根堆插入一個(gè)具有最小值的元素時(shí)，該元素需要逐層向上調(diào)整，直到被調(diào)整到堆頂位置為止。10 .數(shù)據(jù)元素序列11 ,12,13,7,8,9, 23,4,5是第二趟排序后的結(jié)果，則該排序算法只能是插入排序。氣泡排序基本思想：設(shè)待排序?qū)ο笮蛄兄械膶ο髠€(gè)數(shù)為n。一般地

31、，第i趟起泡排序從1到n-i+1依次比較相鄰兩個(gè)記錄地關(guān)鍵字，如果發(fā)生逆序，則交換之，其結(jié)果是這n-i+1個(gè)記錄中，關(guān)鍵字最大的記錄被交換到第n-i+1的位置上，最多作n-1趟。簡單選擇排序基本思想 ：第一趟在 R1.n中選最小的，與 R1交換第二趟在R2.n中選最小的，與 R2交換，依次類推，進(jìn)行n-1次選擇后，整個(gè)文件有序。直接插入排序基本思想將一個(gè)記錄插入到已排序的有序表中，使插入后的表仍然有序。折半插入排序基本思想 ：將一個(gè)記錄插入到已排序的有序表中，使插入后的表仍然有序，但插入時(shí)利用折半搜索法尋找元素的插入位置。歸并排序基本思想：又一類不同的排序方法，將兩個(gè)或兩個(gè)以上的有序表合并成一

32、個(gè)新的有序表。快速排序基本思想：取R1.n中任一記錄作為 樞軸”，一趟排序之后樞軸的值均小于樞軸”左邊的值，樞軸右邊的值均大于 樞軸”的值。堆排序基本思想：1 .如何將一個(gè)無序序列調(diào)整為堆？2 .如何在互換堆頂之后重新調(diào)整為堆（關(guān)鍵）？希爾排序 （Shell Sort） 基本思想 :1 .n大，劃分成若干子序列，分別直接插入排序。2 .待整個(gè)記錄 基本有序”時(shí)，對整體直接重排。11 .馮諾依曼計(jì)算機(jī)中 指令和數(shù)據(jù)均以二進(jìn)制形式存放在存儲(chǔ)器中,CPU區(qū)分它們的依據(jù)是 指令周期的不同階段。12 .十講制轉(zhuǎn)換：十進(jìn)制轉(zhuǎn)任意進(jìn)制的通用方法是：除x取余倒排法（x代表進(jìn)制數(shù)）。如：將十進(jìn)制數(shù)76轉(zhuǎn)換成任意

33、進(jìn)制1 .轉(zhuǎn)成二進(jìn)制76 / 2 . 0=38 / 2 . 0=19 / 2 . 1=9 / 2 . 1=4 / 2 . 0=2 / 2 . 0=1 / 2 . 176(10) = 1001100(2)2 .轉(zhuǎn)成八進(jìn)制76 / 8 . 4=9 / 8 . 1=1 / 8 . 176(10) = 114(8)3.轉(zhuǎn)成十六進(jìn)制76 / 16 . 12=4 / 16 . 476(10)=40(16)B :二進(jìn)制數(shù)。Q :八進(jìn)制數(shù)。D :十進(jìn)制數(shù)。H :十六進(jìn)制數(shù)。負(fù)數(shù)用十六進(jìn)制和八進(jìn)制怎么表示？使用補(bǔ)碼（二進(jìn)制），而且還要指定字長比如說一個(gè)二字節(jié)整型的-2就應(yīng)該是：11111111 11111110

34、再轉(zhuǎn)化其它進(jìn)制 十六進(jìn)制：FFFE八進(jìn)制：17777613 .浮點(diǎn)數(shù)加減運(yùn)算過程一般包括 對階、尾數(shù)運(yùn)算、規(guī)格化、舍入和判溢出 等步驟。設(shè)浮點(diǎn)數(shù)的 階碼和尾 婺均采用補(bǔ)碼表示,且位數(shù)分別為5位和7位(均含2位符號位)。若有兩個(gè)數(shù) X=2A7*29/32 , Y=2A5*5/8, 則用浮點(diǎn)加法計(jì)算 X+Y的最終結(jié)果是發(fā)生溢出浮點(diǎn)數(shù)表示:小數(shù)點(diǎn)的位置可以在一定范圍內(nèi)浮動(dòng)。E為階，包括階符和階碼(整數(shù))，階碼為數(shù)決定了浮點(diǎn)數(shù)的表示范圍。M為位數(shù)，包括數(shù)符和尾數(shù)，表示數(shù)的精度和正負(fù)。對階原則：小階對大階。雙符號位判溢：力口，減后。兩個(gè)符號位出現(xiàn)01”，表示已經(jīng) 遹近，即結(jié)果大于+1.14 .存儲(chǔ)器的分

35、類：1 .按存儲(chǔ)介子分：(1)半導(dǎo)體存儲(chǔ)器；(2)磁表面存儲(chǔ)器；(3)光介子存儲(chǔ)器。2 .按存取方式分類：(1)隨機(jī)存取存儲(chǔ)器 RAM ; (2)順序存儲(chǔ)器 SAM ; (3)直接存取存儲(chǔ)器 DAM。3 .按計(jì)算機(jī)功能分類：(1)主存儲(chǔ)器(主存)用于存放計(jì)算機(jī)運(yùn)行期間的大量程序和數(shù)據(jù)的存儲(chǔ)器，CPU能直接訪問。由 MOS存儲(chǔ)器構(gòu)成。(2)高速緩沖存儲(chǔ)器(Cache)Cache是介于CPU和主存之間高速小容量存儲(chǔ)器，用于存放最活躍的程序塊和數(shù)據(jù)。由靜態(tài)MOS存儲(chǔ)器構(gòu)成。特點(diǎn)：速度快，但容量小，位價(jià)格較高。主存和Cache一起構(gòu)成計(jì)算機(jī)的 內(nèi)存儲(chǔ)器(內(nèi)存)，是 CPU能直接訪問的存儲(chǔ)器 。(3)輔

36、助存儲(chǔ)器(外存儲(chǔ)器)存放當(dāng)前暫不參與運(yùn)行的程序和數(shù)據(jù)，需要時(shí)再與主存成批交換信息的存儲(chǔ)器。特點(diǎn)是容量大，可存放大量的程序和數(shù)據(jù)，但速度慢。(4)控制存儲(chǔ)器(CM )在微程序控制的計(jì)算機(jī)中，用于存放執(zhí)行指令的微程序的存儲(chǔ)器。CM 一般由ROM構(gòu)成，屬于控制器的一部分。4 .其它分類：a.按讀寫功能分類：(1)只讀存儲(chǔ)器(ROM):工作時(shí)只能讀出不能寫入的存儲(chǔ)器。(2)讀寫存儲(chǔ)器(RAM):既能讀出又能寫入的存儲(chǔ)器。b.按信息的可保存性分類(1)永久性存儲(chǔ)器：指斷電后仍能保存信息的存儲(chǔ)器，如磁表面存儲(chǔ)器。(2)非永久性存儲(chǔ)器：指斷電后信息即消失的存儲(chǔ)器，如半導(dǎo)體讀寫存儲(chǔ)器。某計(jì)算機(jī)的Cache共有

37、16塊，采用2路組相連映射方式(即每組2塊)。每個(gè)主存塊大小為 32字節(jié)，按字節(jié)編址。主存129號單元所在主存塊應(yīng)裝入到Cache組號是(4)15 .主存容量是根據(jù)地址線的位數(shù) 來確定的，在16位PC機(jī)中地址總線的寬度是 20位,則主存大小為:2A20 byte=1MB,現(xiàn)在的PC機(jī)一般都是32位地址總線的，最大直接尋址空間為：2八32,即主存最大容量為 4GB某計(jì)算機(jī)主存容量為 /KB,其中ROM區(qū)為4KB,其余為RAM區(qū)，按字節(jié)編址。現(xiàn)要用2K*8位的ROM 芯片和4K*4位的RAM芯片來設(shè)計(jì)該存儲(chǔ)器，則需要上述規(guī)格的 ROM芯片數(shù)和RAM芯片數(shù)分別是2 3016 .某計(jì)算機(jī)字長16位，主

38、存按字節(jié)編址，轉(zhuǎn)換指令采用相對尋址，由兩個(gè)字節(jié)組成，第一字節(jié)為操作碼字段，第二字節(jié)為相對位移量字段。假定取指令時(shí)，每取一字節(jié)PC自動(dòng)加1。若某轉(zhuǎn)移指令所在主存地址為2000H ,相對位移量字段的內(nèi)容為06H,則該轉(zhuǎn)移指令成功轉(zhuǎn)移后的目標(biāo)地址是(2008H)pc值相對FL：以當(dāng)前程序計(jì)數(shù)器 pc的內(nèi)容為基址，加上指令給出的一字節(jié)補(bǔ)碼數(shù)（偏移量）形成新的的尋址方式稱為相對尋址。目的地址=源地址+相對轉(zhuǎn)移指令字節(jié)數(shù) +指令中給定的偏移量（rel）.17 .RISC（精簡指令系統(tǒng)）的敘述:（1） .選用的是使用頻率很高的一些簡單指令；（2） .指令長度固定，指令格式及尋址方式種類少；（3） .只有取數(shù)

39、/存數(shù)指令訪問存儲(chǔ)器，其余指令的操作都在寄存器之間進(jìn)行；（4） .大多數(shù)指令可在一個(gè)計(jì)算機(jī)周期內(nèi)完成。18 .指令周期是取出并執(zhí)行一條指令的時(shí)間。指令周期常常有若干個(gè)CPU周期，CPU周期也稱為機(jī)器周期，由于CPU訪問一次內(nèi)存所花費(fèi)的時(shí)間較長，因此通常用內(nèi)存中讀取一個(gè)指令字的最短時(shí)間來規(guī)定CPU周期。這就是說一條指令取出階段（通常為取指）需要一個(gè) CPU周期時(shí)間。而一個(gè) CPU周期時(shí)間又包含若干個(gè)時(shí)鐘周期（通常為節(jié)拍脈沖或T周期，它是處理操作的最基本的單位）。這些時(shí)鐘周期的總和則規(guī)定了一個(gè)CPU周期的時(shí)間寬度。某計(jì)算機(jī)的指令流水線由四個(gè)功能段組成，指令流經(jīng)各功能段的時(shí)間（忽略各功能段之間的緩沖

40、時(shí)間）分別是90ns、80ns、70ns、60ns,則計(jì)算機(jī)的 CPU時(shí)鐘周期是（90ns）。19 .相對于 微程序控制器，硬布線控制器的特點(diǎn)是指令執(zhí)行速度快，指令功能的修改和擴(kuò)展難。20 .假設(shè)某系統(tǒng)總線在一個(gè)總線周期中并行傳輸4字節(jié)信息，一個(gè)總線周期占用2個(gè)時(shí)鐘周期，總線時(shí)鐘頻率為10MHz ,則總線帶寬 是（20MB/S）時(shí)鐘周期和時(shí)鐘頻率互為倒數(shù)關(guān)系。1KHz=1000Hz ;1MHz=1000KHz并行總線帶寬（MB/s）=并行總線時(shí)鐘頻率（MHz） * 并行總線位寬（bit/8 = B） * 每時(shí)鐘傳輸幾組數(shù)據(jù) （cycle）串行總線帶寬（MB/s）=串行總線時(shí)鐘頻率（MHz） *

41、串行總線位寬（bit/8 = B） *串行總線管線*編碼方式*每時(shí)鐘傳輸幾組數(shù)據(jù) （cycle）1 字節(jié)（Byte） = 8 位（bit）21 .假設(shè)某計(jì)算機(jī)的存儲(chǔ)系統(tǒng)由Cache和主存組成，某程序執(zhí)行過程中訪存1000次，其中訪問Cache缺失（未命中）50次，則 Cache的命中率 是（95%）22 .能引起外部中斷的事件 是:鍵盤入（人的干預(yù)）或外請求。（外中斷都是強(qiáng)迫中斷）23 .單處理機(jī)系統(tǒng) 中,可并行的是（II、III和IV ）I進(jìn)程與進(jìn)程II處理機(jī)與設(shè)備III處理機(jī)與通道IV設(shè)備與設(shè)備24 .進(jìn)程調(diào)度算法中，綜合考慮進(jìn)程等待時(shí)間和執(zhí)法世間是：（高響應(yīng)比優(yōu)先調(diào)度算法 ）.FCFS:

42、誰先到就緒隊(duì)列，將處理機(jī)分給誰；時(shí)間片輪轉(zhuǎn)調(diào)度法：以先來后到的次序+時(shí)間片輪轉(zhuǎn)；優(yōu)先級調(diào)度：選優(yōu)先級最高的進(jìn)程占用處理機(jī)（優(yōu)先級可動(dòng)態(tài)改變）;短進(jìn)程優(yōu)先：取所需的運(yùn)行時(shí)間最短的進(jìn)程（該算法能使平均等待時(shí)間最短）.25 .某計(jì)算機(jī)系統(tǒng)有 8臺(tái)打印機(jī)，有 K個(gè)進(jìn)程競爭使用，每個(gè)進(jìn)程最多需要3臺(tái)打印機(jī)。該 系統(tǒng)可能會(huì)發(fā)生死鎖的K的最小值是（4）26 .分區(qū)分配內(nèi)存管理方式的上要保護(hù)措施是（界地址保護(hù)）27 .一個(gè)分段存儲(chǔ)管理 系統(tǒng)中,地址長度為 32位，其中段號占8位，則最大段長是（2人24）.分頁與分段的區(qū)別：分頁:信息的物理單位大小一樣，由系統(tǒng)固定地址空間是一維的分段:信息的邏輯單位大小不等，由

43、用戶確定地址空間是二維的28 .文件物理結(jié)構(gòu)中,適合隨機(jī)訪問且易于文件擴(kuò)展 的是（索引結(jié)構(gòu)）.連續(xù)Z構(gòu)：將一個(gè)文件中邏輯上連續(xù)的信息存放到存儲(chǔ)介質(zhì)的依次相鄰的塊上便形成順序結(jié)構(gòu)，這類文件 叫連續(xù)文件，又稱順序文件。優(yōu)點(diǎn)：簡單；支持順序存取和隨機(jī)存??；順序存取速度快；所需的磁盤尋道次數(shù)和尋道時(shí)間最少缺點(diǎn)：建立文件前需要能預(yù)先確定文件長度，以便分配存儲(chǔ)空間；修改、插入和增生文件記錄有困難；對直接存儲(chǔ)器作連續(xù)分配，會(huì)造成少量空閑塊的浪費(fèi)。鏈接結(jié)構(gòu)：一個(gè)文件的信息存放在若干不連續(xù)的物理塊中，各塊之間通過指針連接，前一個(gè)物理塊指向下一個(gè)物理塊。優(yōu)點(diǎn)：提高了磁盤空間利用率 ，不存在外部碎片問題；有利于文件

44、插入和刪除；有利于文件動(dòng)態(tài)擴(kuò)充.缺點(diǎn)：存取速度慢，不適于隨機(jī)存取；可靠性問題，如指針出錯(cuò)；更多的尋道次數(shù)和尋道時(shí)間；鏈接指針 占用一定的空間.索引結(jié)構(gòu)：一個(gè)文件的信息存放在若干不連續(xù)物理塊中，系統(tǒng)為每個(gè)文件建立一個(gè)專用數(shù)據(jù)結(jié)構(gòu)-索引表。表中每一欄目指出文件信息所在的邏輯塊號和與之對應(yīng)的物理塊號。索引表的物理地址則由文件說明信息項(xiàng)給出。優(yōu)點(diǎn)：保持了鏈接結(jié)構(gòu)的優(yōu)點(diǎn) ，又解決了其缺點(diǎn)；即能順序存取 ，又能隨機(jī)存取；滿足了文件動(dòng)態(tài)增長、插 入刪除的要求；也能充分利用外存空間。缺點(diǎn)：較多的尋道次數(shù)和尋道時(shí)間；索引表本身帶來了系統(tǒng)開銷如：內(nèi)外存空間，存取時(shí)間。29.SCAN調(diào)度 仲梯調(diào)度）算法:電梯調(diào)度算

45、法基于日常生活中的電梯工作模式：電梯保持按一個(gè)方向移動(dòng)，直到在那個(gè)方向上沒有請求為止，然后改變方向。反映在磁盤調(diào)度上，總是沿著移動(dòng)臂的移動(dòng)方向選擇距離磁頭當(dāng)前位置最近的 I/O請求作為下一次調(diào)度的對象。如果該方向上已無I/O請求，則改變方向再做選擇。35, 45,假設(shè)磁頭當(dāng)前位于第 105道，正在向磁道序號增加的方向移動(dòng)?，F(xiàn)在一個(gè)磁道訪問請求序列為12, 68, 110, 180, 170, 195,采用SCAN調(diào)度（電梯調(diào)度）算法得到的磁道訪問序列是：110,170,180,195,68,45,35,12。30 .文件系統(tǒng)中，文件訪問控制信息存儲(chǔ)的合理位置是（文件控制塊）。31 .硬鏈接：在

46、磁盤上有一份內(nèi)容一樣的文件產(chǎn)生，但不改變文件的Inode,也就是與原文件共用Inode。軟鏈接：不在磁盤上有一份內(nèi)容一樣的文件產(chǎn)生，但產(chǎn)生新的Inode o設(shè)文件F1的當(dāng)前引用計(jì)數(shù)值為 1,先建立F1的符號鏈接（軟鏈接）文件 F2,再建立F1的硬鏈接文件F3,然后刪除F1。此時(shí)，F(xiàn)2和F3的引用計(jì)數(shù)值分別是（1, 1）。32 .程序員利用系統(tǒng)調(diào)用打開I/O設(shè)備時(shí)，通常使用的 設(shè)備標(biāo)識(shí)是（邏輯設(shè)備名）。33 .在OSI參考模型中，自下而上第一個(gè)提供端到端服務(wù)的層次是（傳輸層）。自下而上方法的一般從檢查物理層開始。自下而上分別稱為：物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層、會(huì)話層、表示層和應(yīng)用層。傳輸層

47、是兩臺(tái)計(jì)算機(jī)經(jīng)過網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)通信時(shí)，第一個(gè)端到端的層次，具有緩沖作用。34 .1924年奈奎斯特（Nyquist）就推導(dǎo)出在理想低通信道的最高大碼元傳輸速率的公式：理想低通信道的最高大碼元傳輸速率C=2W.log2 N （其中W是想低通信道的帶寬,N是電平強(qiáng)度）信道帶寬與數(shù)據(jù)傳輸速率白關(guān)系可以奈奎斯特（Nyquist）準(zhǔn)則與香農(nóng)（Shanon）定律描述。奈奎斯特定理描述了有限帶寬、無噪聲信道的最大數(shù)據(jù)傳輸速率與信道帶寬的關(guān)系。香農(nóng)定理則描述了有限帶寬、有隨機(jī)熱噪聲信道的最大傳輸速率與信道帶寬、信噪比之間的關(guān)系。奈奎斯特準(zhǔn)則指出:對于二進(jìn)制數(shù)據(jù)信號的最大數(shù)據(jù)傳輸速率Rmax與通信信道帶寬 B （

48、 B=f,單位Hz）的關(guān)系可以寫為：Rmax = 2*B（bps）香農(nóng)定理指出：在有隨機(jī)熱噪聲的信道上傳輸數(shù)據(jù)信號時(shí)，數(shù)據(jù)傳輸速率Rmax與信道帶寬B、信噪比S/N的關(guān)系為：Rmax = B*log2（1+S/N）以 2 為底,1+S/N 的對數(shù)式中，Rmax單位為bps,帶寬B單位為Hz,信噪比S/N通常以dB （分貝）數(shù)表示。若 S/N=30（dB）,那么信噪比根據(jù)公式： S/N（dB）=10*lg（S/N）貝U S/N=1000。若帶寬 B=3000Hz ,貝U Rmax 30kbps o（1）對于帶寬為6MHz的信道，若用4種不同的狀態(tài)來表示數(shù)據(jù)，在不考慮熱噪聲的情況下，該信道的最大數(shù)

49、據(jù)傳輸速率是多少？答：由無熱噪聲的奈奎斯特公式：C=2Hlog2N=2*6M*log24=24Mbps ,即該信道的最大數(shù)據(jù)傳輸速率是24Mbps（2）在無噪聲情況下,若某通信鏈路的帶寬為3KHz,采用4個(gè)相位，每個(gè)相位具有 4種振幅的QAM調(diào)制技術(shù)，則該通信鏈路的最大數(shù)據(jù)傳輸速率是（24kbps）C=2Hlog2N =2*3k*log216=24kbps.35 .后退N幀ARQ就是從出錯(cuò)處重發(fā)已發(fā)出過的 N個(gè)幀。數(shù)據(jù)鏈路層采用了后退 N幀（GBN）協(xié)議，發(fā)送方已經(jīng)發(fā)送了編號為07的幀。當(dāng)計(jì)時(shí)器超時(shí)時(shí)，若發(fā)送方只收到0、2、3號幀的確認(rèn)，則發(fā)送方需要重發(fā)的幀數(shù)是（4）。36 .以太網(wǎng)交換機(jī)進(jìn)行

50、轉(zhuǎn)發(fā)決策時(shí)使用的PDU地址是（目的物理地址）。ARP協(xié)議是"Address Resolution Protocol （地址解析協(xié)議）的縮寫。在局域網(wǎng)中，網(wǎng)絡(luò)中實(shí)際傳輸?shù)氖菐?，幀里面是有目?biāo)主機(jī)的MAC地址的。在以太網(wǎng)中，一個(gè)主機(jī)要和另一個(gè)主機(jī)進(jìn)行直接通信，必須要知道目標(biāo)主機(jī)的 MAC地址。但這個(gè)目標(biāo) MAC地址是如何獲得的呢？它就是通過地址解析協(xié)議獲得的。所謂 地址解析”就是主機(jī)在發(fā)送幀前將目標(biāo)IP地址轉(zhuǎn)換成目標(biāo) MAC地址的過程。ARP協(xié)議的基本功能就是通過目標(biāo)設(shè)備的IP地址，查詢目標(biāo)設(shè)備的 MAC地址，以保證通信的順利進(jìn)行。37 .CSMA/CD是一種分布式介質(zhì)訪問控制協(xié)議，網(wǎng)

51、中的各個(gè)站（節(jié)點(diǎn)）都能獨(dú)立地決定數(shù)據(jù)幀的發(fā)送與接收。每個(gè)站在發(fā)送數(shù)據(jù)幀之前，首先要進(jìn)行載波監(jiān)聽，只有介質(zhì)空閑時(shí)，才允許發(fā)送幀。這時(shí)，如果兩個(gè)以上的站同時(shí)監(jiān)聽到介質(zhì)空閑并發(fā)送幀，則會(huì)產(chǎn)生沖突現(xiàn)象，這使發(fā)送的幀都成為無效幀，發(fā)送隨即宣告失敗。每個(gè)站必須有能力隨時(shí)檢測沖突是否發(fā)生，一旦發(fā)生沖突，則應(yīng)停止發(fā)送，以免介質(zhì)帶寬因傳送無效幀而被白白浪費(fèi)， 然后隨機(jī)延時(shí)一段時(shí)間后，再重新爭用介質(zhì)， 重發(fā)送幀。CSMA/CD協(xié)議簡單、可靠,其網(wǎng)絡(luò)系統(tǒng)（如 Ethernet）被廣泛使用。在一個(gè)采用CSMA/CD協(xié)議的網(wǎng)絡(luò)中，傳輸介質(zhì)是一根完整的電纜，傳輸速率為1Gbps,電纜中的信號傳播速度是200 000km/

52、s。若最小數(shù)據(jù)幀長度減少 800比特，則最遠(yuǎn)的兩個(gè)站點(diǎn)之間的距離至少需要（減少80）。最短幀長=2*L*10A9（b/s） +200 000000m/s=10*L（bit）.38 .主機(jī)甲和主機(jī)乙之間建立一個(gè)TCP連接,主機(jī)甲向主機(jī)乙發(fā)送了兩個(gè)連續(xù)的TCP段,分別含300字節(jié)和500字節(jié)的有效載荷，第一個(gè)段的序列號為 200,主機(jī)乙正確接收到兩個(gè)段后，發(fā)送給主機(jī)甲的確認(rèn)序列號是（1000）。例如，序列號等于前一個(gè)報(bào)文段的序列號與前一個(gè)報(bào)文段中數(shù)據(jù)字節(jié)的數(shù)量之和。例如，假設(shè)源主機(jī)發(fā)送3個(gè)報(bào)文段.每個(gè)報(bào)文段有 100字節(jié)的數(shù)據(jù).且第一個(gè)報(bào)文段的序列號是1000.那么接收到第一個(gè)報(bào)文段后，目的主機(jī)返

53、回含確認(rèn)號 1100的報(bào)頭。接收到第二個(gè)報(bào)文段（其序號為1100）后，目的主機(jī)返回確認(rèn)號1200。接收到第三個(gè)報(bào)文段后，目的主機(jī)返回確認(rèn)號 1300。39 .確定擁塞窗口的大小的過程：在剛建立連接時(shí)，將擁塞窗口的大小初始化為該連接所需的最大連接數(shù) 據(jù)段的長度值，并發(fā)送一個(gè)最大長度的數(shù)據(jù)段(當(dāng)然必須是接收窗口允許的)。如果在定時(shí)器超時(shí)前得到 確認(rèn)，將擁塞窗口的大小增加一個(gè)數(shù)據(jù)段的字節(jié)數(shù)，并發(fā)送兩個(gè)數(shù)據(jù)段，如果每個(gè)數(shù)據(jù)段在定時(shí)器超時(shí)前都得到確認(rèn)，就再在原基礎(chǔ)上增加一倍，即為4個(gè)數(shù)據(jù)段的大小，如此反復(fù)，每次都在前一次的基礎(chǔ)上加倍。當(dāng)定時(shí)器超時(shí)或達(dá)到發(fā)送窗口設(shè)定值，停止擁塞窗口尺寸的增加。這種反復(fù)稱為

54、慢速啟動(dòng)，所有的TCP協(xié)議都支持這種方法。一個(gè)TCP連接總是以1KB的最大段發(fā)送 TCP段，發(fā)送方有足夠多的數(shù)據(jù)要發(fā)送。當(dāng)擁塞窗口為16KB時(shí)發(fā)生了超時(shí)，如果接下來的4個(gè)RTT (往返時(shí)間)時(shí)間內(nèi)的 TCP段的傳輸都是成功的，那么當(dāng)?shù)?個(gè)RTT時(shí)間內(nèi)發(fā)送的所有 TCP段都得到肯定應(yīng)答時(shí)，擁塞窗口大小是(9KB)。40 .FTP客戶和服務(wù)器間傳遞 FTP時(shí)，使用的連接是(建立在TCP之上的控制連接)。綜合應(yīng)用題41 .該方法求得的路徑不一定是最短路徑。例如，對于下圖所示的帶權(quán)圖，如果按照題中的原則，從A到C的最短路徑為 A B-C,事實(shí)上其最短路徑為 A- D-C。從4到C的能短格行力A-BtC

55、事實(shí)上其量燉路較為(a)-(S')210(p)(c)42. (1)算法基本思想如下：從頭至尾遍歷單鏈表，并用指針P指向當(dāng)前節(jié)點(diǎn)的前 K個(gè)節(jié)點(diǎn)。當(dāng)遍歷到鏈表的最后一個(gè)節(jié)點(diǎn)時(shí)，指針P所指向的節(jié)點(diǎn)即為所查找的節(jié)點(diǎn)。(2)詳細(xì)實(shí)現(xiàn)步驟：增加兩個(gè)指針變量和一個(gè)整型變量，從鏈表頭向后遍歷，其中指針P1指向當(dāng)前遍歷的節(jié)點(diǎn)，指針 P指向P1所指向節(jié)點(diǎn)的前 K個(gè)節(jié)點(diǎn)，如果P1之前沒有K個(gè)節(jié)點(diǎn)，那么P指向表頭 節(jié)點(diǎn)。用整型變量i表示當(dāng)前遍歷了多少節(jié)點(diǎn)，當(dāng) i>k時(shí)，指針p隨著每次遍歷，也向前移動(dòng)一個(gè)節(jié) 點(diǎn)。當(dāng)遍歷完成時(shí)，p或者指向表頭就節(jié)點(diǎn)，或者指向鏈表中倒數(shù)第K個(gè)位置上的節(jié)點(diǎn)。(3)算法描述：Int LocateElement(linklist list,int k) P1=list->link;P=list;i=1;while(P1) P1=P1->link;i+；if(