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

1、1-19.確定下列各程序段的程序步，確定劃線語句的執(zhí)行次數(shù)，確定下列各程序段的程序步，確定劃線語句的執(zhí)行次數(shù)，計(jì)算它們的漸近時(shí)間復(fù)雜度。計(jì)算它們的漸近時(shí)間復(fù)雜度。(1) i=1; k=0; do k=k+10*i; i+; while(i=n-1)劃線語句的執(zhí)行次數(shù)為劃線語句的執(zhí)行次數(shù)為 n-1 ,漸近時(shí)間復(fù)雜度為漸近時(shí)間復(fù)雜度為O(n)(2）i=1; x=0; do x+; i=2*i; while （in）; 劃線語句的執(zhí)行次數(shù)為劃線語句的執(zhí)行次數(shù)為 log2n ,漸近時(shí)間復(fù)雜度為漸近時(shí)間復(fù)雜度為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 ,漸近時(shí)間復(fù)雜度為漸近時(shí)間復(fù)雜度為O(n1/2)2-4Loc(Aijk)=134+(i*n*p+j*p+k)*22-9. 設(shè)有長(zhǎng)度為設(shè)有長(zhǎng)度為n 的一維整型數(shù)組的一維整型數(shù)組A，設(shè)計(jì)一個(gè)算法，將原數(shù)，設(shè)計(jì)一個(gè)算法，將原數(shù)組中的元素以逆序排列組中的元素以逆序排列void Invert(T elements, int length) /length數(shù)組長(zhǎng)度數(shù)組長(zhǎng)度/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五個(gè)元素依次進(jìn)棧（進(jìn)棧五個(gè)元素依次進(jìn)棧（進(jìn)棧后可立即出棧），問能否得到下列序列。若能得后可立即出棧），問能否得到下列序列。若能得到，則給出相應(yīng)的到，則給出相應(yīng)的push和和pop序列；若不能，則序列；若不能，則說明理由。說明理由。（1）A，B，C，D，E（1）能得到該序列。）能得到該序列。相應(yīng)的相應(yīng)的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五個(gè)元素依次進(jìn)棧（進(jìn)棧五個(gè)元素依次進(jìn)棧（進(jìn)棧后可立即出棧），問能否得到下列序列。若能得后可立即出棧），問能否得到下列序列。若能得到，則給出相應(yīng)的到，則給出相應(yīng)的push和和pop序列；若不能，則序列；若不能，則說明理由。說明理由。（2）A，C，E，B，D（2）不能得到該序列，在）不能得到該序列，在E出棧時(shí)，出棧時(shí)，B和和D在棧在棧中，中，B比比D先進(jìn)棧，所以先進(jìn)棧，所以D應(yīng)比應(yīng)比B先出棧。先出棧。（3）不能得到該序列，在）不能得到該序列，在C出棧時(shí)，出棧時(shí)，A和和B在棧中在棧中，A比比B先進(jìn)棧，所以先進(jìn)棧，所以B應(yīng)比應(yīng)比A先出棧。先出棧。 3-1. 設(shè)設(shè)A，B，C，D

5、，E五個(gè)元素依次進(jìn)棧（進(jìn)棧五個(gè)元素依次進(jìn)棧（進(jìn)棧后可立即出棧），問能否得到下列序列。若能得到后可立即出棧），問能否得到下列序列。若能得到，則給出相應(yīng)的，則給出相應(yīng)的push和和pop序列；若不能，則說序列；若不能，則說明理由。明理由。（3）C，A，B，D，E（4）能得到該序列。）能得到該序列。相應(yīng)的相應(yīng)的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五個(gè)元素依次進(jìn)棧（進(jìn)棧五個(gè)元素依次進(jìn)棧（進(jìn)棧后可立即出棧），問能否得到

6、下列序列。若能得到后可立即出棧），問能否得到下列序列。若能得到，則給出相應(yīng)的，則給出相應(yīng)的push和和pop序列；若不能，則說序列；若不能，則說明理由。明理由。（4）E，D，C，B，A4-1. 設(shè)線性表采用順序表示方式，并假定順序表是設(shè)線性表采用順序表示方式，并假定順序表是有序的（設(shè)有序的（設(shè)表中元素已按非遞減次序排列表中元素已按非遞減次序排列）。編寫）。編寫函數(shù)，實(shí)現(xiàn)線性表的如下運(yùn)算：函數(shù)，實(shí)現(xiàn)線性表的如下運(yù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+); / 查找首個(gè)大于等于查找首個(gè)大于等于x的元素位置，并記錄在的元素位置，并記錄在i中中 if (lst-Elementsi=x)return i;/x在表中時(shí)，返回

8、在表中時(shí)，返回x的位置的位置 if (IsFull(lst) /或或if(lst-Size=lst-maxList)return -1; /表已滿時(shí)，無法插入，返回表已滿時(shí)，無法插入，返回-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ù)，實(shí)現(xiàn)線性表的如下運(yùn)算：函數(shù)，實(shí)現(xiàn)線性表的如下運(yù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+);/找到首個(gè)大于找到首個(gè)大于y的元素位置的元素位置j sum=j-i; while(jn) lsti+

10、=lstj+;/刪除刪除sum個(gè)元素個(gè)元素 n=n-sum;for (j=i;jy) /大于大于y的元素前移的元素前移lsti+=lstj+;else/小于等于小于等于y的元素刪除的元素刪除 j+; n-; 006003000700000008100000090261031473283310449列三元組：列三元組： 10302632833101474494.7 求對(duì)題圖求對(duì)題圖4-1的稀疏矩陣執(zhí)行矩陣轉(zhuǎn)置時(shí)數(shù)組的稀疏矩陣執(zhí)行矩陣轉(zhuǎn)置時(shí)數(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é)點(diǎn)的節(jié)點(diǎn)個(gè)數(shù)分別為個(gè)數(shù)分別為n1,n2,nm，求葉子節(jié)點(diǎn)的數(shù)目。，求葉子節(jié)點(diǎn)的數(shù)目。設(shè)度為設(shè)度為0的節(jié)點(diǎn)個(gè)數(shù)為的節(jié)點(diǎn)個(gè)數(shù)為n0則：則：樹的總度數(shù)樹的總度數(shù)=節(jié)點(diǎn)總個(gè)數(shù)節(jié)點(diǎn)總個(gè)數(shù)-1即：即：1*n1+2*n2+m*nm =n0+ n1+n2+n3+.+ nm-1因此葉子節(jié)點(diǎn)數(shù)目為：因此葉子節(jié)點(diǎn)數(shù)目為：n0=n2+2*n3+.+ (m-1)nm+16-5. 找出所有二叉樹，其節(jié)點(diǎn)在下列兩種次序下找出所有二叉樹，其節(jié)點(diǎn)在下列兩種次序下恰好都以同樣的次序出現(xiàn)：恰好都

12、以同樣的次序出現(xiàn)：（1）先序和中序；（）先序和中序；（2）先序和后序；（）先序和后序；（3）中）中序和后序序和后序（1）或者為空二叉樹，或者所有結(jié)點(diǎn)的左子樹都）或者為空二叉樹，或者所有結(jié)點(diǎn)的左子樹都是空的單支樹是空的單支樹（2）或者為空二叉樹，或者只有根結(jié)點(diǎn)的二叉樹）或者為空二叉樹，或者只有根結(jié)點(diǎn)的二叉樹（3）或者為空二叉樹，或者所有結(jié)點(diǎn)的右子樹都）或者為空二叉樹，或者所有結(jié)點(diǎn)的右子樹都是空的單支樹是空的單支樹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)路徑長(zhǎng)度：加權(quán)路徑長(zhǎng)度：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 對(duì)上題的例子，若采用雙散列法，試以散列函對(duì)上題的例子，若采用雙散列法，試以散列函數(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對(duì)80：（3+1*9）%11=1 對(duì)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 對(duì)50：（6+1*6）%11=1 （6+2*6）%11=75 52 24 41 13 30 0(1)(1)各個(gè)頂點(diǎn)的入度和出度各個(gè)頂點(diǎn)的入度和出度頂點(diǎn)頂點(diǎn) 入度入度 出度出度0 03 30 01 12 22 22 21 12 23 31 12 24 42 23 35 51 11 1(2)(2)強(qiáng)連通分量強(qiáng)連通分量(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所建立的鄰接表上進(jìn)行以頂點(diǎn)所建立的鄰接表上進(jìn)行以頂點(diǎn)2 2為起為起點(diǎn)頂點(diǎn)的深度優(yōu)先搜索和寬度優(yōu)先搜索。分別畫出點(diǎn)頂點(diǎn)的深度優(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所建立的鄰所建立的鄰接表對(duì)應(yīng)的圖為：接表對(duì)應(yīng)的圖為：以頂點(diǎn)以頂點(diǎn)2為起點(diǎn)頂點(diǎn)的深度優(yōu)先為起點(diǎn)頂點(diǎn)的深度優(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以頂點(diǎn)以頂點(diǎn)2為起點(diǎn)頂點(diǎn)的寬度優(yōu)先為起點(diǎn)頂點(diǎn)的寬度優(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為源點(diǎn)，生成的最小代價(jià)生成樹為：為源點(diǎn)，生成的最小代價(jià)生成樹為：（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）簡(jiǎn)單選擇排序）簡(jiǎn)單選擇排序初始序列初始序列 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