|
蘇州大學06年真題 數據結構與操作系統 （B）卷
查看(2049) 回復(0) |
|
|
發表于
樓主
專業名稱：計算機應用技術、計算機軟件以理論 考試科目：數據結構與操作系統 （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 |
|
回復話題 |
||
|
|
|
|