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

1、浙江工商大學(xué)2018年全國碩士研究生入學(xué)考試試卷（A）卷考試科曰：845計算機基礎(chǔ)綜合總分：150分考試時間：3小時I、數(shù)據(jù)結(jié)構(gòu)(75分）一、問答（每小題10分，共30分〉1.(10分）給定二叉樹的兩種遍歷序歹1j，分別是：前序遍歷序列：DACEBHFGI中序遍歷序列：DCBEHAGIF請給出這棵二叉樹的后序遍歷序列，并簡述由任意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。2.(10分〉已知排序碼值序列｛192207235

2、6515｝，請寫出快速排序第一趟的排序結(jié)果（假設(shè)我們選擇第一個元素19做為基數(shù)），并描述快速排序算法思想。3.(10分）選取哈希函數(shù)H(k)=Ck)MOD11。用二次探測處理沖突，試在一10的散列地址空間中對關(guān)鍵字序列（22415346301301）造哈希表，并求等概率情況下查找成功時的平均查找長度。二、算法和程序設(shè)計（每小題15分，共45分）1.(15分〉編寫一算法，在不增加輔助空間的前提下，將兩個遞增的單鏈表合并為一個遞增的單鏈表。

3、2.(15分〉編寫一算法，描述如何將一個中序表達式轉(zhuǎn)化為后序表達式。例如，輸入如果是2345則輸出為234＊十肘。3.05分〉編寫一函數(shù)intheight(structtree豐root），求二叉樹的高度。假設(shè)空二叉樹的高度為Oostructtree定義如下：structtreeintdatastructtreeleftrightII、操作系統(tǒng)（75分）三、簡答題（每小題6分，共30分）1.(6分〉簡述操作系統(tǒng)主要功能。2.(6分〉進程

4、狀態(tài)有哪些？這些狀態(tài)之間如何轉(zhuǎn)換？3.(6分）產(chǎn)生死鎖的四個必要條件。4.(6分）TLB(TranslationLookasideBuffer）快表的作用。5.(6分）簡述SCAN掃描算法（電梯算法）。四、綜合題（每小題15分，共45分）1.C15分〉一個采用請求式頁面存儲的系統(tǒng)，其物理內(nèi)存為512M字節(jié)，虛擬地址空間大小為4G字節(jié)，頁面大小為4K字節(jié)，試問：(1）物理地址應(yīng)設(shè)為多少位？(2）主存中有多少物理頁？(3）虛擬地址應(yīng)該設(shè)多少

5、位？(4）虛擬地址空間最多可以有多少頁？(5）頁內(nèi)最大和最小偏移量是多少？答案寫在答題紙上，寫在試卷上無效第l頁（其2頁）2.(15分）有M個生產(chǎn)者凹，P2，…，PM和K個消費者ClC2，…，CK，一個大小為n的環(huán)形緩沖區(qū)，生產(chǎn)者把產(chǎn)品放入緩沖區(qū)，消費者從緩沖區(qū)取產(chǎn)品來消費。請用wait和signal原語實現(xiàn)生產(chǎn)者和消費者的同步操作。3.Cl5分〉設(shè)系統(tǒng)中物理頁的數(shù)量為150。在TO時刻按表I所示分配給三個進程Pl、P2和P3。系統(tǒng)采用