一、1.單項選擇題

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

0.若線性表最常用的運算是查找第i個元素及其前驅的值，則下列存儲方式最節省時間的是 (     )。

A.單鏈表
B.雙鏈表
C.單循環鏈表
D.順序表

1.在非空雙循環鏈表中q所指的結點前插入一個由p所指結點的過程依次為：p->next=q；p->prior—=q->prior；q->prior=p；下一條語句是(     )。

A.q->next=p；
B.q一>prior->next=p；
C.p->prior->next=p；
D.p->next->priox=p；

2.在一個長度為n的順序存儲線性表中，刪除第i個元素(1≤i≤n+1)時，需要從前向后依次前移的元素個數是(     )。

A.n-i
B.n-i+1
C.n-i-1
D.i

3.將兩個長度為n的遞增有序表歸并成一個長度為2n的遞增有序表，最少需要進行關鍵字比較次數是(     )。

A.1
B.n-1
C.n
D.2n

4.已知一算術表達式的中綴形式為A+B*C-D／E，后綴形式為ABC*+DE／一，其前綴形式為(     )。

A.一A+B*C／DE
B.一A+B*CD／E
C.一+*ABC／DE
D.一+A*BC／DE

5.一個循環隊列Q最多可存儲m個元素，已知其頭尾指針分別是：front和rear，則判定該循環隊列為滿的條件是(     )。

A.Q．rear—Q．front==m
B.Q．rear!=Q．front
C.Q．front=(Q．rear+1)％m
D.Q．front==Q．rear％m+1

6.某二叉樹的先序和后序序列正好相反，則該二叉樹一定是(     )。

A.空或只有一個結點
B.高度等于其結點數
C.任一結點無左孩子
D.任一結點無右孩子

7.對二叉樹的結點從1開始進行連續編號，要求每個結點的編號大于其左、右孩子的編號，同一結點的左右孩子中，其左孩子的編號小于其右孩子的編號，為實現編號可采用的遍歷是 (     )。

A.先序
B.中序
C.后序
D.從根開始按層次遍歷

8.一棵哈夫曼樹共有9個結點，則其葉子結點的個數為(     )。

A.4
B.5
C.6
D.7

9.下列有關散列查找的敘述正確的是(     )。

A.散列存儲法只能存儲數據元素的值，不能存儲數據元素之間的關系
B.散列沖突是指同一個關鍵字對應多個不同的散列地址
C.用線性探測法解決沖突的散列表中，散列函數值相同的關鍵字總是存放在一片連續的存儲單元中
D.若散列表的裝填因子α《1，則可避免沖突的產生

10.以下排序方法中，不需要進行關鍵字的比較的是(     )。

A.快速排序
B.歸并排序
C.基數排序
D.堆排序

11.“容量為640KB的存儲器”是指(     )。

A.640×10³字節的存儲器
B.640×10³位的存儲器
C.640×2¹⁰位的存儲器
D.640×2¹⁰字節的存儲器

12.在微程序控制的計算機中，若要修改指令系統，只要(     )。

A.改變時序控制方式
B.改變微指令格式
C.增加微命令個數
D.改變控制存儲器的內容

13.生成多項式為x³+x+1，則數據信息10101的CRC編碼是(     )。

A.10010111
B.10000111
C.10101101
D.11101001

14.判斷加減法溢出時，可采用判斷進位的方式，如果符號位的進位為C0，最高數值位為C1，產生溢出的條件是(     )。
 I．C0生進位；  Ⅱ．C1產生進位；
 Ⅲ．C0、C1都產生進位；  Ⅳ．C0、C1都不產生進位；
 V．C0產生進位，C1不產生進位；  Ⅵ．C0不產生進位，C1產生進位

A.I和Ⅱ
B.Ⅲ
C.Ⅳ
D.V和Ⅵ

15.內存按字節編址，地址從90000H到CFFFFH，若用存儲容量為1 6K×8bit芯片構成該內存，至少需要的芯片數是(     )。

A.2
B.4
C.8
D.1 6

16.某計算機指令字長為16位，指令有雙操作數、單操作數和無操作數3種格式，每個操作數字段均有6位二進制表示，該指令系統共有m條(m<16)雙操作數指令，并存在無操作數指令。若采用擴展操作碼技術，那么最多還可設計出單操作數指令的條數是(     )。

A.2²
B.(2⁴-m)×2⁶-1
C.(2⁴一m)×2⁶
D.(2⁴一m)×(2⁶-1)

