2023年研究生入學(xué)考試試題(A)

1、2007年研究生入學(xué)考試試題(A)考試科目：計算機軟件技術(shù)根底 報考學(xué)科、專業(yè)：計算機應(yīng)用技術(shù)請注意:全部答案必須寫在答題紙上，否那么不給分。一、名詞解釋第14題，每題3分，第5、6題要求先寫出英文全稱，再用中文簡要解釋其含義，每題4分，共20分數(shù)據(jù)類型 2、線程原語 4、虛擬設(shè)備WPL 6、DMA二、填空題每題2分，共20分1、假設(shè)B =K， R是一個邏輯結(jié)構(gòu)，r是一個K到K的1 ：1關(guān)系，rR，假設(shè)k，kK，且r，那么稱k是k的 ，k是k的 。2、設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范圍是0n-1，其頭尾指針分別為f和r，那么該循環(huán)隊列中數(shù)據(jù)元素的個數(shù)為 。3、設(shè)有一個三對角矩陣An*n，將其三條對角線

2、上的元素逐行地存儲到向量B0.3n-3中，那么元素A5,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實驗室的兩個程序員Ken T

3、hompson和Dennis Ritchie于 年在PDP11機器上開發(fā)實現(xiàn)的。三、簡答題每題5分，共30分設(shè)多項式P(x)5x63x44x3x12，請用兩種不同的線性存儲結(jié)構(gòu)表示該多項式，畫出它們的存儲映像圖。設(shè)一棵二叉樹的前序遍歷序列為B A L F E C D H G， 后序遍歷序列為L F A D H C G E B，請畫出該二叉樹，并分別給出該二叉樹的中序遍歷序列和按層次遍歷序列。第 1 頁，共 5 頁2007年研究生入學(xué)考試試題考試科目：計算機軟件技術(shù)根底 報考學(xué)科、專業(yè)：計算機應(yīng)用技術(shù)請注意:全部答案必須寫在答題紙上，否那么不給分。鐵路進行列車調(diào)度時, 常把站臺設(shè)計成棧式結(jié)構(gòu)，試

4、問：1設(shè)有編號為1，2，3，4的四輛列車, 順序開入站臺, 那么可能的出站序列有多少種？ 2假設(shè)進站五輛列車，其順序為1，2，3，4，5, 那么是否能夠得到4，5，2，1，3和3，4，2，5，1這樣的出站序列？請說明原因或給出得到該序列的列車進站、出站過程。假設(shè)Hash函數(shù)為：Hkey= 3*key % 11 其中 * 為乘法、 % 為取余運算，下同并采用開放地址法處理沖突，其求下一地址的函數(shù)為： D1 = Hkey； Di = Di-1+7*key% 11 i = 2，3， 試在010的散列地址空間中對關(guān)鍵字序列22，41，53，46，30，13，01，67構(gòu)造Hash表，并求出在等概率情況

5、下查找成功的平均查找長度。什么叫搶占式處理機調(diào)度和非搶占式處理機調(diào)度？先來先效勞FCFS、優(yōu)先數(shù)法各屬于哪種調(diào)度方式？某系統(tǒng)采用請求分頁存儲管理方案，其邏輯地址有32 bits，頁內(nèi)地址占12 bits。有一個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分 void p ( int n ) if ( n 0 ) p ( n-1 ) ； printf ( “ %d , &n ) ；p ( n-1 ) ；print

6、f ( “ %d , &n ) ； 當(dāng)調(diào)用 p ( 4 ) 時，其完整的輸出結(jié)果為： 第 2 頁，共 5 頁2007年研究生入學(xué)考試試題考試科目：計算機軟件技術(shù)根底 報考學(xué)科、專業(yè)：計算機應(yīng)用技術(shù)請注意:全部答案必須寫在答題紙上，否那么不給分。以下算法的功能是利用堆進行排序，請在空白處填上適宜語句以完成該算法。void sift (RecType R ，int k，int m ) int i，j，x； RecType temp； int finished = 0； i = k ； ； x = R i . key； temp = R k ； while ( j m & ! finished )

