說明所有試題答案一律寫在答題卡上

1、說明：所有試題答案一律寫在答題卡上，否則均以零分處理。一、單項選擇題(每小題2分，共40分)1.某二叉樹的先序序列和后序序列正好相同，則該二叉樹一定是( )的二叉樹。 A.空或只有一個結(jié)點B.高度等于其結(jié)點數(shù) C.任一結(jié)點無左孩子D.任一結(jié)點無右孩子2.下列排序算法中，時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(log2n)的是( ) A.堆排序B.冒泡排序 C.直接選擇排序 D.快速排序3.下列排序算法中，( )算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時，花費的時間反而最多。 A.堆排序 B.冒泡排序 C.快速排序D.SHELL排序4.一個棧的輸入序列為1 2 3 4 5，則下列序列中不可能是棧的輸

2、出序列的是( ) A. 2 3 4 1 5B. 5 4 1 3 2 C. 2 3 1 4 5D. 1 5 4 3 25.設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范圍是1n，其頭尾指針分別為f和r，則其元素個數(shù)為( ) A. r-fB. r-f+1 C. (r-f) mod n+1D. (r-f+n) mod n6.若某鏈表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采用( )存儲方式最節(jié)省時間。 A.單鏈表 B.雙鏈表 C.帶頭結(jié)點的雙循環(huán)鏈表D.單循環(huán)鏈表7.在有n個結(jié)點的二叉鏈表中，值為非空的鏈域的個數(shù)為( ) A. n-1B. 2n-1 C. n+1D. 2n+18.一棵左右子樹均不

3、空的二叉樹在先序線索化后，其空指針域數(shù)為( ) A. 0 B. 1 C. 2D.不確定9.數(shù)組A56的每個元素占5個單元，將其按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A45的地址為( ) A. 1140B. 1145 C. 1120D. 112510.有一個長度為12的有序表，按二分查找法對該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的ASL為（ ） A35/12 B37/12 C39/12 D43/1211.對有18個元素的有序表作二分查找，則查找A3的比較序列的下標(biāo)依次為( ) A. 1，2，3B. 9，5，2，3 C. 9，5，3D. 9，4，2，312.快速

4、排序算法在最好情況下的時間復(fù)雜度為( ) A. O(n)B. O(nlog2n) C. O(n2)D. O(log2n)13.下列排序算法中，某一趟結(jié)束后未必能選出一個元素放在其最終位置上的是( )A.堆排序B.冒泡排序 C.快速排序D.直接插入排序14.二叉樹在線索化后，仍不能有效求解的問題是( ) A.先序線索二叉樹中求先序后繼 B.中序線索二叉樹中求中序后繼 C.中序線索二叉樹中求中序前趨 D.后序線索二叉樹中求后序后繼15.DFS算法的時間復(fù)雜度為( ) A. O(n) B. O(n3) C. O(n2)D. O(n+e)16.隊列操作的原則是( ) A.先進(jìn)先出B.后進(jìn)先出 C.只能

5、進(jìn)行插入D.只能進(jìn)行刪除17.有64個結(jié)點的完全二叉樹的深度為( )(根的層次為1)。 A. 8 B. 7 C. 6D. 518.設(shè)哈希表長m=14，哈希函數(shù)H（key）=key % 11，表中已有4 個結(jié)點：addr (15) =4 , addr (38) =5 ,addr (61)=6 ,addr (84)=7如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點的地址是（ ）A8 B3 C5 D919.數(shù)據(jù)表A中有10000個元素，如果僅要求求出其中最大的10個元素，則采用( )排序算法最節(jié)省時間。 A.堆排序B.希爾排序 C.快速排序 D.直接選擇排序20.在10階B樹中根結(jié)點所包含的關(guān)鍵碼個

6、數(shù)最少為（ ）。 A. 0B. 1C. 3D. 4二、判斷題(正確的打“”，錯的打“×”。每小題1分，共10分)1.給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。( )2.由于希爾排序的最后一趟與直接插入排序過程相同，因此前者一定比后者花費的時間多。( )3.在對鏈隊列作出隊操作時，不會改變front指針的值。( )4.若一個棧的輸入序列為123n，其輸出序列的第一個元素為n，則其輸出序列的每個元素ai一定滿足ai=n-i+1(i=1,2.,n)。( )5.二叉樹中的葉子結(jié)點就是二叉樹中沒有左右子樹的結(jié)點。( )6.一棵樹中的葉子結(jié)點數(shù)一定等于與其對應(yīng)的二叉樹中的葉子結(jié)

7、點數(shù)。( )7.有向圖用鄰接矩陣表示后，頂點i的人度等于鄰接矩陣中第i列的元素個數(shù)。( )8.有向圖的鄰接表和逆鄰接表中的結(jié)點數(shù)一定相同。( )9.刪除二叉排序樹中一個結(jié)點，再重新插入上去，一定能得到原來的二叉排序樹。( )10.圖G的拓?fù)湫蛄形ㄒ唬瑒t其弧數(shù)必為n-1(其中n為G的頂點數(shù))。( )三、填空題(每空2分，共20分)1.在有n個葉子結(jié)點的哈夫曼樹中，總結(jié)點數(shù)是_。2.一棵樹T采用二叉鏈表存儲，如果樹T中某結(jié)點為葉子結(jié)點，則在二叉鏈表BT中所對應(yīng)的結(jié)點一定_。3.已知數(shù)組A1010為對稱矩陣，其中每個元素占5個單元?，F(xiàn)將其下三角部分按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元

8、中，則元素：A56對應(yīng)的地址是_。4.在有n個結(jié)點的無向圖中，其邊數(shù)最多為_。5.取出廣義表A=(x,(a,b,c,d)中原子x的函數(shù)是_。6.對矩陣采用壓縮存儲是為了_。7.帶頭結(jié)點的雙循環(huán)鏈表L為空表的條件是_。8.在雙鏈表中，在指針P所指結(jié)點前面插入一個指針S所指向的結(jié)點時的語句序列是：S->next=P;S->prior=P->prior;P->prior=S;_；9.對廣義表A=(x,(a,b),c,d)的運算head (head (tail (A)的結(jié)果是_。10.判斷線索二叉樹中某結(jié)點指針P所指結(jié)點有左孩子的條件是_。四、簡答題(每小題5分，共15分)1.

9、用Prim算法以結(jié)點1為根畫出下圖的一棵最小生成樹,按生成的順序描述邊序列,并寫出其WPL。2.將下面順序表建成一個小根堆。(要求畫出最后生成的堆,并采用順序表的形式加以描述)(70，12，20，31，1，5，44，66，61，200，30，80，150，4，28)3.已知一棵二叉樹的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，請構(gòu)造出該二叉樹，并寫出后序序列。五、綜合應(yīng)用題(共15分)1. 已知一樹的雙親表示法如下，其中各兄弟結(jié)點是依次出現(xiàn)的，畫出該樹及對應(yīng)的二叉樹。(7分)。 123456789101112131415dataABCDEFGHIJKLMNOparent-1111223344566782. 程序填空。(每空2分,共計8分)已知二叉樹中的結(jié)點類型BinTreeNode定義為: struct BinTreeNode ElemType data；BinTreeNode *left, *right；其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。下面函數(shù)的功能是從二叉樹BT中查找值為X的結(jié)點，若查找成功則返回結(jié)點地址，否則返回空。請在劃有橫線的地方填寫合適內(nèi)容。BinTreeNode* BTF(Bi