3.12.35門專業(yè)課05試卷數(shù)據(jù)結(jié)構(gòu)12本a

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

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

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

4、序表示；（3）給出它的轉(zhuǎn)置矩陣的三元組線性表和順序表示。24.給出圖 2 的深度優(yōu)先搜索遍歷方法遍歷圖，并用 Prim 算法畫出最小生成樹。A1BF24342CDGH21123.將圖 1林轉(zhuǎn)換成二叉樹，并中序遍歷二叉樹。EACE圖 2 無向圖BGHDF圖 1 二叉樹得分得分if (s-top=MaxSize-1)return 0;/*棧滿的情況，即棧上溢出*/s-datas-top=e;return 1;25.給定權值（2，3，2，1，5，6，7，8），構(gòu)造相應的WPL。樹，并給出帶權路徑長度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 ()得分評卷人得分得分得分得分得分return 0;q-rear=(q-rear+1)%MaxSize; q-dataq-rear=e;return 1;五、算法設計（本大題共 2 小題，每小題 10 分，共 20 分）31.假設二叉樹采用二叉鏈子結(jié)點的個數(shù)。結(jié)構(gòu)，試設計一個算法，統(tǒng)計一棵給定二叉樹的所有葉30.將一個單鏈表的線性