全國計算機聯(lián)考基礎綜合考研試題

2011年全國碩士研究生入學統(tǒng)一考試計算機科學與技術學科聯(lián)考計算機學科專業(yè)基礎綜合試題一、單項選擇題：1～40小題，每小題2分，共80 是描述問題規(guī)模的非負2011年全國碩士研究生入學統(tǒng)一考試計算機科學與技術學科聯(lián)考計算機學科專業(yè)基礎綜合試題一、單項選擇題：1～40小題，每小題2分，共80 是描述問題規(guī)模的非負整數(shù)，下面程序片段的時間復雜度 2．元依次進入初始為空的棧中，若元素進棧后可停留、可出棧，直到所有元素出棧，則在所有可能的出棧序列中，以元素d開頭的序列個數(shù) 素。若初始時隊列為空，且要求第1別 A[0...n-1]中，且隊列非空時front和rear分別指向隊頭元素和隊尾個進入隊列的元素存儲在A[0]處，則初始時front和rearB．0，n-C．n-D．n-1，n-4．若一棵完全二叉樹個結點，則該二叉樹中葉結點的個數(shù) 和4，3，2，1，則該二叉樹5．若一棵二叉樹的前序遍歷序列和后序遍歷序列分別中序遍歷序列不會 個結點的樹，其葉結點個數(shù)116，該樹對應的二叉樹中無右孩子的結點個7．對于下列關鍵字序列，不可能構成某二叉排序樹中一條查找路徑的序列 A Ⅱ．設計沖突（碰撞）Ⅲ．處理沖突（碰撞）時避免產(chǎn)生聚集（堆積）A10．為實現(xiàn)快速排序算法，待排序序列宜采用的存儲方式 11．已知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18整過程中元素之間進行的比較次數(shù) 12．下列選項中，描述浮點數(shù)操作速度指標的 13．floatIEEE754floatx位浮點寄存器11．已知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18整過程中元素之間進行的比較次數(shù) 12．下列選項中，描述浮點數(shù)操作速度指標的 13．floatIEEE754floatx位浮點寄存器FR1中，且x=-8.25，則FR1的內(nèi)容 A．C104B．C242C．C184 D．C1C214．下列各類存儲器中，不采用隨機存取方式的 的主存儲器，則存儲器地址寄存器MAR的位數(shù)至少 A．22B．23C．25D．2616．偏移尋址通過將某個寄存器內(nèi)容與一個形式地址相加而生成有效地址。下列尋址方式中，屬于偏移尋址方式的是 。B．基址尋C．相對尋D．變址尋17．某機器有一個標志寄存器，其中有進位/借位標志CF、零標志ZF、符號標志SF和溢出標志條件轉移指bgt（無符號整數(shù)比較大于時轉移）的轉移條件 A．CFOFB．SFZFC．CFZFD．CFSF18．下列給出的指令系統(tǒng)特點中，有利于實現(xiàn)指令流水線的 Ⅲ．只有Load/Store指令才能對操作數(shù)進行存儲訪19.假定不采B．僅C．僅D．Ⅰ、Ⅱ、 和指令預取技術，且機器處于“開中斷”狀態(tài)，則在下列有關指令執(zhí)行的 每個指令周期中CPU每個指令周期一定大于或等于一個CPU時鐘周20．在系統(tǒng)總線的數(shù)據(jù)線上，．可能傳輸?shù)?C．握手（應答）信BD．中斷類型21．某計算機有五級中斷L4～L0，中斷屏蔽字為M4M3M2M1M0，Mi=1（0≤i≤4）表示對Li級中斷進行屏蔽。若中斷響應優(yōu)先級從高到低的順序是L4→L0→L2→L1→L3，則L1的中斷處理程序中設置的中斷屏蔽字 22．某計算機處理器主頻為50MHz，采用定時查詢方式控制設備AI/O，查詢程序運行一次所用的時鐘周期數(shù)至少為500A200CPU用于設備A的I/O的時間占整個CPU時間的百分比至少 23．下列選項中，滿足短任務優(yōu)先且不會發(fā)生饑餓現(xiàn)象的調度算法 C．時間片輪BD24．下列選項中，在用戶態(tài)執(zhí)行的 25．在支持多線程的系統(tǒng)中，進程A．進程P的代碼段CP創(chuàng)建的若干個線程不能共享的 BPDPP用戶程序發(fā)出磁盤I/O請求后，系統(tǒng)的正確處理流程是 25．在支持多線程的系統(tǒng)中，進程A．進程P的代碼段CP創(chuàng)建的若干個線程不能共享的 BPDPP用戶程序發(fā)出磁盤I/O請求后，系統(tǒng)的正確處理流程是 27此時的安全序列 D28．在缺頁處理過程中，操作系統(tǒng)執(zhí)行的操作可能 29．當系統(tǒng)發(fā)生抖動（thrashing）時，可以采取的有效措施 A30．在虛擬內(nèi)存管理中地址變換機構將邏輯地址變換為物理地址形成該邏輯地址的階段 31．某文件占10個磁盤塊，現(xiàn)要把該文件磁盤塊逐個讀入主存緩沖區(qū)，并送用戶區(qū)進行分析，假設一個緩沖區(qū)與一個磁盤塊大小相同，把一個磁盤塊讀入緩沖區(qū)的時間為100s，將緩沖區(qū)的數(shù)據(jù)傳送到用戶區(qū)的時間是50s，CPU對一塊數(shù)據(jù)進行分析的時間為50s。在單緩沖區(qū)和雙緩沖區(qū)結構下，讀入并分析完該文件的時間分別 A．1500s、C．1550s、B．1550s、D．2000s、32．有兩個并發(fā)執(zhí)行的進P1P2，共享初值1的變x。P1x1，P2x111//1操作loadR1,xincR1store//減1操作loadR2，xdecR2store//R1兩個操作完成后，x的 A．可能為-1B．只能為200001021120132011131001200C0、1D．可能為-1、0、1或參考模型的網(wǎng)絡層提供的 34．若某通信鏈路的數(shù)據(jù)傳輸速率D．有連接可靠的虛電路服2400bit/s，采 相位調制C0、1D．可能為-1、0、1或參考模型的網(wǎng)絡層提供的 34．若某通信鏈路的數(shù)據(jù)傳輸速率D．有連接可靠的虛電路服2400bit/s，采 相位調制，則該鏈路的波特率 A．600B．1200C．4800D．960035．數(shù)據(jù)鏈路層采用選擇重傳協(xié)議（SR）傳輸數(shù)據(jù)，發(fā)送方已發(fā)送了0～3號數(shù)據(jù)幀，現(xiàn)已收到號幀的確認，而0、2。36．下列選項中，對正確接收到的數(shù)據(jù)幀進行確認。37R1/24R1IP組正確地路由到圖中所有的子網(wǎng)，則在 中需要增加的一條路由（目的網(wǎng)絡，子網(wǎng)掩碼，下一跳A．38．在子網(wǎng)/30中，能接收目的地址為的IP分組的最大主機數(shù) 主機甲向主機乙發(fā)送一個（SYN=1，seq=1220）的TCP段，期望與主機乙建立TCP連接，若主機乙接受該連接請求，則主機乙向主機甲發(fā)送的正確的TCP段可能是 。B．（SYN=1，ACK=1，seq=11220，ack=11220）主機甲與主機乙之間已建立一個TCP連接，主機甲向主機乙發(fā)送了3個連續(xù)的TCP段，分別300B、400B500B390013個段，則主機乙發(fā)送給主機甲的確認序號 70小題，共41．（8分）6個頂點（頂點編號為0～5）的有向帶權圖G，其鄰接矩陣A按行為主序（行優(yōu)先）46∞∞∞5∞∞∞43∞∞33G的鄰接矩陣A畫出有向帶權圖G求圖G42（15若序列S1=（11，13，15，17，19），則S1的中位數(shù)是15，兩個序列的中位數(shù)是含它們所G的鄰接矩陣A畫出有向帶權圖G求圖G42（15若序列S1=（11，13，15，17，19），則S1的中位數(shù)是15，兩個序列的中位數(shù)是含它們所有元素的升序序列的中位數(shù)。例如，若S2=（2，4，6，8，20）S1S2的中位數(shù)是11?，F(xiàn)在有兩個等長升序序AB，試設計一個在時間和空間兩方面都盡可能高效的算法，找出兩個序列AB的中位數(shù)。要求：C或C++或JAVA43．（11分）假定在一個8位字長的計算機中運行如下C程序unsignedintunsignedintintm=x;intn=y;unsignedintunsignedintintk1=m-n;int若編譯88位寄存器R1～R8分別分配給變量x、y、m、n、z1、z2、k1k2執(zhí)行上述程序段后，寄存器R1、執(zhí)行上述程序段后，變量m和和R6的內(nèi)容分別是什么（用十六進制表示的值分別是多少（用十進制表示上述程序段涉及帶符號整數(shù)加/減、無符號整數(shù)加/減運算，這四種運算能否利用同一個加法器輔助電路實現(xiàn)？簡述理由。計算機內(nèi)部如何判斷帶符號整數(shù)加/減運算的結果是否發(fā)生溢出？上述程序段中，哪些帶符號整數(shù)運算語句的執(zhí)行結果會發(fā)生溢出？44．（12分）某計算機存儲器按字節(jié)編址，虛擬（邏輯）地址空間大小為16MB，主存（物理）空間大小為1MB，頁面大小為4KB；Cache采用直接映射方式，共行；主存與Cache之間交換的塊大為32B。系統(tǒng)運行到某一時刻時，頁表的部分內(nèi)容和的部分內(nèi)容分別如題44-圖、題44-012345670123456744-a44-b圖Cache10—11110—111110—10—1虛擬地址共有幾位，哪幾位表示虛頁號？物理地址共有幾位，哪幾位表示頁框號（物理頁號使用物理地址訪問Cache時，物理地址應劃分成哪幾個字段？要求說明每個字段的位數(shù)及在物001C60H所在的頁面是否在主存中？若在主存中，則該虛擬地址對應的物理地址是什么？訪問該地址時是否Cache命中？要求說明理由。4TLB共可存放8個頁表項，若其當前內(nèi)容（十六進制）44-虛擬地址共有幾位，哪幾位表示虛頁號？物理地址共有幾位，哪幾位表示頁框號（物理頁號使用物理地址訪問Cache時，物理地址應劃分成哪幾個字段？要求說明每個字段的位數(shù)及在物001C60H所在的頁面是否在主存中？若在主存中，則該虛擬地址對應的物理地址是什么？訪問該地址時是否Cache命中？要求說明理由。4TLB共可存放8個頁表項，若其當前內(nèi)容（十六進制）44- 圖所示，則此時虛擬地 所在的頁面是否存在主存中？要求說明理由組號有效位標記頁框號有效位標記頁框號有效位標記頁框號有效位標記頁框號0144-c圖TLB45（8分）某銀行提供1個服務窗口和10個供顧客等待的座位。顧客到達銀行時，若有空座位，則到取號機上領取一個號，等待叫號。取號機每次僅允許一位顧客使用。當營業(yè)員空閑時，通過叫號選取一位顧客，并為其服務。顧客和營業(yè)員的活動過程描述如下：{process{}process{{}}請?zhí)砑颖匾男盘柫亢蚉、（wait()、signal()）操作，實現(xiàn)上述過程中的互斥與同步。要求寫出完整的過程，說明信號量的含義并賦初值。46（7分）某文件系統(tǒng)為一級目錄結構，文件的數(shù)據(jù)一次性寫入磁盤，已寫入的文件不可修改，但可多次創(chuàng)建新文件。請回答如下問題。在連續(xù)、鏈式、索引三種文件的數(shù)據(jù)塊組織方式中，哪種更合適？要求說明理由。為定位文件數(shù)據(jù)塊，需要FCB中設計哪些相關描述字段？為快速找到文件，對于FCB，是集中存儲好，還是與對應的文件數(shù)據(jù)塊連續(xù)存儲好？要求說明47．（9分）某主機的MAC00-15-C5-C1-5E-28，IP00（私有地址。題47-圖是網(wǎng)絡拓撲47-b圖是該主機進行Web請求的1個以太網(wǎng)數(shù)據(jù)幀前80B的十六進制及ASCII碼內(nèi)容0——10——110——10——47-a圖網(wǎng)絡拓撲47-a圖網(wǎng)絡拓撲c5c15e28080045 b...P.. ......GET/rfc.htmlHTTPba9d0a026447-b以太網(wǎng)數(shù)據(jù)幀（WebIPMAC