1、若元素a,b,c,d,e,f依次進棧，允許進棧、退棧操作交替進行。但不允許連續三次進行退棧工作，則不可能得到的出棧序列是( D )
A：dcebfa B：cbdaef C：dbcaef D：afedcb
2、某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，則不可能得到的順序是( C )
A：bacde B：dbace C：dbcae D：ecbad
3、下列線索二叉樹中(用虛線表示線索)，符合后序線索樹定義的是( B )
4、在下列所示的平衡二叉樹中插入關鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關鍵字37所在結點的左、右子結點中保存的關鍵字分別是( C )
A：13，48 B：24，48 C：24，53 D：24，90
5、在一棵度為4的樹T中，若有20個度為4的結點，10個度為3的結點，1個度為2的結點，10個度為1的結點，則樹T的葉節點個數是(B)
A：41 B：82 C：113 D：122
6、對n(n大于等于2)個權值均不相同的字符構成哈夫曼樹，關于該樹的敘述中，錯誤的是(B)
A：該樹一定是一棵完全二叉樹
B：樹中一定沒有度為1的結點
C：樹中兩個權值最小的結點一定是兄弟結點
D：樹中任一非葉結點的權值一定不小于下一任一結點的權值
7、若無向圖G-(V.E)中含7個頂點，則保證圖G在任何情況下都是連通的，則需要的邊數最少是(A)
A ：6 B：15 C：16 D：21
8、對下圖進行拓補排序，可以得到不同的拓補序列的個數是(B )
A：4 B：3 C：2 D：1
9、已知一個長度為16的順序表L，其元素按關鍵字有序排列，若采用折半查找法查找一個不存在的元素，則比較次數最多是(A)
A：4 B：5 C：6 D：7
10、采用遞歸方式對順序表進行快速排序，下列關于遞歸次數的敘述中，正確的是(D)
A：遞歸次數與初始數據的排列次序無關
B：每次劃分后，先處理較長的分區可以減少遞歸次數
C：每次劃分后，先處理較短的分區可以減少遞歸次數
D：遞歸次數與每次劃分后得到的分區處理順序無關
11、對一組數據(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，III
13、假定有4個整數用8位補碼分別表示r1=FEH ,r2=F2H ,r3=90H,r4=F8H,若將運算結果存放在一個8位的寄存器中，則下列運算會發生溢出的是(C)
A： r1*r2 B ：r2*r3 C：r1*r4 D：r2*r4
14、假定變量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=f
A：僅I和II B：僅I和III C：僅II和III D：僅III和IV
15、假定用若干個2k*4位芯片組成一個8*8位存儲器，則地址0B1FH所在芯片的最小地址是(D)
A：0000H B：0600H C： 0700H D：0800H
16、下列有關RAM和ROM的敘述中，正確的是(A)
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
17、下列命令組合情況中，一次訪存過程中，不可能發生的是(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、CRT、USB、EISA B：ISA、CPI、VESA、EISA
C：ISA、SCSI、RAM、MIPS D：ISA、EISA、PCI、PCI-Express
21、單級中斷系統中，中斷服務程序執行順序是(A)
I、保護現場 II、開中斷 III、關中斷 IV、保存斷點
V、中斷事件處理 VI、恢復現場 VII、中斷返回
A：I、V、VI、II、VII B：III、I、V、VII
C：III、IV、V、VI、VII D：IV、I、V、VI、VII
22、假定一臺計算機的顯示存儲器用DRAM芯片實現，若要求顯示分辨率為1600*1200，顏色深度為24位，幀頻為85Hz，顯示總帶寬的50% 用來刷新屏幕，則需要的顯存總帶寬至少約為(D)
A ：245 Mbps B：979 Mbps
C：1958 Mbps D：7834Mbps
23、下列選項中，操作S提供的給應用程序的接口是(A)
A：系統調用 B：中斷
C：庫函數 D：原語
24、下列選項中，導致創進新進程的操作是(C)
I用戶成功登陸 II設備分配 III啟動程序執行
A：僅I和II B：僅II和III
C：僅I和III D：I，II，III
25、設與某資源相關聯的信號量初值為3，當前值為1，若M表示該資源的可用個數，N表示等待資源的進程數，則M,N分別是(B )
A：0，1 B：1，0 C：1，2 D：2，0
26、下列選項中，降低進程優先權級的合理時機是( A )
A：進程的時間片用完 B：進程剛完成Z/O，進入就緒隊列
C：進程長期處于就緒隊列中 D：就緒從就緒狀態轉為運行態
27、進行P0和P1的共享變量定義及其初值為( A )
boolean flag[2];
int turn=0;
flag[0]=faulse;flag[1]=faulse;
若進行P0和P1訪問臨界資源的類C代碼實現如下：
Void p0()// 進程p0 Void p1()// 進程p1
{while(TURE)} {while(TURE)}
Flag[0]=TURE;ture=1 Flag[1]=TURE; ture=1
While (flag[1]&&(turn==1)) While (flag[0]&&(turn==0))
臨界區：
Flag[0]=FALSE; Flag[1]=FALSE;
} }
} }
則并發執行進程P0和P1時產生的情況是：
A：不能保證進程互斥進入臨界區，會出現“饑餓”現象
B：不能保證進程互斥進入臨界區，不會出現“饑餓”現象
C：能保證進程互斥進入臨界區，會出現“饑餓”現象
D：能保證進程互斥進入臨界區，不會出現“饑餓”現象
28、某基于動態分區存儲管理的計算機，其主存容量為55mb(初試為空間)，采用最佳適配(Best fit)算法，分配和釋放的順序為：分配15mb，分配30mb，釋放15mb，分配8mb，此時主存中最大空閑分區的大小是( B )
A：7mb B：9mb C：10mb D：15mb
29、某計算機采用二級頁表的分頁存儲管理方式，按字節編制，頁大小為216字節，頁表項大小為2字節，邏輯地址結構為
頁目編號頁號頁內偏移量
邏輯地址空間大小為216頁，則表示整個邏輯地址空間的頁目錄表中包含表項的個數至少是( B )
A：64 B：128 C：256 D：512
30、設文件索引節點中有7個地址項，其中4個地址項為直接地址索引，2個地址項是一級間接地址索引，1個地址項是二級間接地址索引，每個地址項大小為4字節，若磁盤索引塊和磁盤數據塊大小均為256字節，則可表示的單個文件的最大長度是( C )
A：33kb B：519kb C：1057kb D：16513kb
31、設置當前工作目錄的主要目的是( C )
A：節省外存空間 B：節省內容空間
C：加快文件的檢索速度 D：加快文件的讀寫速度
32、本地用戶通過鍵盤登錄系統時，首先獲得鍵盤輸入信息的程序是(B )
A：命令解釋程序 B：中斷處理程序
C：系統調用程序 D：用戶登錄程序
33、下列選項中，不屬于網絡體系結構中所描述的內容是( C )
A：網絡的層次 B：每一層使用的協議
C：協議的內部實現細節 D：每一層必須完成的功能
34、在下圖所示的采用“存儲-轉發”方式分組的交換網絡中，所有鏈路的數據傳輸速度為100mbps，分組大小為1000B，其中分組頭大小20B，若主機H1向主機H2發送一個大小為980000B的文件，則在不考慮分組拆裝時間和傳播延遲的情況下，從H1發送到H2接收完為止，需要的時間至少是( A )
A：80ms B：80.08ms C：80.16ms D：80.24ms
35、某自治系統采用RIP協議，若該自治系統內的路由器R1收到其鄰居路由器R2的距離矢量中包含信息，則可能得出的結論是( A )
A：R2可以經過R1到達net1，跳數為17
B：R2可以到達net1，跳數為16
C：R1可以經過R2到達net1，跳數為17
D：R1不能進過R2到達net1
36、若路由器R因為擁塞丟棄IP分組，則此時R可以向發出該IP分組的源主機發送的ICMP報文件類型是( C )
A：路由重定向 B：目的不可達
C：源抑制 D：超時
37、某網絡的IP地址為192.168.5.0/24采用長子網劃分，子網掩碼為255.255.255.248，則該網絡的最大子網個數，每個子網內的最大可分配地址個數為( B )
A：32，8 B：32，6
C：8，32 D：8，30
38、下列網絡設備中，能夠抑制網絡風暴的是( C )
Ⅰ中繼器 Ⅱ集線器 Ⅲ網橋 Ⅳ路由器
A：僅Ⅰ和Ⅱ B：僅Ⅲ
C：僅Ⅲ和Ⅳ D：僅Ⅳ
39、主機甲和主機乙之間已建立一個TCP連接，TCP最大段長度為1000字節，若主機甲的當前擁塞窗口為4000字節，在主機甲向主機乙連接發送2個最大段后，成功收到主機乙發送的第一段的確認段，確認段中通告的接收窗口大小為2000字節，則此時主機甲還可以向主機乙發送的最大字節數是( A )
A：1000 B：2000
C：3000 D：4000
40、如果本地域名服務無緩存，當采用遞歸方法解析另一網絡某主機域名時，用戶主機本地域名服務器發送的域名請求條數分別為( A )
A：1條，1條 B：1條，多條
C：多條，1條 D：多條，多條
二、綜合應用題：41-47小題，共計70分
41.(10分)將關鍵字序列(7、8、11、18、9、14)散列存儲到散列列表中，散列表的存儲空間是一個下標從0開始的一個一維數組散列函數維：H(key)=(key×3)MODT，處理沖突采用線性探測再散列法，要求裝填(載)因子為0.7
問題：
(1)請畫出所構造的散列表;
(2)分別計算等概率情況下，查找成功和查找不成功的平均查找長度。
解答：
(1)由裝載因子0.7，數據總數7個→存儲空間長度為10→P=10
所以，構造的散列表為：
0123456789
3071411818.9..
H(7)=(7×3)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.2
42.(13分)設將n(n,1)個整數存放到一維數組R中，試設計一個在時間和空間兩方面盡可能有效的算法，將R中保有的序列循環左移P(0﹤P﹤n)個位置，即將R中的數據由(X0 X1 ……Xn-1)變換為(Xp Xp+1 ……Xn-1 X0 X1 ……Xp-1)要求：
(1)給出算法的基本設計思想。
(2)根據設計思想，采用C或C++或JAVA語言表述算法，關鍵之處給出注釋。
(3)說明你所設計算法的時間復雜度和空間復雜度
解答：
(1)前P個數依次進隊，while(1﹤n-p)A{i}-{i+p}：p個數依次出對，進入數組末尾
(2)詳細程序略
(3)時間復雜度O(N);空間復雜度o(p)
43.(11分)某計算機字長為16q位，主存地址空間大小為128KB，按字編址，采用字長指令格式，指令名字段定義如下：
轉移指令采用相對尋址方式，相對偏移是用補碼表示，尋址方式定義如下：
Ms/Md尋址方式助記符含義
000B寄存器直接Rn操作數=(Rn)
001B寄存器間接(Rn)操作數=((Rn))
010B寄存器間接、自增(Rn)+操作數=((Rn))，(Rn)+1→Rn
011B相對D(Rn)轉移目標地址=(PC)+(Rn)
注：
(X)表示有儲蓄地址X或寄存器X的內容，請回答下列問題：
(1)該指令系統最多可有多少條指令?該計算機最多有多少個通用寄存器?存儲器地址寄存器(MDR)至少各需多少位?
(2)轉移指令的目標地址范圍是多少?
(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的關系，注意補碼計算的偏移地址。
44.(12分)某計算機的主存地址空間為256MB，按字節編址，指令Cache分離‘均有8個Cache行，每個Cache行的大小為64MB，數據Cache采用直接映射方式，現有兩個功能相同的程序A和B,其偽代碼如下所示：
假定int 類型數據用32位補碼表示，程序編譯時i,j, sum 均分配在寄存器中，數據a按行優先方式存放，其地址為320(十進制數)，請回答下列問題，要求說明理由或給出計算過程。
(1)、若不考慮用于cache一致性維護和替換算法的控制位，則數據Cache的總容量是多少?
(2)、要組元素a[0][31]和a[1][1]各自所在的主存塊對應的Cache行號分別是多少(Cache行號從0開始)?
(3)、程序A和B的數據訪問命令中各是多少?那個程序的執行時間更短?
簡答：考點：Cache容量計算，直接映射方式的地址計算，以及命中率計算(行優先遍歷與列優先遍歷命中率分別很大)
45、(7分)假設計算機系統采用CSCAN(循環掃描)磁盤調度策略，使用2KB的內存空間記錄16384個磁盤塊的空間狀態
(1)、請說明在上述條件下如何進行磁盤塊空閑狀態管理。
(2)、設某單面磁盤旋轉速度為每分鐘6000轉。每個磁道有100個扇區，相臨磁道間的平均移動時間為1ms.
若在某時刻，磁頭位于100號磁道處，并沿著磁道號大的方向移動(如下圖所示)，磁道號請求隊列為50.90.30.120.對請求隊列中的每個磁道需讀取1個隨機分布的扇區，則讀完這個扇區點共需要多少時間?要求給出計算過程。
46.(8分)設某計算機的邏輯地址空間和物理地址空間均為64KB.按字節編址。若某進程最多需要6頁(Page)數據存儲空間，頁的大小為1KB.操作系統采用固定分配局部置換策略為此進程分配4個頁框(Page Fame).
頁號頁根號裝入時刻訪問位
071301
142301
222001
391601
當該進程執行到時刻260時，要訪問邏輯地址為17CAH的數據，請問答下列問題：
(1)、該邏輯地址對應的頁號是多少?
(2)、若采用先進先出(FIFO)置換算法，該邏輯地址對應的物理地址是多少?要求給出計算過程。
(3)、若采用時鐘(CLOCK)置換算法，該邏輯地址對應的物理地址是多少?要求給出計算過程。(設搜索下一頁的指針沿順時針方向移動，且當前指向2號頁框，示意圖如下。)
解答：17CAH=(0001 0111 1100 1010)2
(1)頁大小為1K，所以頁內偏移地址為10位，于是前6位是頁號，所以第一間的解為：5
(2)FIFO，則被置換的頁面所在頁框為7，所以對應的物理地址為(0001 1111 1100 1010)2-IFCAH
(3)CLOCK,則被置換的頁面所在頁框為2，所以對應的物理地址為(0000 1011 1100 1010)2-OBCAH
47、(9分)某局域網采用CSMA/CD協議實現介質訪問控制，數據傳輸速率為10MBPS,主機甲和主機乙之間的距離為2KM，信號傳播速度是200 000KMS.請回答下列問題，并給出計算過程。
(1)若主機甲和主機乙發送數據時發生沖突，則從開始發送數據時刻起，到兩臺主機均檢測到沖突時刻止，最短需經多長時間?最長需經過多長時間?(假設主機甲和主機乙發送數據過程中，其他主機不發送數據)
(2)若網絡不存在任何沖突與差錯，主機甲總是以標準的最長以大網數據鎖(1518字節)向主機乙發送數據，主機乙每成功收到一個數據鎖后，立即發送下一個數據鎖，此時主機甲的有效數據傳輸速率是多少?(不考慮以大網鎖的前導碼)
解答：
(1)當甲乙同時向對方發送數據時，兩臺主機均檢測到沖突所需時間最短;
1KM/200000KM/S*2=1*10(-5)S
當一方發送的數據馬上要到達另一方時，另一方開始發送數據，兩臺主機均檢測到沖突所需時間最長;
2KM/2000000KM/S*2=2*10(-5)S
(2)發送一鎖所需時間;1518B/10MBPS=1.2144MS
數據傳播時間;2KM/200 000KM/S=1*10(-5)S=0.01MS
有效的數據傳輸速率=10MBPS*1.2144MS/1.2244MS=9.92MBPS
