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

　　A.索引存儲(chǔ)方法

　　B.順序存儲(chǔ)方法

　　C.鏈?zhǔn)酱鎯?chǔ)方法

　　D.散列存儲(chǔ)方法

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

　　A.直接前趨

　　B.直接后繼

　　C.開始結(jié)點(diǎn)

　　D.終端結(jié)點(diǎn)

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

　　A.O(1)

　　B.O(log2n)

　　C.O(n)

　　D.O(n2)

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

　　A.需判別隊(duì)是否空

　　B.需判別隊(duì)是否滿

　　C.限制在鏈表頭p進(jìn)行

　　D.限制在鏈表尾p進(jìn)行

　　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分)

　　請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。

　　16.下列程序段的時(shí)間復(fù)雜度為_______。

　　i=0;s=0;

　　while(s

　　{i++;

　　s=s+i;

　　}

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

　　18.從一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(1≤i≤n)時(shí)，需向前移動(dòng)_______個(gè)元素。

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

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

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

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

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

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

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

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

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

　　28.選擇排序的平均時(shí)間復(fù)雜度為_______。

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

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

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

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

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

　　先搜索頂點(diǎn)序列。

　　題32圖

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

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

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

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

　　typedef struct tagnode

　　{keytype key;

　　struct tagnode*next;

　　}*pointer,node;

　　typedef pointer openhash[n];

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