計(jì)算機(jī)綜合2021年真題

2021年真題408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)研PDF:YanPDF.COM注：【】內(nèi)為本題同類知識(shí)點(diǎn)歷年考頻信息一、選擇題本大題共40小題，共80分。[1]已知頭指針h指向一個(gè)帶頭結(jié)點(diǎn)的非空單循環(huán)鏈表，結(jié)點(diǎn)結(jié)構(gòu)為如下圖，其中next是指向直接后繼結(jié)點(diǎn)的指針，P是尾指針，q是臨時(shí)指針?，F(xiàn)要?jiǎng)h除該鏈表的第一個(gè)元素，正確的語句序列是 Odatanexth->next=h->next->next;q=h->next;free(q);B.q=h->next;h->next=h->next->next；free(q);q=h->next;h->next=q->next;if(p!=q)p=h；free(q);q=h->next;h->next=q->next;if(p==q)p=h;free(q);[2]已知初始為空的隊(duì)列Q的一端僅能進(jìn)行入隊(duì)操作，另外一端既能進(jìn)行人隊(duì)操作又能進(jìn)行出隊(duì)操作。若Q的入隊(duì)序列是1、2、3、4、5,則不能得到的出隊(duì)序列是一oA.5,4,3,1,2B.5,3,1,2,4 C.4,2,1,3,5 D.4,1,3,2,5[4]已知二維數(shù)組A按行優(yōu)先方式存儲(chǔ)，每個(gè)元素占用1個(gè)存儲(chǔ)單元。若元素A[0][0]的存儲(chǔ)地址是100,A[3][3]的存儲(chǔ)地址是220,則元素A[5][5]的存儲(chǔ)地址是一。A.295 B.300 C.301 D.306[3]某森林F對(duì)應(yīng)的二叉樹為T,若T的先序遍歷序列是a,b,d,c,e,g,f,中序遍歷序列是b,d,a,e,g,c,f,則F中樹的棵數(shù)是 。A.1 B.2 C.3 D.4(9】若某二叉樹有5個(gè)葉結(jié)點(diǎn)，其權(quán)值分別為10,12,16,21,30則其最小的帶權(quán)路徑長度(WPL)是一oA.89 B.200 C.208 D.289[7]給定平衡二叉樹如下圖所示，插入關(guān)鍵字23后，根中的關(guān)鍵字是一oA.16B.20C.23A.16B.20C.23D.25[7]給定如下有向圖，該圖的拓?fù)溆行蛐蛄械膫€(gè)數(shù)是―。A.1 B.2 C.3 D.4I5]使用Dijkstra算法求下圖中從頂點(diǎn)1到其余各頂點(diǎn)的最短路徑，將當(dāng)前找到的從頂點(diǎn)1到頂點(diǎn)2,3,4,5的最短路徑長度保存在數(shù)組dist中，求出第二條最短路徑后，dist中的內(nèi)容更新為一。A.26,3,14,6B.25,3,14,6 C.21,3,14,6D.15,3,14,6【8】在一棵高度為3的3階B樹中，根為第1層，若第2層中有4個(gè)關(guān)鍵字，則該樹的結(jié)點(diǎn)個(gè)數(shù)最多是A.11 B.10 C.9 D.8[4]設(shè)數(shù)組S[]={93,946,372,9,146,151,301,485,236,327,43,892},采用最低位優(yōu)先(LSD)基數(shù)排序?qū)排列成升序序列。第1趟分配、收集后，元素372之前、之后緊鄰的元素分別是―。A.43,892 B.236,301 C.301,892 D.485,301[9]將關(guān)鍵字6,9,1,5,8,4,7依次插入到初始為空的大根堆H中，得到的H是A.9,8,7,6,5,4,1 B.9,8,7,5,6,1,4C.9,8,7,5,6,4,1 D.9,6,7,5,8,4,1[3]2017年公布的全球超級(jí)計(jì)算機(jī)TOP500排名中，我國“神威?太湖之光”超級(jí)計(jì)算機(jī)蟬聯(lián)第一，其浮點(diǎn)運(yùn)算速度為93.0146PFLOPS,說明該計(jì)算機(jī)每秒鐘內(nèi)完成的浮點(diǎn)操作次數(shù)約為一A.9.3x1013次 B.9.3x1015次 C.9.3千萬億次 D.9.3億億次已知帶符號(hào)整數(shù)用補(bǔ)碼表示，變量x,y,z的機(jī)器數(shù)分別為FFFDH,FFDFH,7FFCH下列結(jié)論中,正確的是——oA.若x,y和z為無符號(hào)整數(shù)，則z<rr<yB.若x,y和z為無符號(hào)整數(shù)，則工<y<zC.若x,y和z為帶符號(hào)整數(shù)，則r<y<zD.若x,y和z為帶符號(hào)整數(shù)，則g</<z.[7]下列數(shù)值中，不能用IEEE754浮點(diǎn)格式精確表示的是A.1.2 B.1.25 C.2.0 D.2.5.［5］某計(jì)算機(jī)的存儲(chǔ)器總線中有24位地址線和32位數(shù)據(jù)線，按字編址，字長為32位。如果000000H~3FFFFFH為RAM區(qū)，那么需要512Kx8位的RAM芯片數(shù)為一。A.8 B.16 C.32 D.64.［8］若計(jì)算機(jī)主存地址為32位，按字節(jié)編址，Cache數(shù)據(jù)區(qū)大小為32KB,主存塊大小為32B,采用直接映射方式和回寫（WriteBack）策略，則Cache行的位數(shù)至少是一。A.275 B.274 C.258 D.257.［4］下列寄存器中，匯編語言程序員可見的―。.指令寄存器 H.微指令寄存器 UL基址寄存器 IV.標(biāo)志/狀態(tài)寄存器A.僅I、II b.僅I、iv c.僅n、iv d.僅in、iv13］下列關(guān)于數(shù)據(jù)通路的敘述中，錯(cuò)誤的是—。A.數(shù)據(jù)通路包含ALU等組合邏輯（操作）元件B.數(shù)據(jù)通路包含寄存器等時(shí)序邏輯（狀態(tài)）元件C.數(shù)據(jù)通路不包含用于異常事件檢測及響應(yīng)的電路D.數(shù)據(jù)通路中的數(shù)據(jù)流動(dòng)路徑由控制信號(hào)進(jìn)行控制19.［15］下列關(guān)于總線的敘述中，錯(cuò)誤的是一。A.總線是在兩個(gè)或多個(gè)部件之間進(jìn)行數(shù)據(jù)交換的傳輸介質(zhì)B.同步總線由時(shí)鐘信號(hào)定時(shí)，時(shí)鐘頻率不一定等于工作頻率C.異步總線由握手信號(hào)定時(shí)，一握手過程完成一位數(shù)據(jù)交換D.突發(fā)（Burst）傳送總線事務(wù)可以在總線上連續(xù)傳送多個(gè)數(shù)據(jù)20,下列選項(xiàng)中，不屬于I/O接口的是一。A.磁盤驅(qū)動(dòng)器 B.打印機(jī)適配器C.網(wǎng)絡(luò)控制器 D.可編程中斷控制器.［11］異常事件在當(dāng)前指令執(zhí)行過程中進(jìn)行檢測，中斷請(qǐng)求則在當(dāng)前指令執(zhí)行后進(jìn)行檢測。下列事件中，相應(yīng)處理程序執(zhí)行后，必須回到當(dāng)前指令重新執(zhí)行的是―。A.系統(tǒng)調(diào)用 B.頁缺失 C.DMA傳送結(jié)束 D.打印機(jī)缺紙.下列是關(guān)于多重中斷系統(tǒng)中CPU響應(yīng)中斷的敘述，其中錯(cuò)誤的是_。A.僅在用戶態(tài)（執(zhí)行用戶程序）下，CPU才能檢測和響應(yīng)中斷CPU只有在檢測到中斷請(qǐng)求信號(hào)后，才會(huì)進(jìn)入中斷響應(yīng)周期C.進(jìn)入中斷響應(yīng)周期時(shí)，CPU一定處于中斷允許（開中斷）狀態(tài)D.若CPU檢測到中斷請(qǐng)求信號(hào)，則一定存在未被屏蔽的中斷源請(qǐng)求信號(hào).下列指令中，只能在內(nèi)核態(tài)執(zhí)行的是―。A.trap指令 B.I/O指令 C.數(shù)據(jù)傳送指令 D.設(shè)置斷點(diǎn)指令.［1］下列操作中，操作系統(tǒng)在創(chuàng)建新進(jìn)程時(shí)，必須完成的是.申請(qǐng)空白的進(jìn)程控制塊n.初始化進(jìn)程控制塊in.設(shè)置進(jìn)程狀態(tài)為執(zhí)行態(tài)A.僅I b.僅I、n c.僅I、hi d.僅n、ni.【5】下列內(nèi)核的數(shù)據(jù)結(jié)構(gòu)或程序中，分時(shí)系統(tǒng)實(shí)現(xiàn)時(shí)間片輪轉(zhuǎn)調(diào)度需要使用的是―。.進(jìn)程控制塊n.時(shí)鐘中斷處理程序in.進(jìn)程就緒隊(duì)列iv.進(jìn)程阻塞隊(duì)列A.僅H、Hl B.僅I、IV C.僅I、11、Hl D.僅1、11、IV.[12]某系統(tǒng)中磁盤的磁道數(shù)為200(0-199),磁頭當(dāng)前在184號(hào)磁道上。用戶進(jìn)程提出的磁盤訪問請(qǐng)求對(duì)應(yīng)的磁道號(hào)依次為184,187,176,182,199。若采用最短尋道時(shí)間優(yōu)先調(diào)度算法(SSTF)完成磁盤訪問，則磁頭移動(dòng)的距離(磁道數(shù))是一。A.37 B.38 C.41 D.4210)下列事件中，可能引起進(jìn)程調(diào)度程序執(zhí)行的是―。.中斷處理結(jié)束 U.進(jìn)程阻塞 HL進(jìn)程執(zhí)行結(jié)束 IV.進(jìn)程的時(shí)間片用完A.僅I、III B.僅n、IV C.III,IV D.I、H、III和IV.[19]某請(qǐng)求分頁存儲(chǔ)系統(tǒng)的頁大小為4KB,按字節(jié)編址。系統(tǒng)給進(jìn)程P分配2個(gè)固定的頁框,并采用改進(jìn)型Clock置換算法，進(jìn)程P頁表的部分內(nèi)容如下表所示。若P訪問虛擬地址為02A01H的存儲(chǔ)單元，則經(jīng)地址變換后得到的物理地址是一。頁號(hào)2戶；存在位1：存在，0：不存在訪問位1：訪問，0未訪問修改位1：修改，0：未修改220H000360H110480H111A.00A01H B.20A01H C.60A01H D.80A01H.[20]在采用二級(jí)頁表的分頁系統(tǒng)中，CPU頁表基址寄存器中的內(nèi)容是A.當(dāng)前進(jìn)程的一級(jí)頁表的起始虛擬地址B.當(dāng)前進(jìn)程的一級(jí)頁表的起始物理地址C.當(dāng)前進(jìn)程的二級(jí)頁表的起始虛擬地址D.當(dāng)前進(jìn)程的二級(jí)頁表的起始物理地址.[4]若目錄dir下有文件filel,則為刪除該文件內(nèi)核不必完成的工作是一。A.刪除filel的快捷方式B.釋放filel的文件控制塊C.釋放filel占用的磁盤空間D.刪除目錄dir中與filel對(duì)應(yīng)的目錄項(xiàng).[4]若系統(tǒng)中有n(n22)個(gè)進(jìn)程，每個(gè)進(jìn)程均需要使用某類臨界資源2個(gè)，則系統(tǒng)不會(huì)發(fā)生死鎖所需的該類資源總數(shù)至少是—OA.2 B.n C.n+1 D.2n.[4]下列選項(xiàng)中，通過系統(tǒng)調(diào)用完成的操作是―。A.頁置換 B.進(jìn)程調(diào)度 C.創(chuàng)建新進(jìn)程 D.生成隨機(jī)整數(shù).[3]在TCP/IP參考模型中，由傳輸層相鄰的下一層實(shí)現(xiàn)的主要功能是一。A.對(duì)話管理 B.路由選擇C.端到端報(bào)文段傳輸 D.結(jié)點(diǎn)到結(jié)點(diǎn)流量控制.[3]若下圖為一段差分曼徹斯特編碼信號(hào)波形，則其編碼的二進(jìn)制位串是―。A.10111001 B.11010001 C.00101110 D.10110110.[6]現(xiàn)將一個(gè)IP網(wǎng)絡(luò)劃分為3個(gè)子網(wǎng)，若其中一個(gè)子網(wǎng)是192.1689128/26,則下列網(wǎng)絡(luò)中,不可能是另外兩個(gè)子網(wǎng)之一的是一。A./25 B./26C.92/26 D.92/27.[2]若路由器向MTU=800B的鏈路轉(zhuǎn)發(fā)一總長度為1580B的1P數(shù)據(jù)報(bào)（首部長度為20B）時(shí),進(jìn)行了分片，且每個(gè)分片盡可能大，則第2個(gè)分片的總長度字段和MF標(biāo)志位的值分別是A.796,0 B.796,1 C.800,0 D.800,1.[3]某網(wǎng)絡(luò)中的所有路由器均采用距離向量路由算法計(jì)算路由。若路由器E與鄰居路由器A,B,C和D之間的直接鏈路距離分別是8,10,12和6,且E收到鄰居路由器的距離向量如下表所示，則路由器E更新后的到達(dá)目的網(wǎng)絡(luò)Netl?Net4的距離分別是_。目的網(wǎng)絡(luò)A的距離向量B的距離向量c的距離向量D的距離向量Netl1232022Net212353028Net324181636Net43630824A.9,10,12,6B.9,10,28,20C.9,20,12,20D.9,20,28,20.[3]若客戶首先向服務(wù)器發(fā)送FIN段請(qǐng)求斷開TCP連接，則當(dāng)客戶收到服務(wù)器發(fā)送的FIN段并向服務(wù)器發(fā)送了ACK段后，客戶的TCP狀態(tài)轉(zhuǎn)換為A.CLOSE_WA1TB.T1ME.WA1T C.F1N_WA1T_1 D.F1N_WA1T_2.[5]若大小為12B的應(yīng)用層數(shù)據(jù)分別通過1個(gè)UDP數(shù)據(jù)報(bào)和1個(gè)TCP段傳輸，則該UDP數(shù)據(jù)報(bào)和TCP段實(shí)現(xiàn)的有效載荷（應(yīng)用層數(shù)據(jù)）最大傳輸效率分別是—oA.37.5%,16.7%B.37.5%,37.5%C.60.0%,16.7% D.60.0%,37.5%.設(shè)主機(jī)甲通過TCP向主機(jī)乙發(fā)送數(shù)據(jù)，部分過程如下圖所示甲在t0時(shí)刻發(fā)送一個(gè)序號(hào)seq=501、封裝200B數(shù)據(jù)的段，在力1時(shí)刻收到乙發(fā)送的序號(hào)seq=601、確認(rèn)序號(hào)ack_seq=501。接收窗口rcvwnd=500B的段，則甲在未收到新的確認(rèn)段之前，可以繼續(xù)向乙發(fā)送的數(shù)據(jù)序號(hào)范圍是一。A.501~1000 B.601?1100 C.701~1000 D.801?1100二、簡答題本大題共7小題，共70分。.[6](15分)已知無向連通圖G由頂點(diǎn)集V和邊集E組成，|E|>0,當(dāng)G中度為奇數(shù)的頂點(diǎn)個(gè)數(shù)為不大于2的偶數(shù)時(shí)，G存在包含所有邊且長度為|E|的路徑(稱為EL路徑)。設(shè)圖G采用鄰接矩陣存儲(chǔ)，類型定義如下：typedefstruct{//圖的定義intnumVertices,numEdges；//圖中實(shí)際的項(xiàng)點(diǎn)數(shù)和邊數(shù)charVerticesList[MAXV];//頂點(diǎn)表。MAXV為已定義常量intEdge[MAXV][MAXV];//鄰接矩陣}MGraph;請(qǐng)?jiān)O(shè)計(jì)算法intlsExistEL(MGraphG),判斷G是否存在EL路徑，若存在，則返回1,否則返回0o要求：(1)給出算法的基本設(shè)計(jì)思想。(2)根據(jù)設(shè)計(jì)思想，采用C或C++語言描述算法，關(guān)鍵之處給出注釋。(3)說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。.[8](8分)已知某排序算法如下：voidcmpCountSort(inta[]/intb[],intn){intizj,*count;count=(int*)malloc(sizeof(int)*n);//C++語言：count=newint[n];for(i=0;i<n;i++)count[i]=0;for(i=0;i<n-l；i++)for(j=i+l;j<n；j++)if(a[i]<a[j])count[j]++；elsecount[i]++;for(i=0;i<n;i++)b[count[i]]-a[i];free(count);//C++語言：deletecount;}請(qǐng)回答下列問題。(1)若有inta[]={25,-10,25,10,11,19),b[6]；則調(diào)用cmpCountSort(a,b,6)后數(shù)組b中的內(nèi)容是什么？(2)若a中含有n個(gè)元素，則算法執(zhí)行過程中，元素之間的比較次數(shù)是多少？(3)該算法是穩(wěn)定的嗎？若是，則闡述理由；否則，修改為穩(wěn)定排序算法。.[16](15分)假定計(jì)算機(jī)M字長為16位，按字節(jié)編址，連接CPU和主存的系統(tǒng)總線中地址線為20位、數(shù)據(jù)線為8位，采用16位定長指令字，指令格式及其說明如下：格式6位2位2位2位4位指令功能或指令類型說明R型000000rsrtrdoplR[rd]-R[rs]oplR[rt]I型op2rsrtimm含ALU運(yùn)算、條件轉(zhuǎn)移和訪存操作3類指令J型op3targetPC的低10位一target其中，opl~op3為操作碼，rs,rt和rd為通用寄存器編號(hào)，R[r]表示寄存器r的內(nèi)容，imm為立即數(shù)，target為轉(zhuǎn)移目標(biāo)的形式地址。請(qǐng)回答下列問題。(l)ALU的寬度是多少位？可尋址主存空間大小為多少字節(jié)？指令寄存器、主存地址寄存器(MAR)和主存數(shù)據(jù)寄存器(MDR)分別應(yīng)有多少位？(2)R型格式最多可定義多少種操作？I型和J型格式總共最多可定義多少種操作？通用寄存器最多有多少個(gè)？(3)假定opl為0010和0011時(shí)，分別表示帶符號(hào)整數(shù)減法和帶符號(hào)整數(shù)乘法指令，則指令01B2H的功能是什么(參考上述指令功能說明的格式進(jìn)行描述)？若1,2,3號(hào)通用寄存器當(dāng)前內(nèi)容分別為B052H,0008H,0020H,則分別執(zhí)行指令01B2H和01B3H后，3號(hào)通用寄存器內(nèi)容各是什么？各自結(jié)果是否溢出？(4)若采用I型格式的訪存指令中imm(偏移量)為帶符號(hào)整數(shù)，則地址計(jì)算時(shí)應(yīng)對(duì)imm進(jìn)行零擴(kuò)展還是符號(hào)擴(kuò)展？(5)無條件轉(zhuǎn)移指令可以采用上述哪種指令格式？.[27](8分)假設(shè)計(jì)算機(jī)M的主存地址為24位，按字節(jié)編址；采用分頁存儲(chǔ)管理方式，虛擬地址為30位，頁大小為4KB；TLB采用2路組相聯(lián)方式和LRU替換策略，共8組。請(qǐng)回答下列問題。(1)虛擬地址中哪幾位表示虛頁號(hào)？哪幾位表示頁內(nèi)地址？(2)已知訪問TLB時(shí)虛頁號(hào)高位部分用作TLB標(biāo)記，低位部分用作TLB組號(hào)，M的虛擬地址中哪幾位是TLB標(biāo)記？哪幾位是TLB組號(hào)？(3)假設(shè)TLB初始時(shí)為空，訪問的虛頁號(hào)依次為10,12,16,7,26,4,12和20,在此過程中,哪一個(gè)虛頁號(hào)對(duì)應(yīng)的TLB表項(xiàng)被替換？說明理由。(4)若將M中的虛擬地址位數(shù)增加到32位，則TLB表項(xiàng)的位數(shù)增加幾位？.[9](7分)下表給出了整型信號(hào)量S的wait。和signal。操作的功能描述，以及采用開/關(guān)中斷指令實(shí)現(xiàn)信號(hào)量操作互斥的兩種方法。功能描述方法1方法2semaphoreS;semaphoreS;semaphoreS;waiMS){wait(S){wait(S){while(S<=0);關(guān)中斷;關(guān)中斷；S=S-1;while(S<=0);while(S<=0){)S=S-1;開中斷；開中斷；關(guān)中斷；signal(S){}}S=S+1;S=S-1;)signal(S){開中斷；關(guān)中斷；)S=S+1;signal(S){開中斷；關(guān)中斷；}S=S+1;開中斷；)請(qǐng)回答下列問題。(1)為什么在wait。和signalQ操作中對(duì)信號(hào)量S的訪問必須互斥執(zhí)行？(2)分別說明方法1和方法2是否正確。若不正確，請(qǐng)說明理由。(3)用戶程序能否使用開/關(guān)中斷指令實(shí)現(xiàn)臨界區(qū)互斥？為什么？.(8分)某計(jì)算機(jī)用硬盤作為啟動(dòng)盤，硬盤第一個(gè)扇區(qū)存放主引導(dǎo)記錄，其中包含磁盤引導(dǎo)程序和分區(qū)表。磁盤引導(dǎo)程序用于選擇要引導(dǎo)哪個(gè)分區(qū)的操作系統(tǒng)，分區(qū)表記錄硬盤上各分區(qū)的位置等描述信息。硬盤被劃分成若千個(gè)分區(qū)，每個(gè)分區(qū)的第一個(gè)扇區(qū)存放分區(qū)引導(dǎo)程序，用于引導(dǎo)該分區(qū)中的操作系