專業(yè)名稱：計算機應用技術、計算機軟件以理論 考試科目：數(shù)據(jù)結構與操作系統(tǒng) （B）卷

一． 數(shù)據(jù)結構部分
注意：算法可以用類C、類C++、類JAVA或類PASCAL任一語言編寫，并有類型說明。

1、（15分）名詞解釋
（1）堆棧
（2）最小生成數(shù)
（3）折半（二分）查找
（4）堆排序
（5）連通分量

2、(15分)雙端隊列是限定插入和刪除操作在表的兩端進行的線性表。假設
依次輸入數(shù)據(jù)元素為1、2、3、4、5和6，試問通過使用（a）隊列；（b）雙
端隊列，能否得到下列輸出序列？
（1）1 2 3 4 5 6 （2）2 4 3 6 5 1 （3）1 5 2 4 3 6
（4）4 2 1 3 5 6 （5）1 2 6 4 5 3 （6）5 2 6 3 4 1

3、（15分）試設計一個算法，將二叉樹中的葉子結點按從左到右的順序放入
一個線性表。假設二叉樹采用二叉鏈表存儲結構，線性表采用動態(tài)分配順序
存儲結構。

4、（15分）子串的定位操作index(s,t)通常稱為串的模式匹配（其中t稱為
模式），試編寫一個模式匹配算法，匹配過程為：先匹配模式的首尾字符，若
匹配成功，調用函數(shù)substr（取子串）求檢查模式的首尾之間的字符是否與
目標的相應字符相匹配，若匹配不成功，則進行下一次匹配。

5、（15分）請采用遞歸方式對一單鏈表進行歸并排序。假設單鏈表中每個
元素皆為整數(shù)，試設計算法完成次操作。










二、操作系統(tǒng)部分
6、（15分）請判斷以下說法是否正確，并說明理由。
（1）在單CPU的計算機系統(tǒng)中，進程是不能并行操作的。
（2）在死鎖發(fā)生后，參與死鎖的所有進程都占有資源。
（3）存儲管理中的請求式分頁系統(tǒng)必定需要重定位機制的支持。

7、（15分）請解釋以下的概念：
（1）中斷
（2）虛擬設備
（3）中級調度
（4）Cache
（5）LRU算法

8、（15分）在虛擬存儲技術中，系統(tǒng)將進行進程運行時所缺的頁面調入內存的
時機有預調頁策略和請求式調頁策略兩種。請說明這兩種策略的原理，并結合
具體的實例比較這兩種策略的優(yōu)劣。

9、（15分）有一個數(shù)據(jù)采集和處理系統(tǒng)，出3個負責采集數(shù)據(jù)的設備，一個
緩沖區(qū)和2個數(shù)據(jù)處理程序組成。其工作原理如下：
（1） 每個采集數(shù)據(jù)的設備分別由一個進程控制，標記為D1、，D2和D3，
并且每次采集到的數(shù)據(jù)大小固定為K。
（2） 緩沖區(qū)的大小為2*K（可以存放采集到的2份數(shù)據(jù)）。
（3） 兩個數(shù)據(jù)處理程序運行后，演變?yōu)檫M程P1和P2。
（4） 僅當緩沖區(qū)中有D1和D2采集到的各一份數(shù)據(jù)時，P1取出這兩份數(shù)
據(jù)并處理。
（5） 僅當緩沖區(qū)中有D1和D3采集到的各一份數(shù)據(jù)時，P2取出這兩份數(shù)
據(jù)并處理。
請用信號量機制實現(xiàn)以上5個進程的同步，并保證系統(tǒng)不會發(fā)生死鎖。

10、（15分）有一批數(shù)據(jù)，共有32000條記錄，每條記錄的結構如下：
字段 姓名 地址 年齡 專業(yè)
類型 字符 字符 數(shù)字 字符
長度（字符） 4-8 0-100 1 0-20
該數(shù)據(jù)的內容固定不變，其用途主要是用于根據(jù)姓名來檢索其他相關信
息。現(xiàn)把這些數(shù)據(jù)以文件形式存放在磁盤上，該磁盤的物理塊大小為4KB。
請設計存放該批數(shù)據(jù)的文件的邏輯結構（可以不存儲在一個文件中）和物理
結構（在磁盤上的存儲結構），使得檢索操作能盡可能少訪問磁盤。并計算
在該結構下，每次檢索平均需要訪問多少個物理塊。（假設文件的目錄已經
調人內存，文件存放在外存）
zz

一小時有多少分鐘？（答案為數(shù)字）

考研論壇提示：
1、請勿發(fā)布個人聯(lián)系方式或詢問他人聯(lián)系方式，包括QQ和手機等。
2、未經允許不得發(fā)布任何資料出售、招生中介等廣告信息。
3、如果發(fā)布了涉及以上內容的話題或跟帖，您在考研網的注冊賬戶可能被禁用。