2007年研究生入學(xué)考試試題(A)考試科目：計算機軟件技術(shù)基礎(chǔ)報考學(xué)科、專業(yè)：計算機應(yīng)用技術(shù)請注意:全部答案必須寫在答題紙上，否則不給分。一、名詞解釋（第1~4題，每題3分，第5、6題要求先寫出英文全稱，再用中文簡要解釋其含義，每題4分，共20分）數(shù)據(jù)類型2、線程原語4、虛擬設(shè)備WPL6、DMA二、填空題（每題2分，共20分）1、假設(shè)B=（K，R）是一個邏輯結(jié)構(gòu)，r是一個K到K的1：1關(guān)系，r∈R，若k，k’∈K，且<k，k’>∈r，則稱k’是k的①，k是k’的②。2、設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范圍是0～n-1，其頭尾指針分別為f和r，則該循環(huán)隊列中數(shù)據(jù)元素的個數(shù)為。3、設(shè)有一個三對角矩陣An*n，將其三條對角線上的元素逐行地存儲到向量B[0..3n-3]中，則元素A[5,6]的存儲單元下標(biāo)為。（假設(shè)下標(biāo)都從0開始）4、可采用折半查找法進行查找的數(shù)據(jù)表一般應(yīng)滿足的條件為①和②。5、操作系統(tǒng)具備處理并發(fā)任務(wù)的能力，其最重要的硬件支持是。6、每個信箱可以由①和②兩部分組成。7、死鎖產(chǎn)生的根本原因是①和②。8、文件包括①和②兩種，前者是指文件內(nèi)的信息不再劃分獨立的單位，整個文件是由一串信息組成，后者是指文件內(nèi)的信息按邏輯上獨立的含義劃分信息單位。9、通道在執(zhí)行通道程序的過程中，需要訪問內(nèi)存中的兩個固定單元，①和②。10、UNIX操作系統(tǒng)的第一個版本Versional是①公司下屬的Bell實驗室的兩個程序員KenThompson和DennisRitchie于②年在PDP11機器上開發(fā)實現(xiàn)的。三、簡答題（每題5分，共30分）設(shè)多項式P(x)＝5x6＋3x4－4x3＋x－12，請用兩種不同的線性存儲結(jié)構(gòu)表示該多項式，畫出它們的存儲映像圖。設(shè)一棵二叉樹的前序遍歷序列為BALFECDHG，后序遍歷序列為LFADHCGEB，請畫出該二叉樹，并分別給出該二叉樹的中序遍歷序列和按層次遍歷序列。第1頁，共5頁2007年研究生入學(xué)考試試題考試科目：計算機軟件技術(shù)基礎(chǔ)報考學(xué)科、專業(yè)：計算機應(yīng)用技術(shù)請注意:全部答案必須寫在答題紙上，否則不給分。鐵路進行列車調(diào)度時,常把站臺設(shè)計成棧式結(jié)構(gòu)，試問：（1）設(shè)有編號為1，2，3，4的四輛列車,順序開入站臺,則可能的出站序列有多少種？（2）若進站五輛列車，其順序為1，2，3，4，5,那么是否能夠得到4，5，2，1，3和3，4，2，5，1這樣的出站序列？請說明原因或給出得到該序列的列車進站、出站過程。假設(shè)Hash函數(shù)為：H（key）=3*key%11（其中*為乘法、%為取余運算，下同）并采用開放地址法處理沖突，其求下一地址的函數(shù)為：D1=H（key）；Di=（Di-1+（7*key））%11（i=2，3，…）試在0~10的散列地址空間中對關(guān)鍵字序列（22，41，53，46，30，13，01，67）構(gòu)造Hash表，并求出在等概率情況下查找成功的平均查找長度。什么叫搶占式處理機調(diào)度和非搶占式處理機調(diào)度？先來先服務(wù)（FCFS）、優(yōu)先數(shù)法各屬于哪種調(diào)度方式？某系統(tǒng)采用請求分頁存儲管理方案，其邏輯地址有32bits，頁內(nèi)地址占12bits。有一個4頁的作業(yè)，其邏輯頁號為0，1，2，3分別裝入內(nèi)存空間的7，8，16，19塊。試問：作業(yè)的虛存空間有多大？系統(tǒng)的頁面大小為多少？邏輯地址5000對應(yīng)的物理地址是多少？四、程序理解、填空題（第1題4分，第2題16分，第3題8分，共28分）voidp(intn){if(n>0){p(n-1)；printf(“%d”,&n)；p(n-1)；printf(“%d”,&n)；}}當(dāng)調(diào)用p(4)時，其完整的輸出結(jié)果為：第2頁，共5頁2007年研究生入學(xué)考試試題考試科目：計算機軟件技術(shù)基礎(chǔ)報考學(xué)科、專業(yè)：計算機應(yīng)用技術(shù)請注意:全部答案必須寫在答題紙上，否則不給分。五、綜合應(yīng)用題（第1題12分，第2題15分，共27分）在一個漆黑的夜晚，一伙旅行者需要通過一座橫跨于深谷間的小橋，他們只有一盞老式的油燈作照明。要想成功過橋，燈光是必需的，此外因為橋很窄，最多僅容兩人同時過橋，更糟糕的是油燈里的油量有限，要盡可能快地過橋。而且由于過橋需要照明，所以任何兩個人一起過橋時，都得由走得慢的人決定過橋時間。則：假設(shè)A、B、C、D四個人，A過橋需要1分鐘，B過橋需要2分鐘，C過橋需要5分鐘，D過橋需要10分鐘，請安排他們的過橋次序使其總的過橋時間最短，并算出其過橋時間。針對n個人，他們的過橋時間分別為數(shù)組T[n]，試說明一個能夠滿足以上需求的安排他們過橋次序的算法思想（或算法）。有個寺廟，廟中有小和尚、老和尚若干人，廟里有一只水缸，由小和尚提水入缸給老和尚飲用，每次只能入缸1桶水或取缸中1桶水。水缸可容10桶水，水取自同一口井中。水井徑窄，每次僅能容一只水桶取水，水桶總數(shù)為3個。試用同步工具寫出小和尚、老和尚取水、用水的活動過程。六、算法設(shè)計分析題（第1題12分，第2題13分，共25分）1、設(shè)二叉樹以二叉鏈表為存儲結(jié)構(gòu)，首先定義該二叉樹的數(shù)據(jù)結(jié)構(gòu)，然后針對二叉樹中一個結(jié)點（由指針p所指），設(shè)計一個求p的兄弟結(jié)點的算法（若p沒有兄弟，則返回空指針）。2、設(shè)有向圖的鄰接表表示結(jié)構(gòu)如下：#defineMaxVexNum30//最大頂點數(shù)typedefstructArcNode{intadjvex；//該弧弧頭所指向的頂點下標(biāo)structArcNode*nextarc；//指向下一條弧的指針I(yè)nfoType*info；//與該弧相關(guān)的其它信息}ArcNode；typedefstructVNode{VertexTypedata；//頂點信息ArcNode*firstarc；//指向出自該頂點的第一條弧的指針}VNode，AdjList[MaxVexNum]；tyoedefstruct{intvexnum，arcnum；//分別存放圖中頂點、弧的數(shù)目AdjListvertices；