數據結構習題課課件

《數據結構》習題課作者：王麗萍1《數據結構》習題課作者：王麗萍1第2章線性表在線性表中最常用的操作是存取第i個元素及其前驅的值，采用順序表存儲方式最省時間。某線性表中最常用的操作是存取序號為i的元素和在最后進行插入和刪除運算，則采用順序表存儲方式時間性能最好。在鏈表中最常用的操作是刪除表中最后一個結點和在最后一個結點之后插入元素，則采用_D_最節(jié)省時間。

A.帶頭指針的單向循環(huán)鏈表B.雙向鏈表C.帶尾指針的單向循環(huán)鏈表D.帶頭指針的雙向循環(huán)鏈表

2第2章線性表在線性表中最常用的操作是存取第i個元素在線性表中最常用的操作是存取第i個元素及其前驅的值，可采用_ABCD_存儲方式。A.順序表B.單向鏈表C.雙向循環(huán)鏈表D.單向循環(huán)鏈表假設兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲結構，請編寫算法，將A表和B表歸并成一個按元素值遞減有序排列的線性表C，并要求利用原表的（即A表和B表的）結點空間存儲表C。

3在線性表中最常用的操作是存取第i個元素及其前驅的值，可采用_voidmerge(LinklistA,LinklistB,LinklistC){ Linklistpa,pb,p; pa=A->next; pb=B->next; C=A; C->next=NULL; free(B);

4voidmerge(LinklistA,Linklist

while(pa&&pb) { if(pa->data<=pb->data) { p=pa; pa=pa->next; p->next=C->next; C->next=p; }

5 while(pa&&pb)5

else { p=pb; pb=pb->next; p->next=C->next; C->next=p; }}

6 else6 if(!pa) { while(pb) { p=pb; pb=pb->next; p->next=C->next; C->next=p; } }

7 if(!pa)7

elseif(!pb) { while(pa) { p=pa; pa=pa->next; p->next=C->next; C->next=p; } }}

8 elseif(!pb)8建立一個帶頭結點的線性鏈表，用以存放輸入的二進制數，鏈表中每個結點的data域存放一個二進制位，并在此鏈表上實現對二進制數加1的運算。(假設鏈表L為從低位到高位）voidAddOne(LinklistL) { Linklistp=L->next; while(p->next&&p->data==1) { p->data=0; p=p->next; }

9建立一個帶頭結點的線性鏈表，用以存放輸入的二進制數，鏈表中每

if(p->next) p->data=1; else { if(p->data==0) p->data=1; else { p->data=0; Linklistq=(Linklist)malloc(sizeof(Node));

10 if(p->next)10

q->data=1; q->next=NULL; p->next=q;}}return;}

11 q->data=1;11第三章棧和隊列設隊列中有A、B、C、D、E這5個元素，其中隊首元素為A。如果對這個隊列重復執(zhí)行下列4操作：（1）輸出隊首元素；（2）把隊首元素值插入到隊尾；（3）刪除隊首元素；（4）再次刪除隊首元素。直到隊列成為空隊列為止，是否可能得到輸出隊列：A、C、E、C、C

12第三章棧和隊列設隊列中有A、B、C、D、E這5個元素，其試利用棧編寫計算下列遞歸函數的非遞歸形式的算法。0,m=0,n≥0g(m,n)=

g(m-1,2n)+n,m>0,n≥0(程序）13試利用棧編寫計算下列遞歸函數的非遞歸形式的算法。13第6章樹和二叉樹畫出與下列已知序列對應的樹T：樹的先根次序訪問序列為CFKDAIEBCHJ樹的后根次序訪問序列為DIAEKFCJHBG（P177)樹與二叉樹的轉換關系：樹中的任意一個結點都對應于二叉樹中的一個結點。樹中某結點的第一個孩子在二叉樹中是相應結點的左孩子，樹中某結點的右兄弟結點在二叉樹中是相應結點的右孩子。樹的后根遍歷序列=二叉樹的中序遍歷序列14第6章樹和二叉樹畫出與下列已知序列對應的樹T：14根據先序序列和中序序列確定二叉樹將二叉樹轉化為樹：

二叉樹中每個結點都對應于樹中每個結點；二叉樹中某結點的左孩子為樹中該結點的第一個孩子；二叉樹中某節(jié)點的右孩子為樹中該結點的右兄弟。

15根據先序序列和中序序列確定二叉樹15假設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分別為：0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10構造哈夫曼樹的算法步驟：（P184）找最小樹：在森林F中選擇兩棵結點權值最小的二叉樹，作為一棵新二叉樹的左右子樹，標記新二叉樹的根結點權值為其左、右子樹的根結點權值之和；刪除與加入：從F中刪除被選中的那兩棵二叉樹，同時把新構成的二叉樹加入到森林F中。

16假設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分(1)0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10

0.020.030.0517(1)0.07,0.19,0.02,0.06,0.32,0.（2）0.07,0.19,0.06,0.32,0.21,0.10，0.05

0.020.030.050.060.1118（2）0.07,0.19,0.06,0.32,0.21,0.（3）0.07,0.19,0.32,0.21,0.10，0.11

0.020.030.050.060.110.070.170.1019（3）0.07,0.19,0.32,0.21,0.10，0.（4）0.19,0.32,0.21,0.11，0.17

0.020.030.050.060.110.070.170.100.2820（4）0.19,0.32,0.21,0.11，0.170.0（5）0.19,0.32,0.21,0.28

0.020.030.050.060.110.070.170.100.280.190.400.2121（5）0.19,0.32,0.21,0.280.020.03（6）0.32，0.28，0.40

0.020.030.050.060.110.070.170.100.280.190.400.210.320.6022（6）0.32，0.28，0.400.020.030.050（7）0.40，0.60

0.020.030.050.060.110.070.170.100.280.190.400.210.320.600.100101010101010123（7）0.40，0.600.020.030.050.060.已知二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結點的數目。intleaf(BitreeT){ if(!T) return0; if(!T->Lchild&&!T->Rchild) return1; return(leaf(T->Lchild)+leaf(T->Rchild));}

24已知二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結第7章圖已知如圖（P245,圖7.30)所示的AOE-網，試求：

25第7章圖已知如圖（P245,圖7.30)所示的AOE-（1）每個事件的最早發(fā)生時間和最晚發(fā)生時間；事件vi的最早發(fā)生時間ve(i)：從源點到頂點vi的最長路徑的長度。ve(0)=0;ve(i)=Max{ve(k)+dut(<k,i>)}事件vi的最晚發(fā)生事件vl(i):在保證匯點按其最早發(fā)生時間發(fā)生這一前提下，求事件vi的最晚發(fā)生時間。vl(n-1)=ve(n-1)vl(i)=Min{vl(k)-dut(<i,k>)}

