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