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

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

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

2、(15分)雙端隊(duì)列是限定插入和刪除操作在表的兩端進(jìn)行的線性表。假設(shè)
依次輸入數(shù)據(jù)元素為1、2、3、4、5和6，試問(wèn)通過(guò)使用（a）隊(duì)列；（b）雙
端隊(duì)列，能否得到下列輸出序列？
（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分）試設(shè)計(jì)一個(gè)算法，將二叉樹中的葉子結(jié)點(diǎn)按從左到右的順序放入
一個(gè)線性表。假設(shè)二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，線性表采用動(dòng)態(tài)分配順序
存儲(chǔ)結(jié)構(gòu)。

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

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










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

7、（15分）請(qǐng)解釋以下的概念：
（1）中斷
（2）虛擬設(shè)備
（3）中級(jí)調(diào)度
（4）Cache
（5）LRU算法

8、（15分）在虛擬存儲(chǔ)技術(shù)中，系統(tǒng)將進(jìn)行進(jìn)程運(yùn)行時(shí)所缺的頁(yè)面調(diào)入內(nèi)存的
時(shí)機(jī)有預(yù)調(diào)頁(yè)策略和請(qǐng)求式調(diào)頁(yè)策略兩種。請(qǐng)說(shuō)明這兩種策略的原理，并結(jié)合
具體的實(shí)例比較這兩種策略的優(yōu)劣。

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

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

目前中國(guó)有1角紙幣嗎？

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