26（1）每個事件的最早發(fā)生時間和最晚發(fā)生時間；26（1）每個事件的最早發(fā)生時間；ve(0)=0

ve(1)=max{ve(0)+dut(<0,1>)}=5ve(2)=max{ve(0)+dut(<0,2>)}=6ve(3)=max{ve(1)+dut(<1,3>),ve(2)+dut(<2,3>)}=12ve(4)=max{ve(3)+dut(<3,4>),ve(2)+dut(<2,4>)}=15

……27（1）每個事件的最早發(fā)生時間；27（1）每個事件的最晚發(fā)生時間；vl(9)=ve(9)=23vl(8)=min(vl(9)-dut(<8,9>)}=21vl(7)=min(vl(8)-dut(<7,8>)}=19vl(6)=min(vl(9)-dut(<6,9>)}=19vl(5)=min(vl(8)-dut(<5,8>)}=16vl(4)=min(vl(5)-dut(<4,5>),vl(7)-dut(<4,7>)}=15

……

28（1）每個事件的最晚發(fā)生時間；28（2）每個活動的最早開始時間和最晚開始時間；活動ai的最早開始時間e(i):如果活動ai對應的弧為<j,k>,則e(i)等于從源點到頂點j的最長路徑的長度，即：e(i)=ve(j);活動ai的最晚開始時間l(i):如果活動ai對應的弧為<j,k>,其持續(xù)時間為dut(<j,k>),則有：l(i)=vl(k)-dut(<j,k>)。

29（2）每個活動的最早開始時間和最晚開始時間；29每個活動的最早開始時間

e(<0,1>)=ve(0)=0e(<0,2>)=ve(0)=0e(<1,3>)=ve(1)=5e(<2,3>)=ve(2)=6e(<2,4>)=ve(2)=6e(<3,4>)=ve(3)=12

