一、1.單項選擇題

單項選擇題
1-40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項是最符合題目要求的。

0.棧S最多只能容納4個元素，現在6個元素按A，B，C，D，E，F的順序進棧，下列哪一個序列是可能的出棧序列(  )?

A.EDCBAF
B.BCEFAD
C.CBEDAF
D.ADFEBC

1.有A，B，C，D，E 5個元素按次序入棧，在各種可能的出棧次序中，以元素C，D最先出棧的序列中，下列正確的一組是(  )。

A.CDBAE CDABE
B.CDEBA CDBEA
C.CDEAB CDABE
D.CEBAE CDAEB

2.已知一棵完全二叉樹的第6層(設根為第1層)有8個葉結點，則完全二叉樹的結點個數最多是(  )。

A.39
B.52
C.111
D.119

3.將森林轉換為對應的二叉樹，若在二叉樹中，結點u是結點v的父結點的父結點，則在原來的森林中，u和v可能具有的關系是(  )。
 Ⅰ．父子關系
 Ⅱ．兄弟關系
 Ⅲ．u的父結點與v的父結點是兄弟關系@A@只有Ⅱ@B@Ⅰ和Ⅱ@C@Ⅰ和Ⅲ@D@Ⅰ、Ⅱ和Ⅲ

A.只有Ⅱ
B.Ⅰ和Ⅱ
C.Ⅰ和Ⅲ
D.Ⅰ、Ⅱ和Ⅲ

4.線索化的二叉樹中，某結點*p沒有孩子的充要條件是(  )。

A.p-＞lchild=NULL
B.p-＞ltag=1&&p-＞rtag=1
C.p-＞ltag=0
D.p-＞lchild=NULL&&p-＞ltag=1

5.設二叉排序樹中關鍵字由1~1 000的整數構成，現要查找關鍵字為363的結點，下列關鍵字序列不可能是在二叉排序樹上查找到的序列是(  )。

A.2，252，401，398，330，344，397，363
B.924，220，911，244，898，258，362，363
C.925，202，911，240，912，245，363
D.2，399，387，219，266，382，381，278，363

6.在下列查找的方法中，平均查找長度與結點個數n無關的查找方法是(  )。

A.順序查找
B.二分法
C.利用二叉搜索樹
D.利用哈希(hash)表

7.

A.14
B.19
C.21
D.26

8.將兩個長度為N的有序表歸并到一個長度為2N的有序表，最少需要比較的次數是(  )，最多需要比較的次數是(  )。

A.N，2N-1
B.N-1，2N
C.N，2N
D.N-1，2N-1

9.用直接插入排序方法對下列4個表進行(由小到大)的排序，比較次數最少的是(  )。

A.94，32，40，90，80，46，21，69
B.21，32，46，40，80，69，90，94
C.32，40，2l，46，69，94，90，80
D.90，69，80，46，21，32，94，40

10.CPU 中決定指令執行順序的是(  )。

A.指令寄存器IR
B.程序計數器PC
C.程序狀態字寄存器PSWR
D.主存地址寄存器MAR

11.一個C語言程序在一臺32位機器上運行。程序中定義了三個變量x、y和z，其中x和z是int型，y為short型。當x=127，y=-9時，執行賦值語句z=x+y后，x、y和z的值分別是(  )。

A.x=0000007FH，y=FFF9H，z=00000076H
B.x=0000007FH，y=FFF9H，z=FFFF0076H
C.x=0000007FH，y=FFF7H，z=FFFF0076H
D.x=0000007FH，y=FFF7H，z=00000076H

12.原碼兩位乘中，符號位單獨處理，參加操作的數是(  )。

A.原碼
B.補碼
C.絕對值的原碼
D.絕對值的補碼

13.在Cache和主存構成的兩級存儲系統中，Cache的存取時間為100 ns，主存的存取時間為1μs，Cache訪問失敗后CPU才開始訪存。如果希望Cache-主存系統的平均存取時間不超過Cache存取時間的15％，則Cache的命中率至少應為(  )。

A.95％
B.98％
C.98．5％
D.99．5％

14.雙端口存儲器之所以能高速讀寫是因為(  )。

A.采用了兩套獨立的存儲體
B.采用了兩套相互獨立的讀寫電路
C.采用了新型的器件
D.兩套讀寫電路分時使用存儲體

15.某機主存容量64 KB，按字節編址。主存地址0100H處有一條相對轉移指令，指令字長16位，其中，第一個字節為操作碼，第二個字節為相對位移量(用補碼表示)，則該指令執行結束后，后繼指令的地址范圍可能是(  )。

