2013年山東科技考研專業(yè)課真題830數(shù)據(jù)結(jié)構(gòu)與操作系統(tǒng)

1、數(shù)據(jù)結(jié)構(gòu)部分一、簡答題（10 分，每題 5 分）1、數(shù)據(jù)元間的關(guān)系在計算機(jī)中的有幾種表示方法？各特點？空間考慮，則應(yīng)該首先選取2、對于堆排序法，快速排序法和歸并排序法，若僅從節(jié)省其中哪種方法？其次選取哪種方法？若僅考慮排序結(jié)果的穩(wěn)定性，則應(yīng)該選取其中哪種方法？若僅從平均情況下排序最快這一點考慮，則應(yīng)該選取其中哪些方法二、應(yīng)用題（55 分）1、證明：同一棵二叉樹的所有葉子結(jié)點，的相對位置出現(xiàn)（即先后順序相同）。（8 分序序列、中序序列以及后序序列中都按相同2、設(shè)有正文 AADBAACACCDACACAAD，字符集為 A,B,C,D,設(shè)計一套二進(jìn)制編碼，使得上述正文的編碼最短。（10 分）3、對于

2、下圖完成下列指定操作。（12 分）從頂點 A 出發(fā)，求它的深度優(yōu)先生成樹。從頂點 E 出發(fā)，求它的廣度優(yōu)先生成樹。(3)根據(jù)姆(Prim) 算法，求它的最小生成樹。4. 設(shè)哈希(Hash)表的地址范圍為 017，哈希函數(shù)為：H (K)=K MOD 16,K 為關(guān)鍵字，用線性探測再散列法處理，輸入關(guān)鍵字序列: (10,24,32,17,31,30,46,47,40,63,49)構(gòu)造哈希表，試回答下列問題：（15 分）畫出哈希表示意圖。若查找關(guān)鍵字 63，需要依次與哪些關(guān)鍵字比較?若查找關(guān)鍵字 60，需要依次與哪些關(guān)鍵字比較?假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。5奇偶交換排序

3、如下所述：對于初始序列 A1，A2,An,第一趟對所有奇數(shù) i（1=iAi+1，則將兩者交換；第二趟對所有偶數(shù) i（2=iAi+1，則將兩者交換；第三趟對所有奇數(shù) i（1=in）；第四趟對所有偶數(shù) i（2=in）,，依次類推直至到整個序列有序為止。 （10 分）分析這種排序方法的結(jié)束條件。寫出用這種排序方法對 35，70，33，65，24，21，33 進(jìn)行排序時，每一趟的結(jié)果。三、算法設(shè)計題（25 分)答題要求：用自然語言說明所采用算法的；給出每個算法所需的數(shù)據(jù)結(jié)構(gòu)定義，并做必明；用 C 語言寫出對應(yīng)的算法程序，并做必要的注釋?？臻g只能使用指針）。 (10 分)1、編程實現(xiàn)單鏈表的就地逆置（額

4、外2、二叉樹采用二叉鏈表結(jié)構(gòu)，設(shè)計算法統(tǒng)計二叉樹的深度（二叉樹的最大層數(shù)）和寬度（二叉樹中所有層中結(jié)點的最大個數(shù)）。（15 分）操作系統(tǒng)部分一： 簡單題 （共27分）1：操作系統(tǒng)的四個基本特征是什么？并請分析它們之間的關(guān)系。（本小題 3 分2：請簡述進(jìn)程和程序的差異、進(jìn)程和線程的差異。（本小題 6 分3：處理死鎖的基本方法有哪幾種？并請分析它們的優(yōu)缺點。（本小題 4 分4：“根據(jù)分為三種”，請問是哪三種？并請分析 DLL時間的不同，可把方式的優(yōu)點。（本小題 4 分）5：小題 4 分SPOOLING 技術(shù)？一個 SPOOLING 系統(tǒng)主要由哪幾部分組成？（本6：連續(xù)分配、分配和索引分配是外存管理

5、中常用的分配方式。請分析三者的優(yōu)點和缺點。（本小題 6 分二：算法和計算題（共33分）1：設(shè) A、B 兩進(jìn)程共用一個緩沖區(qū) Q 進(jìn)行通信，A 向 Q 寫入信息，B 則從 Q 讀出信息。為了保證進(jìn)程 A、B 之間的通信順利進(jìn)行，某同學(xué)設(shè)計了一個如下圖所示的算法，該算法使用一個信號量 S 進(jìn)行進(jìn)程 A、B 之間的同步。請問，該算法是否正確?若有錯，請原因并予以改正。（本題 10 分）2：某虛擬器的用戶空間共有 32 個頁面，每頁 1KB，而主存為 16KB。假定某時刻系統(tǒng)為用戶的第 0、1、2、3 頁分配的物理塊號為 5、10、4、7，而該用戶作業(yè)的長度為 6 頁。請問：（本題總計 10 分）（提示：請注意邏輯地址是由哪兩部分組成的）1)十六進(jìn)制的邏輯地址（也稱為虛擬地址）0A5C 對應(yīng)的物理地址是什么？（2分）2)的十六進(jìn)制的邏輯地址是 103C，那么會出現(xiàn)什么現(xiàn)象？操作系統(tǒng)如果要是如何處理這種現(xiàn)象的，并請說明處理過程。（6 分）如果要的十六進(jìn)制的邏輯地址是 1A5C，那么會出現(xiàn)什么現(xiàn)象3)（2 分）3：假設(shè)磁盤有 200 個磁道，磁盤請求隊列中都是隨機(jī)請求，它們按照到達(dá)的次序分別處于 55、58、39、 8、90、 60、 50、38、184 號磁道上，當(dāng)前磁頭在 100 號磁道上，并向磁道號增加的方向移動。請給出按著 FCFS、SSTF 算法進(jìn)行磁盤調(diào)度時的次序，