南郵_數(shù)據(jù)結(jié)構(gòu)作業(yè)答案講解

1、1-19.確定下列各程序段的程序步，確定劃線語句的執(zhí)行次數(shù)，確定下列各程序段的程序步，確定劃線語句的執(zhí)行次數(shù)，計算它們的漸近時間復雜度。計算它們的漸近時間復雜度。(1) i=1; k=0; do k=k+10*i; i+; while(i=n-1)劃線語句的執(zhí)行次數(shù)為劃線語句的執(zhí)行次數(shù)為 n-1 ,漸近時間復雜度為漸近時間復雜度為O(n)(2）i=1; x=0; do x+; i=2*i; while （in）; 劃線語句的執(zhí)行次數(shù)為劃線語句的執(zhí)行次數(shù)為 log2n ,漸近時間復雜度為漸近時間復雜度為O(log2n)(3) for(int i=1;i=n;i+) for(int j=1;j=i

2、;j+) for (int k=1;k=(y+1)*(y+1) y+;劃線語句的執(zhí)行次數(shù)為劃線語句的執(zhí)行次數(shù)為 n1/2 ,漸近時間復雜度為漸近時間復雜度為O(n1/2)2-4Loc(Aijk)=134+(i*n*p+j*p+k)*22-9. 設(shè)有長度為設(shè)有長度為n 的一維整型數(shù)組的一維整型數(shù)組A，設(shè)計一個算法，將原數(shù)，設(shè)計一個算法，將原數(shù)組中的元素以逆序排列組中的元素以逆序排列void Invert(T elements, int length) /length數(shù)組長度數(shù)組長度/elements為需要逆序的數(shù)組為需要逆序的數(shù)組 T e; for (int i=1;iLink; p-Link=

3、first;first=p; p=q;return first; 3-1. 設(shè)設(shè)A，B，C，D，E五個元素依次進棧（進棧五個元素依次進棧（進棧后可立即出棧），問能否得到下列序列。若能得后可立即出棧），問能否得到下列序列。若能得到，則給出相應的到，則給出相應的push和和pop序列；若不能，則序列；若不能，則說明理由。說明理由。（1）A，B，C，D，E（1）能得到該序列。）能得到該序列。相應的相應的push和和pop序列為：序列為：push(A); pop(); push(B); pop(); push(C); pop(); push(D); pop(); push(E); pop(); 3-1

4、. 設(shè)設(shè)A，B，C，D，E五個元素依次進棧（進棧五個元素依次進棧（進棧后可立即出棧），問能否得到下列序列。若能得后可立即出棧），問能否得到下列序列。若能得到，則給出相應的到，則給出相應的push和和pop序列；若不能，則序列；若不能，則說明理由。說明理由。（2）A，C，E，B，D（2）不能得到該序列，在）不能得到該序列，在E出棧時，出棧時，B和和D在棧在棧中，中，B比比D先進棧，所以先進棧，所以D應比應比B先出棧。先出棧。（3）不能得到該序列，在）不能得到該序列，在C出棧時，出棧時，A和和B在棧中在棧中，A比比B先進棧，所以先進棧，所以B應比應比A先出棧。先出棧。 3-1. 設(shè)設(shè)A，B，C，D

5、，E五個元素依次進棧（進棧五個元素依次進棧（進棧后可立即出棧），問能否得到下列序列。若能得到后可立即出棧），問能否得到下列序列。若能得到，則給出相應的，則給出相應的push和和pop序列；若不能，則說序列；若不能，則說明理由。明理由。（3）C，A，B，D，E（4）能得到該序列。）能得到該序列。相應的相應的push和和pop序列為：序列為：push(A); push(B); push(C); push(D); push(E); pop(); pop(); pop(); pop(); pop();3-1. 設(shè)設(shè)A，B，C，D，E五個元素依次進棧（進棧五個元素依次進棧（進棧后可立即出棧），問能否得到

6、下列序列。若能得到后可立即出棧），問能否得到下列序列。若能得到，則給出相應的，則給出相應的push和和pop序列；若不能，則說序列；若不能，則說明理由。明理由。（4）E，D，C，B，A4-1. 設(shè)線性表采用順序表示方式，并假定順序表是設(shè)線性表采用順序表示方式，并假定順序表是有序的（設(shè)有序的（設(shè)表中元素已按非遞減次序排列表中元素已按非遞減次序排列）。編寫）。編寫函數(shù)，實現(xiàn)線性表的如下運算：函數(shù)，實現(xiàn)線性表的如下運算：（1）int Search_Insert(List *lst,T x)后置條件：在有序的順序表中搜索元素后置條件：在有序的順序表中搜索元素x。若若x在表中，則在表中，則返回返回x在表

7、中的位置在表中的位置。否則，若表未滿，則在表中插入新元素否則，若表未滿，則在表中插入新元素x，并且插，并且插入后，線性表仍然是有序的，入后，線性表仍然是有序的，返回新元素返回新元素x的位置的位置；若表已滿，無法插入新元素，則若表已滿，無法插入新元素，則返回返回-1。int Search_Insert(List *lst, T x) int i,j; for(i=0; (xlst-Elementsi)&(iSize);i+); / 查找首個大于等于查找首個大于等于x的元素位置，并記錄在的元素位置，并記錄在i中中 if (lst-Elementsi=x)return i;/x在表中時，返回

8、在表中時，返回x的位置的位置 if (IsFull(lst) /或或if(lst-Size=lst-maxList)return -1; /表已滿時，無法插入，返回表已滿時，無法插入，返回-1 for (j=lst-Size-1; j=i; j-)lst-Elementj+1=lst-Elementj; lst-Elementi=x; /新元素即插入位置新元素即插入位置i處處 lst.Size+; return i;/插入新元素并返回該元素的位置插入新元素并返回該元素的位置4-1. 設(shè)線性表采用順序表示方式，并假定順序表是設(shè)線性表采用順序表示方式，并假定順序表是有序的（設(shè)有序的（設(shè)表中元素已按

9、非遞減次序排列表中元素已按非遞減次序排列）。編寫）。編寫函數(shù)，實現(xiàn)線性表的如下運算：函數(shù)，實現(xiàn)線性表的如下運算：（2）void Search_Delete(List *lst, T x,T y)前置條件：前置條件：xSize=0) printf(“The list is empty”);return -1; int i,j,sum=0; for (i=0;tempix&in-1) return;/沒有符合條件的元素沒有符合條件的元素 for (j=i;lstj=y&jn;j+);/找到首個大于找到首個大于y的元素位置的元素位置j sum=j-i; while(jn) lsti+

10、=lstj+;/刪除刪除sum個元素個元素 n=n-sum;for (j=i;jy) /大于大于y的元素前移的元素前移lsti+=lstj+;else/小于等于小于等于y的元素刪除的元素刪除 j+; n-; 006003000700000008100000090261031473283310449列三元組：列三元組： 10302632833101474494.7 求對題圖求對題圖4-1的稀疏矩陣執(zhí)行矩陣轉(zhuǎn)置時數(shù)組的稀疏矩陣執(zhí)行矩陣轉(zhuǎn)置時數(shù)組num和和k的值。的值。col01234numcol10212kcol01134行三元組行三元組： （1）無序樹：）無序樹：9棵棵（2）有序樹：）有序樹：1

11、2棵棵（3）二叉樹：）二叉樹：30棵棵3棵棵6棵棵6棵棵6棵棵各各6棵棵6-3. 設(shè)在度為設(shè)在度為m的樹中，度為的樹中，度為1，2，m的節(jié)點的節(jié)點個數(shù)分別為個數(shù)分別為n1,n2,nm，求葉子節(jié)點的數(shù)目。，求葉子節(jié)點的數(shù)目。設(shè)度為設(shè)度為0的節(jié)點個數(shù)為的節(jié)點個數(shù)為n0則：則：樹的總度數(shù)樹的總度數(shù)=節(jié)點總個數(shù)節(jié)點總個數(shù)-1即：即：1*n1+2*n2+m*nm =n0+ n1+n2+n3+.+ nm-1因此葉子節(jié)點數(shù)目為：因此葉子節(jié)點數(shù)目為：n0=n2+2*n3+.+ (m-1)nm+16-5. 找出所有二叉樹，其節(jié)點在下列兩種次序下找出所有二叉樹，其節(jié)點在下列兩種次序下恰好都以同樣的次序出現(xiàn)：恰好都

12、以同樣的次序出現(xiàn)：（1）先序和中序；（）先序和中序；（2）先序和后序；（）先序和后序；（3）中）中序和后序序和后序（1）或者為空二叉樹，或者所有結(jié)點的左子樹都）或者為空二叉樹，或者所有結(jié)點的左子樹都是空的單支樹是空的單支樹（2）或者為空二叉樹，或者只有根結(jié)點的二叉樹）或者為空二叉樹，或者只有根結(jié)點的二叉樹（3）或者為空二叉樹，或者所有結(jié)點的右子樹都）或者為空二叉樹，或者所有結(jié)點的右子樹都是空的單支樹是空的單支樹ABFCDEGH先序：先序：DEHFJGCKAB中序：中序：HEJFGKCDAB后序：后序：HJKCGFEBADDEAFJGBCHKint SizeL(BTree Bt) return

13、SizeofLeaf(Bt.Root); int SizeofLeaf(BTNode *p) if(!p) return 0; if( (!(p-RChild)&(!(p-LChild) )return 1; return SizeofLeaf(p-LChild)+SizeofLeaf(p-RChild); void ExchBt(BTree Bt)Exch(Bt.Root);void Exch(BTNode *p)if (p)BTNode *q=p-LChild;p-LChild=p-RChild;p-RChild=q;Exch(p-LChild); Exch(p-RChild);

14、A:1010 B:1011 C:100 D:00 E:01 F:11加權(quán)路徑長度：加權(quán)路徑長度：WPL=(2+3)4+53+(7+9+12)2=91 3725451456659176建成的二叉樹建成的二叉樹37254514566591刪除刪除76后后372514566591刪除刪除45后后282536343543339-3 9-3 設(shè)散列表設(shè)散列表ht11ht11，散列函數(shù)，散列函數(shù)h(key)=key % 11h(key)=key % 11。采用線性探查法、二次探查法解決沖突，試用關(guān)鍵采用線性探查法、二次探查法解決沖突，試用關(guān)鍵字值序列：字值序列：7070，2525，8080，3535，60

15、60，4545，5050，5555分別分別建立散列表。建立散列表。線性探查法：線性探查法：Keyh(Key)70425380335260545150655005545352570806050123456789109-3 9-3 設(shè)散列表設(shè)散列表ht11ht11，散列函數(shù)，散列函數(shù)h(key)=key % 11h(key)=key % 11。采用線性探查法、二次探查法解決沖突，試用關(guān)鍵采用線性探查法、二次探查法解決沖突，試用關(guān)鍵字值序列：字值序列：7070，2525，8080，3535，6060，4545，5050，5555分別分別建立散列表。建立散列表。二次探查法：二次探查法：Keyh(Key

16、)70425380335260545150655004535802570605055123456789109-4 9-4 對上題的例子，若采用雙散列法，試以散列函對上題的例子，若采用雙散列法，試以散列函數(shù)數(shù)h h1 1(key)=key % 11(key)=key % 11， h h2 2(key)=key % 9+1(key)=key % 9+1建立散建立散列表。列表。0558035257060455012345678910Keyh1(Key)704253803352605451506550h2(Key)88997162對80：（3+1*9）%11=1 對45：（1+1*1）%11=2 （1

17、+2*1）%11=3（1+3*1）%11=4 （1+4*1）%11=5（1+5*1）%11=6 對50：（6+1*6）%11=1 （6+2*6）%11=75 52 24 41 13 30 0(1)(1)各個頂點的入度和出度各個頂點的入度和出度頂點頂點 入度入度 出度出度0 03 30 01 12 22 22 21 12 23 31 12 24 42 23 35 51 11 1(2)(2)強連通分量強連通分量(3)(3)鄰接矩陣鄰接矩陣0 00 00 00 00 00 01 01 00 10 10 00 00 10 10 00 01 01 00 00 01 01 01 01 01 11 10 0

18、0 00 10 11 01 00 00 00 00 02 24 41 13 35 50 05 52 24 41 13 30 00 0 5 5 0 0 1 12 23 34 45 50 0 3 3 4 4 4 4 0 0 2 2 1 1 1 10 01 12 23 34 45 5void Degree(Graph g, int *d) int i; int n=g.Vertices; Enode* p; for (i=0;in;i+) di=0; for (i=0;inextArc)dp-adjVex+; for (i=0;in;i+) cout“d“i“=“di;10-6 10-6 在題在題1

19、0-210-2所建立的鄰接表上進行以頂點所建立的鄰接表上進行以頂點2 2為起為起點頂點的深度優(yōu)先搜索和寬度優(yōu)先搜索。分別畫出點頂點的深度優(yōu)先搜索和寬度優(yōu)先搜索。分別畫出遍歷所得到的深度優(yōu)先搜索和寬度優(yōu)先搜索的生成遍歷所得到的深度優(yōu)先搜索和寬度優(yōu)先搜索的生成森林（或生成樹）。森林（或生成樹）。5 52 24 41 13 30 00 0 5 5 0 0 1 12 23 34 45 50 0 3 3 4 4 4 4 0 0 2 2 1 1 1 10 01 12 23 34 45 5題題10-2所建立的鄰所建立的鄰接表對應的圖為：接表對應的圖為：以頂點以頂點2為起點頂點的深度優(yōu)先為起點頂點的深度優(yōu)先搜

20、索所得到深度優(yōu)先搜索生成樹：搜索所得到深度優(yōu)先搜索生成樹：0 0 5 5 0 0 1 12 23 34 45 50 0 3 3 4 4 4 4 0 0 2 2 1 1 1 10 01 12 23 34 45 55 52 24 41 13 30 0深度優(yōu)先遍歷：深度優(yōu)先遍歷：2，4，5，0，1，3以頂點以頂點2為起點頂點的寬度優(yōu)先為起點頂點的寬度優(yōu)先搜索所得到寬度優(yōu)先搜索生成樹：搜索所得到寬度優(yōu)先搜索生成樹：5 52 24 41 13 30 00 0 5 5 0 0 1 12 23 34 45 50 0 3 3 4 4 4 4 0 0 2 2 1 1 1 10 01 12 23 34 45 5寬

21、度優(yōu)先遍歷：寬度優(yōu)先遍歷：2，4，1，5，0，34 42 25 50 03 31 11 17 72 21 15 56 69 92 24 42 25 50 03 31 11 17 72 21 15 5Prim算法以算法以1為源點，生成的最小代價生成樹為：為源點，生成的最小代價生成樹為：（1）直接插入排序）直接插入排序初始序列（初始序列（61）87 12 03 08 70 97 75 53 26第第1趟趟 （61 87）12 03 08 70 97 75 53 26第第2趟趟 （12 61 87）03 08 70 97 75 53 26第第3趟趟 （03 12 61 87）08 70 97 75

22、53 26第第4趟趟 （03 08 12 61 87）70 97 75 53 26第第5趟趟 （03 08 12 61 70 87）97 75 53 26第第6趟趟 （03 08 12 61 70 87 97）75 53 26第第7趟趟 （03 08 12 61 70 75 87 97）53 26第第8趟趟 （03 08 12 53 61 70 75 87 97）26第第9趟趟 （03 08 12 26 53 61 70 75 87 97） （3）冒泡排序（注意冒泡排序只排了）冒泡排序（注意冒泡排序只排了7趟）趟）初始序列初始序列(61 87 12 03 08 70 97 75 53 26)第

23、第1趟趟 61 12 03 08 70 87 75 53 26 97 第第2趟趟 12 03 08 61 70 75 53 26 87 97第第3趟趟 03 08 12 61 70 53 26 75 87 97第第4趟趟 03 08 12 61 53 26 70 75 87 97第第5趟趟 03 08 12 53 26 61 70 75 87 97第第6趟趟 03 08 12 26 53 61 70 75 87 97第第7趟趟 03 08 12 26 53 61 70 75 87 97（4）快速排序）快速排序初始序列初始序列61 87 12 03 08 70 97 75 53 26 第第1趟趟

24、 (53 26 12 3 8) 61 (97 75 70 87) 第第2趟趟 ( 8 26 12 3) 53 61 (97 75 70 87) 第第3趟趟 (3) 8 (12 26) 53 61 (97 75 70 87) 第第4趟趟 3 8 12 (26) 53 61 (97 75 70 87) 第第5趟趟 3 8 12 26 53 61 (87 75 70) 97 第第6趟趟 3 8 12 26 53 61 (70 75) 87 97 第第7趟趟 3 8 12 26 53 61 70 (75) 87 97 （5）簡單選擇排序）簡單選擇排序初始序列初始序列 61 87 12 03 08 70 97 75 53 26第第1趟趟 （03）87 12 61 08 70 97 75 53 26第第2趟趟 （03 08）12 61 87 70 97 75 53 26第第3趟趟 （03 08 12）61 87 70 97 75 53 26第第4趟趟 （03 08 12 26）87 70 97 75 53 61第第5趟趟 （03 08 12 26 53）70 97 75 87 61第第6趟趟 （03 08 12 26 53