【正文】 的命中率是 A． 5% % % % ，能引起外部中斷的事件是 A．鍵盤輸入 0 ，可并行的是 I 進程與進程 II 處理機與設(shè)備 III 處理機與通道 IV 設(shè)備與設(shè)備 A． I、 II 和 III B. I、 II 和 IV C. I、 III 和 IV D. II、 III 和 IV ，綜合考慮進程等待時間和執(zhí)行時間的是 A．時間片輪轉(zhuǎn)調(diào)度算法 8 臺打印機，有 K 個進程競爭使用，每個進程最多需要 3 臺打印機。別看錯了。當計時器超時時，若發(fā)送方只收到 0、 3 號幀的確認，則發(fā)送方需要重發(fā)的幀數(shù)是 A． 2 PDU 地址是 A．目的物理地址 IP 地址 IP 地址 CSMA/CD 協(xié)議的網(wǎng)絡(luò)中，傳輸介質(zhì)是一根完整的電纜，傳輸速率為 1Gbps，電纜中的信號傳播速度是 200 000km/s。 41.（ 10 分）帶權(quán)圖（權(quán)值非負，表示邊連接的兩頂點間的距離）的最短路徑問題是找出 從初始頂點到目標頂點之間的一條最短路徑。在不改變鏈表的前提下，請設(shè)計一個盡可能高效的算法，查找鏈表中倒數(shù)第 k 個位置上的結(jié)點（ k 為正整數(shù)）。假定某外設(shè)的 數(shù)據(jù)傳輸率為 ，采用中斷方式與主機進行數(shù)據(jù)傳送，以 32 位為傳輸單位，對應(yīng)的中斷服務(wù)程序包含 18 條指令，中斷服務(wù)的其他開銷相當于 2 條指令的執(zhí)行時間。圖中所有控制信號為 1 時表示有效、為 0 時表示無效。 data link 數(shù)據(jù)通路結(jié)構(gòu) 下表給出了上述指令取值和譯碼階段每個節(jié)拍（時鐘周期）的功能和有效控制信號，請按表中描 述方式用表格列出指令執(zhí)行階段每個節(jié)拍的功能和有效控制信號。要求用偽代碼描述。設(shè)有虛地址訪問序列 2362H、 1565H、 25A5H，請問： （ 1） 依次訪問上述三個虛地址，各需多少時間？給出計算過程。 將 IP 地址空間 ，分配給局域網(wǎng) 局域網(wǎng) 2，每個局域網(wǎng)分配的地 頁號 頁框號 有效位 （存在位） 0 101H 1 1 0 2 254H 1 址數(shù)不少于 120 個，請給出子網(wǎng)劃分結(jié)果。 2022 年計算機統(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è)置一個打印數(shù)據(jù)緩沖區(qū)，該緩沖區(qū)的 邏輯結(jié)構(gòu) 應(yīng)該是（隊列） 棧 的定義 :棧是只準在表尾進行插入和刪除的線性表，稱為 LIOFO（即后進先出表）。隊列也稱為先進先出表（ FIFO） 樹 的定義：樹是包含 n 個結(jié)點的有限 集合（ n0） 圖 的定義：圖（ Graph）是由非空的頂點集合和一個描述頂點之間關(guān)系 ——邊（或者弧）的集合組成。 叉樹定義 :若一棵二叉樹中每個結(jié)點的左、右子樹的高度至多相差 1，則稱此樹為平衡二叉樹。左子 樹和右子樹的順序不能互換。 森林轉(zhuǎn)換為對應(yīng)的二叉樹 :兄弟之間連線，父只與長子連線。 m 階 B 樹 （ 1970 年， 和 提出了一種適用于 外查找 的樹，它是一種 平衡多叉樹 ） 定義： ⑴ 樹中每個結(jié)點至多有 m 個孩子； ⑵ 除根結(jié)點和葉子結(jié)點外，其它每個結(jié)點至少有 m/2 個孩子； ⑶ 若根結(jié)點不是葉子結(jié)點，則至少有 2 個孩子 (除非 B 樹只有一個結(jié)點 )； ⑷ 所有葉子結(jié)點都出現(xiàn)在同一層，葉子結(jié)點不包含任何關(guān)鍵字信息； ⑸ 有 k 個孩子的非終 端結(jié)點恰好包含有 k1 個關(guān)鍵字 (各節(jié)點內(nèi)關(guān)鍵字均升序或降序排列 ). (Heap)分為小根堆和大根堆兩種，對于一個小根堆，它是具有如下特性的一棵完全二叉樹： (1)若樹根結(jié)點存在左孩子，則根結(jié)點的值 (或某個域的值 )小于等于左孩子結(jié)點的值 (或某個域的值 )； (2)若樹根結(jié)點存在右孩子，則根結(jié)點的值 (或某個域的值 )小于等于右孩子結(jié)點的值 (或某個域的值 )； (3)以左、右孩子為根的子樹又各是一個堆。根據(jù)堆的定義可知，堆頂結(jié)點，即整個完全二叉樹的根結(jié)點，對于小根堆來說具有最小值，對于大根堆來說具有最大值。 氣 泡排序基本思想 ： 設(shè)待排序?qū)ο笮蛄兄械膶ο髠€數(shù)為 n。 折半插入排序基本思想 ： 將一個記錄插入到已排序的有序表中，使插入后的表仍然有序，但插入時利用折半搜索法尋找元素的插入位置。 “基本有序 ”時，對整體直接重排。 如：將十進制數(shù) 76 轉(zhuǎ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 ：二進制數(shù)。 負數(shù)用十六進制和八進制怎么表示 ？ 使用 補碼（二進制） ，而且還要指定字長 比如說一個二字節(jié)整型的 2 就應(yīng)該是： 11111111 11111110 再轉(zhuǎn)化其它進制 十六進制： FFFE 八進制： 177776 加減運算過程一般包括 對階、尾數(shù)運算、規(guī)格化、舍入和判溢出 等步驟。 M 為位數(shù)，包括數(shù)符和尾數(shù)，表示數(shù)的精度和正負。(2)磁表面存儲器 。由 MOS 存儲器構(gòu)成。 主存和 Cache 一起構(gòu)成計算機的 內(nèi)存儲器 （內(nèi)存），是 CPU 能直接訪問的存儲器 。 CM 一般由 ROM 構(gòu)成，屬于控制器的一部分。 (2)非永久性存儲器 :指斷電后信息即消失的存儲器，如半導體讀寫存儲器?，F(xiàn)要用2K*8 位的 ROM 芯片和 4K*4 位的 RAM 芯片來設(shè)計該存儲器，則需要上述規(guī)格的 ROM芯片數(shù)和 RAM 芯片數(shù)分別是 2 30 16 位，主存按字節(jié)編址，轉(zhuǎn)換指令采用相對尋址，由兩個字節(jié)組成，第一字節(jié)為操作碼字段，第二字節(jié)為相對位移量字段。 。這些時鐘周期的總和則規(guī)定了一個 CPU 周期的時間寬度。 1KHz=1000Hz； 1MHz=1000KHz 并行總線帶寬 (MB/s) = 并行總線時鐘頻率 (MHz) * 并行總線位寬 (bit/8 = B) * 每 時鐘傳輸幾組數(shù)據(jù) (cycle) 串行總線帶寬 (MB/s) = 串行總線時鐘頻率 (MHz) * 串行總線位寬 (bit/8 = B) * 串行總線管線 * 編碼方式 * 每時鐘傳輸幾組數(shù)據(jù) (cycle) 1 字節(jié)（ Byte） = 8 位（ bit） Cache 和主存組成，某程序執(zhí)行過程中訪存 1000 次，其中訪問 Cache 缺失（未命中） 50 次，則 Cache 的命中率 是 (95%) 是 :鍵盤輸入 (人的干預(yù) )或外請求。 短進程優(yōu)先 :取所需的運行時間最短的進程 (該算法能使平均等待時間最短 ). 8 臺打印機，有 K 個進程競爭使用，每個進程最多需要 3 臺打印機。 鏈接結(jié)構(gòu) ：一個文件的信息存放在若干不連續(xù)的物理塊中，各塊之間通過指針連接，前一個物理塊指向下一個物理塊。 優(yōu)點：保持了鏈接結(jié)構(gòu)的優(yōu)點 ,又解決了其缺點；即能順序存取 ,又能隨機存??；滿足了文件動態(tài)增長、插入刪除的要求；也能充分利用外存空間。如果該方向上已無 I/O 請求，則改變方向再做選擇。 ：在磁盤上有一份內(nèi)容一樣的文件產(chǎn)生，但不改變文件的 Inode,也就是與原文件共用 Inode。 I/O 設(shè)備時，通常使用的 設(shè)備標識是（邏輯設(shè)備名）。 傳輸層是兩臺計算機經(jīng)過網(wǎng)絡(luò)進行數(shù)據(jù)通信時 ,第一個端到端的層次，具有緩沖作用。 奈奎斯特準則 指出：對于二進制數(shù)據(jù)信號的最大數(shù)據(jù)傳輸速率 Rmax與通信信道帶寬 B（ B=f,單位 Hz)的關(guān)系可以寫為： Rmax＝ 2*B(bps) 香農(nóng)定理 指出：在有隨機熱噪聲的信道上傳輸數(shù)據(jù)信號時，數(shù)據(jù)傳輸速率 Rmax 與信道帶寬 B、信噪比 S/N 的關(guān)系為： Rmax＝ B*log2(1+S/N)) [以 2 為底 ,1+S/N 的對數(shù) ] 式中， Rmax 單位為 bps,帶寬 B 單位為 Hz，信噪比 S/N 通常以 dB（分貝）數(shù)表示。 數(shù)據(jù)鏈路層采用了后退 N 幀（ GBN）協(xié)議，發(fā)送方已經(jīng)發(fā)送了編號為 0~7 的幀。在局域網(wǎng)中，網(wǎng)絡(luò)中實際傳輸?shù)氖?“幀 ”，幀里面是有目標主機的 MAC 地址的。 ARP 協(xié)議的基本功能就是通過目標設(shè)備的 IP 地址，查詢目標設(shè)備的 MAC 地址，以保證通信的順利進行。每個站必須有能力隨時檢測沖突是否發(fā)生，一旦發(fā)生沖突，則應(yīng)停止發(fā)送，以免介質(zhì)帶寬因傳送無效幀而被白白浪費，然后隨機延時一段時間后，再重新爭用介質(zhì)，重發(fā)送幀。 最短幀長 =2*L*10^9(b/s)247。接收到第二個報文段（其序號為 1100）后，目的主機返回確認號 1200。當定時器超時或 達到發(fā)送窗口設(shè)定值，停止擁塞窗口尺寸的增加。 客戶和服務(wù)器間傳遞 FTP 時，使用的連接是 (建立在 TCP 之上的控制連接 )。當遍歷 到鏈表的最后一個節(jié)點時，指針 P 所指向的節(jié)點即為所查找的節(jié)點。 （ 3）算法描述： Int LocateElement(linklist list,int k) { P1=listlink。 i++。 return 1。 Parbegin P1:begin X=produce()。 If x%2==0 V(s2)。 P(mutex)。 V(empty)。 V(mutex)?？傻萌齻€虛地址的頁號 P 如下（十六進制的一位數(shù)字轉(zhuǎn)換成 4 位二進制，因此，十六進制的低三位正好為頁內(nèi)位移，最高位為頁號）： 2362H： P=2，訪問快表 10ns，因初始為空，訪問頁表 100ns 得到頁框號，合成物理地址后訪問主存 100ns，共計 10ns+100ns+100ns=210ns。由此可得 1565H 的物理地址為 101565H。 根據(jù)無類 IP 地址的規(guī)則，每個網(wǎng)段中有兩個地址是不分配的：主機號全 0 表示網(wǎng)絡(luò)地址，主機號全 1 表示廣播地址。 X 是整數(shù)。局 域網(wǎng) 1 的網(wǎng)絡(luò)地址和掩碼在問題（ 1）已經(jīng)求出來了，為。 局域網(wǎng) 2 的網(wǎng)絡(luò)地址和掩碼在問題（ 1）中已經(jīng)求出來了，為 。由于域名服務(wù)器的 IP 地址為 ，而該地址為主機地址，因此掩碼為 。默認路由是一種特殊的靜態(tài)路由，指的是當路由表中與包的目的地址之間沒有匹配的表項時路由器能夠做出的選擇。同時路由器 R1 連接的網(wǎng)絡(luò)需要通過路由器 R2 的 L0 口才能到達互聯(lián)網(wǎng)絡(luò)，因此下一跳地址填寫 L0 的 IP 為 。但不允許連續(xù)三次進行退棧工作，則不可能得到的出棧序列是（ D ） A： dcebfa B： cbdaef C： dbcaef D： afedcb 某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，則不可能得到的順序是（ C ） A： bacde B： dbace C： dbcae D： ecbad 下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（ B ） 在下列所示的平衡二叉樹中插入關(guān)鍵字 48 后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字 37 所在結(jié)點的左、右子結(jié)點中保存的關(guān)鍵字分別是（ C ） A： 13， 48 B： 24， 48 C： 24， 53 D： 24， 90 在一棵度為 4 的樹 T 中，若有 20 個度為 4 的結(jié)點， 10 個度為 3 的結(jié)點， 1 個度為 2 的結(jié)點， 10 個度為 1 的結(jié)點，則樹 T 的葉節(jié)點個數(shù)是（ B） A： 41 B： 82 C： 113 D： 122 對 n(n 大于等于 2)個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是（ B） A：該樹一定是一棵完全二叉樹 B：樹中一定沒有度為 1 的結(jié)點 C：樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點 D：樹中任一非葉結(jié)點的權(quán)值一定不小于下一任一結(jié)點的權(quán)