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

緒論和線性表習題一、 選擇題1.在一個單鏈表中，若p結(jié)點不是最后結(jié)點，在p之后插入s結(jié)點，則實行( )。 A. s-next=p；p-next=s; B、 s-next=p-next; p-next=s； C. s-next=p-next;p=s; D. p-next=s;s-next=p;2.與單鏈表相比,雙鏈表優(yōu)點之一( ). A.插入刪除操作更簡單. B.可隨機訪問 C.可省略表頭指針和表尾指針 D、 順序訪問相臨結(jié)點更靈活3.在長度為n的順序表的第i(1in+1)個位置上插入一個元素，元素的移動次數(shù)為( ) A、 n-i+1 B.n-i C.i D.i-1 4.對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為( ) A.順序表 B.用頭指針表示的單循環(huán)鏈表 C、 用尾指針表示的單循環(huán)鏈表 D.單鏈表 5.在需要經(jīng)常查找結(jié)點的前驅(qū)與后繼的場合中，使用( )比較合適。 A.單鏈表 B、 雙鏈表 C.順序表 D.循環(huán)鏈表6.下面關(guān)于線性表的敘述中，錯誤的為( ) A.順序表使用一維數(shù)組實現(xiàn)的線性表 B.順序表必須占用一片連續(xù)的存儲單元 C.順序表的空間利用率高于鏈表 D、 在鏈表中，每個結(jié)點只有一個鏈域7.帶頭結(jié)點head的單鏈表為空的判斷條件是( ) A. head=NUIL B、 head-next=NUIL C. head-next=head D. head!=NUIL8.線性表通常采用兩種存儲結(jié)構(gòu)是( ) A、 順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu) B.散列方式和索引方式 C.鏈表存儲結(jié)構(gòu)和數(shù)組 D.線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)9線性表采用鏈式存儲時，結(jié)點的存儲地址（ ） A必須是不連續(xù)的 B、 連續(xù)與否均可 C必須是連續(xù)的 D和頭結(jié)點的存儲地址相連續(xù)10將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復(fù)雜度為（ ） AO（1） BO（n） C、 O（m） DO（m+n）11、在單鏈表中，指針p指向元素為x的結(jié)點，實現(xiàn)“刪除x的后繼”的語句是( )A.p=p-next; B、 p-next=p-next-next;C.p-next=p; D.p=p-next-next;12在頭指針為head且表長大于1的單循環(huán)鏈表中，指針p指向表中某個結(jié)點，若p-next-next=head,則( )A.p指向頭結(jié)點 B.p指向尾結(jié)點C.*p的直接后繼是頭結(jié)點 D、 *P的直接后繼是尾13.為了最快地對線性結(jié)構(gòu)的數(shù)據(jù)進行某數(shù)據(jù)元素的讀取操作，則其數(shù)據(jù)存儲結(jié)構(gòu)宜采用( )方式。A、順序存儲 B.鏈式存儲C.索引存儲 D.散列存儲答案：1-5 BDACB 6-10 DBABC 11-13 BDA二、判斷題(判斷下列各小題，正確的在題后括號內(nèi)打“”，錯的打“”。)1、單鏈表中的頭結(jié)點就是單鏈表的第一個結(jié)點。( )2、所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的邏輯關(guān)系。( )3、在線性結(jié)構(gòu)中，每個結(jié)點都有一個直接前驅(qū)和一個直接后繼。( )三、填空題1、在單鏈表中設(shè)置頭結(jié)點的作用_ 。2、.設(shè)head為帶有頭結(jié)點的單鏈表的頭指針，則判斷單鏈表為空的條件是：_。3、.帶頭結(jié)點的循環(huán)鏈表L為空表的條件是_ _ _。帶頭結(jié)點的雙循環(huán)鏈表L為空表的條件是_ 。4、在如圖所示的鏈表中，若在指針p所指的結(jié)點之后插入數(shù)據(jù)域值相繼為a和b的兩個結(jié)點，則可用下列兩個語句實現(xiàn)該操作，它們依次是_ _和_。 5、.通常單鏈表的頭結(jié)點指的是_ _；單鏈表的首結(jié)點指的是_ _。6、在一個帶頭結(jié)點的單循環(huán)鏈表中，p指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針head可用p表示為 。7、從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需_ _一個位置。1、簡化插入刪除算法. 2、head-next= =NULL_。3、 L-next=L _。L-next=L-prior=L 4、_s-next-next=p-next_和_p-next=s_。 5、_在單鏈表第一個結(jié)點之前增設(shè)的一個類型相同的結(jié)點_； _表結(jié)點中的第一個結(jié)點_。6、pnextnext=head 。7、_向前移動_四、算法閱讀題 1、閱讀下面的算法 LinkList mynote(LinkList L) /L是不帶頭結(jié)點的單鏈表的頭指針 if(L&L-next) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； return L； 請回答下列問題： （1）說明語句S1的功能； （2）說明語句組S2的功能； （3）設(shè)鏈表表示的線性表為（a1,a2, ,an）,寫出算法執(zhí)行后的返回值所表示的線性表。(1)查詢表的尾節(jié)點 (2)將第一個節(jié)點鏈接到表的尾部成為新的尾節(jié)點(3)（a2,a3,.an,a1）2、以下函數(shù)中，h是帶頭結(jié)點的雙向循環(huán)鏈表的頭指針。 (1)說明程序的功能； (2)當鏈表中結(jié)點數(shù)分別為1和6(不包括頭結(jié)點)時，請寫出程序中while循環(huán)體的執(zhí)行次數(shù)。 int f(DListNode *h) DListNode *p,*q; int j=1; p=h-next; q=h-prior; while(p!=q | p-prior!=q)&(j!=0) if(p-data=q-data) p=p-next; q=q-prior; else j=0; return j; （1）是否對稱（2）1-0；6-3五、應(yīng)用題1、假定在學生的檔案中含有：姓名、學號、年齡、性別。如采用線性表作為數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)檔案管理問題，分別給出線性表的在順序?qū)崿F(xiàn)下的類型定義和在鏈接實現(xiàn)下的類型定義。2.假設(shè)以帶頭結(jié)點的單循環(huán)鏈表作非遞減有序線性表的存儲結(jié)構(gòu)。請設(shè)計一個時間復(fù)雜度為O(n)的算法，刪除表中所有數(shù)值相同的多余元素，并釋放結(jié)點空間。例如：(7，10，10，21，30，42，42，42，51，70)經(jīng)算法操作后變?yōu)?7，10，21，30，42，51，70)參考答案：typedef struct node int data;struct node * next;LinkList;Delete_Eq(LinkList * head) LinkList * p, * q, * s; p=head; doq= p-next;if(p-data = = q-data) s= q; free(s); q = q-next; else p=q;while(p-next != head);2、線性表逆置void Convers(LinkList *head) LinkList * p, *q, *r; p = head; q = p-next; p-next = NULL; while ( q!= NULL) r=q-next; q-next=p; p=q; q=r; head = p;棧和隊列習題 1. 簡述下面所給算法的功能是什么？（假設(shè)棧元素為整數(shù)類型） （1） void ex31(SeqStack *S) int A80,i,n; n=0; while(!empty(S) An=popS; n+; for(i=0;ik）項(f0,f1,f2,)的算法，其函數(shù)定義如下： 0 n=0f(n)= 1 n=1 f(n-2)+f(n-1) n=2算法如下：因為循環(huán)隊列長度為K，所以在執(zhí)行算法結(jié)束時，留在隊列中的元素應(yīng)是所求序列中的最后k項。由于只有k個元素空間，則在計算fi時，隊列總是處在頭尾相接的狀態(tài)，因此只須一個指針rear 指向當前的隊尾。每次求得一個fi之后即送入(rear% k)的位置上，沖掉原來對頭元素。#define m maxlentypedef struct int rear; int datam;CirQueue;int Fibonacci(int i) /求序列的前n項算法 if(i = 0) return 0; else if(i= = 1) return 1; else return (Fibonacci(i-2) +Fibonacci(i-1);void Fibonacci( CirQueue * Q, int k)int i, n; Q-rear = 0; scanf(“%d” ,&n); for(i =0; irear =i; if ( i =k) Q-rear = Q-rear% k; Q-data Q-rear = Fibonacci(i); 3算法閱讀假設(shè)兩個隊列共享一個循環(huán)向量空間（參見右下圖）， 其類型Queue2定義如下： typedef struct DateType dataMaxSize； int front2,rear2； Queue2；對于i=0或1，fronti和reari分別為第i個隊列的頭指針和尾指針。請對以下算法填空，實現(xiàn)第i個隊列的入隊操作。 int EnQueue (Queue2 *Q,int i,DateType x) /若第 i個隊列不滿，則元素x入隊列，并返回1；否則返回0 if(i1)return 0； if(Qreari=Qfront return 0； Qdata =x； Qreari= ; return1； (i1)%2(或1i) Qreari (Qreari1)%Maxsize4、假定在一個鏈隊列中只設(shè)置隊列為指針，不設(shè)置對首指針，并且讓隊尾節(jié)點的指針域指向隊首節(jié)點（稱此微循環(huán)隊列），試分別寫出在循環(huán)鏈隊上進行插入和刪除操作的算法。插入算法：void QInsert（LNode * &Rear , const Elemtype & item） LNode * newptr = new LNode ; if(newptr = = NULL) printf(“wrong”); exit(1); newptr -data =item; if(Rear = = NULL) Rear = newptr -next = newptr; else newptr-next =Rear -next; Rear -next = newptr; Rear = newptr; 刪除算法：ElemType QDelte(LNode * & Rear) if(Rear = =NULL) printf(“Linked queue is empty ！”)； exit(1);LNode * p = Rear -next;if( p = = Rear) Rear =NULL;else Rear -next = p-next;ElemType temp = p-data;free(p);return temp; 第四章 串習題練習：1、串長度的定義是（ ）A.串中不同字母的個數(shù) B.串中不同字符的個數(shù) C.串中所含字符的個數(shù)，且大于0 D. 串中所含字符的個數(shù)2、如下陳述中正確的式（ ）。A、串是一種特殊的線性表 B、串的長度必須大于0 C、串中元素只能是字母 D、空串就是空白串3、設(shè)字符串s1=”abcdefg”,s2=”pqrst”,則運算s=strcat(substr(s1,2,length(s2),substr(s1,length（s2）,2)后串值為（ ）。A.“bsdefef” B.“bcpqrst”C.“bsdefg”D.“bcdef” 4、設(shè)有兩個串s和t,求t在s中首次出現(xiàn)的位置的運算是（ ）A.連接B.模式匹配C.求子串D.求串長一、例子例1：從串s1(為順序存儲結(jié)構(gòu))中第k個字符起求出首次與字符串s2相同的子串的起始位置。分析：從第k個元素開始掃描s1 ，當其元素值與s2第一個元素值相同時，判斷它們之后的元素值是否依次相同，直到s2結(jié)束為止。若都相同則返回當前位置值，否則繼續(xù)上述過程直到s1掃描完為止。算法如下： #define MaxStrSize 256 typedef struct char chMaxStrSize; int Len; SeqString; int PartPosition(SeqString *s1, SeqString *s2,int k) int i,j; i=k; /*作為掃描s1的下標*/ j=1； /*作為掃描s2的下標*/ while(ilen&jlen) if(s1-chi=s2-chj) i+;j+; else i=i-j+2; j=1;if(js2-len) return i-s2-len; else return 0;例2：從串s中刪除所有與串t 相同的子串。 分析：可利用前面題目的函數(shù)。從位置1開始調(diào)用函數(shù)PartPosition(),若找到了相同的子串，則調(diào)用刪除子串函數(shù)DelSubstring()將其刪除，再查找后面位置的相同子串，方法與前同。算法如下： void DelSubstring(SeqString *s,SeqString *t) int j,k,i=1; k=1;while(ilen)&(k!=0) if(k=PartPosition(s,t,i)0) for(j=k+t-len;jlen;j+) s-chj-t-len=s-chj; /*刪除從k開始的子串*/ s-len=s-len-t-len /*修改s串的長度*/i=k; s-chs-len=0; /*賦一個串結(jié)束符*/例3：已知S和T是用結(jié)點大小為1的單鏈表存儲的兩個串，試設(shè)計一個算法找出S中第一個不在T中出現(xiàn)的字符。 分析：根據(jù)題意，要用到兩重循環(huán)，從S中取出第一個字符，與T串中的每個 字符依次進行比較，如果一直沒有遇到相等的字符，則S中取出的字符就是要求的字符，退出循環(huán)；若遇到相同的字符，則再從S中取出第二個字符與T中的字符進行比較，依次進行下去。 算法如下：typedef struct node char data;struct node *next;LinkStrNode;typedef LinkStrNode *LinkString;char FindChar(LinkString S, LinkString T) LinkStrNode *p,*q;P=S;While(p!=NULL)q=T; while(q!=NULL) if(p-data!=q-data) q=q-next; /繼續(xù)下一個字符的比較 else break; /若有相同的字符，跳出內(nèi)循環(huán) if(q=NULL) return p-data; /返回要求的字符 break;p=p-next; return “#”; /沒有要求的字符二、算法設(shè)計題1、試寫一算法，實現(xiàn)順序串的比較運算strcmp(S,T),當ST時，函數(shù)值為1，當S=T時，函數(shù)值為0，當ST時，函數(shù)值為-1。分析：算法： int strcmp(SeqString S,SeqString T) int i=0; while(iS.len&iT.chi) return 1; else if(S.chiT.len) return 1 else return -1;2、已知采用順序存儲結(jié)構(gòu)的串S，試寫一個算法刪除S中第i個字符開始的j個字符。 分析： 先判斷i和j是否在有效范圍內(nèi)（即i+jS-len) printf(“i或j超出有效范圍”); else for(k=i+j-1;klen;k+) S-chk-j=S-chk; /移位刪除j個字符。 S-len=S-len-j; /串長度減1 3、設(shè)S和T是兩個采用順序結(jié)構(gòu)存儲的串，試寫一個算法將串S中的第i個字符開始的j個字符用串T替換。 算法如下： SeqSAtring *replace(SeqString *S, SeqString *T,int i,int j) int k,l; k=T-len-j; if(k0) /說明T的長度大于被替換的串的長度，因此S串需要后移 for(l=S-len-1;l=i+T-len-1;l-) S-chl+k=S-chl; else for(l=i+T-len;llen-1;l+) S-chl+k=S-chl; /說明T的長度小于被替換的串的長度，因此S串需要前移 for(l=0;llen;l+) S-chi+l-1=T-chl; /插入串T S-len=S-len+T-len-j; /修改串S的串長度 Return S; /返回串S 第五章 多維數(shù)組和廣義表 一、應(yīng)用題（1）已知二維數(shù)組Am*n按“行優(yōu)先順序”存儲在內(nèi)存中，假設(shè)每個元素占d個存儲單元，第一個元素的存儲地址表示為LOC(A00),那么計算數(shù)組A的任意元素Aij的存儲地址公式是什么？LOC(aij)=LOC(a00)+(i*n+j)*d （2）已知二維數(shù)組A510按“行優(yōu)先順序”存儲在內(nèi)存中，假設(shè)每個元素占3個存儲單元，第一個元素的存儲地址表示為1000,那么計算數(shù)組A的A34的存儲地址。LOC(A234=LOC(A00)+(3*10+4)*3（3）已知一個10階對稱矩陣A,采用壓縮存儲方式存儲（以行序為主，每個元素占一個單元），起始地址為1100，則A45的地址多少？因為A是對稱矩陣，A45又在上三角，所以存儲位置k=j*(j-1)/2+i-1= ,因此，A45的存儲地址為LOC(SA)+k*d=二、自測題1、 一維數(shù)組和線性表區(qū)別是：（ ）A。前者長度固定，后者長度可變 B.長度均可變C.無區(qū)別 D. 長度均固定2、稀疏矩陣一般存儲方法有兩種（ ）和（ ）3、N是一個5*8的二維數(shù)組，當M按行序方式存儲時，表示該數(shù)組的第十個元素是（ ）。A。N22 B、N21 C、N11 D、N12 樹習題一、1.深度為K的完全二叉樹至少有_個結(jié)點，至多有_個結(jié)點。.(1)2k-1(2)2k-1。2.樹的三種常用存儲結(jié)構(gòu)是：孩子鏈表表示法、_和_。 (1)孩子兄弟鏈表示法 (2)雙親表示法。3.在有n個結(jié)點的二叉鏈表中，值為非空的鏈域的個數(shù)為( ) A. n-1B. 2n-1 C. n+1D. 2n+14.一棵左右子樹均不空的二叉樹在先序線索化后，其空指針域數(shù)為( ) A. 0B. 1 C. 2D.不確定5.一棵樹T采用二叉鏈表存儲，如果樹T中某結(jié)點為葉子結(jié)點，則在二叉鏈表BT中所對應(yīng)的結(jié)點一定_。2. 左右子樹空6.有64個結(jié)點的完全二叉樹的深度為( )(根的層次為1)。 A. 8B. 7 C. 6D. 57.二叉樹在線索化后，仍不能有效求解的問題是( ) A.先序線索二叉樹中求先序后繼 B.中序線索二叉樹中求中序后繼 C.中序線索二叉樹中求中序前趨 D.后序線索二叉樹中求后序后繼8在一棵度為3的樹中,度為3的結(jié)點個數(shù)為2,度為2 的結(jié)點個數(shù)為1,則度為0的結(jié)點個數(shù)為( ) A4 B5 C6 D79.具有N個結(jié)點的完全二叉樹的深度為_。 log2N+1。10.樹的三種主要的遍歷方法是：_、_和層次遍歷。(1)先根遍歷(2)后根遍歷。11.判斷線索二叉樹中某結(jié)點指針P所指結(jié)點有左孩子的條件是_。 P-ltag=112已知一棵完全二叉樹中共有768結(jié)點，則該樹中共有 個葉子結(jié)點。 384 13、在有n個葉子結(jié)點的哈夫曼樹中，總結(jié)點數(shù)是_。 n-1二、1、給定二叉樹的中序遍歷結(jié)果為abc，請畫出能得到此中序遍歷結(jié)果的二叉樹的所有形態(tài)。共有5種不同形態(tài)的二叉樹，具體如下2、已知一棵二叉樹的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，請構(gòu)造出該二叉樹。3、有一份電文中共使用五個字符：a、b、c、d、e,它們的出現(xiàn)頻率依次為8、14、10、4、18，請構(gòu)造相應(yīng)的哈夫曼樹，求出每個字符的哈夫曼編碼。哈夫曼樹為：542232121048141800011110dacbe 相應(yīng)的哈夫曼編碼為： a:001 b:10 c:01 d:000 e:114請畫出與下列二叉樹對應(yīng)的森林。 5已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，閱讀下面算法。 typedef struct node DateType data； Struct node * next； ListNode； typedef ListNode * LinkList ； LinkList Leafhead=NULL； Void Inorder (BinTree T) LinkList s； If(T) Inorder(Tlchild)； If (!Tlchild)&(!Trchild) s=(ListNode*)malloc(sizeof(ListNode)； sdata=Tdata； snext=Leafhead； Leafhead=s； Inorder(Trchild)； 對于如下所示的二叉樹 （1）畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)； （2）說明該算法的功能。.(1)LeafheadFHGD （2）中序遍歷二叉樹，按遍歷序列中葉子結(jié)點數(shù)據(jù)域的值構(gòu)建一個以Leafhead為頭指針的逆序單鏈表（或按二叉樹中葉子結(jié)點數(shù)據(jù)自右至左鏈接成一個鏈表）。6、綜合應(yīng)用題已知一樹的雙親表示法如下，其中各兄弟結(jié)點是依次出現(xiàn)的，畫出該樹及對應(yīng)的二叉樹。123456789101112131415dataABCDEFGHIJKLMNOparent011122334456678計算二叉樹的深度的算法。（1） 從森林轉(zhuǎn)換為二叉樹：（2）.計算二叉樹的深度的算法：int depth(tree *T)if(!T)return 0;else return 1+max(depth(T-Lchild),depth(-Rchild); 7.某二叉樹的線索鏈表存儲結(jié)構(gòu)如圖(b)所示，其中p為指向根結(jié)點的指針，圖(a)為結(jié)點結(jié)構(gòu)。閱讀下列算法，并回答問題：(1)寫出執(zhí)行函數(shù)調(diào)用f(p)的輸出結(jié)果；(2)簡述函數(shù)f的功能。void f(BinThrTree t) while(t) printf(t-data); if(t-lchild) t=t-lchild; else t=t-rchild; (1)(2)8、以二叉樹二叉鏈表為存儲結(jié)構(gòu)，編寫在二叉樹中查找數(shù)值為x的節(jié)點及求所在節(jié)點在樹中層次數(shù)的算法。（1） 按值查找。使用前序遍歷 void FindBT(BinTree T) if( T != = NULL)&(!found) if(T-Data = =x) P = T; found =1; else FindBT(T-lchild); FIndBT(T-rchild); BinNode * FindX(BinTree T, DataType x) int found = 0; BinNode * P; P =NULL; FindBT(T); return (P); (2) int h =0;void Level(BinTree T, BinNode *P, int lh)if( T = = NULL)h=0;elseif(T)；elseLevel(T-lchild, P,lh+1);if(h = =0)Level(T-rchild ,P，lh+1); 圖習題一、1.下列說法錯誤的是( )。 A.一個圖的鄰接矩陣表示是唯一的 B.一個圖的鄰接表表示是不唯一的 C.一個圖的生成樹必為該圖的極小連通子圖 D.一個無環(huán)有向圖的拓撲排序序列必唯一2.設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有( )條邊才能確保是一個連通圖。 A.5 B.6 C.7 D.83.DFS算法的時間復(fù)雜度為( ) A. O(n)B. O(n3) C. O(n2)D. O(n+e)4.對于一個具有n個頂點的無向圖，若采用鄰接表表示，則存放表頭結(jié)點的數(shù)組的大小為( ) A.n B.n+1 C.n-1 D.n+邊數(shù)5.在一個具有n個頂點的無向圖中，要連通全部頂點至少需要( )條邊。 A.n B.n+1 C.n-1 D.n/26在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為( ) Ae B2e Cn2e Dn22e二、1.圖的主要存儲結(jié)構(gòu)有兩種，分別為：_和_。 (1)鄰接矩陣(2)鄰接表。2.在無向圖的鄰接矩陣A中，若Ai,j等于1，則Aj,i等于_。13已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相應(yīng)的廣度優(yōu)先遍歷序列為 。 a b e f c d g 三、1.請畫出下面無向圖的鄰接矩陣和鄰接表。 接矩陣為：0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0鄰接表為：2.求出下圖的一棵最小生成樹。3.以鄰接表為存儲結(jié)構(gòu)，寫出連通圖的深度優(yōu)先搜索算法。typedef struct node int adjvex; struct node *next;JD;typedef struct tnode int vexdata; struct node *firstarc;TD;void dfs(TD g,int v,int visited) JD *w; int i; printf(%d ,v); visitedv=1; w=gv.firstarc; while(w!=NULL) i=w-adjvex; if(visitedi=0) dfs(g,i,visited); w=w-next; 4已知一個無向圖的頂點集為a, b, c, d, e ,其鄰接矩陣如下所示ab cde (1)畫出該圖的圖形； （2）根據(jù)鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。該圖的圖形為： 深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedc5.已知帶權(quán)圖的鄰接矩陣表示和鄰接表表示的形式說明分別如下：#defineMaxNum50 /圖的最大頂點數(shù)#defineINFINITYINT_MAX /INT_MAX為最大整數(shù)，表示typedefstruct charvexsMaxNum; /字符類型的頂點表 intedgesMaxNumMaxMum; /權(quán)值為整型的鄰接矩陣 intn,e; /圖中當前的頂點數(shù)和邊數(shù)MGraph; /鄰接矩陣結(jié)構(gòu)描述typedefstructnode intadjvex; /鄰接點域 intweight; /邊的權(quán)值 structnode*next; /鏈指針域EdgeNode; /邊表結(jié)點結(jié)構(gòu)描述typedefstruct charvertex; /頂點域 EdgeNode*firstedge; /邊表頭指針VertexNode; /頂點表結(jié)點結(jié)構(gòu)描述typedefstructVertexNodeadjlistMaxNum;/鄰接表 intn,e;/圖中當前的頂點數(shù)和邊數(shù)ALGraph; /鄰接表結(jié)構(gòu)描述下列算法是根據(jù)一個帶權(quán)圖的鄰接矩陣存儲結(jié)構(gòu)G1建立該圖的鄰接表存儲結(jié)構(gòu)G2，請?zhí)钊牒线m的內(nèi)容，使其成為一個完整的算法。voidconvertM(MGraph*G1,ALGraph*G2) inti,j; EdgeNode*p; G2-n=G1-n; G2-e=G1-e; for(i=0;iadjlisti.vertex=G1-vexsi; G2-adjlisti.firstedge=(1);for(i=0;iin;i+) for(j=0;jedgesijweight=(2); p-adjvex=j; p-next=G2-adjlisti.firstedge; (3) ; (1)NULL(2)G1-edgesij(3) G2-adjlisti.firstedge = p6、已知一個圖的鄰接表如下所示。請畫出該鄰接表表示的圖，并依此鄰接表進行從頂點a出發(fā)的深度優(yōu)先遍歷，畫出由此得到的深度優(yōu)先生成樹。7、已知圖G的鄰接表如下所示，則對該圖執(zhí)行下列算法FindNo后的輸出結(jié)果是什么？并請說明該算法的功能。void FindNo (