《數(shù)據(jù)結(jié)構(gòu)》――應(yīng)用題復(fù)習(xí)概要2022年4月1.寫出執(zhí)行下列程序段時，語句S的執(zhí)行次數(shù)。for(i=1;i<n;i++)for(j=n;j>=i;j--)S;2.假設(shè)n為2的乘冪，并且n>2，試求下列算法的時間復(fù)雜度及變量count的值（以n的函數(shù)形式表示）intTime(intn){intcount:=0;x:=2;while(x<n/2){x:=2*x;count:=count+1};return(count);}3.已知雙向鏈表、指針P、Q所指的結(jié)點和結(jié)點的結(jié)構(gòu)（數(shù)據(jù)域DATA、指針域LL及RL），分別畫出經(jīng)過下述算法后的雙向鏈表。(1)Q->RL=P->RL;P->RL=Q;Q->RL->LL=Q;Q->LL=P;(2)Q->RL=P;P->LL->RL=Q;Q->LL=P->LL;P->LL=Q;(3)P->LL->RL=P->RL;P->RL->LL=P->LL;4.設(shè)棧S的初始狀態(tài)為空，元素a,b,c,d,e和f依次通過棧S，試分析下列各組出棧次序，每組所用的最大容量。（1）a,b,c,d,e,f；（2）f,e,d,c,b,a；（3）b,d,c,f,e,a5.有字符串A+B*C-D，試寫出利用棧操作將該字符串序列改為ABC*+D-的操作步驟，這里用X和S分別表示字符的進棧和出棧操作（例如把字符ABCD改為ACBD的操作步驟為XSXXSSXS）。XSXXSXXSSSXXSS6.一棵二叉樹的結(jié)點數(shù)采用順序存儲結(jié)構(gòu)，存于下列數(shù)組T中，畫出該二叉樹。7.已知一棵樹的雙親表示如下，其中各兄弟結(jié)點依此排列，試畫出該樹及對應(yīng)的孩子兄弟表示的二叉樹。12345679101112131415ABCDEFGHIJKLMNOParent0111223448Data3566788.有一個完全二叉樹按層次順序存放在一維數(shù)組中，如下所示：請指出結(jié)點P的父結(jié)點，左子女，右子女。9.將下列二叉鏈表改為先序線索鏈表1A0202B04053C10064D0705E10106F00007G0008H000dataLTaglchildRTagrchild380010.下表給出用帶二個標(biāo)識的按先序遍歷進行順序存儲的二叉樹，對于結(jié)點k，規(guī)定：ltag(k)=0，k有左孩子；ltag(k)=1，k無左孩子；rtag(k)=0，k有右孩子；rtag(k)=1，k無右孩子。1ltag02034567891011110101dataAGEIDJHCFBrtag000101011111.已知一棵二叉樹的后序遍歷為CDBGHFIEA，中序遍歷為CBDAGFHEI。畫出此二叉樹并寫出其先序遍歷序列。12.一棵二叉樹的先序序列和中序序列分別如下，畫出該二叉樹并寫出它的后序遍歷的序列。先序序列：中序序列：DBHEAFICGABDEHCFIG后序遍歷為DHEBIFGCA13.已知一棵二叉樹的中序遍歷為DBHEAFICG，后序遍歷為DHEBIFGCA。畫出此二叉樹并寫出其先序遍歷序列。先序遍歷：ABDEHCFIG14.一棵二叉樹的先序序列和中序序列分別如下，畫出該二叉樹的中序線索二叉鏈表。先序序列：ABCDEFGHIJ15.一棵二叉樹的先序序列和中序序列分別如下，畫出該二叉樹的二叉鏈表。先序序列：ABDFCEG中序序列：BFDAEGC中序序列：CBEDAGHFJI16.一棵二叉樹的先序、中序和后序序列分別如下，試求出空格處的內(nèi)容，并畫出該二叉樹。先序：ABDFKICEHJG中序：DBKFIAHEJCG后序：DKIFBHJEGCA先序：ABDFKICEHJG中序：DBKFIAHEJCG后序：DKIFBHJEGCA17.二叉樹的先序、中序和后序序列分別如下，試求出空格處的內(nèi)容，并構(gòu)造出該二叉樹先序序列ABCDEFGH中序序列BDECAGFH后序序列EDCBGHFA18.已知一棵二叉樹的層次遍歷序列為ABCDEFGHIJ，中序遍歷序列為DBGEHJACIF，請畫出該二叉樹。19.對下面的兩棵樹，分別畫出其順序存儲結(jié)構(gòu)。ABDIJEKCFG20.一棵二叉樹的結(jié)點數(shù)據(jù)采用順序存儲結(jié)構(gòu)，存儲于下列數(shù)組T中，畫出該二叉數(shù)。9101112131415161718192021ABDEIJCF12345678Teafdgcjlhb21.用權(quán)分別為2，3，6，7，8次序的葉子結(jié)點構(gòu)造一棵哈夫曼樹（結(jié)點標(biāo)出權(quán)值），若葉子結(jié)點次序改為8，7，6，3，2，所構(gòu)造的哈夫曼樹是否相同？22.以數(shù)據(jù)集{3，4，5，8，12，18，20，30}為葉子結(jié)點的權(quán)值，（1）構(gòu)造一棵哈夫曼樹；（2）計算其帶權(quán)路徑長度。23.按照給定的權(quán)值{10，12，14，5，30，40}，構(gòu)造相應(yīng)的赫夫曼樹。24.以數(shù)據(jù)集{15，3，14，2，6，9，16，17}為葉子結(jié)點的權(quán)值，（1）構(gòu)造一棵哈夫曼樹；（2）計算其帶權(quán)路徑長度。25.有一電文中使用5各字符A,B,C,D,E，他們出現(xiàn)的頻率依次為4，7，5，2，9，試為每個字符設(shè)計哈夫曼編碼。WPL=60A:001B:10C:01D:000E:1126.給定權(quán)的集合{5，29，7，8，14，23，3，11}，構(gòu)造相應(yīng)哈夫曼樹。WPL=104+75+92=27127.畫出根據(jù)Prim算法對下列連通網(wǎng)從頂點A出發(fā)構(gòu)造其最