11.數(shù)據(jù)在計算機存儲器內(nèi)表示時，根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址，這種方法稱為( )

　　A.索引存儲方法

　　B.順序存儲方法

　　C.鏈式存儲方法

　　D.散列存儲方法

　　12.在單鏈表中，存儲每個結(jié)點有兩個域，一個是數(shù)據(jù)域，另一個是指針域，指針域指向該結(jié)點的( )

　　A.直接前趨

　　B.直接后繼

　　C.開始結(jié)點

　　D.終端結(jié)點

　　13.在已知頭指針的單鏈表中，要在其尾部插入一新結(jié)點，其算法所需的時間復雜度為( )

　　A.O(1)

　　B.O(log2n)

　　C.O(n)

　　D.O(n2)

　　14.在鏈隊列中執(zhí)行入隊操作，( )

　　A.需判別隊是否空

　　B.需判別隊是否滿

　　C.限制在鏈表頭p進行

　　D.限制在鏈表尾p進行

　　15.一整數(shù)序列26，59，77，31，51，11，19，42，以二路歸并排序從小到大排序，第一階段的歸并結(jié)果為( )

　　A.31，51，11，42，26，77，59，19

　　B.26，59，31，77，11，51，19，42

　　C.11，19，26，31，42，59，51，77

　　D.26，11，19，31，51，59，77，42

　　二、填空題(本大題共13小題，每小題2分，共26分)

　　請在每小題的空格中填上正確答案。錯填、不填均無分。

　　16.下列程序段的時間復雜度為_______。

　　i=0;s=0;

　　while(s

　　{i++;

　　s=s+i;

　　}

　　17.數(shù)據(jù)的存儲結(jié)構(gòu)被分為順序存儲結(jié)構(gòu)、_______、散列存儲結(jié)構(gòu)和索引存儲結(jié)構(gòu)4種。

　　18.從一個長度為n的順序表中刪除第i個元素(1≤i≤n)時，需向前移動_______個元素。

　　19.在單鏈表中，插入一個新結(jié)點需修改_______個指針。

　　20.在隊列結(jié)構(gòu)中，允許插入的一端稱為_______。

　　21.稀疏矩陣采用的壓縮存儲方法是_______。

　　22.向一個棧頂指針為top的鏈棧中插入一個新結(jié)點*p時，應執(zhí)行p->next=top和_______操作。

　　23.有m個葉結(jié)點的哈夫曼樹所具有的結(jié)點數(shù)為_______。

　　24.在一棵具有n個結(jié)點的完全二叉樹中，從樹根起，自上而下、自左至右地給所有結(jié)點編號。設根結(jié)點編號為1。若編號為i的結(jié)點有右孩子，那么其右孩子的編號為_______。

　　25.在一棵樹中，_______結(jié)點沒有前驅(qū)結(jié)點。

　　26.一個具有n個頂點的有向完全圖的弧數(shù)是_______。

　　27.n個頂點的無向圖G用鄰接矩陣A[n][n]存儲，其中第i列的所有元素之和等于頂點Vi的_______。

　　28.選擇排序的平均時間復雜度為_______。

　　三、應用題(本大題共5小題，每小題6分，共30分)

　　29.在棧的輸入端元素的輸入順序為1，2，3，4，5，6，進棧過程中可以退棧，則退棧時能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，寫出進棧、退棧過程，若不能，簡述理由。(用push(x)表示x進棧，pop(x)表示x退棧)

　　30.已知一棵二叉樹的中根遍歷序列為CBEDFAGH，后根遍歷序列為CEFDBHGA，畫出該二叉樹。

　　31.給定表(15，11，8，20，14，13)，試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r為空的二叉排序樹，畫出插入完成后的二叉排序樹，并判斷該二叉排序樹是否為平衡二叉排序樹，若為非平衡二叉排序樹，將它調(diào)整為平衡二叉排序樹。

　　32.如題32圖所示無向圖，(1)寫出其鄰接矩陣;(2)寫出三種以頂點A為起點的深度優(yōu)

　　先搜索頂點序列。

　　題32圖

　　33.用冒泡排序法對數(shù)據(jù)序列(49，38，65，97，76，134，27，49)進行排序，寫出排序過程。并說明冒泡排序是否為穩(wěn)定排序。

　　四、算法設計題(本大題共2小題，每小題7分，共14分)

　　34.編寫計算二叉樹中葉子結(jié)點數(shù)目的算法。

　　35.開散列表的類型定義如下：

　　typedef struct tagnode

　　{keytype key;

　　struct tagnode*next;

　　}*pointer,node;

　　typedef pointer openhash[n];

　　試寫出開散列表上的查找算法。