A.0000H~FFFFH
B.0080H～017FH
C.0082H～0181H
D.0080H～01FFH

16.下列哪個選項不是RISC的特點(  )。

A.只有取數和存數指令訪問存儲器，其余指令都在寄存器之間進行
B.由使用頻率高的簡單指令和很有用且不復雜的指令組成
C.使用RISC技術后，指令系統又回到了計算機發展早期的比較簡單的情況
D.使用優化的編譯程序

17.下列微指令的編碼方式中，執行速度最快的是(  )。

A.直接編碼
B.字段直接編碼
C.字段間接編碼
D.無法判斷

18.相對于微程序控制器，硬布線控制器的特點是(  )。

A.指令執行速度慢，指令功能的修改和擴展容易
B.指令執行速度慢，指令功能的修改和擴展難
C.指令執行速度快，指令功能的修改和擴展容易
D.指令執行速度快，指令功能的修改和擴展難

19.某機采用計數器定時查詢方式來進行總線判優控制，共有4個主設備競爭總線使用權，當計數器初值恒為10₂時，4個主設備的優先級順序為(  )。

A.設備0＞設備1＞設備2＞設備3
B.設備2＞設備1＞設備0＞設備3
C.設備2＞設備3＞設備0＞設備1
D.設備2=設備3=設備0=設備1

20.下列通道中，以字節為單位進行數據傳送的是(  )。

A.字節多路通道
B.選擇通道
C.數組多路通道
D.以上都是

21.下列選項中，能引起外部中斷的事件是(  )。

A.鍵盤輸入
B.除數為0
C.浮點運算下溢
D.訪存缺頁

22.單處理機系統中，可并行的是(  )。
Ⅰ進程與進程 Ⅱ處理機與設備 Ⅲ處理機與通道 Ⅳ設備與設備

A.Ⅰ、Ⅱ和Ⅲ
B.Ⅰ、Ⅱ和Ⅳ
C.Ⅰ、Ⅲ和Ⅳ
D.Ⅱ、Ⅲ和Ⅳ

23.下列進程調度算法中，綜合考慮進程等待時間和執行時間的是(  )。

A.時間片輪轉調度算法
B.短進程優先調度算法
C.先來先服務調度算法
D.高響應比優先調度算法

24.某計算機系統中有8臺打印機，有K個進程競爭使用，每個進程最多需要3臺打印機。該系統可能會發生死鎖的K的最小值是(  )。

A.2
B.3
C.4
D.5

25.在虛擬存儲系統中，若進程在內存中占3位(開始時為空)，采用先進先出頁面淘汰算法，當執行訪問頁號序列為1，2，3，4，1，2，5，1，2，3，4，5，6時，將產生(  )次缺頁中斷。

A.7
B.8
C.9
D.10

26.拿內存加上外存容量之和與虛擬存儲空間相比，其大小關系是(  )。

A.前者比后者大
B.前者比后者小
C.二者相等
D.不一定

27.位示圖可用于磁盤空間的管理。設某系統磁盤共有500塊，塊號從0到499；第0字的第0位表示第0塊，第0字的第1位表示第1塊，依次類推。若用位示圖法管理這500塊的盤空間，當字長為32位時，第i個第j位對應的塊號是(  )。

A.32i+j
B.32i+j-1
C.32i+j-32
D.32i+j-32-1

28.考慮一文件存放在100個數據塊中，文件控制塊、索引塊或索引信息都駐留內存。那么，如果( )，不需要做任何磁盤I／O操作。

A.采用contiguous allocation策略，將最后一個數據塊搬到文件頭部
B.采用single level indexed allocation策略，將最后一個數據塊插入文件頭部
C.采用linked allocation策略，將最后一個數據塊插入文件頭部
D.采用linked allocation策略，將第一個數據塊插入文件尾部

29.文件系統中，設立打開文件系統功能調用的基本操作是(  )。

A.把文件信息從輔存讀到內存
B.把文件的控制管理信息從輔存讀到內存
C.把文件的FAT表信息從輔存讀到內存
D.把磁盤的超級塊從輔存讀到內存

30.文件系統采用樹形目錄結構后，對于不同用戶的文件，其文件名(  )。

A.應該不同
B.由操作系統類型決定
C.可以相同也可以不同
D.受系統約束

31.對于硬盤上存放的信息，物理上讀寫的最小單位是一個(  )。

A.二進制
B.字節
C.物理塊
D.邏輯記錄

