【正文】 是 A． 39 ，若在二叉樹中，結點 u 是結點 v 的父結點的父結點，則在原來的森林中， u 和 v 可能具有的關系是 I．父子關系 關系 III. u 的父結點與 v 的父結點是兄弟關系 II 和 II 和 III 、 II 和 III ，正確的是 I．所有頂點的度之和為偶數(shù) 1 1 I B. 只有 II 和 II 和 III ，不符合 m 階 B 樹定義要求的是 A．根節(jié)點最多有 m 棵子樹 C．各結點內關鍵字均升序或降序排列 5， 8， 12， 19， 28， 20， 15， 22 是小根堆（最小堆），插入關鍵字 3，調整后得到的小根堆是 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 是采用下列 排序方法之一得到的第二趟排序后的結果，則該排序算法只能是 A．起泡排序 若每個元素出棧后立即進入隊列 Q，且 7 個元素出隊的順序是 bdcfeag，則棧 S 的容量至少是 A． 1 。 ，通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫 入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。共 70 分。2022 年統(tǒng)考計算機考研真題 .................................................... 1 一． 單項選擇題，每小題 2 分，共 80 分。 ....................................... 1 二． 綜合應用題。 ................................................... 5 2022 年計算機統(tǒng)考真題參考答案 ............................................... 10 一． 選擇題 ................................................................ 10 二． 綜合應用題 ............................................................. 24 2022 年全國研究生考試計算機統(tǒng)考試題及答案 24 2022 年統(tǒng)考計算機考研真題 一． 單項選擇題，每小題 2分，共 80分。該緩沖區(qū)的邏輯結構應該是 S 和隊列 Q 的初始狀態(tài)均為空，元素 abcdefg 依次進入棧 S。設 N 代表二叉樹的根， L 代表根結點的左子樹， R 代表根結點的右子樹。諾依曼計算機中指令和數(shù)據(jù)均以二進制形式存放在存儲器中， CPU 區(qū)分它們的依據(jù)是 A．指令操作碼的譯碼結果 C 語言程序在一臺 32 位機器上運行。當 x=127， y=9 時，執(zhí)行賦值語句 z=x+y 后， xyz 的值分別是 A． X=0000007FH， y=FFF9H， z=00000076H A． X=0000007FH， y=FFF9H， z=FFFF0076H A． X=0000007FH， y=FFF7H， z=FFFF0076H A． X=0000007FH， y=FFF7H， z=00000076H 、尾數(shù)運算、規(guī)格化、舍入和判溢出等步驟。若有兩個數(shù) X=27 29/32， Y=25 5/8，則用浮點加法計算 X+Y 的最終結果是 A． 00111 1100010 0100010 C． 01000 0010001 Cache 共有 16 塊，采用 2 路組相聯(lián)映射方式（即每組 2 塊）。主存 129 號單元所在主存塊應裝入到的 Cache 組號是 A． 0 64KB，其中 ROM 區(qū)為 4KB，其余為 RAM 區(qū)，按字節(jié)編址。假定取指令時，每取一個字節(jié) PC 自動加1。該系統(tǒng)可能 會發(fā)生死鎖的 K 的最小值 是 （） 不死鎖需要 2K+18，最多支持 3 個進程并發(fā) 。 4 個以上就死鎖，所以會死鎖的最小值是 4。 A． 2 26．分區(qū)分配內存管理方式的主要保護措施是 A．界地址保護 ，地址長度為 32 位，其中段號占 8 位，則段長最大 A． 2 的 8 次方字節(jié) 的 16 次方字節(jié) 的 24 次方字節(jié) 的32 次方字節(jié) ，適合 隨機訪問且易于文件擴展的是 A．連續(xù)結構 105 道，正在向磁道序號增加的方向移動。此時， F2和 F3 的引用計數(shù)值分別是 A． 0、 1 、 1 、 2 、 1 32．程序員利用系統(tǒng)調用打開 I/O 設備時，通常使 用的設備標識是 A．邏輯設備名 OSI 參考模型中，自下而上第一個提供端到端服務的層次是 A．數(shù)據(jù)鏈路層 34．在無噪聲情況下，若某通信鏈路的帶寬為 3kHz，采用 4 個相位，每個相位具有 4 種振幅的 QAM 調制技術，則該通信鏈路的最大數(shù)據(jù)傳輸速率是 A． 12kbps kbps kbps kbps N 幀（ GBN）協(xié)議 ，發(fā)送方已經發(fā)送了編號為 0~7 的幀。若最小數(shù)據(jù)幀長度減少 800 比特，則最遠的兩個站點之間的距離至少需要 A．增加 160m 80m 160m 80m TCP 連接，主機甲向主機乙發(fā)送了兩個連續(xù)的 TCP 段，分別包含 300 字節(jié)和 500 字節(jié)的有效載荷，第一個段的序列號為 200，主機乙正確接收到兩個段后，發(fā)送給主機甲的確認序列號是 A． 500 39．一個 TCP 連接總是以 1KB 的最大段發(fā)送 TCP 段，發(fā)送方有足夠多的數(shù)據(jù)要發(fā)送。共 70分。假定從初始頂點到目標頂點之間存在路徑，現(xiàn)有一種解決該問題的方法： ①設最短路徑初始時僅包含初始頂點，令當前頂點 u 為初始頂點； ②選擇離 u最近且尚未在最短路徑中的一個頂點 v，加入到最短路徑中，修改當前頂點 u=v； ③重復步驟②，直到 u 是目標頂點時為止。 42.（ 15 分）已知一個帶有表頭結點的單鏈表，結點結構為 假設該鏈 表只給出了頭指針 list。若查找成功，算法輸出該結點的 data 值，并返回 1；否則，只返回 0。 43.（ 8 分）某計算機的 CPU 主頻為 500MHz， CPI 為 5（即執(zhí)行每條指令平均需 5 個時鐘周期）。請回答下列問題，要求給出計算過程。假設每次 DMA 傳送大小為 5000B， 且 DMA 預處理和后處理的總開銷為 500 個時鐘周期，則 CPU 用于該外設 I/O 的時間占整個 CPU 時間的百分比是多少？（假設 DMA 與 CPU 之間沒有訪存沖突） 44.（ 13 分）某計算機字長 16 位，采用 16 位定長指令字結構，部分數(shù)據(jù)通路結構如圖所示。例如控制信號 MDRinE 為 1 表示允許數(shù)據(jù)從 DB 打入 MDR， MDRin 為 1 表示允許數(shù)據(jù)從內總線打入 MDR。加法指令“ ADD（ R1）， R0”的功能為（ R0） +（（ R1））→（ R1），即將 R0 中的數(shù)據(jù)與 R1 的內容所指主存單元的數(shù)據(jù)相加，并將結果送入 R1 的內容所指主存單元中保存。 功能和控制信號 時鐘 功能 有效控制信號 C1 MAR← (PC) PCout,MARin C2 MDR← M(MAR) PC← (PC)+1 MemR,MDRinE PC+1 C3 IR← (MDR) MDRout,IRin C4 指令譯碼 無 45.（ 7 分）三個進程 P P P3 互斥使用一個包含 N（ N0）個單元的緩沖區(qū)。請用信號量機制實現(xiàn)這三個進程的同步與互斥活動，并說明所定義的信號量的含義。 46.（ 8 分）請求分頁管理系統(tǒng)中，假設某進程 的頁表內容如下表所示。假設 ① TLB 初始為空； ②地址轉換時先訪問 TLB，若 TLB 未命中，再訪問頁表 （忽略訪問頁表之后的 TLB 更新時間）； ③有效位為 0 表示頁面不在內存，產生缺頁 中斷，缺頁中斷處理后，返回到產生缺頁中斷的指令處重新執(zhí)行。 （ 2） 基于上述訪問序列，虛地址 1565H 的 物理地址是多少？請說明理由。 R1 的 L0 接口的 IP 地址是 ； R2 的 L0 接口 的 IP 地址是 ， L1 接口的 IP 地址是 ， E0接口的 IP 地址是 ；域名服務器的 IP 地址是 。說明理由或給出必要的計算過程。 請采用路由聚合技術，給出 R2 到局域網 1 和 局域網 2 的路由。允許插入和刪除的一端叫棧頂，另一端叫棧底。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。其形式化定義為： G=(V ,E） 其中 G 表一個圖， V 是圖 G 中頂點的集合， E 是圖 G 中邊的集合。若每個元素出棧后立即進入隊列 Q，且 7 個元素出隊的順序是 bdcfeag,則 棧 S 的容量 ？？？（ 3） ，若遍歷后的結點序列為 XXX，則其 遍歷方式 是？？？ 設 N 代表二叉樹的根， L 代表根結點的左子樹， R 代表根結點的右子樹。我們把二叉樹中每個結點的左子樹高度減去右子樹高度定義為該結點的平衡因子 (balance factor)。 6 層（ 設根為第 1 層 ）有 8 個葉結點，則 完全二叉樹的結點個數(shù)最多是？？？（ 111） 二叉樹 ：二叉樹是一種重要的樹形結構，它是 n（ n=0）個結點的有限集，其子樹分為互不相交的兩個集合，分別稱為左子樹和右子樹，左子樹和右子樹也是如上定義的二叉樹。 滿二叉樹 ：深度為 k 結點數(shù)為 2^k1 的二叉樹。 森林轉換為對應的二叉樹 ，若在 二叉樹 中，結點 u 是結點 v 的父結點的父結點，則在 原來的森林中 ， u 和 v 可能具有的關系是 :父子關系或兄弟關系。（左孩子右兄弟） 的敘述 :所有 頂點的度 之和為 偶數(shù) 。 度為零的頂點稱為孤立頂點，度為奇數(shù)的頂點稱為奇點，度為偶數(shù)的頂點稱為偶點。 大根堆的定義與上述類似，只要把小于等于改為大于等于就得到了。 分別為一個小根堆和一個大根堆。 堆排序 利用了大根堆 (或小根堆 )堆頂記錄的關鍵字最大 (或最小 )這一特征，使得在當前無序區(qū)中選取最大 (或最小 )關鍵字的記錄變得簡單。 11， 12， 13， 7， 8， 9， 23， 4， 5 是第二趟排序后的結果，則該排序算法只能是 插入排序。一般地，第 i 趟起 泡排序從 1 到 ni+1 依次比較相鄰兩個記錄地關鍵字，如果發(fā) 生逆序，則交換之，其結果是這 ni+1 個記錄中，關鍵字最 大的記錄被交換到第 ni+1 的位置上，最多作 n1 趟。 直接插入排序基本思想 : 將一個記錄插入到已排序的有序表中，使插入后 的表仍然有序。 歸并排序基本思想 ： 又一類不同的排序方法，將兩個或兩個以上的有序表合并成一個新的有序表。 堆排序基本思想： ？ 調整為堆（關鍵） ？ 希爾排序 (Shell Sort) 基本思想 ： 大，劃分成若干子序列，分別 直接插入排序。 ： 十進制轉任意進制的通用方法是：除 x 取余倒排法（ x 代表進制數(shù)）。 Q ：八進制數(shù)。 H ：十六進制數(shù)。設浮點數(shù)的 階碼和尾數(shù) 均采用 補碼 表示，且位數(shù)分別為 5 位和 7 位（均含 2 位符號位）。 E 為階，包括階符和階碼（整數(shù)），階碼為數(shù)決定了浮點數(shù)的表示范圍。 對階原則：小階對大階。兩個符號 位出現(xiàn) “01”，表示已經 溢出 ，即結果大于 +1. ： :(1)半導體存儲器 。(3)光介子存儲器。 : (1)主存儲器（主存） 用于存放計算機運行期間的大量程序和數(shù)據(jù)的存儲器， CPU 能直接訪問。 (2)高速緩沖存儲器（ Cache） Cache 是介于 CPU 和主存之間高速小容量存儲器，用于存放最活躍的程序塊和數(shù)據(jù)。 特點：速度快，但容量小，位價格較高。 (3)輔助存儲器（外存儲器） 存放當前暫不參與運行的程序