|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
第 1 頁 共 4 頁
成都電子科技大學
2016 年攻讀碩士學位研究生入學考試試題
考試科目：820 計算機專業基礎
注：所有答案必須寫在答題紙上，寫在試卷或草稿紙上均無效。
《計算機操作系統》
一、填空題（10 分，每空 2 分）
1. 若信號量S的初值為4，當前有6個進程在等待信號量S，則當前信號量S的值為 。
2. 某系統中共有 11 臺打印機，X 個進程共享此打印機，每個進程最多請求使用 3 臺打印
機，則該系統中不會發生死鎖的最大 X 值是 。
3. 虛擬存儲管理系統的基礎是程序的 理論。
4. 為滿足 264
地址空間的作業運行，采用多級分頁存儲管理方式，假設頁面大小為 4KB，
在頁表中的每個頁表項需要占 8 字節。那么，為了滿足系統的分頁存儲管理，至少應采
用 級頁表。
5. 某文件系統的文件控制塊占 64B，單個盤塊大小為 1KB，采用一級目錄結構。假設文件
目錄中有 3200 個目錄項，則查找一個文件平均需要訪問 次磁盤。
二、選擇題（14 分，每題 2 分）
1. 若下列指令已裝入指令寄存器，執行時不可能導致 CPU 從用戶態變為內核態的是（ ）。
A．DIV R0，R1； (R0)/(R1)→R0
B．INT n； 產生軟中斷
C．NOT R0； 寄存器 R0 的內容取非
D．MOV R0,addr； 把地址處的內存數據放入寄存器 R0 中
2. 在下列進程調度算法中，不存在進程饑餓現象的調度算法是（ ）。
A．先來先服務 B．反饋調度算法
C．短進程優先 D．基于靜態優先級調度算法
3. 資源的有序分配策略是為了破壞死鎖產生的（ ）條件。
A．互斥 B．請求和保持
C．非剝奪 D．循環等待
4. 在段式存儲管理系統中，若不考慮快表，為獲得一條指令或數據，至少需要訪問（ ）
次內存。
A．1 B．2
C．3 D．4
5. 在設備管理中，不屬于 I/O 控制方式的是（ ）。
A．程序查詢方式 B．中斷驅動方式
C．DMA 方式 D．重定位方式
第 2 頁 共 4 頁
6. 下列文件物理結構中，適合隨機訪問且易于文件擴展的是（ ）。
A．哈希文件 B．索引文件
C．鏈式結構文件 D．連續結構文件
7. 設置當前工作目錄的主要作用是（ ）。
A．加快文件的讀/寫速度 B．加快文件的檢索速度
C．節省外存空間 D．節省內存空間
三、簡答題（4 題，共 21 分）
1. PCB 的主要存儲內容是什么？為什么說 PCB 是進程存在的唯一標志？（6 分）
2. 什么是虛擬存儲器？如何實現頁式虛擬存儲器？（5 分）
3. 什么是設備的獨立性，應如何實現？（5 分）
4. 文件物理結構是指一個文件在外存上的存儲組織形式，那么何謂文件的混合索引結構？
其主要優點是什么？（5 分）
四、分析計算題（2 題，共 30 分）
1. 某計算機采用段頁式虛擬存儲器，已知虛擬地址為 32 位，按字節編址，每個段最多可
以有 2K 頁，頁大小為 16KB，物理主存容量為 512MB。請回答以下問題：（10 分）
（1） 虛擬存儲器的容量是多少？
（2） 給出邏輯地址結構并說明理由。
（3） 計算邏輯地址 0X4EB9FDE3 的段號，段內頁號及頁內偏移值（最后計算結果須
用十六進制表示）。
2. N 個生產者進程和 M 個消費者進程共享大小為 K 的緩沖區，遵循規則如下：
（1） 進程之間必須以互斥方式訪問緩沖區；
（2） 對每 1 條放入緩沖區的數據，所有消費者都必須接收 1 次；
（3） 緩沖區滿時，生產者必須阻塞；
（4） 緩沖區空時，消費者必須阻塞。
請用 P、V 操作實現其同步過程，須說明信號量含義。（20 分）
第 3 頁 共 4 頁
《數據結構》
一、填空題(共 10 空，每空 1 分，共 10 分)
1. 順序表采用的是_________存取方式，線性鏈表采用的是_________存取方式。
2. 深度為 ,( 1)d d ? 的完全二叉樹至少含有_________個節點，至多含有_________個節點。
3. 3 個節點構成的二叉樹有____種不同形狀。3 個元素依次入?？赡艿某鰲Ｐ蛄杏衉___種。
4. 無向連通圖 G 含有 n 個節點e條邊。求 G 的最小生成樹，采用 Prim 算法的時間復雜度
是________，采用 Kruskal 算法的時間復雜度是________。
5. 快速排序算法平均情況下的時間復雜度是_________，空間復雜度是_________。
二、單選題(共 10 題，每題 2 分，共 20 分)
1. 循環隊列為了防止假上溢采用取模運算折疊空間，解決隊頭隊尾指針同指一個單元時候
空滿判定問題，下列( )選項不是常見的方案。
A. 犧牲一個存儲空間 B. 設置一個計數器 C. 設置一個布爾變量 D. 再配置一個指針
2. 下列選項中不屬于規則矩陣的是( )。
A. 三角矩陣 B. 對稱矩陣 C. 對角矩陣 D. 稀疏矩陣
3. 下列選項中符合前綴碼要求的是( )。
A. {0, 1} B. {0, 01, 001, 0001} C. {10, 010, 110, 101} D. {01, 10, 1001, 0110}
4. 下列關于哈夫曼樹的論述不正確的是( )。
A. 哈夫曼樹又被稱為最優二叉樹
B. 哈夫曼樹是帶權路徑最短的二叉樹
C. 一棵哈夫曼樹任意交換左右子樹仍然是一棵哈弗曼樹
D. 對給定的輸入數值集合所生成的哈夫曼樹深度是確定的
5. 無向圖做深度優先搜索和廣度優先搜索共有的特點是( )
A. 都是遞歸類算法 B. 都必須用到棧 C. 都是遍歷類算法 D. 搜索結果都是唯一的
6. 對于 AOE 網絡，若它的關鍵路徑存在，那么該路徑一定是( )。
A. 最長路徑 B. 最短路徑 C. 拓撲排序序列 D. 唯一的一條路徑
7. 拓撲排序解決的問題是( )。
A. 對一個有向圖進行遍歷操作 B. 計算一個有向圖的回路個數
C. 判斷一個有向圖是否有回路 D. 對一個有向圖進行線索化
8. 已知廣義表 GL=((a, b), (c, d, e), (f, g))，定義取表頭函數為 H( )，取表尾函數為 T( )，那么
從 GL 中取出數據元素 d 的操作是( )。
A. H(T(T(H(GL)))) B. H(T(H(GL)))) C. H(T(H(T(GL)))) D. H(T(H(H(GL))))
9. 對序列(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)進行折半查找元素 14，需要依次比較( )。
A. 10, 18, 14 B. 10, 16, 14 C. 10, 18, 12, 14 D. 10, 16, 12, 14
第 4 頁 共 4 頁
10. 下列哪種排序算法在一趟過后不能保證至少有一個元素落在最終位置上的是( )。
A. 冒泡排序 B. 希爾排序 C. 快速排序 D. 簡單選擇排序
三、簡答題(共 6 題，每題 5 分，共 30 分)
1. 設計一種盡可能高效的策略使得單循環鏈表成為隊列，給出入隊和出隊的時間復雜度。
2. 輸入數據序列為(5, 1, 9, 3, 7)，請按輸入序構造排序二叉樹，并繪制出它的中序線索。
3. 輸入數據序列為(10, 30, 40, 20, 15, 25)，請按輸入序構造平衡二叉樹。給出每添加一個節
點后平衡二叉樹的調整結果。
4. 已知輸入關鍵字序列為(13, 14, 15, 16, 17, 5, 4, 3, 2, 1)，根據哈希函數建立哈希表，采用公
共溢出區法解決沖突。已知哈希函數為 Hash(key) = key MOD 11，哈希表長為 11，溢出表長
為 5。請畫出哈希表和溢出表，并計算查找成功時(等概率情況下)的平均查找長度 ASL。
5. 已知 7 項數據記錄為(7, 6, 5, 4, 3, 2, 1)。將它調整成為小頂堆，給出篩選過程。
6. 全源最短路徑問題采用 Floyd 算法進行求解。下面給出了一個由 4 個頂點構成的有向圖
鄰接矩陣 Dist[4][4]和路徑矩陣 Path[4][4]。約定 Dist 中用∞表示不能到達，Path 中
用-1 表示沒有前驅的情況。請計算并給出每一次迭代的結果。(請將答案謄寫在答題紙上)
Dist(-1)
Dist(0)
Dist(1)
Dist(2)
Dist(3)
0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
0 0 1 4 ∞
1 ∞ 0 2 5
2 ∞ ∞ 0 1
3 2 ∞ ∞ 0
Path(-1)
Path(0)
Path(1)
Path(2)
Path(3)
0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
0 -1 0 0 -1
1 -1 -1 1 1
2 -1 -1 -1 2
3 3 -1 -1 -1
四、算法題(共 2 題，共 15 分)
1. 設規模 3 , 1n m m? ? 的順序表存儲在一維數組 int array[n]中，它含有的元素為
1 2 1 2 1 2( , , , , , , , , , , , )m m ma a a b b b c c c 。 請 編 寫 算 法 將 上 述 順 序 表 改 造 成 為
1 2 2 1 1 2( , , , , , , , , , , , )m m mc c c b b b a a a ，要求時間復雜度和空間復雜度盡可能低。程序
設計語言可以選用 C、C++、Java。(8 分)
2. 二叉樹用二叉鏈表結構進行存儲。請編寫算法求二叉樹根節點左右子樹相隔最遠的葉子
節點之間距離。程序設計語言可以選用 C、C++、Java。(7 分)
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
