2023年考研計算機統(tǒng)考408真題

2023年考研計算機統(tǒng)考408真題單項選擇題以下函數(shù)的時間復(fù)雜度是 1。intfunc(intn){ inti=0;sum=0;while(sum<n)sum+=++i;returni;}O(logn)O(n1/2)O(n)O(nlogn)以下關(guān)于棧的表達中，錯誤的是 2。I.采用非遞歸方式重寫遞歸程序時必須使用棧II.函數(shù)調(diào)用時，系統(tǒng)要用棧保存必要的信息III.只要確定了入棧的次序，即可確定出棧次序IV.棧是一種受限的線性表，允許在其兩端進行操作僅I僅I、II、III僅I、III、IV僅II、III、IV適用于壓縮存儲稀疏矩陣的兩種存儲結(jié)構(gòu)是 3。三元組表和十字鏈表三元組表和鄰接矩陣十字鏈表和二叉鏈表鄰接矩陣和十字鏈表要使一棵非空二叉樹的先序序列與中序序列相同，其所有非葉結(jié)點須滿足的條件是 4。只有左子樹只有右子樹結(jié)點的度均為1結(jié)點的度均為2一棵二叉樹的樹形如以下圖所示，其后序序列為e,a,c,b,d,g,f，樹中與結(jié)點a同層的結(jié)點是 5。cdfg字符集{a,b,c,d,e,f,g,h}，假設(shè)各字符的哈夫曼編碼依次是0100,10,0000,0101,001,011,11,0001，那么編碼序列的譯碼結(jié)果是 6。acgabfhadbagbbafbeagdafeefgd無向圖G含有16條邊，其中度為4的頂點個數(shù)為3，度為3的頂點個數(shù)為4，其他頂點的度均小于3。圖G所含的頂點個數(shù)至少是 7。10111315以下二叉樹中，可能成為折半查找判定樹〔不含外部結(jié)點〕的是 8。以下應(yīng)用中，適合使用B+樹的是 9。編譯器中的詞法分析關(guān)系數(shù)據(jù)庫系統(tǒng)中的索引網(wǎng)絡(luò)中的路由表快速查找操作系統(tǒng)的磁盤空閑塊管理在內(nèi)部排序中，假設(shè)選擇了歸并排序而沒有選擇插入排序，那么可能的理由是 10。I.歸并排序的程序代碼更短II.歸并排序的占用空間更少III.歸并排序的運行效率更高僅II僅III僅I、II僅I、III以下排序方法中，假設(shè)將順序存儲更換為鏈式存儲，那么算法的時間效果會降低的是 11。I.插入排序II.選擇排序III.起泡排序IV.希爾排序V.堆排序僅I、II僅II、III僅III、IV僅IV、V假定計算機M1和M2具有相同的指令集體系結(jié)構(gòu)〔ISA〕，主頻分別為1.5GHz和1.2GHz。在M1和M2上運行某基準程序P，平均CPI分別為2和1，那么程序P在M1和M2上運行時間的比值是 12。0.40.6251.62.5某計算機主存按字節(jié)編址，由4個64M*8位的DRAM芯片采用交叉編址方式構(gòu)成，并與寬度為32位的存儲器總線相連，主存每次最多讀寫32位數(shù)據(jù)。假設(shè)double型變量x的主存地址為804001AH，那么讀取x需要的存儲周期是 13。1234某C語言程序段如下：for(i=0;i<=9;i++){ lemp=1;for(j<0;j<=I;j++)temp*=a[j];sum+=temp;}以下關(guān)于數(shù)組a的訪問局部性的描述中，正確的是 14。時間局部性和空間局部性皆有無時間局部性，有空間局部性有時間局部性，無空間局部性時間局部性和空間局部性皆無以下尋址方式中，最適合按下標順序訪問一維數(shù)組元素的是 15。相對尋址存放器尋址直接尋址變址尋址某計算機按字節(jié)編址，指令字長固定且只有兩種指令格式，其中三地址指令29條，二地址指令107條，每個地址字段為6位，那么指令字長至少應(yīng)該是 16。24位26位28位32位以下關(guān)于超標量流水線特性的表達中，正確的是 16。I.能縮短流水線功能段的處理時間II.能在一個時鐘周期內(nèi)同時發(fā)射多條指令I(lǐng)II.能結(jié)合動態(tài)調(diào)度技術(shù)提高指令執(zhí)行并行性僅II僅I、III僅II、IIII、II和III以下關(guān)于主存儲器〔MM〕和控制存儲器〔CS〕的表達中，錯誤的是 18。MM在CPU外，CS在CPU內(nèi)MM按地址訪問，CS按內(nèi)存訪問MM存儲指令和數(shù)據(jù)，CS存儲微指令MM用RAM和ROM實現(xiàn)，CS用ROM實現(xiàn)以下關(guān)于指令流水線數(shù)據(jù)通路的表達中，錯誤的是 19。包含生成控制信號的控制部件包含算法邏輯運算部件〔ALU〕包含通用存放器組和取指部件由組合邏輯電路和時序邏輯電路組合而成以下關(guān)于多總線結(jié)構(gòu)的表達中，錯誤的是 20?？拷麮PU的總線速度較快存儲器總線可支持突發(fā)傳送方式總線之間須通過橋接器相連PCI_Express*16采用并行傳輸方式I/O指令實現(xiàn)的數(shù)據(jù)傳送通常發(fā)生在 21。I/O設(shè)備和I/O端口之間通用存放器和I/O設(shè)備之間I/O端口和I/O端口之間通用存放器和I/O端口之間以下關(guān)于多重中斷系統(tǒng)的表達中，錯誤的是 22。在一條指令執(zhí)行結(jié)束時響應(yīng)中斷中斷處理期間CPU處于關(guān)中斷狀態(tài)中斷請求的產(chǎn)生與當前指令的執(zhí)行無關(guān)CPU通過采樣中斷請求信號檢測中斷請求假設(shè)4個作業(yè)到達系統(tǒng)的時刻和運行時間如下表所示。作業(yè)到達時間t運行時間J103J213J312J431系統(tǒng)在t=2時開始作業(yè)調(diào)度。假設(shè)分別采用先來先效勞和短作業(yè)優(yōu)先調(diào)度算法，那么選中的作業(yè)分別是 23J2、J3J1、J4J2、J4J1、J3執(zhí)行系統(tǒng)調(diào)用的過程包括如下主要操作：返回用戶態(tài)執(zhí)行陷入〔trap〕指令傳遞系統(tǒng)調(diào)用參數(shù)執(zhí)行相應(yīng)的效勞程序正確的執(zhí)行順序是 24。2)3)1)4)2)3)3)1)3)2)4)1)3)4)2)1)某計算機按字節(jié)編址，其動態(tài)分區(qū)內(nèi)存管理采用最正確適應(yīng)算法，每次分配和回收內(nèi)存后都對空閑分區(qū)鏈重新排序。當前空閑分區(qū)信息如下所示。分區(qū)起始地址20K500K1000K200K分區(qū)大小40KB80KB100KB200KB回收起始地址為60K、大小為140KB的分區(qū)后，系統(tǒng)中空閑分區(qū)的數(shù)量、空閑分區(qū)鏈第一個分區(qū)的起始地址和大小分別是 25。3、20K、380KB3、500K、80KB4、20K、180KB4、500K、80KB某文件系統(tǒng)的簇和磁盤扇區(qū)大小分別為1KB和512B。假設(shè)一個文件的大小為1026B，那么系統(tǒng)分配給該文件的磁盤空間大小是 26。1026B1536B1538B2048B以下有關(guān)基于時間片的進程調(diào)度的表達中，錯誤的是 27。時間片越短，進程切換的次數(shù)越多，系統(tǒng)開銷也越大當前進程的時間片用完后，該進程狀態(tài)由執(zhí)行態(tài)變?yōu)樽枞麘B(tài)時鐘中斷發(fā)生后，系統(tǒng)會修改當前進程在時間片內(nèi)的剩余時間影響時間片大小的主要因素包括響應(yīng)時間、系統(tǒng)開銷和進程數(shù)量等。與單道程序系統(tǒng)相比，多道程序系統(tǒng)的優(yōu)先是 28。I.CPU利用率高II.系統(tǒng)開銷小III.系統(tǒng)吞吐量大IV.I/O設(shè)備利用率高僅I、III僅I、IV僅II、III僅I、III、IV以下選項中，磁盤邏輯格式化程序所做的工作是 29。I.對磁盤進行分區(qū)II.建立文件系統(tǒng)的根目錄III.確定磁盤扇區(qū)校驗碼所占位數(shù)IV.對保存空閑磁盤塊信息的數(shù)據(jù)結(jié)構(gòu)進行初始化僅II僅II、IV僅III、IV僅I、II、IV某文件系統(tǒng)中，針對每個文件，用戶類別分為4類：平安管理員、文件主、文件主的伙伴、其他用戶；訪問權(quán)限分為5種：完全控制、執(zhí)行、修改、讀取、寫入。假設(shè)文件控制塊中用二進制位串表示文件權(quán)限，為表示不同類別用戶對一個文件的訪問權(quán)限，那么描述文件權(quán)限的位數(shù)至少應(yīng)為 30。591220假設(shè)文件f1的硬鏈接為f2，兩個進程分別翻開f1和f2，獲得對應(yīng)的文件描述符為fd1和fd2，那么以下表達中，正確的是 31。I.f1和f2的讀寫指針位置保持相同II.f1和f2共享同一個內(nèi)存索引結(jié)點III.fd1和fd2分別指向各自的用戶翻開文件表中的一項僅III僅II、III僅I、III、II和III系統(tǒng)將數(shù)據(jù)從磁盤讀到內(nèi)存的過程包括以下操作：DMA控制器發(fā)出中斷請求初始化DMA控制器并啟動磁盤從磁盤傳輸一塊數(shù)據(jù)到內(nèi)存緩沖區(qū)執(zhí)行“DMA結(jié)束〞中斷效勞程序正確的執(zhí)行順序是 32。3)1)2)4)2)3)1)4)2)1)3)4)1)2)4)3)假設(shè)OSI參考模型的應(yīng)用層欲發(fā)送400B的數(shù)據(jù)〔無拆分〕，除物理層和應(yīng)用層之處，其他各層在封裝PDU時均引入20B的額外開銷，那么應(yīng)用層數(shù)據(jù)傳輸效率約為 33。80%83%87%91%假設(shè)信道在無噪聲情況下的極限數(shù)據(jù)傳輸速率不小于信噪比為30dB條件下的極限數(shù)據(jù)傳輸速率，那么信號狀態(tài)至少是 34。481632在以下圖所示的網(wǎng)絡(luò)中，假設(shè)主機H發(fā)送一個封裝訪問InternetIP分組的IEEE802.11數(shù)據(jù)幀F(xiàn)，那么幀F(xiàn)的地址1、地址2和地址3分別是 35。00-12-34-56-78-9a,00-12-34-56-78-9b,00-12-34-56-78-9c00-12-34-56-78-9b,00-12-34-56-78-9a,00-12-34-56-78-9c00-12-34-56-78-9b,00-12-34-56-78-9c,00-12-34-56-78-9a00-12-34-56-78-9a,00-12-34-56-78-9c,00-12-34-56-78-9b以下IP地址中，只能作為IP分組源IP地址但不能作為目的IP地址是 36。直接封裝RIP，OSPF，BGP報文的協(xié)議分別是 37。TCP、UDP、IPTCP、IP、UDPUDP、TCP、IPUDP、IP、TCP假設(shè)將網(wǎng)絡(luò)劃分為128個規(guī)模相同的子網(wǎng)，那么每個子網(wǎng)可分配的最大IP地址個數(shù)是 38。254256510512假設(shè)甲向乙發(fā)起了一個TCP連接，最大段長MSS=KB，RTT=5ms，乙開辟的接收緩存為64KB，那么甲從連接建立蒽至發(fā)送窗口到達32KB，需經(jīng)過的時間至少是 38。25ms30ms160ms165ms以下關(guān)于FTP協(xié)議的表達中，錯誤的是 40。數(shù)據(jù)連接在每次數(shù)據(jù)傳輸完畢后就關(guān)閉控制連接在整個會話期間保持翻開狀態(tài)效勞器與客戶端的TCP20端口建立數(shù)據(jù)連接客戶端與效勞器的TCP21端口建立控制連接綜合應(yīng)用題請設(shè)計一個算法，將給定的表達式樹〔二叉樹〕轉(zhuǎn)換為等價的中綴表達式〔通過括號反映操作符的計算次序〕并輸出。例如，當以下兩棵表達式作為算法的輸入時：輸出的等價中綴表達式分別為(a+b)*(c+(-d))和(a*b)+(-(-c-d))。二叉樹結(jié)點定義如下：Typedefstructnode{ chardata[10]; //存儲操作數(shù)或操作符Structnode*left,*right; }BTree;要求：給出算法的根本設(shè)計思想。根據(jù)設(shè)計思想，采用C或C++語言描述算法，關(guān)鍵之處給出注釋。使用Prim〔普里姆〕算法求帶權(quán)連通圖的最小〔代價〕生成樹〔MST〕。請答復(fù)以下問題。對以下圖G，從頂點A開始求G的MST，依次給出按算法選出的邊。圖G的MST是唯一的嗎？對任意的帶權(quán)連通圖，滿足什么條件時，其MST是唯一的？fn=i=0n2i=2intf1(unsignedn){ intsum=1,power=1;for(unsignedi=0;i<=n-1;i++) { power*=2;sum+=power; }returnsum;}將f1中的int都改為float，可得到計算f(n)的另一個函數(shù)f2。假設(shè)unsigned和int型數(shù)據(jù)都占32位，float采用IEEE754單精度標準。請答復(fù)以下問題。當n=0時，f1會出現(xiàn)死循環(huán)，為什么？假設(shè)將f1中的變量i和n都定義為int型，那么f1是否還會出現(xiàn)死循環(huán)？為什么？f1(23)和f2(23)的返回值是否相等？機器數(shù)各是什么〔用十六進制表示〕？F1(24)和f2(24)的返回值分別為33554431和33554432.0，為什么不相等？f(31)=232-1，而f1(31)的返回值卻為-1，為什么？假設(shè)使f1(n)的返回值與f(n)相等，那么最大的n是多少？F2(127)的機器數(shù)為7F800000H，對應(yīng)的值是什么？假設(shè)使f2(n)的結(jié)果不溢出，那么最大的n是什么？假設(shè)使f2(n)的結(jié)果精確〔無舍入〕，那么最大的n是多少？在按字節(jié)編址的計算機M上，題43中f1的局部源程序〔局部〕與對應(yīng)的機器級代碼〔包括指令的虛擬地址〕如下：intf1(unsignedn)1 00401020 55 pushebp………………for(unsignedi=0;i<=n-1;i++)…..…………200040105E 394DF4 cmpdwordptr[ebp-0Ch],ecx……………… { power*=2;………………23 00401066 D1E2 shledx,l………………returnsum;………………35 0040107F C3 ret其中，機器級代碼行包括行號、虛擬地址、機器指令和匯編指令。請答復(fù)以下問題。計算機M是RISC還是CISC？為什么？f1的機器指令代碼共占多少字節(jié)？要求給出計算過程。第20條指令cmp通過i減n-1實現(xiàn)對i和n-1的比擬。執(zhí)行f1(0)過程中，當i=0時，cmp指令執(zhí)行后，進/借位標志CF的內(nèi)容是什么？要求給出計算過程。第23條指令shl通過左移操作實現(xiàn)了power*2運算，在f2中能否也用shl指令實現(xiàn)power*2？為什么？假定題44給出的計算機M采用二級分布虛擬存儲管理方式，邪氣地址格式如下：頁目錄號〔10位〕頁表索引〔10位〕頁內(nèi)偏移量〔12位〕請針對題43的函數(shù)f1和題44中的機器指令代碼，答復(fù)以下問題。函數(shù)f1的機器指令代碼占多少頁？取第1條指令(pushebp)時，假設(shè)在進行地址變換的過程中需要訪問內(nèi)存中的頁目錄和頁表，而會分別訪問它們各自的第幾個表項〔編號從0開始〕？M的I/O采用中斷控制方式。假設(shè)進程P在調(diào)用f1之前通過scanf()獲取n的值，那么在執(zhí)行scanf()的過程中，進程P的狀態(tài)會如何變化？CPU是否會進入內(nèi)核態(tài)？某進程中有3個并發(fā)執(zhí)行的線程thread1、thread2和thread3，其偽代碼如下所示。//復(fù)數(shù)的結(jié)構(gòu)類型定義typedefstruct{floata;floatb;}cnum;cnumx,y,z;//全局變量//計算兩個復(fù)數(shù)之和cnumadd(cnump,cnumq){cnums;s.a=p.a+q.a;s.b=p.b+q.b;returns;}thread