……

30每個活動的最早開始時間30每個活動的最晚開始時間

l(<0,1>)=vl(1)-dut(<0,1>)=4l(<0,2>)=vl(2)-dut(<0,2>)=0l(<1,3>)=vl(3)-dut(<1,3>)=9l(<2,3>)=vl(3)-dut(<2,3>)=6

……

31每個活動的最晚開始時間31給出關鍵路徑。關鍵路徑：從源點到匯點的最長路徑的長度為完成整個工程任務所需的時間，該路徑叫做關鍵路徑。關鍵路徑上的活動叫做關鍵活動。關鍵活動：e(i)=l(i)的活動ai即為關鍵活動。

32給出關鍵路徑。32已知如圖（P245,圖7.31）所示的有向網，試利用Dijkstra算法求頂點1到其余頂點的最短路徑，并給出算法執(zhí)行過程中各步的狀態(tài)。

33已知如圖（P245,圖7.31）所示的有向網，試利用DijkDijkstra算法

對于圖G=（V，E），將圖中的頂點分成兩組：

第一組S：已求出的最短路徑的終點集合第二組V-S：尚未求出最短路徑的頂點集合算法將按最短路徑長度的遞增順序逐個將第二組的頂點加入到第一組中，直到所有頂點都被加入到第一組頂點集S為止。

34Dijkstra算法34

3535（1）用Prime算法從頂點9開始，手工構造最小生成樹。

