《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)題及參考答案

PAGE《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)題及參考答案數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算這三個(gè)方面的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是順序鏈?zhǔn)剿饕⒘?。?shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入、刪除、修改、查找、排序。非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：（B）A、一對多關(guān)系B、多對多關(guān)系C、多對一關(guān)系D、一對一關(guān)系數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（C）結(jié)構(gòu)；A、存儲(chǔ)B、物理C、邏輯D、物理和存儲(chǔ)算法分析的目的是（C）A、找出數(shù)據(jù)結(jié)構(gòu)的合理性B、研究算法中的輸入和輸出的關(guān)系C、分析算法的效率以求改進(jìn)D、分析算法的易懂性和文檔性計(jì)算機(jī)算法指的是（C）A、計(jì)算方法B、排序方法C、解決問題的有限運(yùn)算序列D、調(diào)度方法計(jì)算機(jī)算法必須具備輸入、輸出和（B）等5個(gè)特性。A、可行性、可移植性和可擴(kuò)充性B、可行性、確定性和有窮性C、確定性、有窮性和穩(wěn)定性D、易讀性、穩(wěn)定性和安全性數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎？簡單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。分析下面各程序段的時(shí)間復(fù)雜度：for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;~0020O（m*n）`002101A分析下面各程序段的時(shí)間復(fù)雜度：s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;~0021O（n2）`002201A2分析下面各程序段的時(shí)間復(fù)雜度：x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;~0022因?yàn)閤++共執(zhí)行了n-1+n-2+……＋1=n(n-1)/2，所以執(zhí)行時(shí)間為O（n2）`002301A2分析下面各程序段的時(shí)間復(fù)雜度：i=1;while(i<=n)i=i*3;~0023O（log3n）在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)元素，具體移動(dòng)的元素個(gè)數(shù)與有關(guān)。~0025表中一半表長和該元素在表中的位置`002603C1判定一個(gè)棧ST（最多元素為m0）為空的條件是BＡ、ST->top<>0Ｂ、ST->top=0Ｃ、ST->top<>m0Ｄ、ST->top=m0`002702B2向一個(gè)長度為n的向量的第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng)n-i+1個(gè)元素。`002802B2向一個(gè)長度為n的向量中刪除第i個(gè)元素(1≤i≤n)時(shí)，需向前移動(dòng)n-i個(gè)元素。`002902B1在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為，因此，順序表也稱為的數(shù)據(jù)結(jié)構(gòu)。~0029O(1)隨機(jī)存取`003102B1在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由指示。~0031其直接前驅(qū)結(jié)點(diǎn)的鏈域的值`003202B2在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的，其時(shí)間復(fù)雜度為o(n)。~0032前驅(qū)結(jié)點(diǎn)的地址O（n）線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。（x）`003702D1順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。（X）`004502C1在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O（1）的操作是（A）訪問第i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2≤i≤n）在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）將n個(gè)結(jié)點(diǎn)從小到大排序`010609F2從循環(huán)單鏈表中查找出最大值.~0106intsearchmax(linklistl){intmax;int*p;p=l;max=p->data;p=p->next;while(p->next<>nil){if(max<p->data)max=p->data;p=p->next;}returnmax;}`010709F2從循環(huán)單鏈表中查找出最小值.~0107intsearchmin(linklistl){intmin;int*p;p=l;min=p->data;p=p->next;while(p->next<>nil){if(min>p->data)min=p->data;p=p->next;}returnmin;}`011203D1棧和隊(duì)列都是線性表.()~0112正確`011603B1棧的兩個(gè)重要應(yīng)用是___________和_________.~0116在編譯系統(tǒng)運(yùn)行計(jì)算機(jī)語言程序的過程中,利用棧進(jìn)行語法檢查,實(shí)現(xiàn)遞歸調(diào)用.`011703A2棧和隊(duì)列都是運(yùn)算受到限制的特殊的線性表,棧和隊(duì)列有何不同?`011903C1用數(shù)組A存放循環(huán)隊(duì)列的元素值,若其頭指針為front,尾指針為rear,則循環(huán)隊(duì)列中當(dāng)前元素個(gè)數(shù)為(A).A、(rear-front+m)modm B、(rear-front+1)modmC、(rear-front-1+m)modm D、(rear-front)modm~0119A`012003A2設(shè)循環(huán)隊(duì)列Q頭指針為front,尾指針為rear,隊(duì)列的最大容量為M,寫出循環(huán)隊(duì)列隊(duì)滿和隊(duì)空的判定條件.~0120隊(duì)滿條件:(q.front+1)modm=q.rear隊(duì)空條件:q.front=q.rear`012203F2給出循環(huán)隊(duì)列的入隊(duì)和出隊(duì)算法.~0122intENQUEUE(sequeue*sq;datatypex){if(sq->front==(sq->rear+1)%maxsize){printf("queueisfull");returnNULL;}else{sq->rear=(sq->rear+1)%maxsize;sq->data[sq->rear]=x;return(TRUE);}}datatypeDEQUEUE(sequeue*sq){if(EMPTY(sq)){printf("queueisempty");}else{sq->front=(sq->front+1)%maxsize;return(sq->data[sq->front];}}`012503F2設(shè)計(jì)算法判斷一個(gè)算術(shù)表達(dá)式的圓括號(hào)是否正確配對,(提示:對表達(dá)式進(jìn)行掃描,凡遇'('就進(jìn)棧,遇')'就退掉棧頂?shù)?)',表達(dá)式被掃描完畢,棧就為空.)~0125booleanpair(b){stacks;s.top=0;i=1;ch=b[i];while(ch!="@"){if((ch='(')||(ch=')'))switch{'(':push(s,ch);break;')':ifempty(s){pair=false;return;}elsepop(s)}i=i+1;ch=b[i];}ifempty(s)pair=true;elsepair=false;}`012703B2程序段的輸出結(jié)果是_________（隊(duì)列中的元素類型QElemType為char）。voidmain(){QueueQ;InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,’a’);while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);}~0127stack`012909E2什么是二叉排序樹,按如下關(guān)鍵字的插入次序生成一棵二叉排序樹,試畫出此二叉排序樹25,48,36,16,45,20,18,72~0129二叉排序樹或者是一棵空樹,或者是具有如下性質(zhì)的二叉樹:(1)若它的左子樹不空,則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值;(2)若它的右子樹不空,則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值;(3)左右子樹又各是一棵二義排序樹.2516482036721845`013503E1設(shè)循環(huán)隊(duì)列的容量為40（序號(hào)從0到39），現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)運(yùn)算后，有①front=11，rear=19;②front=19，rear=11；問在這兩種情況下，循環(huán)隊(duì)列中各有元素多少個(gè)？~0135用隊(duì)列長度計(jì)算公式：(N＋r－f)%N①L=（40＋19－11）%40=8②L=（40＋11－19）%40=32`013803F2設(shè)兩個(gè)棧共享向量空間V(1:m),它們的棧底分別設(shè)在向量的兩端,且進(jìn)棧的每個(gè)元素只占一個(gè)分量,試寫出這兩個(gè)棧公用的棧操作算法pushi(i,x),popi(i),其中i為0或1,用以指示棧號(hào)~0138pushi(i,x){ifs.top0=s.top1-1printf("orerflow");ifi=0{s.top=s.top1+1;s.elem[s.ti\op]=x;}else{s.top1=s.top0-1;s.elem[s.top]=x;}}popi(i){ifi=0{ifs.top0=0printf("underflow");pop=s.elem[s.top0]s.top1=s.top1-1;}elseif{s.top=m+1printf("underflow");pop=s.elem[s.top1];s.top1=s.top1+1;}}`014003F1設(shè)HS為一個(gè)鏈棧的棧頂指針,試寫出退棧的算法,(回收被刪除的結(jié)點(diǎn))~0140linkstack*POPSTACK(top,datap)linkstack*top;datatype*datap;{linkstack*pif(top==NULL){printf("underflow");returnNULL)}else{*data=top->data;p=top;top=top->next;free(p);returntop;}}`014303E3設(shè)有編號(hào)為1，2，3，4的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序.~0143至少有14種。①全進(jìn)之后再出情況，只有1種：4，3，2，1②進(jìn)3個(gè)之后再出的情況，有3種，3,4,2,13,2,4,13,2,1,4③進(jìn)2個(gè)之后再出的情況，有5種，2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4④進(jìn)1個(gè)之后再出的情況，有5種，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3`014703E2寫出棧的順序存儲(chǔ)結(jié)構(gòu)(即順序棧)的類型定義.~0147順序棧的結(jié)構(gòu):typedefintdatatype;#definemaxsize64typedefstruct{datatypedata[maxsize];inttop}seqstack;seqstack*s;`014803A1寫出隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)(順序隊(duì)列)的類型定義.~0148順序隊(duì)列的結(jié)構(gòu):typedefstruct{datatypedata[maxsize]intfrontrear;}sequeue;sequeue*sq;`015003B2帶有頭結(jié)點(diǎn)的鏈隊(duì)列q,隊(duì)頭指針front,隊(duì)尾指針rear,則置空隊(duì)的算法描述為:q->front=malloc(sizeof(linklist));________________;________________;~0150q->front->next=NULLq->rear=q->front;`015306C2已知完全二叉樹有２８個(gè)結(jié)點(diǎn)，則整個(gè)二叉樹有()個(gè)度為１的結(jié)點(diǎn)。A、0;B、1;C、2;D、不確定~0153B`016506E3已知一棵二叉樹中序和后序序列為分別為:BDCEAFHG和DECBHGFA畫出這棵二叉樹`016806D1哈夫曼樹的帶權(quán)路徑長度WPL等于葉子結(jié)點(diǎn)的權(quán)值之和。()~0168對`016906E3已知二叉樹的先序、中序、后序序列分別如下,但其中有一些已模糊不清,構(gòu)造出該二叉樹.先序:_23_5_78中序:3_41_789后序:_42__651~0169`017206B3在有N(N>0)個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)是：_____。~0172N+1以二叉鏈表作存貯結(jié)構(gòu)，試寫出中序遍歷二叉樹的算法。~0178INORDER()bitree*t;{if(t){INORDER(t->lchild);printf("|t%c|n",t->data);INORDER(t->rchild);}}`018106B2具有N個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_________。~0181└log2n+1┘+1或┌l(fā)og2(n+1)┐`018406A2何謂哈夫曼樹?何謂完全二叉樹,它具有哪些特點(diǎn)?~0184哈夫曼樹：帶權(quán)路徑WPL最小的二叉樹稱最優(yōu)二叉樹或哈夫曼樹。完全二叉樹：若一棵二叉樹至多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于２，并且最下一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹為完全二叉樹。特點(diǎn)：１只有最下面兩層有葉子。２如果一個(gè)結(jié)點(diǎn)無左子樹，那它一定是葉子。３完全二叉樹中任一個(gè)結(jié)點(diǎn)的左子樹深度為Ｔ，其右子樹深度為Ｔ或Ｔ－１。`019006E3已知二叉樹的中序和先序序列分別為:中序序列:DEBAFCHG先序序列:ABDECFGH試構(gòu)造該二叉樹~0190`019106A3度為２的樹與二叉樹的區(qū)別。~0191度為２的樹每個(gè)結(jié)點(diǎn)如度為１子樹無左右之分；而二叉樹則有。`019206F2試編寫算法判斷兩棵二叉樹是否等價(jià),稱二叉樹T1和T2的根結(jié)點(diǎn)的值相同,并且T1的左子樹與T2的左子樹是等價(jià)的，T1的右子樹和T2的右子樹是等價(jià)的.~0192EQUBINTREE(t1,t2)bintree*t1,*t2;{if(t1=NULL&&t1=NULL)returnTRUEelse{if(t1->data=t2->data&&ERUBINTREE(t1->lchild,t2->lchild)&&ERUBINTREE(t1->rchild,t2->rchild))returnTRUE;}elsereturnFALSE;}`019806E2已知一棵度為m的樹中有N1個(gè)度為1的結(jié)點(diǎn),N2個(gè)度為2的結(jié)點(diǎn),問該樹中有多少片葉子.~0198N0=1+(i-1)Ni(i=1tom)`020006E3一個(gè)深度為L的滿K叉樹有如下性質(zhì):第L層上的結(jié)點(diǎn)是葉子結(jié)點(diǎn),其余各層上每個(gè)結(jié)點(diǎn)都有K棵非空子樹,如果按層次順序從1開始對全部結(jié)點(diǎn)編號(hào),問:(1)各層的結(jié)點(diǎn)的數(shù)目是多少?(2)編號(hào)為n的結(jié)點(diǎn)的雙親結(jié)點(diǎn)(若存在)編號(hào)是多少?(3)編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子(若存在)編號(hào)是多少?(4)編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是什么?其右兄弟的編號(hào)是多少?~0200K^(I-1)(1<=I<=k)2.(n+k-2)/k3.kn+I-k+14.nki+1(I=0,1,……);n+1`020807B1一個(gè)具有n個(gè)頂點(diǎn)的連通有向圖至多有_________條弧.~0208n(n-1)`020907B1一個(gè)具有n個(gè)頂點(diǎn)的連通有向圖至少有________條弧.~0209n+1`028106E2把如圖所示的樹轉(zhuǎn)化成二叉樹。~0281注意全部兄弟之間都要連線（包括度為2的兄弟）,并注意原有連線結(jié)點(diǎn)一律歸入左子樹，新添連線結(jié)點(diǎn)一律歸入右子樹。ABECKFHDLGIMJ`028206E2畫出和下列二叉樹相應(yīng)的森林。~0282注意根右邊的子樹肯定是森林，而孩子結(jié)點(diǎn)的右子樹均為兄弟。`029103C1判定一個(gè)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是（）Ａ、QU->rear－QU->front==m0Ｂ、QU->rear－QU->front－1==m0Ｃ、QU->front==QU->rearＤ、QU->front==QU->rear+1~0291A`032108E2用比較兩個(gè)元素大小的方法在一個(gè)給定的序列中查找某個(gè)元素的時(shí)間復(fù)雜度下限是什么?如果要求時(shí)間復(fù)雜度更小,你采用什么方法？此方法的時(shí)間復(fù)雜度是多少?~0321查找某個(gè)元素的時(shí)間復(fù)雜度下限，如果理解為最短查找時(shí)間，則當(dāng)關(guān)鍵字值與表頭元素相同時(shí)，比較1次即可。要想降低時(shí)間復(fù)雜度，可以改用Hash查找法。此方法對表內(nèi)每個(gè)元素的比較次數(shù)都是O（1）。`035607C1用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用(B)來實(shí)現(xiàn)算法的。A、棧B、隊(duì)列C、樹D、圖`035707C1用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用(A)來實(shí)現(xiàn)算法的。A、棧B、隊(duì)列C、樹D、圖`035807C2A．0243156B.0136542C.04231650361542A．0243156B.0136542C.04231650361542建議：0134256`035907C2已知圖的鄰接矩陣,根據(jù)算法，則從頂點(diǎn)0出發(fā)，按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是(C)A、0243156B、0135642C、0423165D、0134256`036007C2已知圖的鄰接矩陣，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是()A、0243651B、0136425C、0423156D、0134256（建議：0123456）~0360B`036107C2已知圖的鄰接矩陣，根據(jù)算法，則從頂點(diǎn)0出發(fā)，按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是()A、0243165B、0135642C、0123465D、0123456~0361C`036207C2已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是()A．0132B.A．0132B.0231C.0321D.0123~0362D`036307C2已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是()A、0321BA、0321B、0123C、0132D、0312~0363A`036407C1深度優(yōu)先遍歷類似于二叉樹的(A)A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷`036507C1廣度優(yōu)先遍歷類似于二叉樹的(D)A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷`037007B1n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接矩陣存儲(chǔ)，則空間復(fù)雜度為O(n2)。n個(gè)頂點(diǎn)e條邊的圖，若采用鄰接表存儲(chǔ)，則空間復(fù)雜度為O(n+e)。`037207B1設(shè)有一稀疏圖G，則G采用鄰接表存儲(chǔ)較省空間。設(shè)有一稠密圖G，則G采用鄰接矩陣存儲(chǔ)較省空間。圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)只適用于有向圖。已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)頂點(diǎn)出發(fā)的方法是將鄰接矩陣的第i行全部置0。圖的深度優(yōu)先遍歷序列不是惟一的。n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為O(n2)；若采用鄰接表存儲(chǔ)時(shí)，該算法的時(shí)間復(fù)雜度為O(n+e)。n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，廣度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為O(n2)；若采用鄰接表存儲(chǔ)，該算法的時(shí)間復(fù)雜度為O(n+e)。圖的BFS生成樹的樹高比DFS生成樹的樹高小或相等。用普里姆(Prim)算法求具有n個(gè)頂點(diǎn)e條邊的圖的最小生成樹的時(shí)間復(fù)雜度為O(n2)；用克魯斯卡爾(Kruskal)算法的時(shí)間復(fù)雜度是O(elog2e)。若要求一個(gè)稀疏圖G的最小生成樹，最好用克魯斯卡爾(Kruskal)算法來求解。若要求一個(gè)稠密圖G的最小生成樹，最好用普里姆(Prim)算法來求解。拓?fù)渑判蛩惴ㄊ峭ㄟ^重復(fù)選擇具有0個(gè)前驅(qū)頂點(diǎn)的過程來完成的。`038507E3已知如圖所示的有向圖，請給出該圖的:每個(gè)頂點(diǎn)的入/出度；鄰接矩陣；鄰接表；逆鄰接表。頂點(diǎn)123456入度出度~0385

