數(shù)據(jù)結(jié)構(gòu)與算法分析六套期末復(fù)習(xí)題(含答案)-展示頁
2025-06-28 23:18本頁面
【正文】 vel列顯示結(jié)點 coutTdata。ilevel1。 //顯示右子樹 coutendl。四、（每小題2分，共8分）（1）二叉排序樹如下圖所示：（2）哈夫曼樹如下圖所示：（3）平衡二叉樹如下圖所示：（4）對于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果：28,80,27,24,23五、（本題15分）從上圖來看，二叉樹的第一層顯示在第一列，第二層顯示在第二列，第三層顯示在第三列；每行顯示一個結(jié)點，從上至下是先顯示右子樹，再顯示根，最后最左子樹，也就是以先遍歷右子樹，最后遍歷左子樹的中序遍歷次序顯示各結(jié)點。五、（本題15分）假設(shè)二叉樹中每個結(jié)點所含數(shù)據(jù)元素均為單字母，以二叉鏈表為存儲結(jié)構(gòu)，試編寫算法按如下圖所示的樹狀顯示二叉樹。試求出空格處的內(nèi)容，并畫出該二叉樹。A）用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)B）用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數(shù)和結(jié)點個數(shù)都有關(guān)C）用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結(jié)點個數(shù)和邊數(shù)都有關(guān)D）用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)（10）設(shè)有關(guān)鍵碼序列(q,g,m,z,a,n,p,x,h)，下面哪一個序列是從上述序列出發(fā)建堆的結(jié)果?（ ?。〢）a,g,h,m,n,p,q,x,z B）a,g,m,h,q,n,p,x,z C）g,m,q,a,n,p,x,h,z D）h,g,m,p,a,n,q,x,z二、（本題8分）對于序列{8,18,6,16,29,28}，試寫出堆頂元素最小的初始堆。A）A、B、C、D、E、G、F B）E、A、G、C、F、B、DC）E、A、C、B、D、G、F D）B、D、C、A、F、G、E （8）該二叉樹的按層遍歷的序列為（ ）。A）11 B）35 C）19 D）53以下68題基于下圖：（6）該二叉樹結(jié)點的前序遍歷的序列為（ ?。）在隊列第i個元素之后插入一個元素 B）從隊頭刪除一個元素C）判斷一個隊列是否為空 D）讀取隊頭元素的值（4）字符A、B、C依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成（ ?。﹤€不同的字符串。 pnext=q。 p=q。 qnext=p。 pnext=q。 試題一一、單項選擇題（每小題 2 分，共20分）（1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？（ ）A）有向圖 B）隊列 C）線索二叉樹 D）B樹（2）在一個單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點后面插入一個由q指向的結(jié)點，則執(zhí)行如下（ ?。┱Z句序列。A）p=q。 B）pnext=q。C）pnext=qnext。 D）qnext=pnext。（3）（ ?。┎皇顷犃械幕具\算。A）14 B）5 C）6 D）8（5）由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ?。?。A）E、G、F、A、C、D、B B）E、A、G、C、F、B、DC）E、A、C、B、D、G、F D）E、G、A、C、D、F、B（7）該二叉樹結(jié)點的中序遍歷的序列為（ ?。）E、G、F、A、C、D、B B）E、A、C、B、D、G、FC）E、A、G、C、F、B、D D）E、G、A、C、D、F、B（9）下面關(guān)于圖的存儲的敘述中正確的是（ ）。三、（本題8分）一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。先序序列： B F ICEH G中序序列： D KFIA EJC 后序序列： K FBHJ G A四、（每小題2分，共8分）設(shè)有序列：w={23,24,27,80,28}，試給出：（1）二叉排序樹；（2）哈夫曼樹；（3）平衡二叉樹；（4）對于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果?！敬鸢浮?=================================一、單項選擇題（1）B （2）D （3）A （4）B （5）B（6）C （7）A （8）C （9）B （10）B二、（本題8分）所構(gòu)造的堆如下圖所示：三、（本題8分）在先序序列空格中依次填A(yù)DKJ，中序中依次填BHG，后序中依次填DIEC。C語言版測試程序見exam1\10c，具體算當(dāng)如下：void DisplayBTWithTreeShape(BiTree T,int level=1)// 按樹狀形式顯示二叉樹，level為層次數(shù)，可設(shè)根結(jié)點的層次數(shù)為1{ if(T) { //空樹不顯式，只顯式非空樹 DisplayBTWithTreeShape(Trchild,level+1)。 //顯示新行 for(int i=0。i++) cout 。 //顯示結(jié)點 DisplayBTWithTreeShape(Tlchild,level+1)。A）2m B）2m1C）2m+1 D）m+1（2）若順序存儲的循環(huán)隊列的QueueMaxSize=n，則該隊列最多可存儲（?。﹤€元素。A）658 B）648 C）633 D）653（5）下列關(guān)于二叉樹遍歷的敘述中，正確的是（ ）。A）2k1 B）2k+1 C）K1 D）k1（7）對線性表進行二分法查找，其前提條件是（ ?。?。A）O(1og2n) B）O(n) C）O(1) D）O(n2)（9）對于線性表（7，34，77，25，64，49，20，14）進行散列存儲時，若選用H（K）=K%7作為散列函數(shù)，則散列地址為0的元素有（ ?。﹤€。A）數(shù)組是不同類型值的集合 B）遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C）樹是一種線性結(jié)構(gòu)D）用一維數(shù)組存儲一棵完全二叉樹是有效的存儲方法二、（本題8分）假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，分別寫出對它進行先序、中序、后序、按層遍歷的結(jié)果。五、（本題8分）設(shè)有一個輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹?！敬鸢浮?=================================一、單項選擇題（每小題 2 分，共20分）（1）B （2）B （3）A （4）D （5）A （6）A （7）C
外語相關(guān)推薦
鄂ICP備17016276號-1