32.IEEE的802委員會已經標準化了很多種類的LAN，其中無線LAN標準是(  )。

A.IEEE802．3
B.IEEE802．5
C.IEEE802．11
D.IEEE802．17

33.有一條無噪聲的8 KHz信道，每個信號包含8級，每秒采樣24 K次，那么可以獲得的最大傳輸速率是( )。

A.24 Kbps
B.32 Kbps
C.48 Kbps
D.72 Kbps

34.

A.115 200 bps
B.57 600 bps
C.28 800 bps
D.230 400 bps

35.在Internet的幾種路由協議中，(  )采用了鏈路狀態路由算法。

A.RIP
B.BGP
C.OSPF
D.NAT

36.一個3 200 bit上的TCP報文傳到IP層，數據鏈路層可以發送的最長數據幀中的數據部分只有1 200 bit。IP層需要向數據鏈路層發送(  )。

A.3 200 bit
B.3 400 bit
C.5 400 bit
D.3 680 bit

37.某公司獲得了一個IP地址段，在不分子網的情況下，最多可以容納65 534個主機，那么這個地址屬于( )。

A.A類地址
B.B類地址
C.C類地址
D.D類地址

38.在TCP／IP模型中，主機采用(  )標識，運行在主機上的應用程序采用(  )標識。

A.端口號，主機地址
B.主機地址，IP地址
C.IP地址，主機地址
D.IP地址，端口號

39.下面(  )協議中，客戶端和服務器之間采用面向無連接的協議進行通信。

A.FTP
B.SMTP
C.TELNET
D.DHCP

二、2.綜合應用題

綜合應用題
41-47小題，共70分。

0. 設有一個由正整數組成的無序(后向)單鏈表，編寫能夠完成下列功能的算法：
 (1)找出最小值結點，且打印該數值。
 (2)若該數值為奇數，則將其與直接后繼結點的數值交換。
 (3)若該數值為偶數，則將其直接后繼結點刪除。

1. 給定序列{3，5，7，9，11，13，15，17)，
  (1)按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成后的二叉排序樹，并求在等概率情況下查找成功的平均查找長度。
  (2)按表中元素的順序構造一棵平衡二叉樹，并求其在等概率情況下查找成功的平均查找長度。

2. 已知4位有效信息為1010，試根據下列要求進行編碼。
  (1)按配偶原則將其編碼為擴展的海明碼，要求能發現兩位錯并糾正一位錯。
  (2)將其編碼為循環冗余校驗碼，生成多項式G(x)=1011。

3. 某機字長32位，采用定長操作碼，單字長指令，共有機器指令100條，CPU內部有通用寄存器32個，可作變址寄存器用，存儲器按字節編址，指令擬用直接尋址、間接尋址、變址尋址和相對尋址等4種尋址方式。
  (1)分別畫出尋址方式由操作碼指出和尋址方式由專用字段指出時的指令格式。
  (2)當指令尋址方式由操作碼指出時，直接和間接尋址可尋址的主存空間大小為多少?
  (3)寫出4種尋址方式下，有效地址EA的表達式。

4. 分頁存儲管理中，頁表的功能是什么?當系統中的地址空間變得非常大時(如32位地址空間)，會給頁表的設計帶來什么樣的新問題?請給出一種解決方法，分析它的優點和缺點。

5. 有一個倉庫，可以存放A和B兩種產品，但要求：
  (1)每次只能存入一種產品(A或B)；
  (2)-N＜A產品的數量-B產品的數量＜M。其中，N和M是正整數。試用P，V操作描述產品A與產品B的入庫過程。

6. 某公司的局域網設置如下所示，兩個局域網通過路由器連接到NAT、服務器上，并且通過NAT服務器連接到Internet上。局域網1的掩碼是192．168．14．0／25，局域網2的掩碼是192．168．14．128／25，NAT服務器的內部IP地址為192．168．13．25，外部IP地址為202．157．85．69，在NAT服務器中有如下的表項：

請問：
(1)地址是192．168．14．175的主機和地址為192．168．14．48的主機分別屬于哪個局域網?
(2)按照題目的配置，路由器的路由表項應該含有哪幾項?
(3)現在有一個目的地址為201．25．68．99，源地址為192．168．14．175，TCP端口為652的IP分組到達NAT、服務器，問NAT服務器是否轉發該分組?如果轉發，分組的IP號和端口號分別是多少?
(4)當NAT服務器收到一個目的地址是202．157．85．69，端口號是4325的TCP數據后，它將轉發給哪個主機?