1、二、填空題（本大題共 10 小題，每小題 2 分，共 20 分）一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(映象)稱(chēng)為 。設(shè)長(zhǎng)度為 n 的線性表順序存貯,若在它的第 i-1 和第 i 個(gè)元間一個(gè)元素, 共需移動(dòng) 個(gè)元素(1next = HL;一個(gè)由指針p 指向的結(jié)點(diǎn)，則執(zhí)行B.p-next = HL; HL = p;D.p-next = HL-next; HL-next = p;（）C.p-next = HL;p = HL;3.依次進(jìn)入一個(gè)棧的元素序列為 a,b,c,d,不到出棧的元素序列有C.b,a,d,c（）A.a.b,c,dB.a,d,c,bD.c,d,a,b下列哪棵樹(shù)是滿二叉樹(shù) A.二叉排序樹(shù)C.有

2、 14 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)無(wú)向完全圖的鄰接矩陣是什么矩陣（）三、算法應(yīng)用題（本大題共 5 小題，每小題 6 分，共 30 分）B.深度為 5 有 31 個(gè)結(jié)點(diǎn)的二叉樹(shù)D.(Huffman)樹(shù)21.對(duì)于給定的一組關(guān)鍵字：42,20,17,13,28,14,23,15 畫(huà)出冒泡排序的各趟結(jié)果。（）A.對(duì)稱(chēng)B.上三角C.下三角D.稀疏6.有n(n0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度（）A.log2(n)+1 7.對(duì)有 3600 個(gè)A.1800B.log2(n)-1C.log2(n)-1D.log2(n)+1的索引順序表(分塊表)進(jìn)行查找,最理想的塊長(zhǎng)為（）D.log2 3600B.60C.1200查找哈希(

3、Hash)表,解決 A.除留余數(shù)法C.直接地址法下列數(shù)據(jù)中，哪個(gè)是非線性數(shù)據(jù)結(jié)構(gòu)的的方法有（）B.線性探測(cè)再散列法D.鏈地址法（）22.已知一個(gè)稀疏矩陣如下圖具有 6 行7 列的一個(gè)稀疏矩陣所示：A.棧B.隊(duì)列C.完全二叉樹(shù)D.線性表0084000000-3000000001010.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為兩大類(lèi)A.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)（）B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)得分得分評(píng)卷人得分評(píng)卷人得分評(píng)卷人題目一二三四五六七八總分核分人題分2020301020100得分0000-70000506000020000（1）寫(xiě)出它的三元組線性表；（2） 給出它的順

4、序表示；（3）給出它的轉(zhuǎn)置矩陣的三元組線性表和順序表示。24.給出圖 2 的深度優(yōu)先搜索遍歷方法遍歷圖，并用 Prim 算法畫(huà)出最小生成樹(shù)。A1BF24342CDGH21123.將圖 1林轉(zhuǎn)換成二叉樹(shù)，并中序遍歷二叉樹(shù)。EACE圖 2 無(wú)向圖BGHDF圖 1 二叉樹(shù)得分得分if (s-top=MaxSize-1)return 0;/*棧滿的情況，即棧上溢出*/s-datas-top=e;return 1;25.給定權(quán)值（2，3，2，1，5，6，7，8），構(gòu)造相應(yīng)的WPL。樹(shù)，并給出帶權(quán)路徑長(zhǎng)度27.Pop(SqStack *&s,ElemType &e)if (s-top=-1)return

5、0;e=s-datas-top;/*棧為空的情況，即棧下溢出*/return 1;28.deQueue(Sueue *&q,ElemType &e)if () return 0;q-front=(q-front+1)%MaxSize;return 1;四、程序填空（本大題共 4 小題，每空 2 分，共 10 分）29.enQueue(Sueue *&q,ElemType e)26.Push(SqStack *&s,ElemType e)if ()得分評(píng)卷人得分得分得分得分得分return 0;q-rear=(q-rear+1)%MaxSize; q-dataq-rear=e;return 1;五、算法設(shè)計(jì)（本大題共 2 小題，每小題 10 分，共 20 分）31.假設(shè)二叉樹(shù)采用二叉鏈子結(jié)點(diǎn)的個(gè)數(shù)。結(jié)構(gòu)，試設(shè)計(jì)一個(gè)算法，統(tǒng)計(jì)一棵給定二叉樹(shù)的所有葉30.將一個(gè)單鏈表的線性