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

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

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

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

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

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、設待排序文件的關鍵碼為（512,275,908,677,503,765,612,897,154,170）以第一元素為分界元素進行快速排序（按關鍵碼值遞增順序），請給出一趟掃描后的結果。（10分）五、算法設計題(本大題共2小題，每題10分，共20分)1、假設二叉樹T采用如下定義的存儲結構：(本題10分)

typedefstructNode{

DataTypedata;

structNode*lchild,*rchild;

}*BiTree;其中，結點的lchild域和rchild域已分別填有指向其左、右孩子結點的指針，編寫一個遞歸算法，計算一棵二叉樹中，度數為2的節點個數。IntCountNode(BiTreeT){//考試編寫代碼}2、編寫一個從數組A[n]中進行二分查找的非遞歸算法。(本題10分)intSearchBin(int*A,intn,intkey){//考試編寫代碼}數據結構答卷學院：專業班級：學院：專業班級：姓名：學號：裝訂線內不要答題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、（