1、、單選題1、若元素a,b,c,d,e,f依次進棧，允許進棧、退棧操作交替進行。但不允許連續三次進行退棧工作，則不可能得到的出棧序列是（D ）A： dcebfa B : cbdaef C : dbcaef D : afedcb2、某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，則不可能得到 的順序是（C）A： bacde B : dbace C: dbcae D : ecbad3、下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（B ）4、在下列所示的平衡二叉樹中插入關鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關鍵字37所在結點的左、右子結點中保存的關鍵字分別是（C

2、 ）A: 13, 48 B: 24, 48 C: 24, 53 D: 24, 905、在一棵度為4的樹T中，若有20個度為4的結點，10個度為3的結點，1個度為2 的結點，10個度為1的結點，則樹T的葉節點個數是（B）A: 41 B : 82 C: 113 D : 1226、對n（n大于等于2）個權值均不相同的字符構成哈夫曼樹，關于該樹的敘述中，錯誤 的是（B）A:該樹一定是一棵完全二叉樹B:樹中一定沒有度為 1的結點C:樹中兩個權值最小的結點一定是兄弟結點D:樹中任一非葉結點的權值一定不小于下一任一結點的權值7、若無向圖G-（V.E）中含7個頂點，則保證圖 G在任何情況下都是連通的，則需要的

3、 邊數最少是（A）A : 6 B : 15 C: 16 D : 218、對下圖進行拓補排序，可以得到不同的拓補序列的個數是（B ）A 4 B: 3 C: 2 D: 19、已知一個長度為16的順序表L,其元素按關鍵字有序排列，若采用折半查找法查找 一個不存在的元素，則比較次數最多是（A）A: 4 B : 5 C : 6 D: 710、采用遞歸方式對順序表進行快速排序，下列關于遞歸次數的敘述中，正確的是（D）A:遞歸次數與初始數據的排列次序無關B:每次劃分后，先處理較長的分區可以減少遞歸次數C:每次劃分后，先處理較短的分區可以減少遞歸次數D:遞歸次數與每次劃分后得到的分區處理順序無關11、對一組數

4、據（2, 12, 16, 88, 5, 10）進行排序，若前三趟排序結果如下（A）第一趟：2, 12, 16, 5, 10, 88第二趟：2, 12, 5, 10, 16, 88第三趟：2, 5, 10, 12, 16, 88則采用的排序方法可能是:A:起泡排序B:希爾排序C:歸并排序D:基數排序12、下列選項中，能縮短程序執行時間的措施是(D)I提高CPU時鐘頻率，II優化數據通過結構，III對程序進行編譯優化A 僅 I 和 II B :僅 I 和 III C :僅 II 和 III D : I , II , III13、假定有4個整數用8位補碼分別表示r1=FEH ,r2=F2H ,r3=

5、90H,r4=F8H,若將運算結果存放在一個8位的寄存器中，則下列運算會發生溢出的是(C)A： r1*r2 B : r2*r3 C : r1*r4 D : r2*r414、假定變量I,f,d 數據類型分別為int,float 和double(int用補碼表示，float和double分別用IEEE754單精度和雙精度浮點數據格式表示)，已知i=785,f=1.5678,d=1.5若在32位機器中執行下列關系表達式，則結果為真是(C)(I)f=(int)(float)I (II)f=(float)(int)f(III)f=(float)(double) (IV)=(d+f)-d=fA：僅 I 和

6、 II B :僅 I 和 III C :僅 II 和 III D :僅 III 和 IV15、假定用若干個2k*4位芯片組成一個 8*8位存儲器，則地址 0B1FH所在芯片的最小 地址是(D)A: 0000H B: 0600H C: 0700H D : 0800H16、下列有關 RAMF口 ROM勺敘述中，正確的是 (A)I、RAM是易失性存儲器，RO屁非易失性存儲器II、RAM和ROMtB是采用隨機存取的方式進行信息訪問III、RAMF口 ROMTB可用作 CacheIV、RAMF口 ROMTB需要進行刷新A:僅 I 和 II B :僅 II 和 III C :僅 I,II , III D

