2020年計(jì)算機(jī)408統(tǒng)考真題

2020第01~40小題，每小題2分，共80將一個IOxlO對稱矩陣M的上三角部分的元素mt,l(l<i冬i:s;10)按列優(yōu)先存入C語言的 B. C. D.對空棧S進(jìn)行Push和Pop操作，入棧序列為a,b,c,d,e,經(jīng)過Push,Push,Pop,Push,Pop,Push,Push,Pop操作后得到的出棧序列是( B. C. D.b,c,對千任意一棵高度為5且有10個結(jié)點(diǎn)的二叉樹，若采用順序存儲結(jié)構(gòu)保存，每個結(jié)點(diǎn)占個存儲單元（僅存放結(jié)點(diǎn)的數(shù)據(jù)信息），則存放該二叉樹需要的存儲單元數(shù)暈至少是 )A. B. C. D.已知森林F及與之對應(yīng)的二叉樹T,若F的先根遍歷序列是a,b,cd,e,f,b,a,d,f,e,c,則T的后根遍歷序列是（）b,a,d,f,e, B.b,d,f,e,c, C.b,f,e,d,c, D.f,e,d,c,b,下列給定的關(guān)鍵字輸入序列中，不能生成如下二叉排序樹的是（）4,5,2,1,C.4,2,5,3,

D.4,2,1,3,若輸出結(jié)果中包含G中的全部頂點(diǎn)，則輸出的頂點(diǎn)序列是G的（）。拓?fù)溆行蛐?B.逆拓?fù)溆行蛐駽.廣度優(yōu)先搜索序 D.深度優(yōu)先搜索序已知無向圖G如下所示，使用克魯斯卡爾(Kruskal)算法I求圖G的最小生成樹，加到最小生成樹中的邊依次是()。(b,f),(b,d),(a,e),(c,e),(b,(b,f),(b,d),(b,e),(a,e),(c,(a,e),(b,e),(c,e),(b,d),(a,e),(c,e),(b,e),(b,f),(b,若使用AOE網(wǎng)估算工程進(jìn)度，則下列敘述中正確的是(D.縮短任一關(guān)鍵活動的時間將會縮短工程的工下列關(guān)千大根堆（至少含2個元素）的敘述中，正確的是（） C.僅1、11和IVD.I、III和IV依次將關(guān)鍵字5,6,9,13,8,2,12,15插入初始為空的4階B曰（）A. B. C.8, D.9,對大部分元素已有序的數(shù)組進(jìn)行排序時，直接插入排序比簡單選擇排序效率更高，其原因是()。A.僅 B.僅 C.僅I、 D.I、II和下列給出的部件中，其位數(shù)（寬度）一定與機(jī)器字長相同的是（） II.III.IV.浮A.僅I、B.僅I、C.僅II、D.僅II、III、已知帶符號整數(shù)用補(bǔ)碼表示，float型數(shù)據(jù)用IEEE754標(biāo)準(zhǔn)表示，假定變量x的類型只可能是int或float，當(dāng)x的機(jī)器數(shù)為C800OOOOH時，x的值可能是( )。- B.- c. D.Structshor七 )若a的首地址為2020FEOOH,a的成員變量x2的機(jī)器數(shù)為1234OOOOH,則其中34H所在 ?022A.2020 B.2020 C.2020 D.2020下列關(guān)千TLB和Cache的敘述中，錯誤的是（）命中率都與程序局部性有 B.缺失后都需要去訪問主C.缺失處理都可以由硬件實(shí) D.都由DRAM存儲器組某計(jì)算機(jī)采用16位定長指令字格式，操作碼位數(shù)和尋址方式位數(shù)固定，指令系統(tǒng)有48條指令，支持直接、間接、立即、相對4種尋址方式。單地址指令中，直接尋址方式的可尋址范圍是()。 B. C.- D.-下列給出的處理器類型中，理想情況下，CPI為l的是（）II.多周期III.基本流水線 IV.超標(biāo)量流水線A.僅I、B.僅I、C.僅II、 D.僅III、下列關(guān)于“自陷"(Trap,也稱陷阱）的敘述中，錯誤的是 )QPI總線是一種點(diǎn)對點(diǎn)全工同步串行總線，總線上的設(shè)備可同時接收和發(fā)送信息，每個方向可同時傳輸20位信息(16位數(shù)據(jù)＋4位校驗(yàn)位），每個QPI數(shù)據(jù)包有80位信息，分2個時鐘周期傳送，每個時鐘周期傳遞2次。因此，QPI總線帶寬為：每秒傳送次數(shù)x2Bx2。若QPI時鐘頻率為2.4GHz,則總線帶寬為()。 B. C. D.下列事件中，屬千外部中斷事件的是I.訪存時缺 II.定時器到

III.A.僅I、 B.僅I、 C.僅II、 D.I、II和D.若設(shè)備采用周期挪用DMA方式進(jìn)行輸入和輸出，每次DMA傳送的數(shù)據(jù)塊大小為512字節(jié)，相應(yīng)的1/0接口中有一個32位數(shù)數(shù)據(jù)緩沖寄存器。對千數(shù)據(jù)輸入過程，下列敘述中，錯誤的是()。?023B.相對千CPU,DMA控制器的總線使用權(quán)的優(yōu)先級更高若多個進(jìn)程共享同一個文件F,則下列敘述中，正確的是 )各進(jìn)程只能用“讀”方式打開文件在系統(tǒng)打開文件表中僅有一個表項(xiàng)包含F(xiàn)的屬性C.D.進(jìn)程關(guān)閉F時，系統(tǒng)刪除F下列選項(xiàng)中，支持文件長度可變、隨機(jī)訪問的磁盤存儲空間分配方式是 )A.索引分 B.鏈接分 C.連續(xù)分 D.動態(tài)分區(qū)分下列與中斷相關(guān)的操作中，由操作系統(tǒng)完成的是 ) A.僅1、 B.僅I、II、 C.僅III、 D.僅II、III、下列與進(jìn)程調(diào)度有關(guān)的因素中，在設(shè)計(jì)多級反饋隊(duì)列調(diào)度算法時需要考慮的是（）I.就緒隊(duì)列的數(shù) II.就緒隊(duì)列的優(yōu)先III.各就緒隊(duì)列的調(diào)度算 IV.進(jìn)程在就緒隊(duì)列間的遷移條A.僅I、 B.僅III、 C.僅II、III、 D.I、II、III和某系統(tǒng)中有A、B兩類資源各6個，tA已分配數(shù)B已分配數(shù)AA已分配數(shù)B已分配數(shù)A需求總量IB需求總23 442I3l|I23t時刻安全性檢測結(jié)果是（)

