【正文】 數(shù)據(jù)的下標為 H(7) = (7*3) MOD 10 = 1 H(8) = (8*3) MOD 10 = 4 H(30) = (30*3) MOD 10 = 0 H(11) = (11*3) MOD 10 = 3 H(18) = (18*3) MOD 10 = 4 H1 = ( H(18) +1) MOD 10 = 5 H(9) = (9*3) MOD 10 = 7 H(14) = (14*3) MOD 10 = 2 所構(gòu)造的散列表如下： 0 1 2 3 4 5 6 7 8 9 30 7 14 11 8 18 9 (2)查找成功的平均查找長度為： ASL1 = (1+1+1+1+2+1+1)/7 = 8/7 查找不成功的平均查找長度為： ASL2 =(7+6+5+4+3+2+1+2+1+1) = 4 （ 1）建立一個可以放下 p 個整數(shù)的輔助隊列，將數(shù)組 R 中的前 p 個整數(shù)依次進入輔助隊列，將 R 中后面的 np 個整數(shù)依次前移 p 個位置，將輔助隊列中的數(shù)據(jù)依次出隊，依次放入 R 中第 np 個整數(shù)開始的位置。 while(i np) { //將 R 中從第 p 個整數(shù)開始的整數(shù)前移 p 個位置。 } （ 3）所設(shè)計的算法的時間復(fù)雜度為 O(n),空間復(fù)雜度為 O(p) 4 （ 1） OP 字段占 4 個 bit 位，因此該指令系統(tǒng)最多有 2^4 = 16 條指令； Rs/Rd 為 3 個 bit，因此最多有 2^3 = 8 個通用寄存器； 128K/2 = 64k = 2^16,所以存儲器地址寄存器位數(shù)至少為 16 位，（ 勤思考研 ）指令字長度為 16 位，所以存儲器數(shù)據(jù)寄存 器至少為 16 位。 4 （ 1） 2KB = 2*1024*8bit = 16384bit。 （ 3）若采用時鐘算法，且當前指針指向 2 號頁框，則第一次循環(huán)時，訪問位都被置為 0，在第二次循環(huán)時 ，將選擇置換 2 號頁框?qū)?yīng)的頁，因此對應(yīng)的二進制物理地址為： 0000 1011 1100 1010，轉(zhuǎn)換為 16 進制物理地址為 0BCAH。 （ 3） cache 的命中率等于訪問 cache 的次數(shù)除以 cache 的次數(shù)加上訪問內(nèi)存的次數(shù)。 i++。 i++。 (3)、采用時鐘 (Clock)置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算過程。 } 假定 int 類型數(shù)據(jù)用 32 位補碼表示，程序編譯時 i， j， sum 均分配在寄存器中，數(shù)組 a 按行優(yōu)先方式存放，其地址為 320(十進制 )。 } 程序 B: int a[256][256]。指令 Cache 分離，均有 8 個 Cache 行，每個 Cache 行大小為 64MB，數(shù)據(jù) Cache 采用直接映射方式，（勤思教育）現(xiàn)有兩個功能相同的程序 A 和B，其偽代碼如下： 程序 A: int a[256][256]。 (2).分別計算等概率情況下，查找成功和查找不成功的平均查找長度。 While (flag[1]amp。 若元素 a、 b、 c、 d、 e、 f 依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退棧工作，則不可能得到的出棧序列是（） A、 dcebfa B、 cbdaef C、 bcaefd D、 afedcb 某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，則不可能得到的順順序是（） A、 bacde B、 dbace C、 dbcae D、 ecbad 下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（） 在下列所示的平衡二叉樹中插入關(guān)鍵字 48 后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字 37 所在結(jié)點的左、右子結(jié)點中 保存的關(guān)鍵字分別是（） A、 13， 48 B、 24， 48 C、 24， 53 D、 24， 90 在一棵度數(shù)為 4 的樹 T 中，若有 20 個度為 4 的結(jié)點， 10 個度為 3 的結(jié)點， 1 個度為 2 的結(jié)點， 10 個度為 1 的結(jié)點，則樹 T 的葉結(jié)點個數(shù)是（） A、 41 B、 82 C、 113 D、 122 對 n（ n=2）個權(quán)值均不相同的字符構(gòu)成哈弗曼樹，關(guān)于該樹的敘述中，錯誤的是（） A、 該樹一定是一棵完全二交叉 B、 樹中一定沒有度為 1 的結(jié)點 C、 樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點 D、 樹中任一非葉結(jié)點的權(quán)值一定不小于下一層任一結(jié)點的權(quán)值 若無向圖 G=（ ）中含 7 個頂點，則保證圖 G 在任何情況下都是連通的，則需要的邊數(shù)最少是（） A、 6 B、 15 C、 16 D、 21 對下圖進行拓撲排序，可以得到不同的拓撲序列的個數(shù)是（） A、 4 B、 3 C、 2 D、 1 已知一個長度為 16 的順序表 L，其元素按關(guān)鍵字有序排列，若采用折半查找法查找一個不存在的元素，則比較次數(shù)最多的是（） A、 4 B、 5 C、 6 D、 7 采用遞歸方式對順序表進行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是（） A、 遞歸次數(shù)于初始數(shù)據(jù)的排列次數(shù)無關(guān) B、 每次劃分 后，（ 勤思考研 ）先處理較長的分區(qū)可以減少遞歸次數(shù)（勤思考研） C、 每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù) D、 遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān) 1對一組數(shù)據(jù) (2， 12， 16， 88， 5， 10)進行排序，若前三趟排序結(jié)果如下： () 第一趟： 2， 12， 16， 5， 10， 88 第二趟： 2， 12， 5， 10， 16， 88 第三趟： 2， 5， 10， 12， 16， 88 則采用的排序方法可能是 法 ，能縮短程序執(zhí)行時間的措施是 () CPU 時鐘頻率 1 和 2 1 和 3 C,僅 2 和 3 ,2,3 4 個整數(shù)用 8 位補碼分別表示 r1=FEH， r2=F2H， r3=90H， r4=F8H，若將運算結(jié)果存放在一個 8位寄存器中，則下列運算會發(fā)生益處的是 () A. r1 x r2 B. r2 x r3 C. r1 x r4 D. r2 x r4 i， f， d 數(shù)據(jù)類型分別為 int, float, double(int 用補碼表示， float 和 double 用 IEEE754 單精度和雙精度浮點數(shù)據(jù)格式表示 )，已知 i=785， f=， d=，若在 32 位機器中執(zhí)行下列關(guān)系表達式，（ 勤思考研 ）則結(jié)果為真的是 () (I) i==(int)(float)I (II)f==(float)(int)f (III)f==(float)(double)f (IV)(d+f)d==f A. 僅 I 和 II B. 僅 I 和 III C. 僅 II 和 III D. 僅 III 和 IV 2K x 4 位芯片組成一個 8K x 8 為存儲器，則 0B1FH 所在芯片的最小地址是 () RAM 和 ROM 得敘述中正確的是 () I RAM 是易失性存儲器， ROM 是非易失性存儲器 II RAM 和 ROM 都是采用隨機存取方式進行信息訪問 III RAM 和 ROM 都可用做 Cache IV RAM 和 ROM 都需要進行刷新 A. 僅 I 和 II B. 僅 II 和 III C. 僅 I ， II， III D. 僅 II， III， IV ，一次訪存過程中，不可能發(fā)生的是 () 未命中， Cache 未命中， Page 未命中 未命中， Cache 命中， Page 命中 命中， Cache 未命中， Page 命中 命中， Cache 命中， Page 未命中 ，反匯編語言程序員可見的是 () (MAR) (PC) (MDR) (IR) () () A. PCI、 CRT、 USB、 EISA B. ISA、 CPI、 VESA、 EISA C. ISA、 SCSI、 RAM、 MIPS D. ISA、 EISA、 PCI、 PCIExpress 2 單級中斷系統(tǒng)中，中斷服務(wù)程序執(zhí)行順序是（） I 保護現(xiàn)場 II 開中斷 III 關(guān)中斷 IV 保存斷點 V 中斷事件處理 VI 恢復(fù)現(xiàn)場 VII 中斷返回 A、 IVVIIIVII B、 IIIIVVII C、 IIIIVVVIVII D、 IVIVVIVII 2 假定一臺計算機的顯示存儲器用 DRAM 芯片實現(xiàn)，（ 勤思考研 ）若要求顯示分辨率為 1600*1200，顏色深度為 24 位，幀頻為 85HZ，現(xiàn)實總帶寬的 50%用來刷新屏幕，則需要的顯存總帶寬至少約為（） A、 245Mbps B、 979Mbps C、 1958Mbps D、 7834Mbps 2 下列選 項中，操作 S 提供的給應(yīng)程序的接口是（） A、 系統(tǒng)調(diào)用 B、 中斷 C、 庫函數(shù) D、 原語 2 下列選項中，導(dǎo)制創(chuàng)進新進程的操作是（） I 用戶登陸成功 II 設(shè)備分配 III 啟動程序執(zhí)行 A、 僅 I 和 II B、 僅 II 和 III C、 僅 I 和 III D、 I、 II、 III 2 設(shè)與某資源相關(guān)聯(lián)的信號量初值為 3，當前值為 1，若 M 表示該資源的可用個數(shù)，（ 勤思考研 ） N 表示等待該資源的進程數(shù)，則 M， N 分別是（） A、 0， 1 B、 1， 0 C、 1， 2 D、 2， 0 2 下列選項中，降低進程優(yōu)先權(quán)級的合理時機是（） A、 進程的時間片用完 B、 進程剛完成 I/O，進入就緒列隊 C、 進程長期處于就緒列隊 D、進程 從就緒狀態(tài)轉(zhuǎn)為運行狀態(tài) 2 進行 PO 和 P1 的共享變量定義及其初值為（） booleam flag[2]。如果沒有默