數(shù)據(jù)結(jié)構(gòu)與算法分析六套期末復(fù)習(xí)題(含答案)(已修改)
2025-07-01 23:18 本頁面
【正文】 試題一一、單項選擇題（每小題 2 分，共20分）（1）以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？（ ?。〢）有向圖 B）隊列 C）線索二叉樹 D）B樹（2）在一個單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點后面插入一個由q指向的結(jié)點，則執(zhí)行如下（ ?。┱Z句序列。A）p=q。 pnext=q。 B）pnext=q。 qnext=p。C）pnext=qnext。 p=q。 D）qnext=pnext。 pnext=q。（3）（ ?。┎皇顷犃械幕具\算。A）在隊列第i個元素之后插入一個元素 B）從隊頭刪除一個元素C）判斷一個隊列是否為空 D）讀取隊頭元素的值（4）字符A、B、C依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成（ ?。﹤€不同的字符串。A）14 B）5 C）6 D）8（5）由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（ ?。?。A）11 B）35 C）19 D）53以下68題基于下圖：（6）該二叉樹結(jié)點的前序遍歷的序列為（ ?。?。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é)點的中序遍歷的序列為（ ）。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）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)于圖的存儲的敘述中正確的是（ ?。）用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(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}，試寫出堆頂元素最小的初始堆。三、（本題8分）一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內(nèi)容，并畫出該二叉樹。先序序列： 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é)果。五、（本題15分）假設(shè)二叉樹中每個結(jié)點所含數(shù)據(jù)元素均為單字母，以二叉鏈表為存儲結(jié)構(gòu)，試編寫算法按如下圖所示的樹狀顯示二叉樹。【答案】==================================一、單項選擇題（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。四、（每小題2分，共8分）（1）二叉排序樹如下圖所示：（2）哈夫曼樹如下圖所示：（3）平衡二叉樹如下圖所示：（4）對于增量d=2按降序執(zhí)行一遍希爾排序的結(jié)果：28,80,27,24,23五、（本題15分）從上圖來看，二叉樹的第一層顯示在第一列，第二層顯示在第二列，第三層顯示在第三列；每行顯示一個結(jié)點，從上至下是先顯示右子樹，再顯示根，最后最左子樹，也就是以先遍歷右子樹，最后遍歷左子樹的中序遍歷次序顯示各結(jié)點。C語言版測試程序見exam1\10c，具體算當(dāng)如下：void DisplayBTWithTreeShape(BiTree T,int level=1)// 按樹狀形式顯示二叉樹，level為層次數(shù)，可設(shè)根結(jié)點的層次數(shù)為1{ if(T) { //空樹不顯式，只顯式非空樹 DisplayBTWithTreeShape(Trchild,level+1)。 //顯示右子樹 coutendl。 //顯示新行 for(int i=0。ilevel1。i++) cout 。 //確保在第level列顯示結(jié)點 coutTdata。 //顯示結(jié)點 DisplayBTWithTreeShape(Tlchild,level+1)。 //顯示左子樹 }}=========================================================================試題二一、單項選擇題（每小題 2 分，共20分）（1）設(shè)Huffman樹的葉子結(jié)點數(shù)為m，則結(jié)點總數(shù)為（?。）2m B）2m1C）2m+1 D）m+1（2）若順序存儲的循環(huán)隊列的QueueMaxSize=n，則該隊列最多可存儲（?。﹤€元素。A）n B）n1 C）n+1 D）不確定（3）下述哪一條是順序存儲方式的優(yōu)點？（ ）A）存儲密度大 B）插入和刪除運算方便 C）獲取符合某種條件的元素方便 D）查找運算速度快（4）設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每個元素占一個空間，問A[2][3](10)存放在什么位置？（腳注(10)表示用10進制表示，m3）（ ?。）658 B）648 C）633 D）653（5）下列關(guān)于二叉樹遍歷的敘述中，正確的是（ ）。A）若一個葉子是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二叉樹的前序遍歷最后一個結(jié)點B）若一個結(jié)點是某二叉樹的前序遍歷最后一個結(jié)點，則它必是該二叉樹的中序遍歷的最后一個結(jié)點C）若一個結(jié)點是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二
外語相關(guān)推薦
鄂ICP備17016276號-1