數(shù)據(jù)結(jié)構(gòu)習題課課件

1、數(shù)據(jù)結(jié)構(gòu)習題課作者：王麗萍1第2章 線性表在線性表中最常用的操作是存取第i個元素及其前驅(qū)的值，采用順序表存儲方式最省時間。某線性表中最常用的操作是存取序號為i的元素和在最后進行插入和刪除運算，則采用順序表存儲方式時間性能最好。在鏈表中最常用的操作是刪除表中最后一個結(jié)點和在最后一個結(jié)點之后插入元素，則采用_D_最節(jié)省時間。 A.帶頭指針的單向循環(huán)鏈表 B.雙向鏈表 C.帶尾指針的單向循環(huán)鏈表 D.帶頭指針的雙向循環(huán)鏈表 2在線性表中最常用的操作是存取第i個元素及其前驅(qū)的值，可采用_ABCD_存儲方式。 A.順序表 B.單向鏈表 C.雙向循環(huán)鏈表 D.單向循環(huán)鏈表假設(shè)兩個按元素值遞增有序排列的線性

2、表A和B，均以單鏈表作為存儲結(jié)構(gòu)，請編寫算法，將A表和B表歸并成一個按元素值遞減有序排列的線性表C，并要求利用原表的（即A表和B表的）結(jié)點空間存儲表C。 3void merge(Linklist A,Linklist B,Linklist C) Linklist pa,pb,p;pa = A-next;pb = B-next;C = A;C-next = NULL;free(B); 4while(pa & pb)if(pa-data data)p = pa;pa = pa-next;p-next = C-next;C-next = p; 5elsep = pb;pb = pb-next;p-n