7、:僅 II , III , IV17、下列命令組合情況中，一次訪存過程中，不可能發生的是(D)A： TLB未命中，Cache未命中，Page未命中B： TLB未命中，Cache命中,Page命中C: TLB命中，Cache未命中，Page命中D： TLB命中，Cache命中，Page未命中18、下列存儲器中，匯編語言程序員可見的是(B)A:存儲器地址寄存器(MAR) B :程序計數器(PC)C：存儲器數據寄存器(MDR) D:指令寄存器(IR)19、下列不會引起指令流水阻塞的是(A)A:數據旁路B:數據相關C:條件轉移D:資源沖突20、下列選項中的英文縮寫均為總線標準的是(D)A: PCI、C

8、RT USB EISA B: ISA、CPk VESA EISAC: ISA、SCSI、RAM MIPS D： ISA、EISA、PCk PCI-Express21、單級中斷系統中，中斷服務程序執行順序是(A)I、保護現場II、開中斷III 、關中斷IV、保存斷點V、中斷事件處理 VI、恢復現場 VII、中斷返回A: I、V、VI、II、VII B : III 、I、V、VIIC: III、IV、V VI、VII D : IV、I、V、VI、VII22、假定一臺計算機的顯示存儲器用DRA城片實現，若要求顯示分辨率為1600*1200,顏色深度為24位，幀頻為85Hz,顯示總帶寬的50%用來刷新

9、屏幕，則需要的顯存總帶寬至 少約為(D)A : 245 Mbps B : 979 MbpsC: 1958 Mbps D : 7834Mbps23、下列選項中，操作 S提供的給應用程序的接口是 (A)A:系統調用B:中斷C:庫函數D:原語24、下列選項中，導致創進新進程的操作是(C)I用戶成功登陸II設備分配III啟動程序執行A 僅I和II B :僅II和IIIC:僅 I 和 III D : I , II , III25、設與某資源相關聯的信號量初值為3,當前值為1,若M表示該資源的可用個數,表示等待資源的進程數，則M,N分別是(B )A: 0, 1 B: 1, 0 C: 1, 2 D: 2,

