2023一、單項選擇題：1~40280項符合試題要求。nx=0；while(n>=(x+l)*(x+l))x=x+l；O(logn) B.O(n1/2) C.O(n) D.O(n2)TBTBT的遍歷中，其遍歷序列與T根遍歷序列一樣的是先序遍歷 B.中序遍歷 C.后序遍歷 D.按層遍歷n115個結(jié)點，那么n值是A.56 B.57 C.58 D.60在任意一棵非空平衡二又樹(AVL樹)T1

vTw2T

形成平衡二又樹T。以下關(guān)于TT的表達(dá)中，正確的選項是2 3 1 3I.假設(shè)vT1

的葉結(jié)點，那么TT1 3

可能不一樣Ⅱ.假設(shè)v不是T1Ⅲ.假設(shè)v不是T1

的葉結(jié)點，那么T1的葉結(jié)點，那么T1

T3T3A.僅I B.僅II C.僅I、Ⅱ D.僅I、ⅢAOE8dA.3和7 B.12和12 C.12和14 D.15和15用有向無環(huán)圖描繪表達(dá)式(x+y)*((x+y)/x)，需要的頂點個數(shù)至少是A.5 B.6 C.8 D.9選擇一個排序算法時，除算法的時空效率外，以下因素中，還需要考慮的是I.數(shù)據(jù)的規(guī)模 Ⅱ.數(shù)據(jù)的存儲方式 Ⅲ.算法的穩(wěn)定性 V.數(shù)據(jù)的初始狀態(tài)A.僅Ⅲ B.僅I、Ⅱ C.僅Ⅱ、Ⅲ、IV D.I、Ⅱ、Ⅲ、Ⅳ11且初始為空的散列表HTH(key)=key%7，承受線性探查(線性探87，40，30，6，11，22，98，20HTHTA.4 B.5.25 C.6 D.6.29T=“abaabaabcabaabcS=“abaabcKMP匹配成功時為止，在匹配過程中進(jìn)展的單個字符間的比較次數(shù)是A.9 B.10 C.12 D.15 排序過程中，對尚未確定最終位置的全部元素進(jìn)展一遍處理稱為一“趟〞。以下序列中，不行能是快速排序其次趟結(jié)果的是A.5，2，16，12，28，60，32，72B.2，16，5，28，12，60，32，72C.2，12，16，5，28，32，72，60D.5，2，12，28，16，32，72，60 12012段個數(shù)是A.1B.2C.3D.4以下關(guān)于馮·諾依曼構(gòu)造計算機(jī)根本思想的表達(dá)中，錯誤的選項是程序的功能都通過中心處理器執(zhí)行指令實現(xiàn)指令和數(shù)據(jù)都用二進(jìn)制表示，形式上無差異指令按地址訪問，數(shù)據(jù)都在指令中直接給出程序執(zhí)行前，指令和數(shù)據(jù)需預(yù)先存放在存儲器中 考慮以下Cunsignedshortusi=65535；shortsi=usi；執(zhí)行上述程序段后，siA.-1 B.-32767 C.-32768 D.-65535以下關(guān)于缺頁處理的表達(dá)中，錯誤的選項是缺頁是在地址轉(zhuǎn)換時CPU檢測到的一種特別缺頁處理由操作系統(tǒng)供給的缺頁處理程序來完成缺頁處理程序依據(jù)頁故障地址從外存讀入所缺失的頁缺頁處理完成后回到發(fā)生缺頁的指令的下一條指令執(zhí)行 某計算機(jī)承受大端方式，按字節(jié)編址。某指令中操作數(shù)的機(jī)器數(shù)為1234FF00H，該操FF12H，基址存放器內(nèi)容為F0000000H，那么該操作數(shù)的LSB(最低有效字節(jié))所在的地址是F000FF12H B.F000FF15H C.EFFFFF12H D.EFFFFF15H以下有關(guān)處理器時鐘脈沖信號的表達(dá)中，錯誤的選項是時鐘脈沖信號由機(jī)器脈沖源發(fā)出的脈沖信號經(jīng)整形和分頻后形成時鐘脈沖信號的寬度稱為時鐘周期，時鐘周期的倒數(shù)為機(jī)器主頻時鐘周期以相鄰狀態(tài)單元間組合規(guī)律電路的最大延遲為基準(zhǔn)確定處理器總是在每來一個時鐘脈沖信號時就開頭執(zhí)行一條的指令 某指令功能為R[r2]←R[r1]+M[R[r0]]，其兩個源操作數(shù)分別承受存放器、存放器間接尋址方式。對于以下給定部件，該指令在取數(shù)及執(zhí)行過程中需要用到的是I.通用存放器組(GPRs) Ⅱ.算術(shù)規(guī)律單元(ALU)Ⅲ.存儲器(Memory) Ⅳ.指令譯碼器(ID)A.僅I、Ⅱ B.僅I、Ⅱ、Ⅲ C.僅Ⅱ、Ⅲ、IV D.僅I、Ⅲ、Ⅳ 在承受“取指、譯碼/取數(shù)、執(zhí)行、訪存、寫回〞5段流水線的處理器中，執(zhí)行如下指令序列，其中s0、s1、s2、s3t2I1：adds2，s1，s0 //R[s2]←R[s1]+R[s0]I2：loads3，0(t2) //R[s3]←M[R[t2]+0]I3：adds2，s2s3 //R[s2]←R[s2]+R[s3]I4：stores2，0(t2) //M[R[t2]+0]←R[s2]以下指令對中，不存在數(shù)據(jù)冒險的是I1和I3 B.I2和I3 C.I2和I4 D.I3和I4 假定一臺計算機(jī)承受3通道存儲器總線，配套的內(nèi)存條型號為DDR3-1333，即內(nèi)存條1333MHz、總線寬度為64位，那么存儲器總線的總帶寬大約是A.10.66GB/s B.32GB/s C.64GB/s D.96GB/s以下關(guān)于磁盤存儲器的表達(dá)中，錯誤的選項是磁盤的格式化容量比非格式化容量小扇區(qū)中包含數(shù)據(jù)、地址和校驗等信息磁盤存儲器的最小讀寫單位為一個字節(jié)磁盤存儲器由磁盤把握器、磁盤驅(qū)動器和盤片組成 某設(shè)備以中斷方式與CPUCPU1GHz，設(shè)備接口中的數(shù)據(jù)緩沖存3250kB/s1000個時鐘周期，那么CPU/輸出的時間占整個CPU是A.1.25% B.2.5% C.5% D.12.5%以下關(guān)于DMA方式的表達(dá)中，正確的選項是DMA數(shù)據(jù)傳送前由DMAⅢ.數(shù)據(jù)傳送由DMAIV.DMA傳送完畢后的處理由中斷效勞程序完成A.僅I、Ⅱ B.僅Ⅰ、Ⅲ、Ⅳ C.僅Ⅱ、Ⅲ、IV D.I、Ⅱ、Ⅲ、IV以下關(guān)于線程的描繪中，錯誤的選項是內(nèi)核級線程的調(diào)度由操作系統(tǒng)完成操作系統(tǒng)為每個用戶級線程建立一個線程把握塊用戶級線程間的切換比內(nèi)核級線程間的切換效率高用戶級線程可以在不支持內(nèi)核級線程的操作系統(tǒng)上實現(xiàn)以下選項中，可能將進(jìn)程喚醒的大事是I.I/O完畢 Ⅱ.某進(jìn)程退出臨界區(qū) Ⅲ.當(dāng)前進(jìn)程的時間片用完A.僅I B.僅Ⅲ C.僅I、Ⅱ D.I、Ⅱ、Ⅲ以下關(guān)于系統(tǒng)調(diào)用的表達(dá)中，正確的選項是I.在執(zhí)行系統(tǒng)調(diào)用效勞程序的過程中，CPU處于內(nèi)核態(tài)Ⅱ.操作系統(tǒng)通過供給系統(tǒng)調(diào)用防止用戶程序直接訪問外設(shè)Ⅲ.不同的操作系統(tǒng)為應(yīng)用程序供給了統(tǒng)一的系統(tǒng)調(diào)用接口IV.系統(tǒng)調(diào)用是操作系統(tǒng)內(nèi)核為應(yīng)用程序供給效勞的接口A.僅I、IV B.僅II、III C.僅I、Ⅱ、IV D.僅I、Ⅲ、Ⅳ以下選項中，可用于文件系統(tǒng)治理空閑磁盤塊的數(shù)據(jù)構(gòu)造是I.位圖 Ⅱ.索引節(jié)點 Ⅲ.空閑磁盤塊鏈 Ⅳ.文件安排表(FAT)A.僅I、Ⅱ B.僅Ⅰ、Ⅲ、Ⅳ C.僅l、Ⅲ D.僅Ⅱ、Ⅲ、Ⅳ 系統(tǒng)承受二級反響隊列調(diào)度算法進(jìn)展進(jìn)程調(diào)度。就緒隊列Q1承受時間片輪轉(zhuǎn)調(diào)度算10ms；就緒隊列Q2Q1Q1Q2Q1；Q1一個時間片后，假設(shè)未完畢，那么轉(zhuǎn)入Q2。假設(shè)當(dāng)前Q1、Q2為空，系統(tǒng)依次創(chuàng)立進(jìn)程Pl、P2后即開頭進(jìn)程調(diào)度Pl、P2CPU30ms20ms，那么進(jìn)程P1、P2統(tǒng)中的平均等待時間為25ms B.20ms C.15ms D.10ms 在分段存儲治理系統(tǒng)中，用共享段表描繪全部被共享的段。假設(shè)進(jìn)程P1和P2共享段S，以下表達(dá)中，錯誤的選項是在物理內(nèi)存中僅保存一份段S的內(nèi)容S在P1P2P1P2共享段SP1P2S時才回收段S LRUP4P0，1，2，7，0，5，3，5，0，2，7，6，那么進(jìn)程訪問上述頁的過程中，產(chǎn)生頁置換的總次數(shù)是A.3 B.4 C.5 D.6以下關(guān)于死鎖的表達(dá)中，正確的選項是可以通過剝奪進(jìn)程資源解除死鎖死鎖的預(yù)防方法能確保系統(tǒng)不發(fā)生死鎖銀行家算法可以推斷系統(tǒng)是否處于死鎖狀態(tài)Ⅳ.當(dāng)系統(tǒng)消滅死鎖時，必定有兩個或兩個以上的進(jìn)程處于堵塞態(tài)A.僅II、Ⅲ B.僅I、Ⅱ、Ⅳ C.僅I、Ⅱ、Ⅲ D.僅IⅢ、Ⅳ某計算機(jī)主存按字節(jié)編址，承受二級分頁存儲治理，地址構(gòu)造如下所示頁名目號(10位) 頁號(10位) 頁內(nèi)偏移(12位)20501225HA.081H、101H B.081H、401H C.201H、101H D.201H、401H在以下動態(tài)分區(qū)安排算法中，最簡潔產(chǎn)生內(nèi)存碎片的是首次適應(yīng)算法 B.最壞適應(yīng)算法 C.最正確適應(yīng)算法 D.循環(huán)首次適應(yīng)算法OSI5過失把握 B.路由選擇 C.會話治理 D.數(shù)據(jù)表示轉(zhuǎn)換100BaseT雙絞線 B.單模光纖 C.多模光纖 D.同軸電纜 對于滑動窗口協(xié)議，假設(shè)分組序號承受3比特編號，發(fā)送窗口大小為5，那么接收窗口最大是A.2 B.3 C.4 D.5 CSMA/CD100Mbps128B，那么在一個沖突域內(nèi)兩個站點之間的單向傳播延時最多是A.2.56μsB.5.12μsC.10.24μsD.20.48μs 101.200.16.0/205IP數(shù)是A.126 B.254 C.510 D.1022某客戶通過一個TCP連接向效勞器發(fā)送數(shù)據(jù)的局38圖所示。客戶在t0

時刻第一次收到確認(rèn)序列號ack_seq=100seq=100TCPseq=100t1t4

t2

t D.3假設(shè)主機(jī)甲主動發(fā)起一個與主機(jī)乙的TCP連接，甲、乙選擇的初始序列號分別為20232046，那么第三次握手TCPA.2023 B.2023 C.2046 D.2047以下關(guān)于網(wǎng)絡(luò)應(yīng)用模型的表達(dá)中，錯誤的選項是P2P在客戶/效勞器(C/S)模型中，客戶與客戶之間可以直接通信C/S在向多用戶分發(fā)一個文件時，P2P模型通常比C/S模型所需時間短二、綜合應(yīng)用題：41~4770(13分)設(shè)線性表L=(a1，a2，a…，an-2，a-1，a。)承受帶頭結(jié)點的單鏈表保存，鏈表中結(jié)點定義如下：typedefstructnode{intdata；structnode*next；}NODE；請設(shè)計一個空間簡潔度為O(1)且時間上盡可能高效的算法，重排列L中的各結(jié)點，得到線性表L”=(aa，aa

，a

…)。要求：

1 n 2

3

n-2給出算法的根本設(shè)計思想依據(jù)設(shè)計思想，承受C或C++語言描繪算法，關(guān)鍵之處給出注釋。說明你所設(shè)計的算法的時間簡潔度。(10分)請設(shè)計一個隊列，要求滿足：①初始時隊列為空；②入隊時，允許增加隊列占用空間；③出隊后，出隊元素所占用的空間可重復(fù)使用，即整個隊列所占用的空間只增不減；④人隊操作和出隊操作的時間簡潔度始終保持為O(1)。請答復(fù)以下問題：該隊列應(yīng)中選擇鏈?zhǔn)酱鎯?gòu)造，還是挨次存儲構(gòu)造？畫出隊列的初始狀態(tài)，并給出推斷隊空和隊滿的條件畫出第一個元素入隊后的隊列狀態(tài)。給出入隊操作和出隊操作的根本過程。(8分)有n(n≥3有m(m≥1)個碗，每兩位哲學(xué)家之間有1根筷子。每位哲學(xué)家必需取到一個碗和兩側(cè)的筷子之后，才能就餐，進(jìn)餐完畢，將碗和筷子放回原位，并連續(xù)考慮。為使盡可能多的哲學(xué)家同時就餐，且防止消滅死鎖現(xiàn)象，請使用信號量的P、V操作(wait、signal操作)描繪上述過程中的互斥與同步，并說明所用信號量及初值的含義。(730010200512B2磁盤的容量是多少？854100260、60005、101660和110560(SSTF后次序是什么？第100530簇在磁盤上的物理地址是什么？將簇號轉(zhuǎn)換成磁盤物理地址的過程是由I/O系統(tǒng)的什么程序完成的？45.(16)f(n)=n！=n×(n-l)×(n-2)×…×2×1f(nC語言函數(shù)fl32M其中，機(jī)器級代碼行包括行號、虛擬地址、機(jī)器指令和匯編指令，計算機(jī)M按字節(jié)編址，int32計算f(10)需要調(diào)用函數(shù)f1多少次？執(zhí)行哪條指令會遞歸調(diào)用f1？上述代碼中，哪條指令是條件轉(zhuǎn)移指令？哪幾條指令確定會使程序跳轉(zhuǎn)執(zhí)行？16call1716call16call4字節(jié)為偏移量，M(4)f(13)=6227020800f1(131932053504，為什么兩者不相等？要f1(13)能返回正確的結(jié)果，應(yīng)如何修改f1(5)第19imuleax,ecxR[eaxR[ecx]，當(dāng)乘法器輸出的高、低32位乘積之間滿足什么條件時，溢出標(biāo)志OF=1？要使CPU處理，編譯器應(yīng)在imul(745M324KB1行push指令和第30行retCache64464B32表示塊內(nèi)地址？哪兒位表示Cache(tag)信息？讀取第16行call令時，只可能在指令Cache(947R為路由器，主機(jī)H1~H4IPRIPVLAN網(wǎng)絡(luò)互連設(shè)備可供選擇。請答復(fù)以下問題：123123IP置正確的IP為確保主機(jī)H1~H4可以訪問Internet，R需要供給什么效勞？H3192.168.1.127IP接收該數(shù)據(jù)報？一、單項選擇題參考答案1.B 2.B3.C4.A5.C6.A 7.D8.C9.B10.D11.B 12.C13.A14.D15.D16.D17.B15.D16.D17.B18.C19.B20.C21.A22.D23.B24.C25.C26.B27.C28.B29.C30.B31.A32.C33.C34.A35.B36.B37.B38.C39.D40.B(1)算法的根本設(shè)計思想：31找到單鏈表的中間結(jié)點；第2步，將單鏈表的后半段結(jié)點原地逆置；第3步，從單鏈表前后兩段中依次各

(3)算法的時間簡潔度：參考答案的時間簡潔度為O(n)?！敬鸢敢c】承受鏈?zhǔn)酱鎯?gòu)造(兩段式單向循環(huán)鏈表)，隊頭指針為front，隊尾指針為rear。front與尾指針rear如以以以下圖所示。取一個結(jié)點，按要求重排。 隊空的斷定條件：front==rear。算法實現(xiàn)： 隊滿的斷定條件：front==rear->next。插入第一個元素后的隊列狀態(tài)：操作的根本過程：【答案要點】//信號量semaphorebowl；//用于協(xié)調(diào)哲學(xué)家對碗的使用semaphorechopsticks[n]；//用于協(xié)調(diào)哲學(xué)家對筷子的使用for(inti=0；i<n；i++)chopsticks[i].value=1；//設(shè)置兩個哲學(xué)家之間筷子的數(shù)量bowl.value=min(n-1，m)；//bowl.value≤n-1，確保不死鎖CoBeginwhile(True){ //哲學(xué)家i考慮；P(bowl)；//取碗P(chopsticks[i])；//取左邊筷子P(chopsticks[(i+l)MODn])；//取右邊筷子就餐；V(chopsticks[i])；V(chopsticks[(i+1)MODn])；V(bowl)；}CoEnd【答案要點】(1)=(30010200512/1024)KB=3×105KB(2)100260、101660、110560、60005。(3100530面號、磁頭號、扇區(qū)號構(gòu)成其所在的柱面號為?100530/(10×200/2)?=100。100530%(10×200/2)=530，磁頭號為?530/(200/2)?=5。扇區(qū)號為(530×2)%200=60。將簇號轉(zhuǎn)換成磁盤物理地址的過程由磁盤驅(qū)動程序完成?！?/p>