【正文】 ，而且還要指定字長(zhǎng) 比如說一個(gè)二字節(jié)整型的 2 就應(yīng)該是： 11111111 11111110 再轉(zhuǎn)化其它進(jìn)制 十六進(jìn)制： FFFE 八進(jìn)制： 177776 加減運(yùn)算過程一般包括 對(duì)階、尾數(shù)運(yùn)算、規(guī)格化、舍入和判溢出 等步驟。 D ：十進(jìn)制數(shù)。 如：將十進(jìn)制數(shù) 76 轉(zhuǎn)換成任意進(jìn)制 76 / 2 ... 0 = 38 / 2 ... 0 = 19 / 2 ... 1 = 9 / 2 ... 1 = 4 / 2 ... 0 = 2 / 2 ... 0 = 1 / 2 ... 1 76(10) = 1001100(2) 76 / 8 ... 4 = 9 / 8 ... 1 = 1 / 8 ... 1 76(10) = 114(8) 76 / 16 ... 12 = 4 / 16 ... 4 76(10)=4C(16) B ：二進(jìn)制數(shù)。諾依曼計(jì)算機(jī)中 指令和數(shù)據(jù) 均以二進(jìn)制形式存放在存儲(chǔ)器中， CPU 區(qū)分它們的依據(jù)是 指令周期的不同階段 。 “基本有序 ”時(shí)，對(duì)整體直接重排。 快速排序基本思想 ： 取 R[1..n]中任一記錄作為 “樞軸 ”，一趟排序之后樞軸的值均小于 “樞軸 ”左邊的值，樞軸右邊的值均大于 “樞軸 ”的值。 折半插入排序基本思想 ： 將一個(gè)記錄插入到已排序的有序表中，使插入后的表仍然有序，但插入時(shí)利用折半搜索法尋找元素的插入位置。 簡(jiǎn)單選擇排序基本思想 ： 第一趟在 R[1..n]中選最小的，與 R[1]交換 第二趟在 R[2..n]中選最小的，與 R[2]交換， 依次類推，進(jìn)行 n1 次選擇后，整個(gè)文件有序。 氣 泡排序基本思想 ： 設(shè)待排序?qū)ο笮蛄兄械膶?duì)象個(gè)數(shù)為 n。 當(dāng)向一個(gè)小根堆插入一個(gè)具有最小值的元素時(shí) ,該元素需要逐層 向上 調(diào)整 ,直到被調(diào)整到 堆頂 位置為止。根據(jù)堆的定義可知，堆頂結(jié)點(diǎn)，即整個(gè)完全二叉樹的根結(jié)點(diǎn)，對(duì)于小根堆來說具有最小值，對(duì)于大根堆來說具有最大值。 由堆的定義可知，若一棵完全二叉樹是堆，則該樹中以 每個(gè)結(jié)點(diǎn)為根的子樹也都是一個(gè)堆。 m 階 B 樹 （ 1970 年， 和 提出了一種適用于 外查找 的樹，它是一種 平衡多叉樹 ） 定義： ⑴ 樹中每個(gè)結(jié)點(diǎn)至多有 m 個(gè)孩子； ⑵ 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有 m/2 個(gè)孩子； ⑶ 若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有 2 個(gè)孩子 (除非 B 樹只有一個(gè)結(jié)點(diǎn) )； ⑷ 所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層，葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息； ⑸ 有 k 個(gè)孩子的非終 端結(jié)點(diǎn)恰好包含有 k1 個(gè)關(guān)鍵字 (各節(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列 ). (Heap)分為小根堆和大根堆兩種，對(duì)于一個(gè)小根堆，它是具有如下特性的一棵完全二叉樹： (1)若樹根結(jié)點(diǎn)存在左孩子，則根結(jié)點(diǎn)的值 (或某個(gè)域的值 )小于等于左孩子結(jié)點(diǎn)的值 (或某個(gè)域的值 )； (2)若樹根結(jié)點(diǎn)存在右孩子，則根結(jié)點(diǎn)的值 (或某個(gè)域的值 )小于等于右孩子結(jié)點(diǎn)的值 (或某個(gè)域的值 )； (3)以左、右孩子為根的子樹又各是一個(gè)堆。 頂點(diǎn)的度 定義：與定點(diǎn) v 相關(guān)聯(lián)的邊數(shù) (每個(gè)環(huán)計(jì)算兩次 )。 森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹 :兄弟之間連線，父只與長(zhǎng)子連線。 完全二叉樹 ：若對(duì)滿二叉樹的結(jié)點(diǎn)從上到下從左到右進(jìn)行編號(hào)，則深度為 k 且有 n 個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為 k 的滿二叉樹的編號(hào)從 1 到 n 一一對(duì)應(yīng)時(shí)，稱為完全二叉樹。左子 樹和右子樹的順序不能互換。因此，平衡樹中每個(gè)結(jié)點(diǎn)的平衡因子只能是 0 或 1。 叉樹定義 :若一棵二叉樹中每個(gè)結(jié)點(diǎn)的左、右子樹的高度至多相差 1，則稱此樹為平衡二叉樹。 S 和隊(duì)列 Q 的初始狀態(tài)均為空 ,元素 abcdefg 依次進(jìn)入棧 S。隊(duì)列也稱為先進(jìn)先出表（ FIFO） 樹 的定義：樹是包含 n 個(gè)結(jié)點(diǎn)的有限 集合（ n0） 圖 的定義：圖（ Graph）是由非空的頂點(diǎn)集合和一個(gè)描述頂點(diǎn)之間關(guān)系 ——邊（或者弧）的集合組成。 隊(duì)列 的定義：隊(duì)列是允許在一端進(jìn)行插入而在另一端進(jìn)行刪除的線性表。 2022 年計(jì)算機(jī)統(tǒng)考真題參考答案 一． 選擇題 1 2 3 4 5 6 7 8 9 10 B C D B C B A D A B 11 12 13 14 15 16 17 18 19 20 C D D C D C A A D B 21 22 23 24 25 26 27 28 29 30 D A D D C A C B A A 31 32 33 34 35 36 37 38 39 40 B A B B C A D D C A ,通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，該緩沖區(qū)的 邏輯結(jié)構(gòu) 應(yīng)該是（隊(duì)列） 棧 的定義 :棧是只準(zhǔn)在表尾進(jìn)行插入和刪除的線性表，稱為 LIOFO（即后進(jìn)先出表）。 請(qǐng)給出 R1 的路由表，使其明確包括到局域網(wǎng) 1 的路由、局域網(wǎng) 2 的路由、域名服務(wù)器的主機(jī)路由和 互聯(lián)網(wǎng)的路由。 將 IP 地址空間 ，分配給局域網(wǎng) 局域網(wǎng) 2，每個(gè)局域網(wǎng)分配的地 頁(yè)號(hào) 頁(yè)框號(hào) 有效位 （存在位） 0 101H 1 1 0 2 254H 1 址數(shù)不少于 120 個(gè)，請(qǐng)給出子網(wǎng)劃分結(jié)果。 47．（ 9 分）某公司網(wǎng)絡(luò)拓?fù)鋱D如下圖所示，路由器 R1 通過接口 E E2 分別連接局域網(wǎng) 局域網(wǎng) 2， 通過接口 L0 連接路由器 R2，并通過路由器 R2 連接域名服務(wù)器與互聯(lián)網(wǎng)。設(shè)有虛地址訪問序列 2362H、 1565H、 25A5H，請(qǐng)問： （ 1） 依次訪問上述三個(gè)虛地址，各需多少時(shí)間？給出計(jì)算過程。 頁(yè)面大小為 4KB，一次內(nèi)存的訪問時(shí)間是 100ns，一次快表（ TLB）的訪問時(shí)間是10ns，處理一次缺頁(yè)的平均時(shí)間為 108ns（已含更新 TLB 和頁(yè)表的時(shí)間），進(jìn)程的駐留集大小固定為 2，采用最近最少使用置換算法（ LRU）和局部淘汰策略。要求用偽代碼描述。P1 每次用 produce（）生成一個(gè)正整數(shù)并用 put（）送入緩沖區(qū)某一空單元中；P2 每次用 getodd（）從該緩沖區(qū)中取出一個(gè)奇數(shù)并用 countodd（）統(tǒng)計(jì)奇數(shù)個(gè)數(shù)； P3 每次用 geteven（）從該緩沖區(qū)中取出一個(gè)偶數(shù)并用 counteven（）統(tǒng)計(jì)偶數(shù)個(gè)數(shù)。 data link 數(shù)據(jù)通路結(jié)構(gòu) 下表給出了上述指令取值和譯碼階段每個(gè)節(jié)拍（時(shí)鐘周期）的功能和有效控制信號(hào)，請(qǐng)按表中描 述方式用表格列出指令執(zhí)行階段每個(gè)節(jié)拍的功能和有效控制信號(hào)。假設(shè) MAR的輸出一直處于使能狀態(tài)。圖中所有控制信號(hào)為 1 時(shí)表示有效、為 0 時(shí)表示無效。 （ 1）在中斷方式下， CPU 用于該外設(shè) I/O 的時(shí)間占整個(gè) CPU 時(shí)間的百分比是多少？ （ 2）當(dāng)該外設(shè)的數(shù)據(jù)傳輸率達(dá)到 5MB/s 時(shí)，改用 DMA 方式傳送數(shù)據(jù)。假定某外設(shè)的 數(shù)據(jù)傳輸率為 ，采用中斷方式與主機(jī)進(jìn)行數(shù)據(jù)傳送，以 32 位為傳輸單位，對(duì)應(yīng)的中斷服務(wù)程序包含 18 條指令，中斷服務(wù)的其他開銷相當(dāng)于 2 條指令的執(zhí)行時(shí)間。要求： （ 1） 描述算法的基本設(shè)計(jì)思想 （ 2） 描述算法的詳細(xì)實(shí)現(xiàn)步驟 （ 3） 根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語言描述算法（使用 C 或 C++或 JAVA 語言實(shí)現(xiàn)），關(guān)鍵之處請(qǐng)給出簡(jiǎn)要注釋。在不改變鏈表的前提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第 k 個(gè)位置上的結(jié)點(diǎn)（ k 為正整數(shù)）。 請(qǐng)問上述方法能否求得最短路徑？若該方法可行，請(qǐng)證明之；否則，請(qǐng)舉例說明。 41.（ 10 分）帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離）的最短路徑問題是找出 從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑。當(dāng)擁塞窗口為 16KB 時(shí)發(fā)生了超時(shí)，如果接下來的 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è)磁道訪問請(qǐng)求序列為 35， 45， 12， 68， 110， 180， 170， 195，采用 SCAN 調(diào)度（電梯調(diào)度）算法得到的磁道訪問序列是 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 ，文件訪問控制信息存儲(chǔ)的合理位置是 A．文件控制塊 31．設(shè)文件 F1 的當(dāng)前引用計(jì)數(shù)值為 1，先建立 F1 的符號(hào)鏈接（軟鏈接）文件 F2，再建立 F1 的硬鏈接文件 F3，然后刪除 F1。別看錯(cuò)了。注意問的如果是“不會(huì)發(fā)生死鎖的最大值”就選 B。若某轉(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í)行過程中訪存 1000 次，其中訪問 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ī)。 現(xiàn)要用 2K 8 位的 ROM 芯片和 4K 4 位的 RAM 芯片來設(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 型。若遍歷后的結(jié)點(diǎn)序列為 3， 1， 7， 5， 6， 2， 4，則其遍歷方式是 A． LRN ，滿足平衡二叉樹定義的是 6 層（設(shè)根為第 1 層）有 8 個(gè)葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多