數(shù)據(jù)結(jié)構(gòu)本科期末綜合練習(xí)四算法分析題

1、.數(shù)據(jù)結(jié)構(gòu)（本科）期末綜合練習(xí)四（算法分析題）1.指出算法的功能并求出其時間復(fù)雜度。int fun(int n)int i =1,s=1;while(sn)s+=+i;return i;功能為：時間復(fù)雜度為：2.指出算法的功能并求出其時間復(fù)雜度。void matrimult(int aMN, int bNL, int cML) /M、N、L均為全局整型常量int i, j, k; for ( i = 0; i M; i+ )for ( j = 0; j L; j+ )cij = 0; for( i =0; i M;i+)for(j=0;jL;j+)for(k=0;kN;k+) cij+=aik

2、*bkj;功能為：時間復(fù)雜性為：3.針對如下算法，回答問題：若數(shù)組An = 12, 24, 0, 38, 0, 0, 0, 0, 29, 0, 45, 0, n = 12，給出算法執(zhí)行后數(shù)組An的狀態(tài)。template void unknown ( T A , int n ) int free = 0;for ( int i = 0; i n; i+ )if ( Ai != 0 ) if ( i != free ) Afree = Ai; Ai = 0;free+; 算法執(zhí)行的結(jié)果4.設(shè)順序表SeqList具有下列操作： int Length( ) const;/計算表長度并返回，若表為空則返

3、回0T Remove( );/刪除當(dāng)前表項并返回其值，置下一表項為當(dāng)前表項T First( ); /取表中第一個表項的值并返回，并置為當(dāng)前表項 T Next( );/取當(dāng)前表項后繼表項的值并返回， /并把此后繼表項置為當(dāng)前表項若順序表中存放的數(shù)據(jù)為29,38,47,16,95,64,73,83,51,10,0,26，表的長度為12，參數(shù)值s=10, t=30，說明算法執(zhí)行后順序表的狀態(tài)和長度的變化。*include *include “SeqList.h”template void unknown ( SeqList& L, T s, T t ) if(!L.Length( ) | s=t)

4、cerr“表為空或參數(shù)值有誤!”endl; exit(1);int i=0;Ttemp=L.First( ); while(i=s & temp=t)L.Remove( ); else temp=L.Next( ); i+;算法執(zhí)行后順序表中的數(shù)據(jù)：算法執(zhí)行后順序表的長度：5.設(shè)字符串String具有下列操作：int Length ( ) const;/計算字符串的長度char getData ( k );/提取字符串第k個字符的值若字符串Tar的值為“ababcabcacbab”，Pat的值為“a b c a c”時，給出算法執(zhí)行后函數(shù)返回的結(jié)果。*include “String.h”int