`038607E3請對下圖的無向帶權(quán)圖：寫出它的鄰接矩陣;寫出它的鄰接表。~0386(1)a→b4→c3b→a4→c5→d5→e9^c→a3→b5→d5→h5^d→b5→c5→e7→f6→g5→h4^e→b9→d7→f3^f→d6→e3→g2^g→d5→f2→h6^h→c5→d4→g6^`038707E3已知二維數(shù)組表示的圖的鄰接矩陣如下圖所示。試分別畫出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。

`038907E3給定下列網(wǎng)G:(1)試著找出網(wǎng)G的最小生成樹，畫出其邏輯結(jié)構(gòu)圖；(2)用兩種不同的表示法畫出網(wǎng)G的存儲(chǔ)結(jié)構(gòu)圖；(3)用C語言（或其他算法語言）定義其中一種表示法（存儲(chǔ)結(jié)構(gòu)）的數(shù)據(jù)類型。AB———————AB———————CE————FG————D解：(1)最小生成樹可直接畫出，如右圖所示。(2)可用鄰接矩陣和鄰接表來描述：a→b12→e4^b→a12→c20→e8→f9^c→b20→d15→g12^d→c15→g10^e→a4→b8→f6^f→b9→e6^g→c12→d10鄰接表為：(3)注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//假設(shè)的最大頂點(diǎn)數(shù)（可取為7）Typedefenum{DG,DN,AG,AN}GraphKind;//有向/無向圖，有向/無向網(wǎng)TypedefstructArcCell{//?。ㄟ叄┙Y(jié)點(diǎn)的定義VRTypeadj;//頂點(diǎn)間關(guān)系，無權(quán)圖取1或0；有權(quán)圖取權(quán)值類型InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];Typedefstruct{//圖的定義VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)表，用一維向量即可AdjMatrixarcs;//鄰接矩陣IntVernum,arcnum;//頂點(diǎn)總數(shù)（7），弧（邊）總數(shù)（9）GraphKindkind;//圖的種類標(biāo)志}Mgraph;`039007F3編寫算法，由依次輸入的頂點(diǎn)數(shù)目、弧的數(shù)目、各頂點(diǎn)的信息和各條弧的信息建立有向圖的鄰接表。~0390解：StatusBuild_AdjList(ALGraph&G)//輸入有向圖的頂點(diǎn)數(shù),邊數(shù),頂點(diǎn)信息和邊的信息建立鄰接表{InitALGraph(G);scanf("%d",&v);if(v<0)returnERROR;//頂點(diǎn)數(shù)不能為負(fù)G.vexnum=v;scanf("%d",&a);if(a<0)returnERROR;//邊數(shù)不能為負(fù)G.arcnum=a;for(m=0;m<v;m++)G.vertices[m].data=getchar();//輸入各頂點(diǎn)的符號(hào)for(m=1;m<=a;m++){t=getchar();h=getchar();//t為弧尾,h為弧頭if((i=LocateVex(G,t))<0)returnERROR;if((j=LocateVex(G,h))<0)returnERROR;//頂點(diǎn)未找到p=(ArcNode*)malloc(sizeof(ArcNode));if(!G.vertices.[i].firstarc)G.vertices[i].firstarc=p;else{for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);q->nextarc=p;}p->adjvex=j;p->nextarc=NULL;}//whilereturnOK;}//Build_AdjList`039107F3試在鄰接矩陣存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)圖的基本操作：DeleteArc(G,v,w)，即刪除一條邊的操作。（如果要?jiǎng)h除所有從第i個(gè)頂點(diǎn)出發(fā)的邊呢？提示：將鄰接矩陣的第i行全部置0）~0391解：//本題中的圖G均為有向無權(quán)圖。StatusDelete_Arc(MGraph&G,charv,charw)//在鄰接矩陣表示的圖G上刪除邊(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(G.arcs[i][j].adj){G.arcs[i][j].adj=0;G.arcnum--;}returnOK;}//Delete_Arc`039207F3試基于圖的深度優(yōu)先搜索策略寫一算法，判別以鄰接表方式存儲(chǔ)的有向圖中是否存在由頂點(diǎn)vi到頂點(diǎn)vj的路徑（i≠j）。注意：算法中涉及的圖的基本操作必須在此存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。~0392intvisited[MAXSIZE];//指示頂點(diǎn)是否在當(dāng)前路徑上intlevel＝1;//遞歸進(jìn)行的層數(shù)intexist_path_DFS(ALGraphG,inti,intj)//深度優(yōu)先判斷有向圖G中頂點(diǎn)i到頂點(diǎn)j是否有路徑,是則返回1,否則返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--){level++;k=p->adjvex;if(!visited[k]&&exist_path(k,j))return1;//i下游的頂點(diǎn)到j(luò)有路徑}//for}//els