2016年全國碩士研究生統(tǒng)一入學(xué)考試自命題試題a卷

1、2016年全國碩士研究生統(tǒng)一入學(xué)考試自命題試題（年全國碩士研究生統(tǒng)一入學(xué)考試自命題試題（A卷）卷）學(xué)科、專業(yè)名稱：計算機(jī)科學(xué)與技術(shù)、軟件工程研究方向：計算機(jī)系統(tǒng)結(jié)構(gòu)081201，計算機(jī)軟件與理論081202，計算機(jī)應(yīng)用技術(shù)081203，軟件工程083500，計算機(jī)技術(shù)(專業(yè)學(xué)位)085211，軟件工程(專業(yè)學(xué)位)085212考試科目名稱及代碼：數(shù)據(jù)結(jié)構(gòu)830考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分?？忌⒁猓核?/p>

2、答案必須寫在答題紙（卷）上，寫在本試題上一律不給分。一、一、單項選擇題單項選擇題(每題每題2分，共分，共30分)1.在線索化二叉樹中，T所指結(jié)點沒有左子樹的充要條件是（）。A.Tlchild=NULLB.Tltag=1C.tltag=1且tlchild=NullD.以上都不對2.一個帶有頭結(jié)點的單鏈表為空的判定條件是()。A.head==NULLB.headnext==NULLC.headnext==headD.head!=NULL3.

3、線性鏈表不具有的特點是（）。A.隨機(jī)訪問B.不必預(yù)估所需存儲空間大小C.插入與刪除時不必移動元素D.所需空間與線性表長度成正比4.在下面的排序方法中，穩(wěn)定的是（）。A.希爾排序B.堆排序C.插入排序D.快速排序5.設(shè)有n個待排序的記錄關(guān)鍵字，則在堆排序中需要（）輔助記錄空間。AO(1)B.O(n)C.O(nlog2n)D.O(n2)6.數(shù)組A［５］［６］的每個元素占5個字節(jié)，將其按行優(yōu)先次序存儲。假設(shè)A[1][1]元素的存儲地址為100

4、0，則元素A［５，５］的存儲地址為()。A.1140B.1145C.1120D.11257.高度為n的完全二叉樹的結(jié)點數(shù)至少為（）。A.2n1B.2n11C.2nD.2n18.設(shè)有一個無向圖G=（V，E）和G’=（V’，E’），如果G’為G的生成樹，則下面不正確的說法是（）。AG’為G的子圖BG’為G的連通分量CG’為G的極小連通子圖且V’=VDG’為G的一個無環(huán)子圖9.在有向圖的鄰接表存儲結(jié)構(gòu)中，頂點V在表結(jié)點中出現(xiàn)的次數(shù)是（）。A.

5、頂點V的度B.頂點V的出度C.頂點V的入度D.依附于頂點V的邊數(shù)10.關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中()。A最短的回路B從源點到匯點的最短路徑C最長的回路D從源點到匯點的最長路徑考試科目：數(shù)據(jù)結(jié)構(gòu)共5頁，第1頁考試科目：數(shù)據(jù)結(jié)構(gòu)共5頁，第2頁四.簡答題（簡答題（45分）分）1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，求解下列問題：(1)畫出此二叉樹。（4分）(2)將該二叉樹轉(zhuǎn)換成森林。（4分）2

6、.設(shè)有一組關(guān)鍵字（712373145589334348）采用哈希函數(shù)：H(key)=key%10，采用開放地址的二次探測再散列方法解決沖突，試在散列地址空間中對該關(guān)鍵字序列(按從左到右的次序)構(gòu)造哈希表，并計算在查找概率相等的前提下，成功查找的平均查找長度。（7分）3.設(shè)有一組初始記錄關(guān)鍵字為(3146825)，要求構(gòu)造一棵平衡二叉樹，并給出構(gòu)造過程。（5分）4.對圖1所示的無向加權(quán)圖完成下列要求：（1）寫出它的鄰接表；（5分）（2）按

7、克魯斯卡爾（Kruskal）算法求其最小生成樹，并給出其過程。（6分）（3）給出從頂點a開始的深度優(yōu)先搜索序列和深度優(yōu)先生成樹。（4分）圖15.已知序列(14254312365453879572434111242811102)。(1)采用希爾排序?qū)υ撔蛄凶魃蚺判颍埥o出第一趟排序的結(jié)果（初始步長為7）。（5分）(2)采用堆排序?qū)υ撔蛄凶魃蚺判?，請給出初始堆以及第一趟排序的結(jié)果。（5分）五算法填空算法填空，（每空每空2分共20分）1.