說(shuō)明所有試題答案一律寫(xiě)在答題卡上

1、說(shuō)明：所有試題答案一律寫(xiě)在答題卡上，否則均以零分處理。一、單項(xiàng)選擇題(每小題2分，共40分)1.某二叉樹(shù)的先序序列和后序序列正好相同，則該二叉樹(shù)一定是( )的二叉樹(shù)。 A.空或只有一個(gè)結(jié)點(diǎn)B.高度等于其結(jié)點(diǎn)數(shù) C.任一結(jié)點(diǎn)無(wú)左孩子D.任一結(jié)點(diǎn)無(wú)右孩子2.下列排序算法中，時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(log2n)的是( ) A.堆排序B.冒泡排序 C.直接選擇排序 D.快速排序3.下列排序算法中，( )算法可能會(huì)出現(xiàn)下面情況：初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而最多。 A.堆排序 B.冒泡排序 C.快速排序D.SHELL排序4.一個(gè)棧的輸入序列為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)隊(duì)列中數(shù)組的下標(biāo)范圍是1n，其頭尾指針?lè)謩e為f和r，則其元素個(gè)數(shù)為( ) A. r-fB. r-f+1 C. (r-f) mod n+1D. (r-f+n) mod n6.若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用( )存儲(chǔ)方式最節(jié)省時(shí)間。 A.單鏈表 B.雙鏈表 C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表7.在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個(gè)數(shù)為( ) A. n-1B. 2n-1 C. n+1D. 2n+18.一棵左右子樹(shù)均不

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

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

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

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

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

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

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