浙江工商大學(xué)2017考研真題之845計(jì)算機(jī)基礎(chǔ)綜合

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

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

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

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

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

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