共6頁，第1頁浙江農(nóng)林大學(xué)20182019學(xué)年第二學(xué)期考試卷(A)課程名稱：數(shù)據(jù)結(jié)構(gòu)課程類別：必修考試方式：閉卷注意事項(xiàng)：1、本試卷滿分100分。2、考試時間120分鐘。題號一二三四五六七八得分得分評閱人填空題(1×12=12分)1、常見的四類基本數(shù)據(jù)結(jié)構(gòu)有：線性結(jié)構(gòu)、_________、__________和圖狀結(jié)構(gòu)。2、棧又稱為表，隊(duì)列又稱為表。3.串S=″Iamaworker″的長度是________。4、設(shè)有二維數(shù)組A[0..9,0..19]，其每個元素占兩個字節(jié)，第一個元素的存儲地址為100，若按行優(yōu)先順序存儲，則元素A[6,6]的存儲地址為。5、使用折半查找時，靜態(tài)查找表必須不僅是______，并且______存儲。6、利用MST性質(zhì)來構(gòu)造最小生成樹的兩種常用算法為_________和__________。7、每次直接或通過基準(zhǔn)元素間接比較兩個元素，若出現(xiàn)逆序排列時就交換它們的位置，此種排序方法叫做排序；每次使兩個相鄰的有序表合并成一個有序表的排序方法叫做排序。判斷(對的打∨,錯誤打×,8×2=16分)在數(shù)據(jù)元素的非空有限集中，存在唯一的一個被稱為”前驅(qū)”的元素，也存在唯一的一個稱為”后繼”的元素()一般情況下，在第i(1<=i<=n)個元素之前插入一個元素，需要將第n個到第i個元素向后移動一個位置，移動元素的個數(shù)為n-i+1()隊(duì)列的基本特征是先進(jìn)后出()數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。赫夫曼樹是指帶權(quán)路徑長度WPL最小的二叉樹。一般而言，在給定條件下構(gòu)造出的赫夫曼樹不是唯一的。()6、路徑長度最長的路徑為關(guān)鍵路徑。()7、由樹轉(zhuǎn)化成二叉樹，其根的右子女指針總是空的。()8、直接選擇排序是一種穩(wěn)定的排序方法。()選擇題（7×3=21分）線性鏈表不具有的特點(diǎn)().A.隨機(jī)訪問B.不必事先估計所需存儲空間大小C.插入與刪除時不必移動元素D.所需空間與線性表長度成正比2、帶頭結(jié)點(diǎn)的單鏈表first為空的判定條件是： A.first==NULL; B.first->link==NULL; C.first->link==first; D.first!=NULL;3、一個棧的輸入序列為1，2，3，4，下面哪一個序列不可能是這個棧的輸出序列？

A.1，3，2，4

B.2，3，4，1

C.4，3，1，2

D.3，4，2，14、具有65個結(jié)點(diǎn)的完全二叉樹的高度為().(根的層次號為1)A.8B.7C.6D.55、ALV樹是一種平衡的二叉排序樹，樹中任一結(jié)點(diǎn)的()

A.左、右子樹的高度均相同

B.左、右子樹高度差的絕對值不超過1C左子樹的高度均大于右子樹的高度

D.左子樹的高度均小于右子樹的高度6、若一棵二叉樹具有10個度為2的結(jié)點(diǎn)，則該二叉樹的度為0的結(jié)點(diǎn)個數(shù)是A.9B.11C.12D.不確定

7、若待排序序列在排序前已按其排序碼遞增順序排列,則采用()方法比較次數(shù)最少.

A.直接插入排序B.快速排序

C.歸并排序D.直接選擇排序基本概念分析題(共31分)1、寫出下列圖的鄰接矩陣和鄰接表（5+5分）V2V2V1V1V3V5V3V5V6V4V6V42、已知一棵二叉樹的前序和中序序列如下：（6+5分）前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,E,F,D,I,H,J,G畫出該二叉排序樹給出該二叉排序樹的后序遍歷3、設(shè)待排序文件的關(guān)鍵碼為（512,275,908,677,503,765,612,897,154,170）以第一元素為分界元素進(jìn)行快速排序（按關(guān)鍵碼值遞增順序），請給出一趟掃描后的結(jié)果。（10分）五、算法設(shè)計題(本大題共2小題，每題10分，共20分)1、假設(shè)二叉樹T采用如下定義的存儲結(jié)構(gòu)：(本題10分)

typedefstructNode{

DataTypedata;

structNode*lchild,*rchild;

}*BiTree;其中，結(jié)點(diǎn)的lchild域和rchild域已分別填有指向其左、右孩子結(jié)點(diǎn)的指針，編寫一個遞歸算法，計算一棵二叉樹中，度數(shù)為2的節(jié)點(diǎn)個數(shù)。IntCountNode(BiTreeT){//考試編寫代碼}2、編寫一個從數(shù)組A[n]中進(jìn)行二分查找的非遞歸算法。(本題10分)intSearchBin(int*A,intn,intkey){//考試編寫代碼}數(shù)據(jù)結(jié)構(gòu)答卷學(xué)院：專業(yè)班級：學(xué)院：專業(yè)班級：姓名：學(xué)號：裝訂線內(nèi)不要答題2、考試時間120分鐘。題號一二三四五得分得分評閱人一、填空題(1×12=12分)1、_________、__________。2、，。3.________。4、。5、______，______。6、_________，_________。7、，。二、判斷(對的打∨,錯誤打×,8×2=16分)1、()2、()3、()4、()5、()6、()7、()8、()三、選擇題（7×3=21分）1、().2、（）3、()4、()5、()6、（