浙江工商大學2017考研真題之845計算機基礎綜合

1、浙江工商大學2017年全國碩士研究生入學考試試卷（A）卷考試科目：845計算機基礎綜合總分：150分考試時間：3小時第I部分數(shù)據(jù)結(jié)構（75分〉一、簡答題（每小題7分，共42分）1.有一份電文中共使用五種字符：abcde，它們的出現(xiàn)頻率依次為15181613110，請畫出對應的編碼赫夫曼樹（請按照左子樹根結(jié)點的權小于等于右子樹根結(jié)點的權的次序構造），并求出該樹的帶權路徑長度。2.已知一棵二叉樹的前序和中序序列，建立該二叉樹，并求該二叉樹的

2、后序序列。前序序列：8631.25497中序序列：1234568793.給定表（23，”，42，”，78952235），請將表調(diào)整成初始最大堆。4.請描述克魯斯卡爾（Kruskal）構造最小生成樹算法。5.設一數(shù)列的輸入順序，為1234，若采用堆枝結(jié)構，試問通過入出挽操作，能否得到合法序列3241，如果能，則給出得到這個序列相應的push和pop操作。6.閱讀下列程序，說明該函數(shù)實現(xiàn)了，什么功能。若原單鏈表中數(shù)據(jù)結(jié)點的值按順序分別為13

3、642S，調(diào)用該函數(shù)后，結(jié)點值有何變化？typedefstructnodeintdatast儼uctnodenext:structnode＊手unc(str、uctnodehead)structnodedletailleadtail=dle=NULLlead=headwhile(lead)｛dle=leadlead=leadnextdlenext=tailtail=dleretu儼ndle｝二、程序設計〈共33分〉1.(12分）若以單鏈

4、表作為存儲結(jié)構，編寫一算法，刪除該線性表中所有大于a且小于b的元素（若表中存在這樣的元素）同時釋放被刪除結(jié)點空間，假設線性表中的元素按遞增有序排列。2.(9分）設棵二叉樹以二叉鏈表為存儲結(jié)構，結(jié)點結(jié)構為!child!datajrchild。設計一個算法，求在前根序列中處于第k個位置的結(jié)點。3.(12分）試寫一算法，將兩棵二叉排序樹合并為一棵二叉排序樹。答案寫在答題紙上，寫在試卷上無效第1頁（共2頁）第口部分操作系統(tǒng)（75分〉三、簡答題〈

5、每小題6分，共30分〉1.簡述引起進程調(diào)度的原因。2.比較分段和分頁兩種內(nèi)存管理機制的不同。3.產(chǎn)生死鎖條件及解決方法。4.SPOOLing技術。5.電梯調(diào)度算法。四、綜合題（每小題15分，共45分）1.(15分）在分頁存儲管理系統(tǒng)中，按如下次序訪問頁：10→6→8→7→10→6→20→10→6→8→7→20，假定分配的物理塊數(shù)為3，試分別計算采用如下頁面置換算法時的缺頁次數(shù):(1）先進先出置換算法（FIFO)(2）最近最久未使用算法C

6、LRU）。2.(15分〉某電信營業(yè)廳提供1個取號機、2個服務窗口和10個供客戶等待的座位?？蛻舻竭_后，如有空位則取號，然后等待叫號：當營業(yè)員空閑時，則叫號選取一位客戶，并提供服務。請用PVC或wait、signal)操作來同步上述過程，要求：(1）寫出所需要的信號量及初始值：（2）用偽碼寫出上述過程。3.(15分）某文件系統(tǒng)采用混合索引分配方式，如圖2所示，有10個直接塊（每個直接塊指向一個數(shù)據(jù)塊），1個一級間接塊，1個二級間接塊和1個