中國科學院大學2015年招收攻讀碩士學位研究生入學統一考試試題

科目名稱：計算機學科綜合(專業)
考生須知：
1．本試卷滿分為150分，全部考試時間總計180分鐘。
2．所有答案必須寫在答題紙上，寫在試題紙上或草稿紙上一律無效。
一、單項選擇題：第1～40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項最符合試題要求。
1． 下列數據結構中，（ ）是非線性數據結構。
A．棧 B.隊列 C.二叉樹 D.堆
2．在非空雙向循環鏈表中q所指的結點后插入一個由p所指的鏈結點的過程依次為：rlink(p)<-rlink(q); rlink(q)<-p; llink(p)<-q; ( )
A. rlink(q)<-p B. rlink(llink(p))<-p
C. llink(rlink(p))<-p D. rlink(rlink(p))<-p
3. 若一個棧以向量V[1…n]存儲，初始棧頂指針top為n+1，則下面x入棧的正確操作是（ ）。
A．top=top+1; V[top]=x B. V[top]=x; top=top+1
C. top=top-1; V[top]=x D. V[top]=x; top=top-1
4. 若6行5列的數組以行序為主序順序存儲，基地址為1000，每個元素占2個存儲單元，則第3行第4列的元素（假定無第0行第0列）的地址是（ ）。
A. 1040 B. 1042 C. 1026 D. 以上答案都不對
5．A[N,N]是對稱矩陣，將下三角（包括對角線）以行序存儲到一維數組T[N(N+1)/2]中，則對任一上三角元素a[i][j]對應T[k]的下標k是（ ）。
A. i(i-1)/2+j B. j(j-1)/2+i C. i(j-i)/2+1 D. j(i-1)/2+1
6. 一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（ ）。
A．CABDEFG B. ABCDEFG C. DACEFBG D. ADCFEGB
7. 有n(n>0)個分支結點的滿二叉樹的深度是（ ）。
科目名稱：計算機學科綜合(專業) 第 2 頁 共 8 頁
A．n2 -1 B. log2(n+1)+1 C. log2(n+1) D. log2(n-1)
8. 無向圖G=(V, E)， 其中V={a, b, c, d, e, f}, E={(a, b), (a, e), (a, c), (b, e), (c, f), (f, d), (e, d)}, 對該圖進行深度優先遍歷，得到的頂點序列正確的是（ ）。
A．a, b, e, c, d, f B. a, c, f, e, b, d
C. a, e, b, c, f, d D. a, e, d, f, c, b
9. 設哈希表長M=14，哈希函數H(KEY) = KEY mod 7。表中已有4個結點：ADDR(15) = 1, ADDR(38) = 3, ADDR(61) = 5; ADDR(84) = 0, 其余地址為空。如用二次探測再哈希法解決沖突，關鍵字為68的結點的地址是（ ）。
A. 8 B. 3 C. 5 D. 6
10. 對{05，46，13，55，94，17，42}進行基數排序，一趟排序的結果是（ ）：
A． 05，46，13，55，94，17，42 B. 05，13，17，42，46，55，94
C． 42，13，94，05，55，46，17 D. 05，13，46，55，17，42，94
11. 下列序列中，（ ）是執行第一趟快速排序后所得的序列。
A．[68，11，18，69][23，93，73] B. [68，11，69，23][18，93，73]
C．[93，73][68，11，69，23，18] D. [73，11，69，23，18][93，68]
12．生產者和消費者問題用于解決（ ）。
A. 多個并發進程共享一個數據對象的問題
B. 多個進程之間的同步和互斥問題
C. 多個進程共享資源的死鎖與饑餓問題
D. 利用信號量實現多個進程并發的問題
13.下面的敘述中，正確的是（ ）。
A. 在一個進程中創建一個新線程比創建一個新進程所需的工作量多
B. 同一個進程中的線程間通信和不同進程中的線程間通信差不多
C. 同一進程中的線程間切換由于許多上下文相同而簡化
D. 同一進程中的線程間通信需要調用內核
14．磁盤高速緩存設在（ ）中。
科目名稱：計算機學科綜合(專業) 第 3 頁 共 8 頁
A. 內存 B. 磁盤控制器 C. Cache D. 磁盤
15．位示圖可用于（ ）。
A. 實現文件的保護和保密 B. 文件目錄的查找
C. 磁盤空間的管理 D. 主存空間的共享
16．虛擬設備是通過（ ）技術實現的。
A. 并行 B. 通道 C. SPOOLING D. 虛擬存儲
17．（ ）不是操作系統的功能。
A. CPU管理 B. 存儲管理 C. 網絡管理 D. 數據管理
18.下面敘述中，錯誤的是（ ）。
A. 操作系統既能進行多任務處理，又能進行多重處理
B. 多重處理是多任務處理的子集
C. 多任務是指同一時間內在同一系統中同時運行多個進程
D. 一個CPU的計算機上也可以進行多重處理
19. （ ）優先級是在創建進程時確定的，確定之后在整個進程運行期間不再改變。
A. 動態 B. 先來先服務 C. 短作業 D. 靜態
20.在分時操作系統中，進程調度經常采用（ ）算法。
A. 時間片輪轉 B. 最高優先級 C. 先來先服務 D. 隨機
21.死鎖產生的四個必要條件是：互斥、（ ）、環路等待和不剝奪。
A. 釋放和阻塞 B. 請求和阻塞 C. 請求和保持 D. 請求和釋放
22.公用電話交換網(PSTN)采用了（ ）交換方式。
A.分組 B.報文 C.信元 D.電路
23.在連續ARQ協議中，當滑動窗口序號位數為n，則發送窗口最大尺寸為( )。
科目名稱：計算機學科綜合(專業) 第 4 頁 共 8 頁
A.2n-1 B.2n-1 C.2n D.2n
24.以下哪個是快速以太網的介質訪問控制方法（ ）
A.CSMA/CD B.令牌總線 C.令牌環 D.100VG-AnyLan
25.ARP協議的功能是（ ）
A.域名地址到IP地址的解析 B.IP地址到域名地址的解析
C.IP地址到物理地址的解析 D.物理地址到IP地址的解析
26.IPv6地址由（ ）位二進制數值組成。
A.16 B.64 C.32 D.128
27.決定局域網特性有三個主要技術，它們是 ( ) 。
A. 傳輸介質、差錯檢測方法和網絡操作系統
B. 通信方式、同步方式和拓樸結構
C. 傳輸介質、拓撲結構和介質訪問控制方法
D. 數據編碼技術、介質訪問控制方法和數據交換技術
28.無法隔離沖突域的網絡互聯設備是（ ）。 A.路由器 B.交換機 C.集線器 D.網橋
29.不是IP數據報操作特點的描述說法是（ ）
A. 每個分組自身攜帶有足夠的信息，它的傳送是被單獨處理的
B．在整個傳送過程中，不需建立虛電路
C．使所有分組按順序到達目的端系統
D．網絡節點要為每個分組做出路由選擇
30.關于路由器說法正確的是（ ）。
A.路由器處理的信息量比交換機少，因而轉發速度比交換機快
B.對于同一目標，路由器只提供延遲最小的最佳路由
C.通常的路由器可以支持多種網絡層協議，并提供不同協議之間的分組轉換
D.路由器不但能夠根據邏輯地址進行轉發，而且可以根據物理地址進行轉發
31．兩個二進制有符號數相加，00111111 + 11101111的十進制結果是（ ）。
A. 302 B. 47 C. 45 D. 46
32．根據存儲內容來進行存取的存儲器稱為（ ）。
科目名稱：計算機學科綜合(專業) 第 5 頁 共 8 頁
A. 雙端口存儲器 B. 相聯存儲器 C. 交叉存儲器 D. 串行存儲器
33．在一個容量為128KB的SRAM存儲器芯片上，按字長32位編址，其地址范圍可從0000H到（ ）。
A. 3fffH B. 7fffH C. 7ffffH D. 3ffffH
34．連續兩次啟動同一存儲器所需的最小時間間隔稱為（ ）。
A. 存儲周期 B. 存取時間 C. 存儲時間 D. 訪問周期
35．依賴硬件的數據傳送方式是（ ）。
A．程序控制 B．程序中斷 C．DMA D．無
36．在程序執行過程中，（ ）控制計算機的運行總是處于取指令、分析指令和執行指令的循環之中。
A．控制器 B．CPU C．指令存儲器 D．指令譯碼器
37．需要周期刷新的存儲器是（ ）。
A．SRAM B．DRAM C．ROM D．雙穩態存儲器
38．CPU的主頻是10MHz，機器周期含3個時鐘周期，則機器周期是（ ）ns。
A．100 B．300 C．33.3 D．30
39．命中率高且電路實現簡單的Cache與內存映射方式是（ ）映射方式。
A．全相聯 B．直接 C．組相聯 D．哈希
40．只能檢測錯誤而不能糾正錯誤的編碼方法是（ ）。
A．卷積碼 B．循環冗余碼 C．海明碼 D．奇偶校驗
二、綜合應用題：41~48小題，共70分。
41．（8分）設計并編程實現鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。（注：用C/C++，Pascal等編程語言書寫）
科目名稱：計算機學科綜合(專業) 第 6 頁 共 8 頁
42.（12分）假設有下面的有向圖：
1） 請給出從頂點a出發得到深度優先遍歷的頂點序列。（遍歷過程中存在多種選擇時，請以字母表順序訪問）
2） 請給出從頂點a出發得到廣度優先遍歷的頂點序列。（遍歷過程中存在多種選擇時，請以字母表順序訪問）
3） 該圖的強連通子圖有多少種？
43. （7分）假設一個磁盤驅動器有5000個柱面，從0 到4999。驅動器正在為柱面153的一個請求提供服務。按FIFO順序，即將到來的請求隊列是86，1470，913，1774，948，1509，1022，1750，130。從現在磁頭位置開始，按照FCFS調度算法，要滿足隊列中即將到來的請求，磁頭總的移動距離（按柱面數計）是多少？
44.（8分）現要對P1~P5五個進程進行調度，下表給出了這五個進程的到達時間、執行時間和優先級，其中，優先級數值越小表示優先級越高。
進程
到達時間 (ms)
執行時間 (ms)
優先級
P1
0
10
5
P2
1
1
1
P3
2
5
3
P4
3
1
2
P5
4
2
4
科目名稱：計算機學科綜合(專業) 第 7 頁 共 8 頁
請根據該表分別采用先來先服務（FCFS）調度算法、非搶占式短進程優先（nonpreemptive SPF）調度算法、搶占式優先權（preemptive priority）調度算法和時間片為2ms的時間片輪轉（RR）調度算法對這五個進程進行調度，畫出CPU執行進程的時間圖。
45.（7分）要發送的數據為1101011011。采用CRC的生成多項式是P(x)=x4+x+1。試求應添加在數據后面的余數。數據在傳輸過程中最后一個1變成了0，問接收端能否發現？若數據在傳輸過程中最后兩個1都變成了0，問接收端能否發現？
46.（8分）假定網絡中的路由器A的路由表有如下的項目（這三列分別表示“目的網絡”、“距離”和“下一跳路由器”）
N1 4 B
N2 2 C
N3 1 F
N4 5 G
現在A收到從C發來的路由信息（這兩列分別表示“目的網絡”和“距離”）：
N1 2
N2 1
N3 3
試求出路由器A更新后的路由表（詳細說明每一個步驟）。
47.（8分）某磁盤存儲器轉速為100轉/秒，共有2個記錄盤面，每毫米10道，每道記錄信息16384B，最小磁道直徑為150mm，共有512道，求：
1）磁盤存儲器的存儲容量；
2）磁盤數據傳輸率；
3）平均等待時間。
48.（12分）一個直接映射的Cache有128個字塊，主機內存包含16K個字塊，
科目名稱：計算機學科綜合(專業) 第 8 頁 共 8 頁
每個塊有16個字，訪問Cache的時間是10ns，填充一個Cache字塊的時間是200ns，Cache的初始狀態為空。
1）如果按字尋址，請定義主存地址字段格式，給出各字段的位寬；
2）CPU從主存中依次讀取位置16-210的字，循環讀取10次，則訪問Cache的命中率是多少？
3）10次循環中，CPU平均每次循環讀取的時間是多少？