10、026、下列選項中，降低進程優先權級的合理時機是(A )A:進程的時間片用完 B:進程剛完成Z/O,進入就緒隊列C:進程長期處于就緒隊列中D:就緒從就緒狀態轉為運行態27、進行P0和P1的共享變量定義及其初值為 (A )boolean flag2;int turn=0;flag0=faulse;flag1=faulse;若進行P0和P1訪問臨界資源的類C代碼實現如下：Void p0()/ 進程 p0 Void p1()/進程 p1while(TURE) while(TURE)Flag0=TURE;ture=1 Flag1=TURE; ture=1While (flag1&(turn=1) Wh

11、ile (flag0&(turn=0)臨界區:Flag0=FALSE; Flag1=FALSE; 則并發執行進程 P0和P1時產生的情況是：A:不能保證進程互斥進入臨界區，會出現“饑餓”現象B:不能保證進程互斥進入臨界區，不會出現“饑餓”現象C:能保證進程互斥進入臨界區，會出現“饑餓”現象D:能保證進程互斥進入臨界區，不會出現“饑餓”現象28、某基于動態分區存儲管理的計算機，其主存容量為55mb（初試為空間），采用最佳適配（Best fit）算法，分配和釋放的順序為：分配15mb,分配30mb,釋放15mb,分配8mb,此時主存中最大空閑分區的大小是（B ）A: 7mb B： 9mb C: 1

12、0mb D： 15mb29、某計算機采用二級頁表的分頁存儲管理方式，按字節編制，頁大小為216字節，頁表項大小為2字節，邏輯地址結構為頁目編號頁號頁內偏移量邏輯地址空間大小為 216頁，則表示整個邏輯地址空間的頁目錄表中包含表項的個數至 少是（B ）A: 64 B : 128 C: 256 D: 51230、設文件索引節點中有 7個地址項，其中4個地址項為直接地址索引， 2個地址項是 一級間接地址索引，1個地址項是二級間接地址索引，每個地址項大小為4字節，若磁盤索引塊和磁盤數據塊大小均為 256字節，則可表示的單個文件的最大長度是（C ）A: 33kb B ： 519kb C: 1057kb

13、D ： 16513kb31、設置當前工作目錄的主要目的是（C ）A:節省外存空間B:節省內容空間C:加快文件的檢索速度D:加快文件的讀寫速度32、本地用戶通過鍵盤登錄系統時，首先獲得鍵盤輸入信息的程序是（B ）A:命令解釋程序 B :中斷處理程序C:系統調用程序 D:用戶登錄程序33、下列選項中，不屬于網絡體系結構中所描述的內容是（C ）A:網絡的層次B:每一層使用的協議C:協議的內部實現細節D:每一層必須完成的功能34、在下圖所示的采用“存儲 -轉發”方式分組的交換網絡中，所有鏈路的數據傳輸速 度為100mbps,分組大小為1000B,其中分組頭大小 20B,若主機H1向主機H2發送一個大

14、小為980000B的文件，則在不考慮分組拆裝時間和傳播延遲的情況下，從H1發送到H2接收完為止，需要的時間至少是 （A ）A： 80ms B： 80.08ms C： 80.16ms D ： 80.24ms35、某自治系統采用 RIP協議，若該自治系統內的路由器R1收到其鄰居路由器 R2的距離矢量中包含信息，則可能得出的結論是（A ）A： R2可以經過R1到達net1 ,跳數為17B: R2可以到達net1 ,跳數為16C: R1可以經過R2到達net1 ,跳數為17D： R1不能進過 R2到達net136、若路由器R因為擁塞丟棄IP分組，則此時R可以向發出該IP分組的源主機發送的 ICMP報文

15、件類型是（C ）A:路由重定向B:目的不可達C:源抑制D:超時37、某網絡的IP地址為192.168.5.0/24 采用長子網劃分，子網掩碼為255.255.255.248 ,則該網絡的最大子網個數，每個子網內的最大可分配地址個數為（B ）A: 32, 8 B: 32, 6C: 8, 32 D: 8, 3038、下列網絡設備中，能夠抑制網絡風暴的是（C ）I中繼器 n集線器出網橋IV路由器A：僅I和n B：僅出C:僅出和IV D:僅IV39、主機甲和主機乙之間已建立一個 TCP連接，TCP最大段長度為1000字節，若主機 甲的當前擁塞窗口為 4000字節，在主機甲向主機乙連接發送 2個最大段后

16、，成功收到主機 乙發送的第一段的確認段，確認段中通告的接收窗口大小為2000字節，則此時主機甲還可以向主機乙發送的最大字節數是 （A）A: 1000 B: 2000C: 3000 D: 400040、如果本地域名服務無緩存，當采用遞歸方法解析另一網絡某主機域名時，用戶主機本地域名服務器發送的域名請求條數分別為（A ）A: 1條，1條B: 1條，多條C:多條，1條D:多條，多條二、綜合應用題：41-47小題，共計70分41.（10分）將關鍵字序列（7、8、11、18、9、14）散列存儲到散列列表中，散列表的存 儲空間是一個下標從 0開始的一個一維數組散列函數維：H（key）=（key x 3）M

17、ODT處理沖突采用線性探測再散列法，要求裝填（載）因子為0.7問題: 請畫出所構造的散列表(2)分別計算等概率情況下，查找成功和查找不成功的平均查找長度。解答：(1)由裝載因子0.7 ,數據總數7個一存儲空間長度為 10-P=10所以，構造的散列表為：01234567893071411S189.9H(7)=(7 X3)MOD10=1(2)查找成功的 ASL=(1+1+1 + 1+2+1+1)/7=8/7查找不成功的 ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.242.(13分)設將n(n,1)個整數存放到一維數組R中，試設計一個在時間和空間兩方面盡可能有效的算法，將R中保有的

18、序列循環左移P(0Pn)個位置，即將R中的數據由(X0X1Xn-1)變換為(Xp Xp+1 Xn-1 X0 X1 Xp-1)要求：(1)給出算法的基本設計思想。(2)根據設計思想，采用 C或C+或JAVA語言表述算法，關鍵之處給出注釋。(3)說明你所設計算法的時間復雜度和空間復雜度解答：(1)前P個數依次進隊，while(1 +1-Rn011B相對D (Rn)轉移目標地址=(PC + (Rn)(X)表示有儲蓄地址 X或寄存器X的內容，請回答下列問題：(1)該指令系統最多可有多少條指令？該計算機最多有多少個通用寄存器？存儲器地址寄存器(MDR年少各需多少位？(2)轉移指令的目標地址范圍是多少？(

19、3)若操作碼0010B表示加法操作(助記符為a d d),寄存器R4和R5的編號分別為100B 和101B, R4的內容為1 2 3 4 H , R5的內容為 5 6 7 8 H ，地址1 2 3 4 H 中的內容為 5 6 7 8 H中的內容為1 2 3 4 H，則匯編語言為 a d d(R4).(R5)+(逗號前原操作數，都號后為目的操作數)對應的機器碼是什么(用十六進制表示)?該指令執行后，哪些寄存器和存儲單元 的內容會改變？改變后的內容是什么？解答：該題的考點是指令系統設計，注意操作位數與指令條數的關系，地址碼與寄存器數的關系，指令字長與 MOR勺關系，存儲容量與 MAR勺關系，注意補

20、碼計算的偏移地址。44.（12分）某計算機的主存地址空間為256MB按字節編址，指令 Cache分離均有8個Cache行，每個Cache行的大小為64MB數據Cache采用直接映射方式，現有兩個功能 相同的程序A和B,其偽代碼如下所示：程序A；Inta256251 n tsum.aray 1 () intfor(i=0Ji 2 5 6;i+)f or(j =0 J 2 5 6J + +) Sum+ = aU j;Return sum;)程序B:Inta256251 n t sumarga y2()(int ? j ,S um = 0,f or(j-0;j 2 56;j + +)f or(i =

21、 O; i 2 5 ft (+)Sum+-aU j:Return sum,假定int類型數據用32位補碼表示，程序編譯時i,j, sum均分配在寄存器中，數據a按行優先方式存放，其地址為320（十進制數），請回答下列問題，要求說明理由或給出計算過程。（1）、若不考慮用于 cache一致性維護和替換算法的控制位，則數據Cache的總容量是多少？（2）、要組元素a031和a11各自所在的主存塊對應的Cache行號分別是多少（Cache行號從0開始）?（3）、程序A和B的數據訪問命令中各是多少？那個程序的執行時間更短 ？簡答：考點：Cache容量計算，直接映射方式的地址計算，以及命中率計算（行優先遍

22、歷與列優先遍歷命中率分別很大）45、（7分）假設計算機系統采用 CSCANg環掃描）磁盤調度策略，使用 2KB的內存空間 記錄16384個磁盤塊的空間狀態（1）、請說明在上述條件下如何進行磁盤塊空閑狀態管理。隨機分布的某扇區0號磁道蔽頭運動方向100號磁道46.(8分)設某計算機的邏輯地址空間和物理地址空間均為64KB.按字節編址。若某進程最多需要6頁(Page)數據存儲空間，頁的大小為1KB.操作系統采用固定分配局部置換策略為此進程分配4個頁框(Page Fame).(2)、設某單面磁盤旋轉速度為每分鐘6000轉。每個磁道有100個扇區，相臨磁道間的平均移動時間為1ms.若在某時刻，磁頭位于100號磁道處，并沿著磁道號大的方向移動 (如下圖所示)，磁道頁號 頁根號號請求隊列為50.90.30.120.對請求隊列中的每個磁道需讀取1個隨機分布的扇區，則讀完這個扇區點共需要多少時間?要求給出計算過程。裝入時刻230訪問位當該進程執行到時刻 260時，要訪問邏輯地址為 17CAH的數據，請問答下列問題:(1)、該邏輯地址對應的頁號是多少 ？(2)、若采用先進先出(FIFO)置換算法，該邏輯地址對應的物理地址是多少？要求給出計算過程。(3)、若采用時鐘(CLOCK瘴換算法，該邏輯地址對應的物理地址是多少？要求給出計算過程。(設搜索下一頁的指針沿順時針方向移動，且當前指向 2號