3、ext = C-next;C-next = p; 6if(!pa)while(pb)p = pb;pb = pb-next;p-next = C-next;C-next = p; 7else if(!pb)while(pa)p = pa;pa = pa-next;p-next = C-next;C-next = p; 8建立一個帶頭結(jié)點的線性鏈表，用以存放輸入的二進制數(shù)，鏈表中每個結(jié)點的data域存放一個二進制位，并在此鏈表上實現(xiàn)對二進制數(shù)加1的運算。(假設(shè)鏈表L為從低位到高位） void AddOne(Linklist L)Linklist p = L-next;while(p-next &

4、 p-data = 1)p-data = 0;p = p-next; 9if(p-next)p-data = 1;elseif(p-data = 0)p-data = 1;elsep-data = 0;Linklist q = (Linklist)malloc(sizeof(Node); 10q-data = 1;q-next = NULL;p-next = q;return; 11第三章 棧和隊列設(shè)隊列中有A、B、C、D、E這5個元素，其中隊首元素為A。如果對這個隊列重復(fù)執(zhí)行下列4操作： （1）輸出隊首元素； （2）把隊首元素值插入到隊尾； （3）刪除隊首元素； （4）再次刪除隊首元素。直到

5、隊列成為空隊列為止，是否可能得到輸出隊列：A、C、E、C、C 12試利用棧編寫計算下列遞歸函數(shù)的非遞歸形式的算法。 0, m = 0,n 0 g(m,n)= g(m - 1,2n)+n, m 0,n 0 (程序）13第6章 樹和二叉樹畫出與下列已知序列對應(yīng)的樹T： 樹的先根次序訪問序列為CFKDAIEBCHJ 樹的后根次序訪問序列為DIAEKFCJHBG（P177)樹與二叉樹的轉(zhuǎn)換關(guān)系：樹中的任意一個結(jié)點都對應(yīng)于二叉樹中的一個結(jié)點。樹中某結(jié)點的第一個孩子在二叉樹中是相應(yīng)結(jié)點的左孩子，樹中某結(jié)點的右兄弟結(jié)點在二叉樹中是相應(yīng)結(jié)點的右孩子。樹的后根遍歷序列 = 二叉樹的中序遍歷序列14根據(jù)先序序列和

6、中序序列確定二叉樹將二叉樹轉(zhuǎn)化為樹： 二叉樹中每個結(jié)點都對應(yīng)于樹中每個結(jié)點； 二叉樹中某結(jié)點的左孩子為樹中該結(jié)點的第一個孩子； 二叉樹中某節(jié)點的右孩子為樹中該結(jié)點的右兄弟。 15假設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為： 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10構(gòu)造哈夫曼樹的算法步驟：（P184） 找最小樹：在森林F中選擇兩棵結(jié)點權(quán)值最小的二叉樹，作為一棵新二叉樹的左右子樹，標記新二叉樹的根結(jié)點權(quán)值為其左、右子樹的根結(jié)點權(quán)值之和； 刪除與加入：從F中刪除被選中的那兩棵二叉樹，同時把新構(gòu)成的二叉樹加入到森林F中。 16(1)0.07,

7、0.19,0.02,0.06,0.32,0.03,0.21,0.10 0.020.030.0517（2）0.07,0.19,0.06,0.32,0.21,0.10，0.05 0.020.030.050.060.1118（3）0.07,0.19,0.32,0.21,0.10，0.11 0.020.030.050.060.110.070.170.1019（4）0.19,0.32,0.21,0.11，0.17 0.020.030.050.060.110.070.170.100.2820（5）0.19,0.32,0.21,0.28 0.020.030.050.060.110.070.170.100.2

8、80.190.400.2121（6）0.32，0.28，0.40 0.020.030.050.060.110.070.170.100.280.190.400.210.320.6022（7）0.40，0.60 0.020.030.050.060.110.070.170.100.280.190.400.210.320.600.100101010101010123已知二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結(jié)點的數(shù)目。 int leaf(Bitree T) if(!T)return 0;if(!T-Lchild & !T-Rchild)return 1;return(leaf(T-Lc

9、hild)+leaf(T-Rchild); 24第7章 圖已知如圖（P245,圖7.30)所示的AOE-網(wǎng)，試求： 25（1）每個事件的最早發(fā)生時間和最晚發(fā)生時間；事件vi的最早發(fā)生時間ve(i)：從源點到頂點vi的最長路徑的長度。 ve(0) = 0; ve(i) = Maxve(k)+dut() 事件vi的最晚發(fā)生事件vl(i):在保證匯點按其最早發(fā)生時間發(fā)生這一前提下，求事件vi的最晚發(fā)生時間。 vl(n-1)=ve(n-1) vl(i)=Minvl(k)-dut() 26（1）每個事件的最早發(fā)生時間； ve(0)=0 ve(1)=maxve(0)+dut()=5 ve(2)=maxve

10、(0)+dut()=6 ve(3)=maxve(1)+dut(),ve(2)+dut()=12 ve(4)=maxve(3)+dut(),ve(2)+dut()=15 27（1）每個事件的最晚發(fā)生時間； vl(9)=ve(9)=23 vl(8)=min(vl(9)-dut()=21 vl(7)=min(vl(8)-dut()=19 vl(6)=min(vl(9)-dut()=19 vl(5)=min(vl(8)-dut()=16 vl(4)=min(vl(5)-dut(),vl(7)-dut()=15 28（2）每個活動的最早開始時間和最晚開始時間；活動ai的最早開始時間e(i):如果活動ai

11、對應(yīng)的弧為,則e(i)等于從源點到頂點j的最長路徑的長度，即：e(i)=ve(j);活動ai的最晚開始時間l(i):如果活動ai對應(yīng)的弧為,其持續(xù)時間為dut(),則有：l(i)=vl(k)-dut()。 29每個活動的最早開始時間 e()=ve(0)=0 e()=ve(0)=0 e()=ve(1)=5 e()=ve(2)=6 e()=ve(2)=6 e()=ve(3)=12 30每個活動的最晚開始時間 l()=vl(1)-dut()=4 l()=vl(2)-dut()=0 l()=vl(3)-dut()=9 l()=vl(3)-dut()=6 31給出關(guān)鍵路徑。關(guān)鍵路徑：從源點到匯點的最長路

12、徑的長度為完成整個工程任務(wù)所需的時間，該路徑叫做關(guān)鍵路徑。關(guān)鍵路徑上的活動叫做關(guān)鍵活動。關(guān)鍵活動：e(i)=l(i)的活動ai即為關(guān)鍵活動。 32已知如圖（P245,圖7.31）所示的有向網(wǎng)，試利用Dijkstra算法求頂點1到其余頂點的最短路徑，并給出算法執(zhí)行過程中各步的狀態(tài)。 33Dijkstra算法 對于圖G=（V，E），將圖中的頂點分成兩組： 第一組S：已求出的最短路徑的終點集合 第二組V-S：尚未求出最短路徑的頂點集合 算法將按最短路徑長度的遞增順序逐個將第二組的頂點加入到第一組中，直到所有頂點都被加入到第一組頂點集S為止。 34 終點從v1到各終點的disti值，pathi值的變化

13、過程i = 2i = 3i = 4i = 5i = 6v220(v1,v2)19(v1,v3,v2)v315(v1,v3)v429(v1,v3,v2,v4)29(v1,v3,v2,v4)v525(v1,v3,v5)25(v1,v3,v5)v645(v1,v3,v5,v6)44(v1,v3,v2,v4,v6)vkV3V2V5V4V6Sv1,v3v1,v3,v2v1,v3,v2,v5v1,v3,v2,v5,v4v1,v3,v2,v5,v4,v635（1）用Prime算法從頂點9開始，手工構(gòu)造最小生成樹。 36Prime算法： 假設(shè)N=(V,E)是連通網(wǎng)，TE為最小生成樹中邊的集合。 初始U= ,( V),TE=; 在所有uU,vV-U的邊中選一條代價最小的邊（ ， ）并入集合TE，同時將 并入U； 重復(fù)（2），直到U=V為止。 此時，TE中必含有n-1條邊，則T=(V,TE)為N的最小生成樹。 37(1) (2) (3) (4)38(5) (6) 39(7) (8) 40(9) 41（2）用Kr