蘇州大學 - 話題

專業名稱：計算機應用技術、計算機軟件以理論 考試科目：數據結構與操作系統 （B）卷

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

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

2、(15分)雙端隊列是限定插入和刪除操作在表的兩端進行的線性表。假設
依次輸入數據元素為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分）試設計一個算法，將二叉樹中的葉子結點按從左到右的順序放入
一個線性表。假設二叉樹采用二叉鏈表存儲結構，線性表采用動態分配順序
存儲結構。

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

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










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

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

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

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

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

中國有多少個民族？

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