2009年統考計算機考研真題一．單項選擇題，每小題2分，共80分。二．綜合應用題。共70分。2009年計算機統考真題參考答案一．選擇題二．綜合應用題2010年全國研究生考試計算機統考試題及答案242009年統考計算機考研真題一．單項選擇題，每小題2分，共80分。1.為解決計算機與打印機之間速度不匹配的問題，通常設置一個打印數據緩沖區，主機將要輸出的數據依次寫入該緩沖區，而打印機則依次從該緩沖區中取出數據。該緩沖區的邏輯結構應該是A.棧B.隊列C.樹D.圖2.設棧S和隊列Q的初始狀態均為空，元素abcdefg依次進入棧S。若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是bdcfeag，則棧S的容量至少是A．1B.2C.3D.43.給定二叉樹圖所示。設N代表二叉樹的根，L代表根結點的左子樹，R代表根結點的右子樹。若遍歷后的結點序列為3，1，7，5，6，2，4，則其遍歷方式是A．LRNB.NRLC.RLND.RNL4.下列二叉排序樹中，滿足平衡二叉樹定義的是5.已知一棵完全二叉樹的第6層（設根為第1層）有8個葉結點，則完全二叉樹的結點個數最多是A．39B.52C.111D.1196.將森林轉換為對應的二叉樹，若在二叉樹中，結點u是結點v的父結點的父結點，則在原來的森林中，u和v可能具有的關系是I．父子關系II.兄弟關系III.u的父結點與v的父結點是兄弟關系A.只有IIB.I和IIC.I和IIID.I、II和III7.下列關于無向連通圖特性的敘述中，正確的是I．所有頂點的度之和為偶數II.邊數大于頂點個數減1III.至少有一個頂點的度為1A.只有IB.只有IIC.I和IID.I和III8.下列敘述中，不符合m階B樹定義要求的是A．根節點最多有m棵子樹B.所有葉結點都在同一層上C．各結點內關鍵字均升序或降序排列D.葉結點之間通過指針鏈接9.已知關鍵序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關鍵字3，調整后得到的小根堆是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.若數據元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的結果，則該排序算法只能是A．起泡排序B.插入排序C.選擇排序D.二路歸并排序11.馮·諾依曼計算機中指令和數據均以二進制形式存放在存儲器中，CPU區分它們的依據是A．指令操作碼的譯碼結果B.指令和數據的尋址方式C.指令周期的不同階段D.指令和數據所在的存儲單元12.一個C語言程序在一臺32位機器上運行。程序中定義了三個變量xyz，其中x和z是int型，y為short型。當x=127，y=-9時，執行賦值語句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.浮點數加減運算過程一般包括對階、尾數運算、規格化、舍入和判溢出等步驟。設浮點數的階碼和尾數均采用補碼表示，且位數分別為5位和7位（均含2位符號位）。若有兩個數X=27×29/32，Y=25×5/8，則用浮點加法計算X+Y的最終結果是A．001111100010B.001110100010C．010000010001D.發生溢出14.某計算機的Cache共有16塊，采用2路組相聯映射方式（即每組2塊）。每個主存塊大小為32字節，按字節編址。主存129號單元所在主存塊應裝入到的Cache組號是A．0B.2C.4D.615.某計算機主存容量為64KB，其中ROM區為4KB，其余為RAM區，按字節編址。現要用2K×8位的ROM芯片和4K×4位的RAM芯片來設計該存儲器，則需要上述規格的ROM芯片數和RAM芯片數分別是A．1、15B．2、15C．1、30D．2、3016.某機器字長16位，主存按字節編址，轉移指令采用相對尋址，由兩個字節組成，第一字節為操作碼字段，第二字節為相對位移量字段。假定取指令時，每取一個字節PC自動加1。若某轉移指令所在主存地址為2000H，相對位移量字段的內容為06H，則該轉移指令成功轉以后的目標地址是A.2006HB.2007HC.2008HD.2009H17.下列關于RISC的敘述中，錯誤的是A．RISC普遍采用微程序控制器B．RISC大多數指令在一個時鐘周期內完成C．RISC的內部通用寄存器數量相對CISC多D．RISC的指令數、尋址方式和指令格式種類相對CISC少18.某計算機的指令流水線由四個功能段組成，指令流經各功能段的時間（忽略各功能段之間的緩存時間）分別是90ns、80ns、70ns和60ns，則該計算機的CPU時鐘周期至少是A．90nsB.80nsC.70nsD.60ns19.相對于微程序控制器，硬布線控制器的特點是A．指令執行速度慢，指令功能的修改和擴展容易B．指令執行速度慢，指令功能的修改和擴展難C．指令執行速度快，指令功能的修改和擴展容易D．指令執行速度快，指令功能的修改和擴展難20.假設某系統總線在一個總線周期中并行傳輸4字節信息，一個總線周期占用2個時鐘周期，總線時鐘頻率為10MHz，則總線帶寬是A．10MB/sB.20MB/SC.40MB/SD.80MB/S21.假設某計算機的存儲系統由Cache和主存組成，某程序執行過程中訪存1000次，其中訪問Cache缺失（未命中）50次，則Cache的命中率是A．5%B.9.5%C.50%D.95%22.下列選項中，能引起外部中斷的事件是A．鍵盤輸入B.除數為0C.浮點運算下溢D.訪存缺頁23.單處理機系統中，可并行的是I進程與進程II處理機與設備III處理機與通道IV設備與設備A．I、II和IIIB.I、II和IVC.I、III和IVD.II、III和IV24.下列進程調度算法中，綜合考慮進程等待時間和執行時間的是A．時間片輪轉調度算法B.短進程優先調度算法C.先來先服務調度算法D.高響應比優先調度算法25.某計算機系統中有8臺打印機，有K個進程競爭使用，每個進程最多需要3臺打印機。該系統可能會發生死鎖的K的最小值是（）不死鎖需要2K+1<8，最多支持3個進程并發。注意問的如果是“不會發生死鎖的最大值”就選B。4個以上就死鎖，所以會死鎖的最小值是4。別看錯了。A．2B.3C.4D.526．分區分配內存管理方式的主要保護措施是A．界地址保護B.程序代碼保護C.數據保護D.棧保護27.一個分段存儲管理系統中，地址長度為32位，其中段號占8位，則段長最大A．2的8次方字節B.2的16次方字節C.2的24次方字節D.2的32次方字節28.下列文件物理結構中，適合隨機訪問且易于文件擴展的是A．連續結構B.索引結構C.鏈式結構且磁盤塊定長D.鏈式結構且磁盤塊變長29.假設磁頭當前位于第105道，正在向磁道序號增加的方向移動。現有一個磁道訪問請求序列為35，45，12，68，110，180，170，195，采用SCAN調度（電梯調度）算法得到的磁道訪問序列是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.文件系統中，文件訪問控制信息存儲的合理位置是A．文件控制塊B.文件分配表C.用戶口令表D.系統注冊表31．設文件F1的當前引用計數值為1，先建立F1的符號鏈接（軟鏈接）文件F2，再建立F1的硬鏈接文件F3，然后刪除F1。此時，F2和F3的引用計數值分別是A．0、1B.1、1C.1、2D.2、132．程序員利用系統調用打開I/O設備時，通常使用的設備標識是A．邏輯設備名B.物理設備名C.主設備號D.從設備號33.在OSI參考模型中，自下而上第一個提供端到端服務的層次是A．數據鏈路層B.傳輸層C.會話層D.應用層34．在無噪聲情況下，若某通信鏈路的帶寬為3kHz，采用4個相位，每個相位具有4種振幅的QAM調制技術，則該通信鏈路的最大數據傳輸速率是A．12kbpsB.24kbpsC.48kbpsD.96kbps35.數據鏈路層采用了后退N幀（GBN）協議，發送方已經發送了編號為0~7的幀。當計時器超時時，若發送方只收到0、2、3號幀的確認，則發送方需要重發的幀數是A．2B.3C.4D.536.以太網交換機進行轉發決策時使用的PDU地址是A．目的物理地址B.目的IP地址C.源物理地址D.源IP地址37.在一個采用CSMA/CD協議的網絡中，傳輸介質是一根完整的電纜，傳輸速率為1Gbps，電纜中的信號傳播速度是200000km/s。若最小數據幀長度減少800比特，則最遠的兩個站點之間的距離至少需要A．增加160mB.增加80mC.減少160mD.減少80m38.主機甲和主機乙間已建立一個TCP連接，主機甲向主機乙發送了兩個連續的TCP段，分別包含300字節和500字節的有效載荷，第一個段的序列號為200，主機乙正確接收到兩個段后，發送給主機甲的確認序列號是A．500B.700C.800D.100039．一個TCP連接總是以1KB的最大段發送TCP段，發送方有足夠多的數據要發送。當擁塞窗口為16KB時發生了超時，如果接下來的4個RTT（往返時間）時間內的TCP段的傳輸都是成功的，那么當第4個RTT時間內發送的所有TCP段都得到肯定應答時，擁塞窗口大小是A．7KBB.8KBC.9KBD.16KB40.FTP客戶和服務器間傳遞FTP命令時，使用的連接是A．建立在TCP之上的控制連接B.建立在TCP之上的數據連接C.建立在UDP之上的控制連接D.建立在UDP之上的數據連接二．綜合應用題。共70分。41.（10分）帶權圖（權值非負，表示邊連接的兩頂點間的距離）的最短路徑問題是找出從初始頂點到目標頂點之間的一條最短路徑。假定從初始頂點到目標頂點之間存在路徑，現有一種解決該問題的方法：①設最短路徑初始時僅包含初始頂點，令當前頂點u為初始頂點；②選擇離u最近且尚未在最短路徑中的一個頂點v，加入到最短路徑中，修改當前頂點u=v；③重復步驟②，直到u是目標頂點時為止。請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則，請舉例說明。42.（15分）已知一個帶有表頭結點的單鏈表，結點結構為datalink假設該鏈表只給出了頭指針list。在不改變鏈表的前提下，請設計一個盡可能高效的算法，查找鏈表中倒數第k個位置上的結點（k為正整數）。若查找成功，算法輸出該結點的data值，并返回1；否則，只返回0。要求：（1）描述算法的基本設計思想（2）描述算法的詳細實現步驟（3）根據設計思想和實現步驟，采用程序設計語言描述算法（使用C或C++或JAVA語言實現），關鍵之處請給出簡要注釋。43.（8分）某計算機的CPU主頻為500MHz，CPI為5（即執行每條指令平均需5個時鐘周期）。假定某外設的數據傳輸率為0.5MB/s，采用中斷方式與主機進行數據傳送，以32位為傳輸單位，對應的中斷服務程序包含18條指令，中斷服務的其他開銷相當于2條指令的執行時間。請回答下列問題，要求給出計算過程。（1）在中斷方式下，CPU用于該外設I/O的時間占整個CPU時間的百分比是多少？（2）當該外設的數據傳輸率達到5MB/s時，改用DMA方式傳送數據。假設每次DMA傳送大小為5000B，且DMA預處理和后處理的總開銷為500個時鐘周期，則CPU用于該外設I/O的時間占整個CPU時間的百分比是多少？（假設DMA與CPU之間沒有訪存沖突）44.（13分）某計算機字長16位，采用16位定長指令字結構，部分數據通路結構如圖所示。圖中所有控制信號為1時表示有效、為0時表示無效。例如控制信號MDRinE為1表示允許數據從DB打入MDR，MDRin為1表示允許數據從內總線打入MDR。假設MAR的輸出一直處于使能狀態。加法指令“ADD（R1），R0”的功能為（R0）+（（R1））→（R1），即將R0中的數據與R1的內容所指主存單元的數據相加，并將結果送入R1的內容所指主存單元中保存。數據通路結構下表給出了上述指令取值和譯碼階段每個節拍（時鐘周期）的功能和有效控制信號，請按表中描述方式用表格列出指令執行階段每個節拍的功能和有效控制信號。功能和控制信號時鐘C1C2功能有效控制信號PCout,MARinMemR,MDRinEPC+1MDRout,IRin無MAR←(PC)MDR←M(MAR)PC←(PC)+1IR←(MDR)C3C4指令譯碼45.（7分）三個進程P1、P2、P3互斥使用一個包含N（N>0）個單元的緩沖區。P1每次用produce（）生成一個正整數并用put（）送入緩沖區某一空單元中；P2每次用getodd（）從該緩沖區中取出一個奇數并用countodd（）統計奇數個數；P3每次用geteven（）從該緩沖區中取出一個偶數并用counteven（）統計偶數個數。請用信號量機制實現這三個進程的同步與互斥活動，并說明所定義的信號量的含義。要求用偽代碼描述。46.（8分）請求分頁管理系統中，假設某進程的頁表內容如下表所示。頁號頁框號有效位（存在位）012101H--254H101頁面大小為4KB，一次內存的訪問時間是100ns，一次快表（TLB）的訪問時間是10ns，處理一次缺頁的平均時間為108ns（已含更新TLB和頁表的時間），進程的駐留集大小固定為2，采用最近最少使用置換算法（LRU）和局部淘汰策略。假設TLB初始為空；②地址轉換時先訪問TLB，若TLB未命中，再訪問頁表（忽略訪問頁表之后的TLB更新時間）；③有效位為0表示頁面不在內存，產生缺頁中斷，缺頁中斷處理后，返回到產生缺頁中斷的指令處重新執行。設有虛地址訪問序列2362H、1565H、25A5H，請問：（1）依次訪問上述三個虛地址，各需多少時間？給出計算過程。（2）基于上述訪問序列，虛地址1565H的物理地址是多少？請說明理由。47．（9分）某公司網絡拓撲圖如下圖所示，路由器R1通過接口E1、E2分別連接局域網1、局域網2，通過接口L0連接路由器R2，并通過路由器R2連接域名服務器與互聯網。R1的L0接口的IP地址是；R2的L0接口的IP地址是，L1接口的IP地址是，E0接口的IP地址是；域名服務器的IP地址是。將IP地址空間/24劃分為兩個子網，分配給局域網1、局域網2，每個局域網分配的地址數不少于120個，請給出子網劃分結果。說明理由或給出必要的計算過程。請給出R1的路由表，使其明確包括到局域網1的路由、局域網2的路由、域名服務器的主機路由和互聯網的路由。請采用路由聚合技術，給出R2到局域網1和局域網2的路由。2009年計算機統考真題參考答案一．選擇題12345678910BCDBCBADAB11121314151617181920CDDCDCAADB21222324252627282930DADDCACBAA31323334353637383940BABBCADDCA1.為解決計算機與打印機之間速度不匹配的問題,通常設置一個打印數據緩沖區，該緩沖區的邏輯結構應該是（隊列）棧的定義:棧是只準在表尾進行插入和刪除的線性表，稱為LIOFO（即后進先出表）。允許插入和刪除的一端叫棧頂，另一端叫棧底。隊列的定義：隊列是允許在一端進行插入而在另一端進行刪除的線性表。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。隊列也稱為先進先出表（FIFO）樹的定義：樹是包含n個結點的有限集合（n>0）圖的定義：圖（Graph）是由非空的頂點集合和一個描述頂點之間關系——邊（或者弧）的集合組成。其形式化定義為：G=(V,E）其中G表一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。2.設棧S和隊列Q的初始狀態均為空,元素abcdefg依次進入棧S。若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是bdcfeag,則棧S的容量？？？（3）3.給定二叉樹圖，若遍歷后的結點序列為XXX，則其遍歷方式是？？？設N代表二叉樹的根，L代表根結點的左子樹，R代表根結點的右子樹。4.平衡二叉樹定義:若一棵二叉樹中每個結點的左、右子樹的高度至多相差1，則稱此樹為平衡二叉樹。我們把二叉樹中每個結點的左子樹高度減去右子樹高度定義為該結點的平衡因子(balancefactor)。因此，平衡樹中每個結點的平衡因子只能是1、0或-1。5.已知一棵完全二叉樹的第6層（設根為第1層）有8個葉結點，則完全二叉樹的結點個數最多是？？？（111）二叉樹：二叉樹是一種重要的樹形結構，它是n（n>=0）個結點的有限集，其子樹分為互不相交的兩個集合，分別稱為左子樹和右子樹，左子樹和右子樹也是如上定義的二叉樹。左子樹和右子樹的順序不能互換。滿二叉樹：深度為k結點數為2^k-1的二叉樹。完全二叉樹：若對滿二叉樹的結點從上到下從左到右進行編號，則深度為k且有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹的編號從1到n一一對應時，稱為完全二叉樹。6.將森林轉換為對應的二叉樹，若在二叉樹中，結點u是結點v的父結點的父結點，則在原來的森林中，u和v可能具有的關系是:父子關系或兄弟關系。森林轉換為對應的二叉樹:兄弟之間連線，父只與長子連線。（左孩子右兄弟）7.無向連通圖特性的敘述:所有頂點的度之和為偶數。頂點的度定義：與定點v相關聯的邊數(每個環計算兩次)。度為零的頂點稱為孤立頂點，度為奇數的頂點稱為奇點，度為偶數的頂點稱為偶點。8.一棵m階B樹（1970年，R.Bayer和E.mccreight提出了一種適用于外查找的樹，它是一種平衡多叉樹）定義：樹中每個結點至多有m個孩子；除根結點和葉子結點外，其它每個結點至少有m/2個孩子；若根結點不是葉子結點，則至少有2個孩子(除非B樹只有一個結點)；所有葉子結點都出現在同一層，葉子結點不包含任何關鍵字信息；有k個孩子的非終端結點恰好包含有k-1個關鍵字(各節點內關鍵字均升序或降序排列).9.堆(Heap)分為小根堆和大根堆兩種，對于一個小根堆，它是具有如下特性的一棵完全二叉樹：(1)若樹根結點存在左孩子，則根結點的值(或某個域的值)小于等于左孩子結點的值(或某個域的值)；(2)若樹根結點存在右孩子，則根結點的值(或某個域的值)小于等于右孩子結點的值(或某個域的值)；(3)以左、右孩子為根的子樹又各是一個堆。大根堆的定義與上述類似，只要把小于等于改為大于等于就得到了。由堆的定義可知，若一棵完全二叉樹是堆，則該樹中以每個結點為根的子樹也都是一個堆。分別為一個小根堆和一個大根堆。根據堆的定義可知，堆頂結點，即整個完全二叉樹的根結點，對于小根堆來說具有最小值，對于大根堆來說具有最大值。堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特征，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。當向一個小根堆插入一個具有最小值的元素時,該元素需要逐層向上調整,直到被調整到堆頂位置為止。10.數據元素序列11，12，13，7，8，9，23，4，5是第二趟排序后的結果，則該排序算法只能是插入排序。氣泡排序基本思想：設待排序對象序列中的對象個數為n。一般地，第i趟起泡排序從1到n-i+1依次比較相鄰兩個記錄地關鍵字，如果發生逆序，則交換之，其結果是這n-i+1個記錄中，關鍵字最大的記錄被交換到第n-i+1的位置上，最多作n-1趟。簡單選擇排序基本思想：第一趟在R[1..n]中選最小的，與R[1]交換第二趟在R[2..n]中選最小的，與R[2]交換，依次類推，進行n-1次選擇后，整個文件有序。直接插入排序基本思想:將一個記錄插入到已排序的有序表中，使插入后的表仍然有序。折半插入排序基本思想：將一個記錄插入到已排序的有序表中，使插入后的表仍然有序，但插入時利用折半搜索法尋找元素的插入位置。歸并排序基本思想：又一類不同的排序方法，將兩個或兩個以上的有序表合并成一個新的有序表。快速排序基本思想：取R[1..n]中任一記錄作為“樞軸”，一趟排序之后樞軸的值均小于“樞軸”左邊的值，樞軸右邊的值均大于“樞軸”的值。堆排序基本思想：1.如何將一個無序序列調整為堆？2.如何在互換堆頂之后重新調整為堆（關鍵）？希爾排序(ShellSort)基本思想：1.n大，劃分成若干子序列，分別直接插入排序。2.待整個記錄“基本有序”時，對整體直接重排。11.馮·諾依曼計算機中指令和數據均以二進制形式存放在存儲器中，CPU區分它們的依據是指令周期的不同階段。12.十進制轉換：十進制轉任意進制的通用方法是：除x取余倒排法（x代表進制數）。如：將十進制數76轉換成任意進制1.轉成二進制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.轉成八進制76/8...4=9/8...1=1/8...176(10)=114(8)3.轉成十六進制76/16...12=4/16...476(10)=4C(16)B：二進制數。Q：八進制數。D：十進制數。H：十六進制數。負數用十六進制和八進制怎么表示？使用補碼（二進制），而且還要指定字長比如說一個二字節整型的-2就應該是：1111111111111110再轉化其它進制十六進制：FFFE八進制：17777613.浮點數加減運算過程一般包括對階、尾數運算、規格化、舍入和判溢出等步驟。設浮點數的階碼和尾數均采用補碼表示，且位數分別為5位和7位（均含2位符號位）。若有兩個數X=2^7*29/32，Y=2^5*5/8,則用浮點加法計算X+Y的最終結果是發生溢出浮點數表示：小數點的位置可以在一定范圍內浮動。E為階，包括階符和階碼（整數），階碼為數決定了浮點數的表示范圍。M為位數，包括數符和尾數，表示數的精度和正負。對階原則：小階對大階。雙符號位判溢：加，減后。兩個符號位出現“01”，表示已經溢出，即結果大于+1.14.存儲器的分類：1.按存儲介子分:(1)半導體存儲器;(2)磁表面存儲器;(3)光介子存儲器。2.按存取方式分類:(1)隨機存取存儲器RAM；(2)順序存儲器SAM；(3)直接存取存儲器DAM。3.按計算機功能分類:(1)主存儲器（主存）用于存放計算機運行期間的大量程序和數據的存儲器，CPU能直接訪問。由MOS存儲器構成。(2)高速緩沖存儲器（Cache）Cache是介于CPU和主存之間高速小容量存儲器，用于存放最活躍的程序塊和數據。由靜態MOS存儲器構成。特點：速度快，但容量小，位價格較高。主存和Cache一起構成計算機的內存儲器（內存），是CPU能直接訪問的存儲器。(3)輔助存儲器（外存儲器）存放當前暫不參與運行的程序和數據，需要時再與主存成批交換信息的存儲器。特點是容量大，可存放大量的程序和數據，但速度慢。(4)控制存儲器（CM）在微程序控制的計算機中，用于存放執行指令的微程序的存儲器。CM一般由ROM構成，屬于控制器的一部分。4.其它分類：a.按讀寫功能分類：(1)只讀存儲器(ROM):工作時只能讀出不能寫入的存儲器。(2)讀寫存儲器(RAM):既能讀出又能寫入的存儲器。b.按信息的可保存性分類(1)永久性存儲器：指斷電后仍能保存信息的存儲器，如磁表面存儲器。(2)非永久性存儲器:指斷電后信息即消失的存儲器，如半導體讀寫存儲器。某計算機的Cache共有16塊，采用2路組相連映射方式（即每組2塊）。每個主存塊大小為32字節，按字節編址。主存129號單元所在主存塊應裝入到Cache組號是(4)15.主存容量是根據地址線的位數來確定的,在16位PC機中地址總線的寬度是20位,則主存大小為:2^20byte=1MB,現在的PC機一般都是32位地址總線的,最大直接尋址空間為:2^32,即主存最大容量為4GB某計算機主存容量為64KB，其中ROM區為4KB，其余為RAM區，按字節編址。現要用2K*8位的ROM芯片和4K*4位的RAM芯片來設計該存儲器，則需要上述規格的ROM芯片數和RAM芯片數分別是23016.某計算機字長16位，主存按字節編址，轉換指令采用相對尋址，由兩個字節組成，第一字節為操作碼字段，第二字節為相對位移量字段。假定取指令時，每取一字節PC自動加1。若某轉移指令所在主存地址為2000H，相對位移量字段的內容為06H，則該轉移指令成功轉移后的目標地址是(2008H)相對尋址:以當前程序計數器pc的內容為基址，加上指令給出的一字節補碼數（偏移量）形成新的pc值的尋址方式稱為相對尋址。目的地址=源地址+相對轉移指令字節數+指令中給定的偏移量(rel).17.RISC(精簡指令系統)的敘述:(1).選用的是使用頻率很高的一些簡單指令；(2).指令長度固定，指令格式及尋址方式種類少；(3).只有取數/存數指令訪問存儲器，其余指令的操作都在寄存器之間進行；(4).大多數指令可在一個計算機周期內完成。18.指令周期是取出并執行一條指令的時間。指令周期常常有若干個CPU周期，CPU周期也稱為機器周期，由于CPU訪問一次內存所花費的時間較長，因此通常用內存中讀取一個指令字的最短時間來規定CPU周期。這就是說一條指令取出階段（通常為取指）需要一個CPU周期時間。而一個CPU周期時間又包含若干個時鐘周期(通常為節拍脈沖或Ｔ周期，它是處理操作的最基本的單位)。這些時鐘周期的總和則規定了一個CPU周期的時間寬度。某計算機的指令流水線由四個功能段組成，指令流經各功能段的時間（忽略各功能段之間的緩沖時間）分別是90ns、80ns、70ns、60ns，則計算機的CPU時鐘周期是(90ns)。19.相對于微程序控制器，硬布線控制器的特點是指令執行速度快，指令功能的修改和擴展難。20.假設某系統總線在一個總線周期中并行傳輸4字節信息，一個總線周期占用2個時鐘周期，總線時鐘頻率為10MHz，則總線帶寬是(20MB/S)時鐘周期和時鐘頻率互為倒數關系。1KHz=1000Hz；1MHz=1000KHz并行總線帶寬(MB/s)=并行總線時鐘頻率(MHz)*并行總線位寬(bit/8=B)*每時鐘傳輸幾組數據(cycle)串行總線帶寬(MB/s)=串行總線時鐘頻率(MHz)*串行總線位寬(bit/8=B)*串行總線管線*編碼方式*每時鐘傳輸幾組數據(cycle)1字節（Byte）=8位（bit）21.假設某計算機的存儲系統由Cache和主存組成，某程序執行過程中訪存1000次，其中訪問Cache缺失（未命中）50次，則Cache的命中率是(95%)22.能引起外部中斷的事件是:鍵盤輸入(人的干預)或外請求。（外中斷都是強迫中斷）23.單處理機系統中，可并行的是（II、III和IV）I進程與進程II處理機與設備III處理機與通道IV設備與設備24.進程調度算法中，綜合考慮進程等待時間和執法世間是:(高響應比優先調度算法).FCFS:誰先到就緒隊列,將處理機分給誰;時間片輪轉調度法:以先來后到的次序+時間片輪轉;優先級調度:選優先級最高的進程占用處理機(優先級可動態改變);短進程優先:取所需的運行時間最短的進程(該算法能使平均等待時間最短).25.某計算機系統有8臺打印機，有K個進程競爭使用，每個進程最多需要3臺打印機。該系統可能會發生死鎖的K的最小值是(4)26.分區分配內存管理方式的主要保護措施是(界地址保護)27.一個分段存儲管理系統中，地址長度為32位，其中段號占8位，則最大段長是(2^24).分頁與分段的區別：分頁:信息的物理單位大小一樣，由系統固定地址空間是一維的分段:信息的邏輯單位大小不等，由用戶確定地址空間是二維的28.文件物理結構中，適合隨機訪問且易于文件擴展的是(索引結構).連續結構:將一個文件中邏輯上連續的信息存放到存儲介質的依次相鄰的塊上便形成順序結構，這類文件叫連續文件，又稱順序文件。優點：簡單;支持順序存取和隨機存取；順序存取速度快；所需的磁盤尋道次數和尋道時間最少.缺點：建立文件前需要能預先確定文件長度，以便分配存儲空間；修改、插入和增生文件記錄有困難；對直接存儲器作連續分配，會造成少量空閑塊的浪費。鏈接結構：一個文件的信息存放在若干不連續的物理塊中，各塊之間通過指針連接，前一個物理塊指向下一個物理塊。優點：提高了磁盤空間利用率,不存在外部碎片問題；有利于文件插入和刪除；有利于文件動態擴充.缺點：存取速度慢，不適于隨機存取；可靠性問題，如指針出錯；更多的尋道次數和尋道時間；鏈接指針占用一定的空間.索引結構：一個文件的信息存放在若干不連續物理塊中，系統為每個文件建立一個專用數據結構索引表。表中每一欄目指出文件信息所在的邏輯塊號和與之對應的物理塊號。索引表的物理地址則由文件說明信息項給出。優點：保持了鏈接結構的優點,又解決了其缺點；即能順序存取,又能隨機存取；滿足了文件動態增長、插入刪除的要求；也能充分利用外存空間。缺點：較多的尋道次數和尋道時間；索引表本身帶來了系統開銷如：內外存空間，存取時間。29.SCAN調度(電梯調度)算法:電梯調度算法基于日常生活中的電梯工作模式：電梯保持按一個方向移動，直到在那個方向上沒有請求為止，然后改變方向。反映在磁盤調度上，總是沿著移動臂的移動方向選擇距離磁頭當前位置最近的I/O請求作為下一次調度的對象。如果該方向上已無I/O請求，則改變方向再做選擇。假設磁頭當前位于第105道，正在向磁道序號增加的方向移動。現在一個磁道訪問請求序列為35，45，12，68，110，180，170，195，采用SCAN調度（電梯調度）算法得到的磁道訪問序列是：110,170,180,195,68,45,35,12。30.文件系統中，文件訪問控制信息存儲的合理位置是(文件控制塊)。31.硬鏈接：在磁盤上有一份內容一樣的文件產生，但不改變文件的Inode,也就是與原文件共用Inode。軟鏈接：不在磁盤上有一份內容一樣的文件產生，但產生新的Inode。設文件F1的當前引用計數值為1，先建立F1的符號鏈接（軟鏈接）文件F2，再建立F1的硬鏈接文件F3，然后刪除F1。此時，F2和F3的引用計數值分別是（1，1）。32.程序員利用系統調用打開I/O設備時，通常使用的設備標識是（邏輯設備名）。33.在OSI參考模型中，自下而上第一個提供端到端服務的層次是（傳輸層）。自下而上方法的一般從檢查物理層開始。自下而上分別稱為：物理層、數據鏈路層、網絡層、傳輸層、會話層、表示層和應用層。傳輸層是兩臺計算機經過網絡進行數據通信時,第一個端到端的層次，具有緩沖作用。34.1924年奈奎斯特(Nyquist)就推導出在理想低通信道的最高大碼元傳輸速率的公式:理想低通信道的最高大碼元傳輸速率C=2W.log2N(其中W是想低通信道的帶寬,N是電平強度)信道帶寬與數據傳輸速率的關系可以奈奎斯特(Nyquist)準則與香農(Shanon)定律描述。奈奎斯特定理描述了有限帶寬、無噪聲信道的最大數據傳輸速率與信道帶寬的關系。香農定理則描述了有限帶寬、有隨機熱噪聲信道的最大傳輸速率與信道帶寬、信噪比之間的關系。奈奎斯特準則指出：對于二進制數據信號的最大數據傳輸速率Rmax與通信信道帶寬B（B=f,單位Hz)的關系可以寫為：Rmax＝2*B(bps)香農定理指出：在有隨機熱噪聲的信道上傳輸數據信號時，數據傳輸速率Rmax與信道帶寬B、信噪比S/N的關系為：Rmax＝B*log2(1+S/N))[以2為底,1+S/N的對數]式中，Rmax單位為bps,帶寬B單位為Hz，信噪比S/N通常以dB（分貝）數表示。若S/N=30(dB),那么信噪比根據公式：S/N(dB)=10*lg(S/N)則S/N=1000。若帶寬B=3000Hz，則Rmax≈30kbps。（1）對于帶寬為6MHz的信道，若用4種不同的狀態來表示數據，在不考慮熱噪聲的情況下，該信道的最大數據傳輸速率是多少？答：由無熱噪聲的奈奎斯特公式:C=2Hlog2N=2*6M*log24=24Mbps，即該信道的最大數據傳輸速率是24Mbps（2）在無噪聲情況下，若某通信鏈路的帶寬為3KHz,采用4個相位，每個相位具有4種振幅的QAM調制技術，則該通信鏈路的最大數據傳輸速率是(24kbps)C=2Hlog2N=2*3k*log216=24kbps.35.后退N幀ARQ就是從出錯處重發已發出過的N個幀。數據鏈路層采用了后退N幀（GBN）協議，發送方已經發送了編號為0~7的幀。當計時器超時時，若發送方只收到0、2、3號幀的確認，則發送方需要重發的幀數是(4)。36.以太網交換機進行轉發決策時使用的PDU地址是(目的物理地址)。ARP協議是“AddressResolutionProtocol”（地址解析協議）的縮寫。在局域網中，網絡中實際傳輸的是“幀”，幀里面是有目標主機的MAC地址的。在以太網中，一個主機要和另一個主機進行直接通信，必須要知道目標主機的MAC地址。但這個目標MAC地址是如何獲得的呢？它就是通過地址解析協議獲得的。所謂“地址解析”就是主機在發送幀前將目標IP地址轉換成目標MAC地址的過程。ARP協議的基本功能就是通過目標設備的IP地址，查詢目標設備的MAC地址，以保證通信的順利進行。37.CSMA/CD是一種分布式介質訪問控制協議，網中的各個站（節點）都能獨立地決定數據幀的發送與接收。每個站在發送數據幀之前，首先要進行載波監聽，只有介質空閑時，才允許發送幀。這時，如果兩個以上的站同時監聽到介質空閑并發送幀，則會產生沖突現象，這使發送的幀都成為無效幀，發送隨即宣告失敗。每個站必須有能力隨時檢測沖突是否發生，一旦發生沖突，則應停止發送，以免介質帶寬因傳送無效幀而被白白浪費，然后隨機延時一段時間后，再重新爭用介質，重發送幀。CSMA/CD協議簡單、可靠，其網絡系統（如Ethernet）被廣泛使用。在一個采用CSMA/CD協議的網絡中，傳輸介質是一根完整的電纜，傳輸速率為1Gbps,電纜中的信號傳播速度是200000km/s。若最小數據幀長度減少800比特，則最遠的兩個站點之間的距離至少需要(減少80)。最短幀長=2*L*10^9(b/s)÷200000000m/s=10*L(bit).38.主機甲和主機乙之間建立一個TCP連接,主機甲向主機乙發送了兩個連續的TCP段,分別含300字節和500字節的有效載荷,第一個段的序列號為200,主機乙正確接收到兩個段后,發送給主機甲的確認序列號是(1000)。例如，序列號等于前一個報文段的序列號與前一個報文段中數據字節的數量之和。例如，假設源主機發送3個報文段，每個報文段有100字節的數據，且第一個報文段的序列號是1000，那么接收到第一個報文段后，目的主機返回含確認號1100的報頭。接收到第二個報文段（其序號為1100）后，目的主機返回確認號1200。接收到第三個報文段后，目的主機返回確認號1300。39.確定擁塞窗口的大小的過程：在剛建立連接時，將擁塞窗口的大小初始化為該連接所需的最大連接數據段的長度值，并發送一個最大長度的數據段（當然必須是接收窗口允許的）。如果在定時器超時前得到確認，將擁塞窗口的大小增加一個數據段的字節數，并發送兩個數據段，如果每個數據段在定時器超時前都得到確認，就再在原基礎上增加一倍，即為4個數據段的大小，如此反復，每次都在前一次的基礎上加倍。當定時器超時或達到發送窗口設定值，停止擁塞窗口尺寸的增加。這種反復稱為慢速啟動，所有的TCP協議都支持這種方法。一個TCP連接總是以1KB的最大段發送TCP段，發送方有足夠多的數據要發送。當擁塞窗口為16KB時發生了超時，如果接下來的4個RTT（往返時間）時間內的TCP段的傳輸都是成功的，那么當第4個RTT時間內發送的所有TCP段都得到肯定應答時，擁塞窗口大小是(9KB)。40.FTP客戶和服務器間傳遞FTP時，使用的連接是(建立在TCP之上的控制連接)。二．綜合應用題41.該方法求得的路徑不一定是最短路徑。例如，對于下圖所示的帶權圖，如果按照題中的原則，從A到C的最短路徑為A→B→C，事實上其最短路徑為A→D→C。42.（1）算法基本思想如下：從頭至尾遍歷單鏈表，并用指針P指向當前節點的前K個節點。當遍歷到鏈表的最后一個節點時，指針P所指向的節點即為所查找的節點。（2）詳細實現步驟：增加兩個指針變量和一個整型變量，從鏈表頭向后遍歷，其中指針P1指向當前遍歷的節點，指針P指向P1所指向節點的前K個節點，如果P1之前沒有K個節點，那么P指向表頭節點。用整型變量i表示當前遍歷了多少節點，當i>k時，指針p隨著每次遍歷，也向前移動一個節點。當遍歷完成時，p或者指向表頭就節點，或者指向鏈表中倒數第K個位置上的節點。（3）算法描述：IntLocateElement(linklistlist,intk){P1=list->link;P=list;i=1;while(P1){P1=P1->link;i++;if(i>k)p=p->next;//如果i>k,則p也往后移}if(p==list)return0;//說明鏈表沒有k個結點else{printf(“%d\n“,p->data);return1;}}43.（1）在中斷方式下，每32位（4B）被中斷一次，故每秒中斷0.5MB/4B=0.5×106/4=12.5×104次要注意的是，這里是數據傳輸率，所以1MB=106B。因為中斷服務程序包含18條指令，中斷服務的其他開銷相當于2條指令的執行時間，且執行每條指令平均需5個時鐘周期，所以，1秒內用于中斷的時鐘周期數為（18+2）×5×12.5×104=12.5×106（2）在DMA方式下，每秒進行DMA操作5MB/5000B=5×106/5000=1×103次因為DMA預處理和后處理的總開銷為500個時鐘周期，所以1秒鐘之內用于DMA操作的時鐘周期數為500×1×103=5×105故在DMA方式下，占整個CPU時間的百分比是（（5×105）/（500×106））×100%=0.1%44.指令執行階段每個節拍的功能和有效控制信號如下所示時鐘功能有效控制信號C5MAR←(R1)PCout,MARinC6MDR←M(MAR)MemR,MDRinEC7A←(R0)R0out,AinC8AC←(MDR)+(A)MDRout,Addr,ACinC9MDR←(AC)ACout,MDRinC10M(MAR)←MDRMDRoutE,MemW45.定義信號量S1控制P1與P2之間的同步；S2控制P1與P3之間的同步；empty控制生產者與消費者之間的同步；mutex控制進程間互斥使用緩沖區。程序如下：Vars1=0,s2=0,empty=N,mutex=1;ParbeginP1:beginX=produce();P(empty);P(mutex);Put();Ifx%2==0V(s2);elseV(s1);V(mutex);end.P2:beginP(s1);P(mutex);4KB,頁內占12位，即16機制的3位則2362H的最高位就是頁號2:10不命中+100頁表+100內存地址1：10不命中+100頁表+108缺頁+100內存地址2：10命中+100內存地址1號頁內偏移565H，缺頁，置換0，101565HGetodd();Countodd():=countodd()+1;V(mutex);V(empty);end.P3:beginP(s2)P(mutex);Geteven();Counteven():=counteven()+1;V(mutex);V(empty);end.Parend.46.（1）根據頁式管理的工作原理，應先考慮頁面大小，以便將頁號和頁內位移分解出來。頁面大小為4KB，即212，則得到頁內位移占虛地址的低12位，頁號占剩余高位。可得三個虛地址的頁號P如下（十六進制的一位數字轉換成4位二進制，因此，十六進制的低三位正好為頁內位移，最高位為頁號）：2362H：P=2，訪問快表10ns，因初始為空，訪問頁表100ns得到頁框號，合成物理地址后訪問主存100ns，共計10ns+100ns+100ns=210ns。1565H：P=1，訪問快表10ns，落空，訪問頁表100ns落空，進行缺頁中斷處理108ns，合成物理地址后訪問主存100ns，共計10ns+100ns+108ns+100ns≈108ns。25A5H：P=2，訪問快表，因第一次訪問已將該頁號放入快表，因此花費10ns便可合成物理地址，訪問主存100ns，共計10ns+100ns=110ns。（2）當訪問虛地址1565H時，產生缺頁中斷，合法駐留集為2，必須從頁表中淘汰一個頁面，根據題目的置換算法，應淘汰0號頁面，因此1565H的對應頁框號為101H。由此可得1565H的物理地址為101565H。47.（1）無類IP地址的核心是采用不定長的網絡號和主機號，并通過相應的子網掩碼來表示（即網絡號部分為1，主機號部分為0）。本題中網絡地址位數是24，由于IP地址是32位，因此其主機號部分就是8位。因此，子網掩碼就是11111111111111111111111100000000，即。根據無類IP地址的規則，每個網段中有兩個地址是不分配的：主機號全0表示網絡地址，主機號全1表示廣播地址。因此8位主機號所能表示的主機數就是2的8次方—2，即254臺。該網絡要劃分為兩個子網，每個子網要120臺主機，因此主機位數X應該滿足下面三個條件：X<8，因為是在主機號位長為8位的網絡進行劃分，所以X一定要小于8位。2的X次方>120,因為根據題意需要容納120臺主機。X是整數。解上述方程，得到X=7.子網掩碼就是11111111111111111111111110000000，即28。所以劃分的兩個網段是：/25與28/25。（2）填寫R1的路由表填寫到局域網1的路由。局域網1的網絡地址和掩碼在問題（1）已經求出來了，為/25。則R1路由表應填入的網絡地址為，掩碼為28。由于局域網1是直接連接到路由器R1的E1口上的，因此，下一跳地址填寫直接路由（Direct）。接口填寫E1.填寫到局域網2的路由表1。局域網2的網絡地址和掩碼在問題（1）中已經求出來了，為28/25。則R1路由表應該填入的網絡地址為28，掩碼為28.由于局域網2是直接連接到路由器R1的E2口上的，因此，下一跳地址填寫直接路由。接口填寫E2。填寫到域名服務器的路由。由于域名服務器的IP地址為，而該地址為主機地址，因此掩碼為55。同時，路由器R1要到DNS服務器，就需要通過路由器R2的接口L0才能到達，因此下一跳地址填寫L0的IP地址（）。填寫互聯網路由。本題實質是編寫默認路由。默認路由是一種特殊的靜態路由，指的是當路由表中與包的目的地址之間沒有匹配的表項時路由器能夠做出的選擇。如果沒有默認路由器，那么目的地址在路由表中沒有匹配表項的包將被丟棄。默認路由在某些時候非常有效，當存在末梢網絡時，默認路由會大大簡化路由器的配置，減輕管理員的工作負擔，提高網絡性能。默認路由叫做“0/0”路由，因為路由的IP地址，而子網掩碼也是。同時路由器R1連接的網絡需要通過路由器R2的L0口才能到達互聯網絡，因此下一跳地址填寫L0的IP為。綜上，填寫的路由表如下：R1路由表（3）填寫R2到局域網1和局域網2的路由表2。局域網1和局域網2的地址可以聚合為/24，而R2去往局域網1和局域網2都是同一條路徑。因此，路由表里面只需要填寫到/24網絡的路由即可，如下表所示R2路由表目的網絡IP地址子網掩碼下一跳IP地址接口L02010年全國研究生考試計算機統考試題及答案一、單選題1、若元素a,b,c,d,e,f依次進棧，允許進棧、退棧操作交替進行。但不允許連續三次進行退棧工作，則不可能得到的出棧序列是（D）A：dcebfaB：cbdaef2、某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，則不可能得到的順序是（C）A：bacdeB：dbaceC：dbcaeD：ecbad3、下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（B）C：dbcaefD：afedcb4、在下列所示的平衡二叉樹中插入關鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關鍵字37所在結點的左、右子結點中保存的關鍵字分別是（C）A：13，48B：24，48C：24，53D：24，905、在一棵度為4的樹T中，若有20個度為4的結點，10個度為3的結點，1個度為2的結點，10個度為1的結點，則樹T的葉節點個數是（B）A：41B：82C：113D：1226、對n(n大于等于2)個權值均不相同的字符構成哈夫曼樹，關于該樹的敘述中，錯誤的是（B）A：該樹一定是一棵完全二叉樹B：樹中一定沒有度為1的結點C：樹中兩個權值最小的結點一定是兄弟結點D：樹中任一非葉結點的權值一定不小于下一任一結點的權值7、若無向圖G-（V.E）中含7個頂點，則保證圖G在任何情況下都是連通的，則需要的邊數最少是（A）A：68、對下圖進行拓補排序，可以得到不同的拓補序列的個數是（B）A：4B：3C：2D：1B：15C：16D：219、已知一個長度為16的順序表L，其元素按關鍵字有序排列，若采用折半查找法查找一個不存在的元素，則比較次數最多是（A）A：4B：5C：6D：710、采用遞歸方式對順序表進行快速排序，下列關于遞歸次數的敘述中，正確的是（D）A：遞歸次數與初始數據的排列次序無關B：每次劃分后，先處理較長的分區可以減少遞歸次數C：每次劃分后，先處理較短的分區可以減少遞歸次數D：遞歸次數與每次劃分后得到的分區處理順序無關11、對一組數據（2，12，16，88，5，10）進行排序，若前三趟排序結果如下（A）第一趟：2，12，16，5，10，88第二趟：2，12，5，10，16，88第三趟：2，5，10，12，16，88則采用的排序方法可能是：A：起泡排序B：希爾排序C：歸并排序D：基數排序12、下列選項中，能縮短程序執行時間的措施是（D）I提高CPU時鐘頻率，II優化數據通過結構，III對程序進行編譯優化A：僅I和IIB：僅I和IIIC：僅II和IIID：I，II，III13、假定有4個整數用8位補碼分別表示r1=FEH,r2=F2H,r3=90H,r4=F8H,若將運算結果存放在一個8位的寄存器中，則下列運算會發生溢出的是（C）A：r1*r2B：r2*r3C：r1*r4D：r2*r414、假定變量I,f,d數據類型分別為int,float和double(int用補碼表示，float和double分別用IEEE754單精度和雙精度浮點數據格式表示)，已知i=785,f=1.5678,d=1.5若在32位機器中執行下列關系表達式，則結果為真是（C）（I）f=(int)(float)I(II)f=(float)(int)f(III)f=(float)(double)(IV)=(d+f)-d=fA：僅I和IIB：僅I和IIIC：僅II和IIID：僅III和IV15、假定用若干個2k*4位芯片組成一個8*8位存儲器，則地址0B1FH所在芯片的最小地址是（D）A：0000HB：0600HC：0700HD：0800H16、下列有關RAM和ROM的敘述中，正確的是（A）I、RAM是易失性存儲器，ROM是非易失性存儲器II、RAM和ROM都是采用隨機存取的方式進行信息訪問III、RAM和ROM都可用作CacheIV、RAM和ROM都需要進行刷新A：僅I和IIB：僅II和IIIC：僅I,II，IIID：僅II，III，IV17、下列命令組合情況中，一次訪存過程中，不可能發生的是（D）A：TLB未命中，Cache未命中，Page未命中B：TLB未命中，Cache命中，Page命中C：TLB命中，Cache未命中，Page命中D：TLB命中，Cache命中，Page未命中18、下列存儲器中，匯編語言程序員可見的是（B）A：存儲器地址寄存器（MAR）C：存儲器數據寄存器（MDR）B：程序計數器（PC）D：指令寄存器（IR）19、下列不會引起指令流水阻塞的是（A）A：數據旁路B：數據相關C：條件轉移D：資源沖突20、下列選項中的英文縮寫均為總線標準的是（D）A：PCI、CRT、USB、EISAC：ISA、SCSI、RAM、MIPSB：ISA、CPI、VESA、EISAD：ISA、EISA、PCI、PCI-Express21、單級中斷系統中，中斷服務程序執行順序是（A）I、保護現場II、開中斷III、關中斷IV、保存斷點V、中斷事件處理VI、恢復現場VII、中斷返回A：I、V、VI、II、VIIB：III、I、V、VIIC：III、IV、V、VI、VIID：IV、I、V、VI、VII22、假定一臺計算機的顯示存儲器用DRAM芯片實現，若要求顯示分辨率為1600*1200，顏色深度為24位，幀頻為85Hz，顯示總帶寬的50%用來刷新屏幕，則需要的顯存總帶寬至少約為（D）A：245MbpsC：1958MbpsB：979MbpsD：7834Mbps23、下列選項中，操作S提供的給應用程序的接口是（A）A：系統調用C：庫函數B：中斷D：原語24、下列選項中，導致創進新進程的操作是（C）I用戶成功登陸II設備分配III啟動程序執行A：僅I和IIC：僅I和IIIB：僅II和IIID：I，II，III25、設與某資源相關聯的信號量初值為3，當前值為1，若M表示該資源的可用個數，N表示等待資源的進程數，則M,N分別是（B）A：0，1B：1，0C：1，226、下列選項中，降低進程優先權級的合理時機是（A）A：進程的時間片用完B：進程剛完成Z/O，進入就緒隊列D：2，0C：進程長期處于就緒隊列中D：就緒從就緒狀態轉為運行態27、進行P0和P1的共享變量定義及其初值為（A）booleanflag[2]；intturn=0；flag[0]=faulse；flag[1]=faulse；若進行P0和P1訪問臨界資源的類C代碼實現如下：Voidp0（）//進程p0{while（TURE）}Voidp1（）//進程p1{while（TURE）}Flag[0]=TURE;ture=1Flag[1]=TURE;ture=1While（flag[1]&&（turn==1））While（flag[0]&&（turn==0））臨界區：Flag[0]=FALSE;Flag[1]=FALSE;}}}}則并發執行進程P0和P1時產生的情況是：A：不能保證進程互斥進入臨界區，會出現“饑餓”現象B：不能保證進程互斥進入臨界區，不會出現“饑餓”現象C：能保證進程互斥進入臨界區，會出現“饑餓”現象D：能保證進程互斥進入臨界區，不會出現“饑餓”現象28、某基于動態分區存儲管理的計算機，其主存容量為55mb（初試為空間），采用最佳適配（Bestfit）算法，分配和釋放的順序為：分配15mb，分配30mb，釋放15mb，分配8mb，此時主存中最大空閑分區的大小是（B）A：7mbB：9mbC：10mbD：15mb29、某計算機采用二級頁表的分頁存儲管理方式，按字節編制，頁大小為216字節，頁表項大小為2字節，邏輯地址結構為頁目編號頁號頁內偏移量邏輯地址空間大小為216頁，則表示整個邏輯地址空間的頁目錄表中包含表項的個數至少是（B）A：64B：128C：256D：51230、設文件索引節點中有7個地址項，其中4個地址項為直接地址索引，2個地址項是一級間接地址索引，1個地址項是二級間接地址索引，每個地址項大小為4字節，若磁盤索引塊和磁盤數據塊大小均為256字節，則可表示的單個文件的最大長度是（C）A：33kbD：16513kbB：519kbC：1057kb31、設置當前工作目錄的主要目的是（C）A：節省外存空間B：節省內容空間C：加快文件的檢索速度D：加快文件的讀寫速度32、本地用戶通過鍵盤登錄系統時，首先獲得鍵盤輸入信息的程序是（B）A：命令解釋程序C：系統調用程序B：中斷處理程序D：用戶登錄程序33、下列選項中，不屬于網絡體系結構中所描述的內容是（C）A：網絡的層次B：每一層使用的協議C：協議的內部實現細節D：每一層必須完成的功能34、在下圖所示的采用“存儲-轉發”方式分組的交換網絡中，所有鏈路的數據傳輸速度為100mbps，分組大小為1000B，其中分組頭大小20B，若主機H1向主機H2發送一個大小為980000B的文件，則在不考慮分組拆裝時間和傳播延遲的情況下，從H1發送到H2接收完為止，需要的時間至少是（A）A：80msB：80.08msC：80.16msD：80.24ms35、某自治系統采用RIP協議，若該自治系統內的路由器R1收到其鄰居路由器R2的距離矢量中包含信息＜net1，16＞，則可能得出的結論是（A）A：R2可以經過R1到達net1，跳數為17B：R2可以到達net1，跳數為16C：R1可以經過R2到達net1，跳數為17D：R1不能進過R2到達net136、若路由器R因為擁塞丟棄IP分組，則此時R可以向發出該IP分組的源主機發送的ICMP報文件類型是（C）A：路由重定向C：源抑制B：目的不可達D：超時37、某網絡的IP地址為/24采用長子網劃分，子網掩碼為48，則該網絡的最大子網個數，每個子網內的最大可分配地址個數為（B）A：32，8C：8，32B：32，6D：8，3038、下列網絡設備中，能夠抑制網絡風暴的是（C）Ⅰ中繼器Ⅱ集線器Ⅲ網橋Ⅳ路由器A：僅Ⅰ和ⅡB：僅ⅢD：僅ⅣC：僅Ⅲ和Ⅳ39、主機甲和主機乙之間已建立一個TCP連接，TCP最大段長度為1000字節，若主機甲的當前擁塞窗口為4000字節，在主機甲向主機乙連接發送2個最大段后，成功收到主機乙發送的第一段的確認段，確認段中通告的接收窗口大小為2000字節，則此時主機甲還可以向主機乙發送的最大字節數是（A）A：1000C：3000B：2000D：400040、如果本地域名服務無緩存，當采用遞歸方法解析另一網絡某主機域名時，用戶主機本地域名服務器發送的域名請求條數分別為（A）A：1條，1條C：多條，1條B：1條，多條D：多條，多條二、綜合應用題：41-47小題，共計70分41.（10分）將關鍵字序列（7、8、11、18、9、14）散列存儲到散列列表中，散列表的存儲空間是一個下標從0開始的一個一維數組散列函數維：H（key）=（key×3）MODT，處理沖突采用線性探測再散列法，要求裝填（載）因子為0.7問題：（1）請畫出所構造的散列表；（2）分別計算等概率情況下，查找成功和查找不成功的平均查找長度。解答：（1）由裝載因子0.7，數據總數7個→存儲空間長度為10→P=10所以，構造的散列表為：03017214311485186.798.9.H（7）=（7×3）MOD10=1（2）查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7查找不成功的ASL=(7+6+