5、 unknown ( String& Tar, String& Pat ) const for ( int i = 0; i = Tar.Length( ) Pat.Length( ); i+ ) int j = 0; while ( j link;while (p) if (p & _(1)_) q=p; p=p-link; else q-link= _(2)_; delete(p);p=_(3)_; /while/ purge_linkst(1) (2) (3)7.設(shè)單鏈表的存儲結(jié)構(gòu)為ListNode=(data,link)，表頭指針為LH，所存線性表L=(a,b,c,d,e,f,g)，若

6、執(zhí)行unknown(LH)調(diào)用下面程序，則寫出執(zhí)行結(jié)束后的輸出結(jié)果。 void unknown（LinkNode *Ha） /Ha為指向單鏈表的頭指針 if(Ha) unknown (Ha-link);coutdata; 8.設(shè)單鏈表結(jié)點的結(jié)構(gòu)為LNode=(data,link)，閱讀下面的函數(shù)，指出它所實現(xiàn)的功能。 int AA(LNode*Ha) /Ha為指向帶表頭附加結(jié)點的單鏈表的表頭指針int n=0;LNode *p=Ha-link;while(p) n+; p=p-link; return(n); 算法功能：9.設(shè)單鏈表結(jié)點的結(jié)構(gòu)為ListNode=(data,link)，下面程序

7、段執(zhí)行后將生成由L所指向的帶頭結(jié)點的單鏈表，給出該單鏈表所對應(yīng)的線性表。ListNode *L=new ListNode;ListNode *p=L;for (int i = 0; i link=new ListNode;p = p-link;p-data = i*2-1; /for p-link = NULL;10.這是一個統(tǒng)計單鏈表中結(jié)點的值等于給定值x的結(jié)點數(shù)的算法，其中有兩行錯誤，請指出錯誤行的行號并改正。int count (ListNode *Ha, ElemType x) / Ha 為不帶頭結(jié)點的單鏈表的頭指針int n = 0; while (Ha!= NULL) Ha = H

8、a-link;if (Ha-data = x) n+; /whilereturn n; /count錯誤語句號: 修改如下:11.寫出下列程序段的輸出結(jié)果:void main()stack S;char x,y;S.InitStack();x=c;y=k;S.Push(x); S.Push(a); S.Push(y);S.Pop(S,x); S.Push(t); S.Push(s);while(!S.IsEmpty() S.Pop(y); couty; coutyendl; /main運行結(jié)果：12.寫出下列程序段的輸出結(jié)果:void main()queue Q;char x,y=c;Q.In

9、itQueue();Q.EnQueue(h); Q.EnQueue(r); Q.EnQueue(y);Q.DeQueue(x); Q.EnQueue(x); Q.DeQueue(x);Q.EnQueue(a);while(Q.IsEmpty( ) Q.DeQueue(y); couty; coutxlink=NULL; while(p1!=NULL&p2!=NULL)if(p1-datadata) _(1)_; p1=p1-link;else p-link=p2; p2=p2-link; _(2)_;if(p1!=NULL) p-link=p1;else _(3)_;p1=p2=NULL;re

10、turn a.link;(1) (2) (3) 16.閱讀下列算法，寫出算法功能。LinkNode* BB(LinkNode *first) if(first=NULL | first-link=NULL) return first; LinkNode*q=first,*p=q-link;q-link=NULL; while(p!=NULL) ListNode*r=p-link; p-link=q;q=p;p=r; return q; 算法功能：17.下面是判斷一個帶表頭結(jié)點的雙向循環(huán)鏈表L其前后結(jié)點值是否對稱相等的算法, 若相等則返回1，否則返回0。請按標(biāo)號補充合適的內(nèi)容。 int symm

11、etry ( DoublelList* DL ) DoublelNode * p = DL-rLink, *q = DL-lLink; while (p != q) if ( p-data = q-data ) p = p-rLink; _(1)_; if(p-lLink=q) _(2)_; else _(3)_; return 1; (1) (2) (3)18.閱讀下面的算法, 寫出它的功能。ListNode* unknown( ) ListNode *first, *p, *q;int x; p = first = new ListNode;cinx;while (x !=0) q =ne

12、w ListNode; q-data = x; p-rlink = q; q-llink = p; p = q; cinx;p-rlink = NULL;return first-rlink;算法功能：19.rear是指向以循環(huán)鏈表表示的隊列的隊尾指針，EnLQueue函數(shù)實現(xiàn)插入 x 為新的隊尾元素的操作。DeLQueue函數(shù)實現(xiàn)刪除隊頭元素并賦給x的操作。請按標(biāo)號補充合適的內(nèi)容。void EnLQueue(ListNode*& rear, ElemType x)/ rear是指向以循環(huán)鏈表表示的隊列的隊尾指針，插入 x 為新的隊尾元素。ListNode*p;p = new ListNode

13、;p-data = x; _(1)_;rear-link = p; rear = p; bool DeLQueue(ListNode*& rear, ElemType& x) / rear是指向以循環(huán)鏈表表示的隊列的隊尾指針，若隊列不空，/則刪除隊頭元素并以 x 帶回，并返回 true, 否則返回 false, x 無意義 if(rear=NULL) return false;if ( rear-link = rear ) x=rear-data; delete rear; rear=NULL; return true;ListNode *p=rear-link;rear-link=p-lin

14、k;_(2)_;delete p; _(3)_;(1) (2) (3) 20. 設(shè)有一個求解漢諾塔（Hanoi）的遞歸算法如下：voidHANOI ( int n, int peg1, int peg2, int peg3 ) if(n=1) coutpeg1peg3endl;else HANOI(n-1, peg1, peg3, peg2); coutpeg1peg3temp An-1:temp;返回結(jié)果：算法功能：22.針對如下算法，設(shè)整數(shù)鏈表L中各結(jié)點的數(shù)據(jù)為12, 24, 30, 90, 84, 36，n的初值為0，則（1）給出執(zhí)行unknown( L.first, n )調(diào)用后的返回

15、結(jié)果;（2）指出算法功能。在算法中g(shù)etLink()函數(shù)返回結(jié)點指針域的值，getData()函數(shù)返回結(jié)點的數(shù)據(jù)域的值。floatunknown ( ListNode *f , int& n ) if ( f = NULL )return 0;else n+;return unknown (f-getLink(),n) + f-getData()/n ;返回結(jié)果：算法功能：23.已知二叉樹中的結(jié)點類型BinTreeNode定義為:struct BinTreeNode ElemType data;BinTreeNode *left, *right;其中data為結(jié)點值域，left和right分別

16、為指向左、右子女結(jié)點的指針域。下面函數(shù)的功能是返回二叉樹BT中值為X的結(jié)點所在的層號，請在劃有橫線的地方填寫合適內(nèi)容。int NodeLevel(BinTreeNode * BT, ElemType X) if(BT=NULL) return 1; /空樹的層號為-1 else if(BT-data=X) return 0; /根結(jié)點的層號為0 /向子樹中查找X結(jié)點 else int c1=NodeLevel(BT-left,X); if(c1=0) _(1)_; int c2=_(2)_; if _(3)_; /若樹中不存在X結(jié)點則返回-1 else return -1; (1)(2)(3)

17、24.已知二叉樹中的結(jié)點類型BinTreeNode定義為:struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。下面函數(shù)的功能是：從二叉樹BT中查找值為X的結(jié)點，返回指向其父結(jié)點的指針。若該結(jié)點不存在或為樹根結(jié)點則返回空。算法中參數(shù)PT的初值為NULL。請在劃有橫線的地方填寫合適內(nèi)容。BinTreeNode* ParentPtr(BinTreeNode* BT, BinTreeNode* PT, ElemType& X) if(BT=NULL) ret

18、urn NULL; else if(BT-data=X) return PT; else if(PT=ParentPtr(BT-left,BT,X) _(1)_; if _(2)_ return PT; else _(3)_; (1)(2)(3)25.已知二叉樹中的結(jié)點類型BinTreeNode定義為:struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。根據(jù)下面函數(shù)的定義指出函數(shù)的功能。算法中參數(shù)BT指向一棵二叉樹。BinTreeNode* BTre

19、eSwopX(BinTreeNode* BT) if(BT=NULL) return NULL;else BinTreeNode* pt=new BinTreeNode;pt-data=BT-data;pt-right=BTreeSwopX(BT-left);pt-left=BTreeSwopX(BT-right); return pt;算法功能：26. 已知二叉樹中的結(jié)點類型STreeNode定義為:struct STreeNode datatype data; STreeNode *lchild, *rchild, *parent;其中data為結(jié)點值域，lchild和rchild分別為指

20、向左、右子女結(jié)點的指針域，parent為指向父親結(jié)點的指針域。根據(jù)下面函數(shù)的定義指出函數(shù)的功能。算法中參數(shù)ST指向一棵二叉樹，X保存一個結(jié)點的值。STreeNode* PN(STreeNode* ST, datatype& X) if(ST=NULL) return NULL; else StreeNode* mt; if(ST-data=X) return ST-parent; else if(mt=PN(ST-lchild,X) return mt; else if(mt=PN(ST-rchild,X) return mt; return NULL; 算法功能：27.已知二叉樹中的結(jié)點類型

21、BinTreeNode定義為: struct BinTreeNode ElemType data;BinTreeNode *left, *right;其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。根據(jù)下面函數(shù)的定義指出函數(shù)的功能。算法中參數(shù)BT指向一棵二叉樹。 void BTC(BinTreeNode* BT)if(BT!=NULL) if( BT-left!=NULL & BT-right!=NULL) if(BT-left-dataBT-right-data) BinTreeNode* t=BT-left;BT-left=BT-right;BT-right=

22、t;BTC(BT-left);BTC(BT-right);算法功能：28.已知二叉樹中的結(jié)點類型BinTreeNode定義為: struct BinTreeNode char data; BinTreeNode *left, *right;其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。假定指針bt指向一棵二叉樹，該二叉樹的廣義表表示為a(b(a,d(f),c(e(,a(k),b)，每次調(diào)用時整數(shù)變量C的值均為0，若：執(zhí)行BTC1(bt,a,C)調(diào)用后，C的值為_(1)_;執(zhí)行BTC1(bt,b,C)調(diào)用后，C的值為_(2)_;執(zhí)行BTC1(bt,c,C)調(diào)用后，

23、C的值為_(3)_;執(zhí)行BTC1(bt,g,C)調(diào)用后，C的值為_(4)_;void BTC1(BinTreeNode* BT, char x, int& k) if(BT!=NULL) if( BT-data=x) k+; BTC1( BT-left, x, k); BTC1( BT-right, x, k); (1)(2)(3)(4)29.已知二叉樹中的結(jié)點類型BinTreeNode定義為: struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。下

24、面函數(shù)的功能是從二叉樹BT中查找值為X的結(jié)點，若查找成功則返回結(jié)點地址，否則返回空。請在劃有橫線的地方填寫合適內(nèi)容。BinTreeNode* BTF(BinTreeNode* BT, ElemType x) if(BT=NULL) _(1)_; else if( BT-data=x) _(2)_; else BinTreeNode* t; if(t=BTF(BT-left, x) _(3)_; _(4)_; else return NULL; (1)(2)(3)(4)30.已知二叉樹中的結(jié)點類型BinTreeNode定義為:struct BinTreeNode char data; BinTr

25、eeNode *left, *right;其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。假定一棵二叉樹采用鏈接存儲，它的廣義表表示為r(b(,d(f,g),t(e)，rt,bt,dt和et指針變量分別保存指向r,b,d和e結(jié)點的指針值，則：執(zhí)行BTM(rt)調(diào)用后，得到的函數(shù)值為_(1)_;執(zhí)行BTM(bt)調(diào)用后，得到的函數(shù)值為_(2)_;執(zhí)行BTM(dt)調(diào)用后，得到的函數(shù)值為_(3)_;執(zhí)行BTM(et)調(diào)用后，得到的函數(shù)值為_(4)_;char BTM(BinTreeNode* BT) static char max=0; if(BT!=NULL) ch

26、ar k1,k2; k1=BTM(BT-left); k2=BTM(BT-right); if(k1max) max=k1; else if(k2max) max=k2; else if(BT-datamax) max=BT-data; return max;(1)t /2分(2)g /2分(3)g /2分(4)e /2分31.已知二叉樹中的結(jié)點類型BinTreeNode定義為:struct BinTreeNode ElemType data;BinTreeNode *left, *right;其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。根據(jù)下面函數(shù)的定義指出

27、函數(shù)的功能。算法中參數(shù)BT指向一棵二叉樹。void preserve(BinTreeNode* BT, ElemType a, int n) static int i=0; if(BT!=NULL) preserve(BT-left, a, n); ai+=BT-data; preserve(BT-right, a, n); 算法功能：32.在a10數(shù)組中的數(shù)據(jù)16,42,35,73,54,38,80為一個最小堆，n為整型變量，其值為7，則執(zhí)行IH(a,n,25)調(diào)用下面算法后數(shù)組a中的數(shù)據(jù)變?yōu)開。void IH(int HBT, int& n, int item) HBTn=item;n+;

28、int x=item; int i=n-1; while(i!=0) int j=(i-1)/2; if(x=HBTj) break; HBTi=HBTj; i=j; HBTi=x;33.在a10數(shù)組中數(shù)據(jù)16,35,42,73,54,58,80為一個最小堆，n為整型變量，其值為7，則執(zhí)行DH(a,n)調(diào)用下面算法后數(shù)組a中的數(shù)據(jù)變?yōu)開。int DH(int HBT, int& n) if(n=0) cerrnull!endl;exit(1);int temp=HBT0;n-;int x=HBTn; int i=0; int j=2*i+1; while(j=n-1) if(jHBTj+1)

29、j+; if(x=HBTj) break; HBTi=HBTj; i=j; j=2*i+1; HBTi=x; return temp;34.已知二叉搜索樹中的結(jié)點類型BinTreeNode定義為:struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。指針參數(shù)BST指向一棵二叉搜索樹。試根據(jù)下面的函數(shù)定義指出此算法的功能。 ElemType FM(BinTreeNode* BST) if(BST=NULL) cerr此樹為空right!=NULL) t=

30、t-right;return t-data;算法功能：35.假定p1和p2是兩個有序單鏈表的表頭指針，用來表示兩個集合，單鏈表中的結(jié)點包括值域data和指向后繼結(jié)點的指針域link，試指出下面算法的功能。ListNode* BU(ListNode* p1, ListNode* p2)ListNode* p3=new ListNode, *p=p3;While(p1!=NULL & p2!=NULL) ListNode* newptr=new ListNode;if(p1-datadata) newptr-data=p1-data; p1=p1-link; else if(p1-datap2-d

31、ata) newptr-data=p2-data; p2=p2-link;else newptr-data=p1-data; p1=p1-link; p2=p2-link;p3-link=newptr;p3=newptr;if(p2!=NULL) p1=p2;while(p1!=NULL) p3=p3-link=new ListNode; p3-data=p1-data; p1=p1-link; p3-link=NULL;p3=p-link; delete p;return p3;算法功能：36.假定p1和p2是兩個單鏈表的表頭指針，用來表示兩個集合，單鏈表中的結(jié)點包括值域data和指向后繼結(jié)

32、點的指針域link，試根據(jù)下面算法指出算法功能。int SS(ListNode* p1, ListNode* p2) while(p2!=NULL) ListNode* r=p1; While(r!=NULL) if(p2-data=r-data) break; r=r-link; if(r=NULL) return 0; p2=p2-link; return 1;37.假定HL為保存一個集合的有序單鏈表的表頭指針，item為一個新元素，HL單鏈表中的結(jié)點包括值域data和指向后繼結(jié)點的指針域link，試根據(jù)下面算法指出算法功能。void IS(ListNode*& HL, const Ele

33、mType& item) ListNode* newptr=new ListNode;newptr-data=item; if(HL=NULL | itemdata) newptr-link=HL; HL=newptr; return; ListNode *cp, *ap; ap=HL; cp=HL-link; while(cp!=NULL) if(itemdata) break; ap=cp; cp=cp-link; newptr-link=cp; ap-link=newptr;算法功能：38.已知二叉搜索樹中的結(jié)點類型BinTreeNode定義為: struct BinTreeNode E

34、lemType data; BinTreeNode *left, *right;其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。參數(shù)t指向一棵二叉搜索樹，該樹的廣義表表示為: 25(10(5,16(12),40(32(,38)。按照下面算法，則：執(zhí)行LN(pt,40)調(diào)用后返回的值為_(1)_。執(zhí)行LN(pt,38)調(diào)用后返回的值為_(2)_。執(zhí)行LN(pt,5)調(diào)用后返回的值為_(3)_。 int LN(BinTreeNode* t, ElemTypeX)if(t=NULL) return 0; else if(t-data=X) return 1;else i

35、f(t-dataX) return 1+LN(t-left,X);elsereturn 1+LN(t-right,X);(1) (2) (3)39.已知二叉樹中的結(jié)點類型BinTreeNode定義為:struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。參數(shù)bt指向一棵二叉樹，引用參數(shù)x一開始具有的值小于樹中所有結(jié)點的值。試根據(jù)下面的函數(shù)定義指出此算法的功能。 int JB(BinTreeNode* bt, ElemType& x) if(bt=NUL

36、L) return 1; else if(JB(bt-left,x)=0) return 0;if(bt-datadata; if(JB(bt-right,x)=0) return 0; else return 1; 算法功能：40. 已知一個有向圖的頂點集V和邊集G分別為：V=0,1,2,3,4;E=,;若它采用鄰接矩陣存儲，對應(yīng)Graph類型的對象為a，則：(1)使用a.count_D(3)調(diào)用下面算法后的返回值是多少.(2)該算法的功能是什么.(3)給出該算法的時間復(fù)雜度。Template int Graph:count_D(int i) int d=0;for (int j=0; jC

37、urrentNode; j+) / CurrentNode為圖中的頂點數(shù)if (Edgeij!=0) d+;if (Edgeji!=0 ) d+;return(d);答（1）（2）（3）41. 假定一個有向圖采用鄰接矩陣存儲, 請指出下面算法的功能。 template void Graph:unknown(int i)int d,j;d = 0;for (j=0; jCurrentNodes; j+) /CurrentNodes為圖中的頂點數(shù) if(Edgeij) d+; Edgeij=0;if(Edgeji) d+; Edgeji=0;CurrentEdges -= d; / Current

38、Edges為圖中的邊數(shù)算法功能：42.已知圖的鄰接表中邊結(jié)點類型Edge的結(jié)構(gòu)為(dest, cost, link)，在表頭向量中指向頂點單鏈表的表頭指針為adj，下面算法是在用鄰接表表示的圖中計算所有頂點的出度，并保存在數(shù)組Degree中。請按標(biāo)號填補合適內(nèi)容。template void Graph:FindDegree(int Degree)int i;Edge *p=NULL;for(i=0; iNumVertices; i+) Degreei =_(1)_; /NumVertices為頂點數(shù)for(i=0; iNumVertices; i+)for (p = NodeTablei.ad

39、j; p!=NULL; _(2)_)_(3)_;答(1)(2)(3)43.已知圖的鄰接表中邊結(jié)點類型Edge的結(jié)構(gòu)為(dest, cost, link)，在表頭向量中指向頂點單鏈表的表頭指針為adj，下面算法是在用鄰接表表示的圖中計算頂點i的入度并返回。請按標(biāo)號填補合適內(nèi)容。 Template intGraph:FindDegree(int i);int deg=0,j;for(j=0; jdest=i) _(2)_; break; else p=_(3)_; return deg; 答(1)(2)(3)44.已知圖的鄰接表中邊結(jié)點類型Edge的結(jié)構(gòu)為(dest, cost, link)，在表

40、頭向量中指向頂點單鏈表的表頭指針為adj，下面算法是在用鄰接表表示的有向圖中刪除所有以i為弧頭（即終點）的有向邊。請按標(biāo)號填補合適內(nèi)容。templatevoid Graph:DeletEdge(int i) int de=0,j;Edge *p, *q;if(i=NumVertices)cout錯誤輸入endl; exit(1); /NumVertices為頂點數(shù) for(j=0;jdest=i) _(1)_; else q=p;_(2)_;if(p!=NULL) if(q=NULL) NodeTablej.adj=p-link; else _(3)_;delete p;de+;NumEdge

41、s=NumEdges-de;答(1)(2)(3) 45. 下面是進行快速排序的一次劃分的算法，請按標(biāo)號填補合適的內(nèi)容。void Exchange(int s, int i, int j) int temp =si; si=sj; _(1)_;int Partition(int seq, int low, int high) int pivotpos=low, pivot=seqlow, i; for(i=low+1; i=high; i+)if(_(2)_)pivotpos+;if(pivotpos!=i) Exchange(seq, pivotpos, i);_(3)_;return pivotpos;答(1) (