17.指令流水線將一條指令的執行過程分為四步，其中第1、2和4步的經過時間為△t如下圖所示。若該流水線順序執行，50條指令共用1 53△t，并且不考慮相關問題，則該流水線的瓶頸第3步的時間是(     )。
  

A.2△t
B.3△t
C.4△t
D.5△t，

18.以下關于CPU的敘述中，錯誤的是(     )。

A.CPU產生每條指令的操作信號并將操作信號送往相應的部件進行控制
B.程序計數器PC除了存放指令地址，也可以臨時存儲算術／邏輯運算結果
C.CPU中的控制器決定計算機運行過程的自動化
D.指令譯碼器是CPU控制器中的部件

19.在系統總線中，地址總線的位數(     )。

A.與機器字長有關
B.與存儲單元個數有關
C.與存儲字長有關
D.與存儲器帶寬有關

20.假設某硬盤由5個盤片構成(共有8個記錄面)，盤面有效記錄區域的外直徑為30厘米，內直徑為10厘米，記錄位密度為250位／毫米，磁道密度為。16道／毫米，每磁道分16個扇區，每扇區512字節，則該硬盤的格式化容量約是(     )。
  

A.A
B.B
C.C
D.D

21.下列情況下，可能不發生中斷請求的是(     )。

A.DMA操作結束
B.一條指令執行完畢
C.機器出現故障
D.執行“軟中斷”指令

22.用戶在編寫程序時計劃讀取某個數據文件中的50個數據塊記錄，他使用操作系統提供的接口是(     )。

A.系統調用
B.圖形用戶接口
C.原語
D.命令行輸入控制

23.計算機系統中2個協作進程之間不能用來進行進程間通信的是(     )。

A.數據庫
B.共享內存
C.消息傳遞機制
D.管道

24.時間片輪轉調度算法是為了(     )。

A.多個終端能得到系統的及時響應
B.使系統變得高效
C.優先級較高的進程得到及時響應
D.需要CPU Et寸間最少的進程最先做

25.一次分配所有資源的方法可以預防死鎖的發生，它破壞的死鎖四個必要條件中的(     )。

A.互斥條件
B.占有并請求
C.非剝奪條件
D.循環等待

26.有二個處理機P1和P2，它們各自有一個cache和主存，分別為C1、C2和M1、M2，其性能見下表：
  
  若兩個處理機的指令系統相同，指令的執行時間與存儲器的平均存取周期成正比，當執行某程序時，cache的命中率為70％，則P1處理機的速度比P2處理機(     )。

A.更快
B.更慢
C.相等
D.不能確定

27.在頁式存儲管理中，每個頁表的表項實際上是用于實現(     )。

A.訪問內存單元
B.靜態重定位
C.動態重定位
D.裝載程序

28.物理文件的組織方式的確定是(     )。

A.應用程序
B.索引文件
C.外存容量
D.操作系統

29.假如一個FCB塊的大小是64字節。盤塊的大小為1KB，則在每個盤塊中能存放的最大FCB數是(     )。

A.64
B.1
C.1000
D.16

30.一個文件的絕對路徑名的出發點是(     )。

A.當前目錄
B.根目錄
C.磁盤盤符
D.公共目錄

31.如果一個沒有內存映射的IO設備與主存之間交換數據，希望這種數據交換不經過CPU來完成，那么，可以采用的最佳方法是(     )。

A.程序查詢方式
B.中斷技術
C.通道技術
D.DMA方式

32.下面對計算機網絡體系結構中協議所做的描述，錯誤的是(     )。

A.網絡協議的三要素是語法、語義和同步
B.協議是控制兩個對等層實體之間通信的規則的集合
C.在OSI參考模型中，要實現第N層的協議，需要使用N+I層提供的服務
D.協議規定了對等層實體之間所交換的信息的格式和含義

33.對于帶寬為6MHz的信道，若用8種不同的狀態來表示數據，在不考慮熱噪聲的情況下，該信道每秒最多能傳送的位數是(     )。

A.36×10⁶
B.18×10⁶
C.48×10⁶
D.96×10⁶

34.在MAC子層中，數據傳輸的基本單元是(     )。

A.比特流
B.MAC幀
C.LLC PDU
D.數據報

35.考慮在一條：1000米長的電纜(無中繼器)上建立一個1Gbps速率的CSMA／CD網絡，假定信號在電纜中的速度為2 X 10⁸米／秒。最小幀長是(     )。