存在安全序列P2、Pl、D.下列因素中，影響請求分頁系統(tǒng)有效（平均）訪存時間的是（） A.僅II、 B.僅I、 C.僅I、III、 D.I、II、III和下列關(guān)千父進(jìn)程與子進(jìn)程的敘述中，錯誤的是 )?024父進(jìn)程與子進(jìn)程不能同時使用同一對千具備設(shè)備獨(dú)立性的系統(tǒng)，下列敘述中，錯誤的是（）某文件系統(tǒng)的目錄項(xiàng)由文件名和索引結(jié)點(diǎn)號構(gòu)成。若每個目錄項(xiàng)長度為64字節(jié)，其中4字節(jié)存放索引結(jié)點(diǎn)號，60字節(jié)存放文件名。文件名由小寫英文字母構(gòu)成，則該文件系統(tǒng)能創(chuàng)建的文件數(shù)量的上限為()。 B. C. D.下列準(zhǔn)則中，實(shí)現(xiàn)臨界區(qū)互斥機(jī)制必須遵循的是（） IV.不能進(jìn)入臨界區(qū)的執(zhí)行態(tài)進(jìn)程立即放棄A.僅I、 B.僅II、 C.僅I、II、 D.僅I、III、下圖描述的協(xié)議要素是（）發(fā)送 接收I.A.僅

II.語B.僅

III.C.僅 D.I、II和下列關(guān)千虛電路網(wǎng)絡(luò)的敘述中，錯誤的是 )需c.D.依據(jù)虛電路號(VCID)在下圖所示的網(wǎng)絡(luò)中，沖突域和廣播域的個數(shù)分別是（）?025以太網(wǎng)交換 路由 B. C. D.假設(shè)主機(jī)甲采用停－等協(xié)議向主機(jī)乙發(fā)送數(shù)據(jù)幀，數(shù)據(jù)幀長與確認(rèn)幀長均為1000B,數(shù)據(jù)傳輸速率是10kbps,單項(xiàng)傳播延時是200ms。則甲的最大信道利用率為（）。 B. C. D.某IEEE802.11無線局域網(wǎng)中，主機(jī)H與AP之間發(fā)送或接收CSMA/CA幀的過程如下圖所示。在H或AP發(fā)送幀前所等待的幀間間隔時間(IFS)中，最長的是（）。 S

