【正文】 D．最短回路31. 下面關(guān)于求關(guān)鍵路徑的說法不正確的是（ ）。 A．存在 B．不存在【中科院計(jì)算所1998 二、6 (2分）】【中國科技大學(xué) 1998二、6（2分）】27．一個(gè)有向無環(huán)圖的拓?fù)渑判蛐蛄校? ）是唯一的?！灸暇├砉ご髮W(xué) 2000 一、21 （）】A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3)23．當(dāng)各邊上的權(quán)值( )時(shí)，BFS算法可用來解決單源最短路徑問題?！局锌圃很浖?1999 六、2（1）（2分）】①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均不正確②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案均不正確 19．下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）：【東北大學(xué) 2000 2（4分）】A．深度優(yōu)先遍歷 B. 拓?fù)渑判? C. 求最短路徑 D. 求關(guān)鍵路徑20. 在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹的 Prim 算法的時(shí)間復(fù)雜度為( )。【武漢大學(xué) 2000 二、7】A．mA B．A C．Am D．Am115. 下列說法不正確的是（ ）。A．逆拓?fù)溆行? B．拓?fù)溆行? C．無序的 【中科院軟件所 1998】10．下面結(jié)構(gòu)中最適于表示稀疏無向圖的是（ ），適于表示稀疏有向圖的是（ ）?！局猩酱髮W(xué) 1998 二、9 （2分）】A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）6．一個(gè)有n個(gè)結(jié)點(diǎn)的圖，最少有（ ）個(gè)連通分量，最多有（ ）個(gè)連通分量?！颈狈浇煌ù髮W(xué) 2001 一、24 （2分）】A．由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列 B．由不同頂點(diǎn)所形成的序列C．由不同邊所形成的序列 D．上述定義都不是2．設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（ ）條邊。A．n1 B．n(n1)/2 C． n(n+1)/2 D．0 E．n2【清華大學(xué) 1998 一、5 （2分）】【西安電子科技大 1998 一、6 （2分）】【北京航空航天大學(xué) 1999 一、7 （2分）】3．一個(gè)n個(gè)頂點(diǎn)的連通無向圖，其邊的個(gè)數(shù)至少為（ ）。A．0 B．1 C．n1 D．n【北京郵電大學(xué) 2000 二、5 （20/8分）】7．在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（ ）倍，在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（ ）倍。A．鄰接矩陣 B．逆鄰接表 C．鄰接多重表 D．十字鏈表 E．鄰接表 【北京工業(yè)大學(xué) 2001 一、3 (2分)】11．下列哪一種圖的鄰接矩陣是對稱矩陣？（ ）【北方交通大學(xué) 2001 一、11 （2分）】A．有向圖 B．無向圖 C．AOV網(wǎng) D．AOE網(wǎng)12． 從鄰接陣矩可以看出，該圖共有（①）個(gè)頂點(diǎn)；如果是有向圖該圖共有（②） 條??；如果是無向圖，則共有（③）條邊?！厩鄭u大學(xué) 2002 二、9 （2分）】A．圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問一次 C．圖的深度遍歷不適用于有向圖B．遍歷的基本算法有兩種：深度遍歷和廣度遍歷 D．圖的深度遍歷是一個(gè)遞歸過程16．無向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（ ）。A. O(n) B. O(n+e) C. O(n2) D. O(n3)【合肥工業(yè)大學(xué) 2001 一、2 （2分）】21. 下面是求連通網(wǎng)的最小生成樹的prim算法：集合VT，ET分別放頂點(diǎn)和邊，初始為（ 1 ），下面步驟重復(fù)n1次: a：（ 2 ）；b：（ 3 ）；最后：（ 4 ）?！局锌圃河?jì)算所2000一、3 (2分）】A．均相等 B．均互不相等 C．不一定相等24. 求解最短路徑的Floyd算法的時(shí)間復(fù)雜度為( )。【北京郵電大學(xué) 2001 一、3 （2分）】A．一定 B．不一定28. 在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是（ ）?！灸暇├砉ご髮W(xué) 1998 一、12 （2分）】 A．求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的 B．一個(gè)事件的最早開始時(shí)間同以該事件為尾的弧的活動(dòng)最早開始時(shí)間相同 C．一個(gè)事件的最遲開始時(shí)間為以該事件為尾的弧的活動(dòng)最遲開始時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差 D．關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上32．下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（ ）。（ ）【南京航空航天大學(xué) 1996 六、4 （1分）】4. 有e條邊的無向圖，在鄰接表中有e個(gè)結(jié)點(diǎn)。（ ）【北京郵電大學(xué) 2002 一、7 （1分）】8．連通分量指的是有向圖中的極大連通子圖。（ ）【青島大學(xué) 2000 四、5 （1分）】12．用鄰接矩陣法存儲(chǔ)一個(gè)圖所需的存儲(chǔ)單元數(shù)目與圖的邊數(shù)有關(guān)。（ ）【東南大學(xué) 2001 一、3 （1分）】【哈爾濱工業(yè)大學(xué) 1999 三、4】16. 鄰接矩陣適用于有向圖和無向圖的存儲(chǔ)，但不能存儲(chǔ)帶權(quán)的有向圖和無向圖，而只能使用鄰接表存儲(chǔ)形式來存儲(chǔ)它。（ ）【南京航空航天大學(xué) 1996 六、8 （1分）】 20. 廣度遍歷生成樹描述了從起點(diǎn)到各頂點(diǎn)的最短路徑。（ ）【山東大學(xué) 2001 一、5 （1分）】25．一個(gè)網(wǎng)（帶權(quán)圖）都有唯一的最小生成樹。（ ）【華南理工大學(xué) 2002 一、6（1分）】29. 求最小生成樹的普里姆(Prim)算法中邊上的權(quán)可正可負(fù)。（ ）【合肥工業(yè)大學(xué) 2000 二、7（1分）】33. 在用Floyd 算法求解各頂點(diǎn)的最短路徑時(shí)，每個(gè)表示兩點(diǎn)間路徑的pathk1[I,J]一定是pathk [I,J]的子集(k=1,2,3,…,n)。（ ）【青島大學(xué) 2002 一、7 （1分）2001 一、8 （1分）】37. 有環(huán)圖也能進(jìn)行拓?fù)渑判?。? ）【合肥工業(yè)大學(xué) 2001 二、6（1分）】41．若一個(gè)有向圖的鄰接矩陣對角線以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù嬖凇＃? ）【青島大學(xué) 2000 四、10（1分）】45. AOE網(wǎng)一定是有向無環(huán)圖。（ ） 【大連海事大學(xué) 2001 一、16 （1分）】49．當(dāng)改變網(wǎng)上某一關(guān)鍵路徑上任一關(guān)鍵活動(dòng)后，必將產(chǎn)生不同的關(guān)鍵路徑?！局貞c大學(xué) 2000 一、1】4．具有10個(gè)頂點(diǎn)的無向圖，邊的總數(shù)最多為______?！竞戏使I(yè)大學(xué) 2000 三、8 （2分）】9．在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)______?！疚靼搽娮涌萍即髮W(xué) 2001軟件 一、2 （2分）】13．N個(gè)頂點(diǎn)的連通圖的生成樹含有______條邊。【北京郵電大學(xué) 2001 二、5 （2分）】17．N個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí),該矩陣至少有_______個(gè)非零元素。【青島大學(xué) 2002 三、8 （2分）】21. 遍歷圖的過程實(shí)質(zhì)上是______，breathfirst search遍歷圖的時(shí)間復(fù)雜度______；depthfirst search遍歷圖的時(shí)間復(fù)雜度______，兩者不同之處在于______，反映在數(shù)據(jù)結(jié)構(gòu)上的差別是______。【南京理工大學(xué) 1999 二、9 （2分）】25. 按下圖所示，畫出它的廣度優(yōu)先生成樹______和深度優(yōu)先生成樹______?！緩B門大學(xué) 1999 一、4】29．克魯斯卡爾算法的時(shí)間復(fù)雜度為______,它對______圖較為適合。請?jiān)谙铝袆澗€處填上正確敘述?！旧綎|工業(yè)大學(xué)1998二、4(6分）】32. 有一個(gè)用于n個(gè)頂點(diǎn)連通帶權(quán)無向圖的算法描述如下：（1）．設(shè)集合T1與T2，初始均為空；（2）．在連通圖上任選一點(diǎn)加入T1；（3）．以下步驟重復(fù)n1次：，j不屬于T1的邊中選最小權(quán)的邊；。【南京理工大學(xué) 1999 二、8（4分）】35. 求從某源點(diǎn)到其余各頂點(diǎn)的Dijkstra算法在圖的頂點(diǎn)數(shù)為10，用鄰接矩陣表示圖時(shí)計(jì)算時(shí)間約為10ms,則在圖的頂點(diǎn)數(shù)為40，計(jì)算時(shí)間約為______ms。【南京理工大學(xué) 1998 三、7（4分）】39．設(shè)有向圖有n個(gè)頂點(diǎn)和e條邊，進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為______?！局貞c大學(xué)2000一、2】42．在 AOV網(wǎng) 中，存在環(huán)意味著______，這是______的；對程序的數(shù)據(jù)流圖來說，它表明存在______。 arcptr=^arode。adjlist=ARRAY[vtxptr]OF vexnode。visited為標(biāo)志數(shù)組。 write(v0)。IF(2)_______ THEN p:=p^.nextarcELSE [write(v)。 (3)_______] ]IF top0 THEN[p:=stack[top]。 CONST nl=max_node_number。 arode=RECORD vexi ,vexj: vtxptr。 firstin，firstout: arcptr。 n: integer。 (1)_______。ENDF；PROC creat(var g: graph)。 g[i].firstout:=NIL。 new (p)。p^.nexti:=: ____(4)____。 v:char): vtxptr0。ENDF。 i:=order(g,v)。 IF (9)______AND(10)______THEN nextadj:=p^.nexti^.vexj ELSE nextadj:=0。 write(v0:2)。 w:=(13)_______。 FOR i:=1 TO n DO IF NOT visited[i] THEN dfs(g,g[i].vexdata)。END. 【北方交通大學(xué) 1999 三（20分）】46．n個(gè)頂點(diǎn)的有向圖用鄰接矩陣array表示，下面是其拓?fù)渑判蛩惴ǎ囇a(bǔ)充完整。i++) indegree[i]= ((1)_______) for(i=0,in。 } topsort (array,indegree,n) { count= ((4)_______) for (i=0。 count++。 if ((8)_______ ) push(i)。 CONST maxn=20 。 chtype=RECORD count : integer 。 PROCEDURE readdata 。 readln (n) 。 ch[i].head:=NIL END。 new( p ) 。 (2) __。 t: nodeptr 。 i:= 0 。i:= i + 1 。 IF ch[k].count=0 THEN BEGIN ch[k].count:=top。 writeln。 topolEND. 【復(fù)旦大學(xué) 1995 三 （18分）】V1V2V3V4V5V648．如下為拓?fù)渑判虻腃程序，（1）．列出對右圖執(zhí)行該程序后的輸出結(jié)果。 top=1。 top=i。 exit(1)。for (ptr=graph[j].link。 if((3)_____) {graph[k].count=top?！颈本┼]電大學(xué) 2002 三 （10分）】6．用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否有關(guān)？【西安電子科技大學(xué) 2000計(jì)應(yīng)用 一、6（5分）】7．請回答下列關(guān)于圖(Graph)的一些問題：（每題4分） （1）．有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有多少條邊?最少有多少條邊? （2）．表示有1000個(gè)頂點(diǎn)、l000條邊的有向圖的鄰接矩陣有多少個(gè)矩陣元素？是否稀疏矩陣？ （3）．對于一個(gè)有向圖，不用拓?fù)渑判颍绾闻袛鄨D中是否存在環(huán)？【清華大學(xué)2000一(12分）】8．解答問題。（4分）（4）．分別畫出該邏輯結(jié)構(gòu)的正向鄰接表和逆向鄰接表。 （3）．其它表示法。【復(fù)旦大學(xué)1998六(10分))367589421