36（1）用Prime算法從頂點9開始，手工構造最小生成樹。36Prime算法：假設N=(V,{E})是連通網，TE為最小生成樹中邊的集合。初始U={,(V),TE=ф;

在所有u∈U,v∈V-U的邊中選一條代價最小的邊（，）并入集合TE，同時將并入U；

重復（2），直到U=V為止。此時，TE中必含有n-1條邊，則T=(V,{TE})為N的最小生成樹。

37Prime算法：37(1)(2)

(3)(4)38(1)(2)(5)

(6)39(5)(7)

(8)40(7)(9)

41(9)（2）用Kruscal算法手工構造最小生成樹。假設N=(V,{E})是連通網，將N中的邊按權值從小到大的順序排列。

將n個頂點看成n個集合；按權值由小到大的順序選擇邊，所選邊應滿足兩個頂點不在同一個頂點集合內，將該邊放到生成樹邊的集合中。同時將該邊的兩個頂點所在的頂點集合合并；重復直到所有的頂點都在同一個頂點集合內。

42（2）用Kruscal算法手工構造最小生成樹。42(1)(2)

4343(3)

(4)44(3)(5)

(6)45(5)(7)

(8)46(7)(9)

47(9)配色方案修改：

48配色方案修改：484949《數據結構》習題課作者：王麗萍50《數據結構》習題課作者：王麗萍1第2章線性表在線性表中最常用的操作是存取第i個元素及其前驅的值，采用順序表存儲方式最省時間。某線性表中最常用的操作是存取序號為i的元素和在最后進行插入和刪除運算，則采用順序表存儲方式時間性能最好。在鏈表中最常用的操作是刪除表中最后一個結點和在最后一個結點之后插入元素，則采用_D_最節(jié)省時間。

A.帶頭指針的單向循環(huán)鏈表B.雙向鏈表C.帶尾指針的單向循環(huán)鏈表D.帶頭指針的雙向循環(huán)鏈表

51第2章線性表在線性表中最常用的操作是存取第i個元素在線性表中最常用的操作是存取第i個元素及其前驅的值，可采用_ABCD_存儲方式。A.順序表B.單向鏈表C.雙向循環(huán)鏈表D.單向循環(huán)鏈表假設兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲結構，請編寫算法，將A表和B表歸并成一個按元素值遞減有序排列的線性表C，并要求利用原表的（即A表和B表的）結點空間存儲表C。

52在線性表中最常用的操作是存取第i個元素及其前驅的值，可采用_voidmerge(LinklistA,LinklistB,LinklistC){ Linklistpa,pb,p; pa=A->next; pb=B->next; C=A; C->next=NULL; free(B);

53voidmerge(LinklistA,Linklist

while(pa&&pb) { if(pa->data<=pb->data) { p=pa; pa=pa->next; p->next=C->next; C->next=p; }

54 while(pa&&pb)5

else { p=pb; pb=pb->next; p->next=C->next; C->next=p; }}

55 else6 if(!pa) { while(pb) { p=pb; pb=pb->next; p->next=C->next; C->next=p; } }

56 if(!pa)7

elseif(!pb) { while(pa) { p=pa; pa=pa->next; p->next=C->next; C->next=p; } }}

57 elseif(!pb)8建立一個帶頭結點的線性鏈表，用以存放輸入的二進制數，鏈表中每個結點的data域存放一個二進制位，并在此鏈表上實現對二進制數加1的運算。(假設鏈表L為從低位到高位）voidAddOne(LinklistL) { Linklistp=L->next; while(p->next&&p->data==1) { p->data=0; p=p->next; }

58建立一個帶頭結點的線性鏈表，用以存放輸入的二進制數，鏈表中每

if(p->next) p->data=1; else { if(p->data==0) p->data=1; else { p->data=0; Linklistq=(Linklist)malloc(sizeof(Node));

59 if(p->next)10

q->data=1; q->next=NULL; p->next=q;}}return;}

60 q->data=1;11第三章棧和隊列設隊列中有A、B、C、D、E這5個元素，其中隊首元素為A。如果對這個隊列重復執(zhí)行下列4操作：（1）輸出隊首元素；（2）把隊首元素值插入到隊尾；（3）刪除隊首元素；（4）再次刪除隊首元素。直到隊列成為空隊列為止，是否可能得到輸出隊列：A、C、E、C、C

61第三章棧和隊列設隊列中有A、B、C、D、E這5個元素，其試利用棧編寫計算下列遞歸函數的非遞歸形式的算法。0,m=0,n≥0g(m,n)=

g(m-1,2n)+n,m>0,n≥0(程序）62試利用棧編寫計算下列遞歸函數的非遞歸形式的算法。13第6章樹和二叉樹畫出與下列已知序列對應的樹T：樹的先根次序訪問序列為CFKDAIEBCHJ樹的后根次序訪問序列為DIAEKFCJHBG（P177)樹與二叉樹的轉換關系：樹中的任意一個結點都對應于二叉樹中的一個結點。樹中某結點的第一個孩子在二叉樹中是相應結點的左孩子，樹中某結點的右兄弟結點在二叉樹中是相應結點的右孩子。樹的后根遍歷序列=二叉樹的中序遍歷序列63第6章樹和二叉樹畫出與下列已知序列對應的樹T：14根據先序序列和中序序列確定二叉樹將二叉樹轉化為樹：

二叉樹中每個結點都對應于樹中每個結點；二叉樹中某結點的左孩子為樹中該結點的第一個孩子；二叉樹中某節(jié)點的右孩子為樹中該結點的右兄弟。

64根據先序序列和中序序列確定二叉樹15假設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分別為：0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10構造哈夫曼樹的算法步驟：（P184）找最小樹：在森林F中選擇兩棵結點權值最小的二叉樹，作為一棵新二叉樹的左右子樹，標記新二叉樹的根結點權值為其左、右子樹的根結點權值之和；刪除與加入：從F中刪除被選中的那兩棵二叉樹，同時把新構成的二叉樹加入到森林F中。

65假設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分(1)0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10

0.020.030.0566(1)0.07,0.19,0.02,0.06,0.32,0.（2）0.07,0.19,0.06,0.32,0.21,0.10，0.05

0.020.030.050.060.1167（2）0.07,0.19,0.06,0.32,0.21,0.（3）0.07,0.19,0.32,0.21,0.10，0.11

0.020.030.050.060.110.070.170.1068（3）0.07,0.19,0.32,0.21,0.10，0.（4）0.19,0.32,0.21,0.11，0.17

0.020.030.050.060.110.070.170.100.2869（4）0.19,0.32,0.21,0.11，0.170.0（5）0.19,0.32,0.21,0.28

0.020.030.050.060.110.070.170.100.280.190.400.2170（5）0.19,0.32,0.21,0.280.020.03（6）0.32，0.28，0.40

0.020.030.050.060.110.070.170.100.280.190.400.210.320.6071（6）0.32，0.28，0.400.020.030.050（7）0.40，0.60

0.020.030.050.060.110.070.170.100.280.190.400.210.320.600.100101010101010172（7）0.40，0.600.020.030.050.060.已知二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結點的數目。intleaf(BitreeT){ if(!T) return0; if(!T->Lchild&&!T->Rchild) return1; return(leaf(T->Lchild)+leaf(T->Rchild));}

73已知二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結第7章圖已知如圖（P245,圖7.30)所示的AOE-網，試求：

74第7章圖已知如圖（P245,圖7.30)所示的AOE-（1）每個事件的最早發(fā)生時間和最晚發(fā)生時間；事件vi的最早發(fā)生時間ve(i)：從源點到頂點vi的最長路徑的長度。ve(0)=0;ve(i)=Max{ve(k)+dut(<k,i>)}事件vi的最晚發(fā)生事件vl(i):在保證匯點按其最早發(fā)生時間發(fā)生這一前提下，求事件vi的最晚發(fā)生時間。vl(n-1)=ve(n-1)vl(i)=Min{vl(k)-dut(<i,k>)}

75（1）每個事件的最早發(fā)生時間和最晚發(fā)生時間；26（1）每個事件的最早發(fā)生時間；ve(0)=0

ve(1)=max{ve(0)+dut(<0,1>)}=5ve(2)=max{ve(0)+dut(<0,2>)}=6ve(3)=max{ve(1)+dut(<1,3>),ve(2)+dut(<2,3>)}=12ve(4)=max{ve(3)+dut(<3,4>),ve(2)+dut(<2,4>)}=15

……76（1）每個事件的最早發(fā)生時間；27（1）每個事件的最晚發(fā)生時間；vl(9)=ve(9)=23vl(8)=min(vl(9)-dut(<8,9>)}=21vl(7)=min(vl(8)-dut(<7,8>)}=19vl(6)=min(vl(9)-dut(<6,9>)}=19vl(5)=min(vl(8)-dut(<5,8>)}=16vl(4)=min(vl(5)-dut(<4,5>),vl(7)-dut(<4,7>)}=15

……

77（1）每個事件的最晚發(fā)生時間；28（2）每個活動的最早開始時間和最晚開始時間；活動ai的最早開始時間e(i):如果活動ai對應的弧為<j,k>,則e(i)等于從源點到頂點j的最長路徑的長度，即：e(i)=ve(j);活動ai的最晚開始時間l(i):如果活動ai對應的弧為<j,k>,其持續(xù)時間為dut(<j,k>),則有：l(i)=vl(k)-dut(<j,k>)。

78（2）每個活動的最早開始時間和最晚開始時間；29每個活動的最早開始時間

e(<0,1>)=ve(0)=0e(<0,2>)=ve(0)=0e(<1,3>)=ve(1)=5e(<2,3>)=ve(2)=6e(<2,4>)=ve(2)=6e(<3,4>)=ve(3)=12

……

79每個活動的最早開始時間30每個活動的最晚開始時間

l(<0,1>)=vl(1)-dut(<0,1>)=4l(<0,2>)=vl(2)-dut(<0,2>)=0l(<1,3>)=vl(3)-dut(<1,3>)=9l(<2,3>)=vl(3)-dut(<2,3>)=6

……

80每個活動的最晚開始時間31給出關鍵路徑。關鍵路徑：從源點到匯點的最長路徑的長度為完成整個工程任務所需的時間，該路徑叫做關鍵路徑。關鍵路徑上的活動叫做關鍵活動。關鍵活動：e(i)=l(i)的活動ai即為關鍵活動。

81給出關鍵路徑。32已知如圖（P245,圖7.31）所示的有向網，試利用Dijkstra算法求頂點1到其余頂點的最短路徑，并給出算法執(zhí)行過程中各步的狀態(tài)。

82已知如圖（P245,圖7.31）所示的有向網，試利用DijkDijkstra算法

對于圖G=（V，E），將圖中的頂點分成兩組：

第一組S：已求出的最短路徑的終點集合第二組V-S：尚未求出最短路徑的頂點集合算法將按最短路徑長度的遞增順序逐個將第二組的頂點加入到第一組中，直到所有頂點都被加入到第一組頂點集S為止。

83Dijkstra算法34

8435（1）用Prime算法從頂點9開始，手工構造最小生成樹。

85（1）用Prime算法從頂點9開始，手工構造最小生成樹。36Prime算法：