7、if ( j = R j . Key ) finished = 1； else ； ； ； ； void heapsort ( RecType R ， int n ) int i ； RecType x ； for ( i = n/2； i = 1； i - - ) ； for ( i = n； i = 2； i - - ) x = R 1 ； R 1 = R i ； R i = x ； ； 第 3 頁，共 5 頁2007年研究生入學(xué)考試試題考試科目：計算機軟件技術(shù)根底 報考學(xué)科、專業(yè)：計算機應(yīng)用技術(shù)請注意:全部答案必須寫在答題紙上，否那么不給分。閱讀如下函數(shù)，請在空格處填上恰當(dāng)?shù)淖⑨?，并說明

8、該函數(shù)的功能。typedef struct node datatype data ； int len ； Lnode ；void mystery ( Lnode &A，Lnode B，Lnode C ) int i，j，k，s，f ； i = 0； j = 0； while ( i = A.len ) & ( j = B.len ) if ( A.data i = = B.data j ) / f = 0 ；for ( k = 0； k = C.len； k + + ) if ( A.data i = = C.data k ) f = 1； if ( f = = 0 ) / - - A.len

9、 ； for ( s = i ； s B.data j ) j + + ； if ( A.data i B.data j ) i + + ； 功能為： 第 4 頁，共 5 頁2007年研究生入學(xué)考試試題考試科目：計算機軟件技術(shù)根底 報考學(xué)科、專業(yè)：計算機應(yīng)用技術(shù)請注意:全部答案必須寫在答題紙上，否那么不給分。五、綜合應(yīng)用題第1題12分，第2題15分，共27分在一個漆黑的夜晚，一伙旅行者需要通過一座橫跨于深谷間的小橋，他們只有一盞老式的油燈作照明。要想成功過橋，燈光是必需的，此外因為橋很窄，最多僅容兩人同時過橋，更糟糕的是油燈里的油量有限，要盡可能快地過橋。而且由于過橋需要照明，所以任何兩個人一

10、起過橋時，都得由走得慢的人決定過橋時間。那么：假設(shè)A、B、C、D四個人，A過橋需要1分鐘，B過橋需要2分鐘，C過橋需要5分鐘，D過橋需要10分鐘，請安排他們的過橋次序使其總的過橋時間最短，并算出其過橋時間。針對n個人，他們的過橋時間分別為數(shù)組T n ，試說明一個能夠滿足以上需求的安排他們過橋次序的算法思想或算法。有個寺廟，廟中有小和尚、老和尚假設(shè)干人，廟里有一只水缸，由小和尚提水入缸給老和尚飲用，每次只能入缸1桶水或取缸中1桶水。水缸可容10桶水，水取自同一口井中。水井徑窄，每次僅能容一只水桶取水，水桶總數(shù)為3個。試用同步工具寫出小和尚、老和尚取水、用水的活動過程。六、算法設(shè)計分析題第1題12

11、分，第2題13分，共25分1、設(shè)二叉樹以二叉鏈表為存儲結(jié)構(gòu)，首先定義該二叉樹的數(shù)據(jù)結(jié)構(gòu)，然后針對二叉樹中一個結(jié)點由指針p所指，設(shè)計一個求p的兄弟結(jié)點的算法假設(shè)p沒有兄弟，那么返回空指針。2、設(shè)有向圖的鄰接表表示結(jié)構(gòu)如下：#define MaxVexNum 30 /最大頂點數(shù)typedef struct ArcNode int adjvex ； /該弧弧頭所指向的頂點下標(biāo) struct ArcNode * nextarc ； /指向下一條弧的指針 InfoType * info ； /與該弧相關(guān)的其它信息 ArcNode ；typedef struct VNode VertexType data ； /頂點信息 ArcNode * firstarc ； /指向出自該頂點的第一條弧的指針 VNode，AdjList MaxVexNum ； tyoedef struct int vexnum，arcnum ；/分別存放