C. D.若主機(jī)甲與主機(jī)乙已建立一條TCP連接，最大段長(MSS)為1KB,往返時間(RTT) )A. B. C. D.若主機(jī)甲與主機(jī)乙建立P連接時，發(fā)送的SN段中的序號為1000,在斷開連接時，甲發(fā)送給乙的FIN段中的序號為5001,則在無任何重傳的情況下，甲向乙已經(jīng)發(fā)送的應(yīng)用層數(shù)據(jù)的字節(jié)數(shù)為()。?026 B. C. D.假設(shè)下圖所示網(wǎng)絡(luò)中的本地域名服務(wù)器只提供遞歸查詢服務(wù)，其他域名服務(wù)器均只提供迭代查詢服務(wù)；局域網(wǎng)內(nèi)主機(jī)訪間Internet上各服務(wù)器的往返時間(RTT)均為Oms,忽略其他各種時延。若主機(jī)H通過超鏈接hp:///index.hml請求瀏覽純文本W(wǎng)eb頁ndx.h,則從點(diǎn)擊超鏈接開始到瀏覽器接收到ndx.h頁面為止，所需的最短時間與最長時間分別是（）。、com B.!Oms, C.20ms, D.20ms,第41~47小題，共70分(13分）定義三元組(a,b,)（其中,b,c均為正數(shù)）的距離D=a-bl+b-l+e-a|。給定3個非空整數(shù)集合S!、＆和S3,按升序分別存儲在3個數(shù)組中。設(shè)計(jì)一個盡可能高效的算法，計(jì)算并輸出所有可能的三元組(a,b,)(,bES2,S3)中的最小距離。例如S1={-1,0,9},S2={-25,-10,10,11},S3={2,9,17,30,41}，則最小距離為2,相應(yīng)的三(9,10,9)。要求l)給出算法的基本設(shè)計(jì)思想根據(jù)設(shè)計(jì)思想，采用C或C+＋語言C10分）若任一現(xiàn)有某字符集（字符個數(shù)?2)的不等長編碼，每個字符的編碼均為二進(jìn)制的0、1序列，砐長為L位，且具有前綴特性。謂回答下列問題：l)(13分）有實(shí)現(xiàn)xxy的兩個C語言函數(shù)如下unsignedumul(unsignedx,unsignedy) {returnx*y;} imul(intx,inty) {returnx*y;}假定某計(jì)算機(jī)M中ALU只能進(jìn)行加減運(yùn)算和邏輯運(yùn)算。請回答下列問題?027l)若M的指令系統(tǒng)中沒有乘法指令，但有加法、減法和位移等指令，則在M上也能實(shí)現(xiàn)上述兩個函數(shù)中的乘法運(yùn)算，為什么？若M的指令系統(tǒng)中有乘法指令，則基千ALU、位移器、寄存器以及相應(yīng)控制邏輯實(shí)現(xiàn)乘法指令時，控制邏輯的作用是什么？針對以下三種情況：＠沒有乘法指令；＠有使用ALU和位移器實(shí)現(xiàn)的乘法指令n位整數(shù)乘法指令可保存2n位乘積，當(dāng)僅取低n位作為乘積時，其結(jié)果可能會發(fā)生溢出。當(dāng)n=32,x=231-1,y=2時，帶符號整數(shù)乘法指令和無符號整數(shù)乘法指令得到的歡y的2n位乘積分別是什么（用十六進(jìn)制表示）？此時函數(shù)umul(）和imul(）果是否溢出？對千無符號整數(shù)乘法運(yùn)算，當(dāng)僅取乘積的低n位作為乘法結(jié)果時，如何用2n位乘積進(jìn)行溢出判斷？(10分）假定主存地址為32位，按字節(jié)編址，指令Cache和數(shù)據(jù)Cache8路組相聯(lián)映射方式，直寫(WriteThrough)寫策略和LRU替換算法，主存塊大小為數(shù)據(jù)區(qū)容量各為32KB。開始時Cache均為空。請Cache每一行中標(biāo)記(Tag)、LRU位各有如下C (k=0;k<1024;k++)若數(shù)組s及其變量k均為int型，int型數(shù)據(jù)占4B,變量K分配在寄存器中，數(shù)組s在主存中的起始地址為0080OOCOH,則該程序段執(zhí)行過程中，訪問數(shù)組s的數(shù)據(jù)Che缺失次數(shù)為多少？若CPU最先開始的訪問操作是讀取主存單元00010003H中的指令，簡要說明從中訪問該指令的過程，包括Cache缺失處理過程7分）現(xiàn)有5個操作A、B、C、D和E,操作C必須在A和B完成后執(zhí)行，操作E必須在C和D完成后執(zhí)行，請使用信號量的wait(）、signal(）操作(P、V操作）描述上述操作之間的同步關(guān)系，并說明所用信號量及其初值。(8分）某32位系統(tǒng)采用基千二級頁表的請求分頁存儲管理方式，按字節(jié)編址，頁目錄項(xiàng)和頁表項(xiàng)長度均為4字節(jié)，虛擬地址結(jié)構(gòu)如下所示。頁目錄號(10位 頁號(10位 頁內(nèi)偏移量(12位某C程序中數(shù)組a[1024][1024]的起始虛擬地址為1080OOOOH,數(shù)組元素占4字節(jié)，該程序運(yùn)行時，其進(jìn)程的頁目錄起始物理地址為00201000H,請回答下列問題。)數(shù)組元素[l][2]的虛擬地址是什么？對應(yīng)的頁目錄號和頁號分別是什么？對應(yīng)的頁目錄項(xiàng)的物理地址是什么？若該目錄項(xiàng)中存放的頁框號為00301H,則[1][2]所在頁對應(yīng)的頁表項(xiàng)的物理地址是什么？?028已知數(shù)組按行優(yōu)先方式存放，若對數(shù)組分別按行遍歷和按列遍歷，則哪種遍歷方式的局部性更好？(9分）某校園網(wǎng)有兩個局域