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

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

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

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

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

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