A.1250
B.1230
C.1280
D.1220

36.將一條物理信道按時間分成若干時間片輪換地給多個信號使用，每一時間片由復用的一個信號占用，這樣可以在一條物理信道上傳輸多個數字信號，這就是(     )。

A.頻分多路復用
B.時分多路復用
C.空分多路復用
D.頻分與時分混合多路復用

37.TCP使用的流量控制協議是(     )。

A.固定大小的滑動窗口協議
B.可變大小的滑動窗口協議
C.后退N幀ARQ協議
D.選擇重發ARQ協議

38.以下關于路由器的路由表說法正確的是(     )。
  I．路由表包含目的網絡和到達該目的網絡的完整路徑
  Ⅱ．路由表必須包含子網掩碼
  Ⅲ．目的網絡和到達該目的網絡路徑上的下一個路由器的IP地址
  Ⅳ．目的網絡和到達該目的網絡路徑上的下一個路由器的MAC地址

A.Ⅱ、Ⅲ
B.只有Ⅲ
C.I、Ⅲ
D.Ⅱ、Ⅲ、Ⅳ

39.FTP客戶和服務器之間一般需要建立的連接個數是(     )。

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

二、2.綜合應用題

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

0. 任意給定1，2……．，n指定為一棵樹的先根遍歷序列；同時任意給定這n個數值 (1，2……．，n)的一個排列p₁，p₂……．p_n為這棵樹的后根遍歷序列。
  (1)根據這樣的先根遍歷序列和后根遍歷序列，是否都可以得到一棵樹?如果能夠，請簡述理由(不要求形式化證明)。如果不能，請給出一個簡單反例。
  (2)如果能得到樹，所得到的樹是否唯一?如果能夠，請簡述理由(不要求形式化證明)。如果不能，請給出一個簡單反例。

1. 設有一個雙向鏈表h，每個結點中除有prior、data和next共3個域外，還有一個訪問頻度域freq，在鏈表被起用之前，每個結點中的freq域的值均被初始化為零。每當進行LocateNode(h，x)運算時，令元素值為x的結點中freq域的值加1，并調整表中結點的次序，使其按訪問頻度的遞減序列排序，以便使頻繁訪問的結點總是靠近表頭。試寫一符合上述要求的LocateNode運算的算法。

2. 地址總線A₁₅～A₀，其中A₀是最低位。存儲器地址空間為3000H～67FFH。其中3000H～4FFFH為ROM區，選用EPROM芯片(4K×2)；5000 H～67．FFH為RAM區，選用RAM芯片(2K×4)。
  (1)組成該存儲器需用多少塊EPROM芯片和RAM芯片?
  (2)EPROM芯片、RAM芯片各需連入哪幾根地址線?
  (3)需設置多少個片選信號，分別寫出各片選信號的邏輯式。

3. CPU內部一般包括PC、MAR、MDR、IR等幾個寄存器及若干通用寄存器。下圖是指令LAD RO，(X)的指令流程圖，其功能是將主存X號單元的數據取到R0寄存器中，圖中M表示主存。
  (1)請完成該指令流程圖中未完成的部分。
  (2)重新畫出當源操作數為間接尋址時的指令流程圖。
  

4. 設有一系統在某時刻的資源分配情況如下：
  
  請回答：
  (1)系統中各進程尚需資源數各是多少?
  (2)當前系統安全嗎?為什么?  ’
  (3)如果此時進程P1提出資源請求(0，4，2，0)，系統能分配給它嗎?若不能則寫出原因，若能則寫出安全序列。

5. 在實現文件系統時，一般為加快文件目錄的檢索速度，可利用“文件控制塊部分裝入”的方法。假設目錄文件(即文件控制塊)存放在磁盤上，磁盤的每個盤塊為512B，每個目錄項占128B，其中文件名占11B。為提高檢索速度，通常將目錄項分解成兩部分，第一部分(包括文件名和文件內部號)占16B，第二部分(包括文件內部號和文件其他描述信息)占122B。假設某一目錄共有254個目錄項(文件控制塊)，試分別給出前、后二種方法查找該目錄文件某一目錄項的平均訪問磁盤次數。

6. 網絡如圖所示。鏈路旁邊注明的數字代表鏈路的長度(假想單位)。試利用Dijk-stra算法求出從結點A到所有其他結點的最短路由。