【正文】 ocateElement(Linklist list,int k) { p1=listlink。用整型變量 i 表示當(dāng)前遍歷 了多少個(gè)結(jié)點(diǎn)，當(dāng) ik 時(shí)，指針 p 隨著每次遍歷，也向前移動(dòng)一個(gè)結(jié)點(diǎn)。當(dāng)遍歷到鏈表的最后一個(gè)結(jié)點(diǎn)時(shí)，指針 p 所指向的結(jié)點(diǎn)即為所查 找的結(jié)點(diǎn)。例如，對(duì)于下圖所示的帶權(quán)圖，如果 按照題中的原則，從 A 到C 的最短路徑為 A→ B→ C，事實(shí)上其最短路徑為 A→ D→ C。 R1 的 L0 接口的 IP 地址是 ； R2 的 L0 接口 的 IP 地址是 ， L1 接口的 IP 地址是 ， E0 接口的 IP 地址是 ；域名服務(wù)器的 IP 地址是 。 （ 2） 基于上述訪問(wèn)序列，虛地址 1565H 的物理地址是多少？請(qǐng)說(shuō)明理由。假設(shè)① TLB 初始為空；②地址轉(zhuǎn)換時(shí)先訪問(wèn) TLB，若 TLB 未命中，再 訪問(wèn)頁(yè) 表（忽略訪問(wèn)頁(yè)表之后的 TLB 更新時(shí)間）；③有效位為 0 表示頁(yè)面不在內(nèi)存，產(chǎn) 生缺頁(yè)中斷，缺頁(yè)中斷處理后，返回到產(chǎn)生缺頁(yè)中斷的指令處重新執(zhí)行。 46.（ 8 分）請(qǐng)求分頁(yè)管理系統(tǒng)中，假設(shè)某進(jìn)程的頁(yè)表內(nèi)容如下表所示。請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)這三個(gè)進(jìn)程的同步與互斥活動(dòng)，并說(shuō)明所定 義的信號(hào)量的含義。 功能和控制信號(hào) 時(shí)鐘 功能 有效控制信號(hào) C1 MAR← (PC) PCout,MARin C2 MDR← M(MAR) PC← (PC)+1 MemR,MDRinE PC+1 C3 IR← (MDR) MDRout,IRin C4 指令譯碼 無(wú) 45.（ 7 分）三個(gè)進(jìn)程 P P P3 互斥使用一個(gè)包含 N（ N0）個(gè)單元的緩沖 區(qū)。加法指令“ ADD（ R1）， R0” 的功能為（ R0） +（（ R1））→（ R1），即將 R0 中的數(shù)據(jù)與 R1 的內(nèi)容所指 主存單元 的數(shù)據(jù)相加，并將結(jié)果送入 R1 的內(nèi)容所指主存單元中保存。例如控 制信號(hào) MDRinE 為 1 表示允許數(shù)據(jù)從 DB 打入 MDR， MDRin 為 1 表示允許數(shù)據(jù)從內(nèi) 總線打入 MDR。假設(shè) 每次 DMA 傳送大小為 5000B，且 DMA 預(yù)處理和后處理的總開(kāi)銷為 500 個(gè)時(shí)鐘周期， 則 CPU 用于該外設(shè) I/O 的時(shí)間占整個(gè) CPU 時(shí)間的百分比是多少？（假設(shè) DMA 與 CPU 之間沒(méi)有訪存沖突） 44.（ 13 分）某計(jì)算機(jī)字長(zhǎng) 16 位，采用 16 位定長(zhǎng)指令字結(jié)構(gòu)，部分?jǐn)?shù)據(jù)通 路結(jié)構(gòu)如圖所示。請(qǐng)回答下列問(wèn)題，要求給出計(jì)算過(guò) 程。要求： （ 1） 描述算法的基本設(shè)計(jì)思想 （ 2） 描述算法的詳細(xì)實(shí)現(xiàn)步驟 （ 3） 根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語(yǔ)言描述算法（使用 C 或 C++ 或 JAVA 語(yǔ)言實(shí)現(xiàn)），關(guān)鍵之處請(qǐng)給出簡(jiǎn)要注釋 43.（ 8 分）某計(jì)算機(jī)的 CPU 主頻為 500MHz， CPI 為 5（即執(zhí)行每條指令平均 需 5 個(gè)時(shí)鐘周期）。在不改變鏈表的前提下，請(qǐng)?jiān)O(shè)計(jì) 一個(gè)盡可能 高效的算法，查找鏈表中倒數(shù)第 k 個(gè)位置上的結(jié)點(diǎn)（ k 為正整數(shù)）。 請(qǐng)問(wèn)上述方法能否求得最短路徑？若該方法可行，請(qǐng)證明之；否則，請(qǐng)舉例說(shuō)明。 41.（ 10 分） 帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離）的最短路 徑問(wèn)題是找出從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間 的一條最短路徑。當(dāng)擁塞窗口為 16KB 時(shí)發(fā)生了超時(shí)，如果接下來(lái)的 4 個(gè) RTT（往返時(shí)間） 時(shí)間內(nèi)的 TCP 段的傳輸都 是成功的，那么當(dāng)?shù)?4 個(gè) RTT 時(shí)間內(nèi)發(fā)送的所有 TCP 段都得到肯定應(yīng)答時(shí)，擁塞窗口大小是 A． 7KB B. 8KB C. 9KB D. 16KB 客戶和服務(wù)器間傳遞 FTP 命令時(shí)，使用的連接是 A．建立在 TCP 之上的控制連接 B. 建立在 TCP 之上的數(shù)據(jù)連接 C. 建立在 UDP 之上的控制連接 D. 建立在 UDP 之上的數(shù)據(jù)連接 二、綜合應(yīng)用題。 當(dāng)計(jì)時(shí)器超時(shí)時(shí)，若發(fā)送方只收到 0、 3 號(hào)幀的確認(rèn)，則發(fā)送方需要重 發(fā)的幀數(shù)是 A． 2 PDU 地址是 A．目的物理地址 IP 地址 IP 地址 CSMA/CD 協(xié)議的網(wǎng)絡(luò)中，傳輸介質(zhì)是一根完整的電纜，傳輸 速率為 1Gbps，電纜中的信號(hào)傳播速度是 200 000km/s?，F(xiàn)有一 個(gè)磁道訪問(wèn)請(qǐng)求序列為 35， 45， 12， 68， 110， 180， 170， 195，采用 SCAN 調(diào)度 （電梯調(diào)度）算法得到的磁道訪問(wèn)序列是 A． 110， 170， 180， 195， 68， 45， 35， 12 ， 68， 45， 35， 12， 170， 180， 195 ， 170， 180， 195， 12， 35， 45， 68 ， 35， 45， 68， 110， 170， 180， 195 ，文件訪問(wèn)控制信息存儲(chǔ)的合理位置是 A．文件控制塊 31．設(shè)文件 F1 的當(dāng)前引用計(jì)數(shù)值為 1，先建立 F1 的符號(hào)鏈接（軟鏈接）文 件 F2，再建立 F1 的硬鏈接文件 F3，然后刪除 F1。若某轉(zhuǎn)移指令所在主存地址為 2022H，相對(duì)位移量字 段的內(nèi)容為 06H，則該轉(zhuǎn)移指令成功轉(zhuǎn)以后的目標(biāo)地址是 RISC 的敘述中，錯(cuò)誤的是 A． RISC 普遍采用微程序控制器 B． RISC 大多數(shù)指令在一個(gè)時(shí)鐘周期內(nèi)完成 C． RISC 的內(nèi)部通用寄存器數(shù)量相對(duì) CISC 多 D． RISC 的指令數(shù)、尋址方式和指令格式種類相對(duì) CISC 少 ，指令流經(jīng)各功能段的時(shí)間（忽 略各功能段之間的緩存時(shí)間）分別是 90ns、 80ns、 70ns 和 60ns，則該計(jì)算機(jī)的 CPU 時(shí)鐘周期至少是 A． 90ns ，硬布線 控制器的特點(diǎn)是 A．指令執(zhí)行速度慢，指令功能的修改和擴(kuò)展容易 B．指令執(zhí)行速度慢，指令功能的修改和擴(kuò)展難 C．指令執(zhí)行速度快，指令功能的修改和擴(kuò)展容易 D．指令執(zhí)行速度快，指令功能的修改和擴(kuò)展難 4 字節(jié)信息，一個(gè)總線周期 占用 2 個(gè)時(shí)鐘周期，總線時(shí)鐘頻率為 10MHz，則總線帶寬是 A． 10MB/s Cache 和主存組成，某程序執(zhí)行過(guò)程中訪存 1000 次，其中訪 問(wèn) Cache 缺失（未命中） 50 次，則 Cache 的命中率是 A． 5% % % % ，能引起外部中斷的事件是 A．鍵盤輸入 0 ，可并行的是 I 進(jìn)程與進(jìn)程 II 處理機(jī)與設(shè)備 III 處理機(jī)與通道 IV 設(shè)備與設(shè)備 A． I、 II 和 III B. I、 II 和 IV C. I、 III 和 IV D. II、 III 和 IV ，綜合考慮進(jìn)程等待時(shí)間和執(zhí)行時(shí)間的是 A．時(shí)間片輪轉(zhuǎn)調(diào)度算法 8 臺(tái)打印機(jī)，有 K 個(gè)進(jìn)程競(jìng)爭(zhēng)使用，每個(gè)進(jìn)程最多需 要 3 臺(tái)打印機(jī)?，F(xiàn)要用 2K 8 位的 ROM 芯片和 4K 4 位的 RAM 芯片來(lái)設(shè)計(jì)該存儲(chǔ)器，則需 要上述規(guī)格的 ROM 芯片數(shù)和 RAM 芯片數(shù)分別是 A． 15 B． 15 C． 30 D． 30 16 位，主存按字節(jié)編址，轉(zhuǎn)移指令采用相對(duì)尋址，由兩個(gè)字 節(jié)組成，第一字節(jié)為操作碼字段，第二字節(jié)為相對(duì)位移量字段。 每個(gè)主存塊大小為 32 字節(jié)，按字節(jié)編址。設(shè)浮點(diǎn)數(shù)的階碼和尾數(shù)均采用補(bǔ)碼表示，且位數(shù)分別為 5 位和 7 位（均 含 2 位符號(hào)位）。程序中定義了三個(gè)變量 xyz， 其中 x和 z 是 int 型， y為 short 型。設(shè) N 代表二叉樹(shù)的根， L 代表根結(jié)點(diǎn)的左子樹(shù)， R 代 表根結(jié)點(diǎn)的右子樹(shù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是 S 和隊(duì)列 Q 的初始狀態(tài)均為空，元素 abcdefg 依次進(jìn)入棧 S。2022年計(jì)算機(jī)考研真題及答案 (統(tǒng)考 ) 一、單項(xiàng)選擇題，每小題 2 分，共 80 分。 ，通常設(shè)置一個(gè)打印數(shù)據(jù)緩 沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取 出數(shù)據(jù)。若每個(gè) 元素出棧后立即進(jìn)入隊(duì)列 Q，且 7 個(gè)元素出隊(duì)的順序是 bdcfeag，則棧 S 的容量 至少是 A． 1 。若遍歷后的結(jié)點(diǎn)序列為 3， 1， 7， 5， 6， 2， 4，則其遍歷方 式是 A． LRN ，滿足平衡二叉樹(shù)定義的是 6 層（設(shè)根為第 1 層）有 8 個(gè)葉結(jié)點(diǎn)，則完全二 叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最多是 A． 39 ，若在二叉樹(shù)中，結(jié)點(diǎn) u 是結(jié)點(diǎn) v 的父結(jié)點(diǎn)的 父結(jié)點(diǎn)，則在原 來(lái)的森林中，u 和 v 可能具有的關(guān)系是 I．父子關(guān)系 III. u 的父結(jié)點(diǎn)與 v 的父結(jié)點(diǎn)是兄弟關(guān)系 II 和 II 和 III 、 II 和 III ，正確的是 I．所有頂點(diǎn)的度之和為偶數(shù) 1 1 I B. 只有 II 和 II 和 III ，不符合 m 階 B 樹(shù)定義要求的是 A．根節(jié)點(diǎn)最多有 m 棵子樹(shù) 上 C．各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列 點(diǎn)之間通過(guò)指針鏈接 5， 8， 12， 19， 28， 20， 15， 22 是小根堆（最小堆），插入 關(guān)鍵字 3，調(diào)整后得到的小根堆是 A． 3， 5， 12， 8， 28， 20， 15， 22， 19 B. 3， 5， 12， 19， 20， 15， 22， 8， 28 C． 3， 8， 12， 5， 20， 15， 22， 28， 19 D. 3， 12， 5， 8， 28， 20， 15， 22， 19 11， 12， 13， 7， 8， 9， 23， 4， 5 是采用下列排序方法 之一得到的第二趟排序后的 結(jié)果，則該排序算法只能是 A．起泡排序 ?諾依曼計(jì)算機(jī)中指令和數(shù)據(jù)均以二進(jìn)制形式存放在存儲(chǔ)器中， CPU 區(qū)分它們的依據(jù)是 A．指令操作碼的譯碼結(jié)果 單元 C 語(yǔ)言程序在一臺(tái) 32 位機(jī)器上運(yùn)行。當(dāng) x=127， y=9 時(shí)，執(zhí)行賦值語(yǔ)句 z=x+y 后， xyz 的值分別是 A． X=0000007FH， y=FFF9H， z=00000076H B． X=0000007FH， y=FFF9H， z=FFFF0076H