《2010年計算機專業統考試題數據結構》由會員分享，可在線閱讀，更多相關《2010年計算機專業統考試題數據結構(23頁珍藏版)》請在人人文庫網上搜索。

1、第七章,圖,基本內容,圖的定義、概念、術語及基本操作 圖的存儲結構，特別是鄰接矩陣和鄰接表 圖的深度優先和廣度優先遍歷 圖的應用(連通分量、最小生成樹、拓撲排序、關鍵路徑、最短路徑),基本內容,圖的遍歷： 深度優先和廣度優先遍歷 在連通圖中，主函數一次調用深度(廣度)優先遍歷過程，可遍歷全部頂點，可以用此方法求連通分量的個數，能夠畫出遍歷中形成的深度(廣度)優先生成樹或生成森林。,深度優先遍歷,int visitedmax; for(i=1;iadjvex=0) dfs(G, p-adjvex); p=p-nextarc; ,廣度優先遍歷,int visitedmax, queuemax; v。

2、oid bfs(Adjlist G, int v) int front=0,rear=0,v1; struct edgenode *p; for(i=1;iadjvex=0) vistitedp-adjvex=1; printf( ); queuerear=p-adjvex; rear+; p=p-nextarc; ,深度優先遍歷非遞歸,void dfs(Adjlist G, int v) struct Arcnode *stack, *p; int visitedmax, top=0; for(i=1;i0|p!=NULL) while(p!=NULL) if(visitedp-adjvex。

3、!=0) p=p-nextarc; else visitedp-adjvex=1; printf(“%d”, p-adjvex); top+; stacktop=p; p=Gp-adjvex.firstarc; if(top0)top-; p=stacktop; p=p-nextarc; ,最小生成樹,最小代價生成樹 連通圖的最小生成樹通常不是唯一的，但最小生成樹邊上的權值之和是唯一的，掌握Prim算法和Kruskal算法，能夠手工分步模擬生成樹的過程。,拓撲排序,拓撲排序是在有向圖上對入度(先、后)為零的頂點的一種排序，通常結果不唯一。 用拓撲排序和深度優先遍歷都可以判斷圖是否存在回路。 掌。

4、握手工模擬算法,關鍵路徑,關鍵路徑是在拓撲有序的前提下求出的從源點到匯點的最長路徑。 減少關鍵活動時間可以縮短工期，是指該活動為所有關鍵路徑所共有，且減少到尚未改變關鍵路徑的前提下才有效。 手工模擬算法過程。,最短路徑,從單源點到其他頂點，以及各個頂點間的最短路徑問題，掌握Dijkstra和Floyd算法，并能手工模擬，掌握用求最短路徑來解決的應用問題。,1、輸入有向圖的頂點數,邊數,頂點信息和邊的信息建立鄰接表 Status Build_AdjList(ALGraph ,2、在鄰接表表示的有向圖G上插入邊(v,w) status Insert_Arc(ALGraph ,3、深度優先判斷有向圖。

5、G中頂點i到頂點j是否有路徑,是則返回1,否則返回0 int visitedMAXSIZE; int exist_path_DFS(ALGraph G,int i,int j) if(i=j) return 1; else visitedi=1; for(p=G.verticesi.firstarc; p; p=p-nextarc) k=p-adjvex; if(!visitedk ,4、判斷鄰接表方式存儲的有向圖G的頂點i到j是否存在長度為k的簡單路徑 int visitedMAXSIZE; int exist_path_len(ALGraph G, int i, int j, int k)。

6、 if(i=j ,5、求有向圖G中頂點u到v之間的所有簡單路徑,k表示當前路徑長度 int pathMAXSIZE, visitedMAXSIZE; /*暫存遍歷過程中的路徑 int Find_All_Path(ALGraph G,int u,int v,int k) pathk=u; visitedu=1; if(u=v) printf(Found one path!n); for(i=0;pathi;i+) printf(%d,pathi); else for(p=G.verticesu.firstarc; p; p=p-nextarc) l=p-adjvex; if(!visitedl)。

7、 Find_All_Path(G,l,v,k+1); visitedu=0; pathk=0; ,6、求一個有向無環圖中最長的路徑 int maxlen, pathMAXSIZE; /*數組path用于存儲當前路徑 int mlpMAXSIZE; /*數組mlp用于存儲已發現的最長路徑 void Get_Longest_Path(ALGraph G) maxlen=0; FindIndegree(G,indegree); for(i=0;iadjvex); printf(%c,c); ,8、給定n個村莊之間的交通圖，若村莊i和j之間有道路，則將頂點i和j用邊連接，邊上的Wij表示這條道路的長度。

8、，現在要從這n個村莊中選擇一個村莊建一所醫院，問這所醫院應建在哪個村莊，才能使離醫院最遠的村莊到醫院的路程最短?試設計一個解答上述問題的算法。 分析： 每個頂點到其余各頂點的最短路徑中最長的有n條，這n條中最短的一條。,9、設頂點a, b, c, d, e表示一個鄉的5個村莊，弧上的權值表示為兩村之間的距離； 求每個村莊到其它村莊的最短距離； 鄉內要建立一所醫院，問醫院設在哪個村莊才能使各村離醫院的距離較近。 分析：每個頂點到其余各頂點最短路徑之和最短的一個。,10、欲用四種顏色對地圖上的國家涂色，有相鄰邊界的國家不能用同一種顏色(點相交不算相鄰)。 (1)試用一種數據結構表示地圖上各國相鄰的。

9、關系。 (2)描述涂色過程的算法。(不要求證明)。 分析：地圖涂色問題可以用“四染色”定理.將地圖上的國家編號(1n)從編號1開始逐一涂色，對每個區域用1色、2色、3色、4色依次試探，若當前所取顏色與周圍已涂色區域不重色，則將該區域顏色入棧；否則，用下一顏色。若14色都與相鄰某區域重色，則需出棧回溯，修改棧頂區域顏色。用鄰接矩陣描述地圖上國家間的關系，n個國家用n階方陣表示，若第i個國家與第j個國家相鄰，矩陣相應位置為1，否則為0。用棧記錄染色結果，棧的下標值為區域號，元素值為色數。,void mapcolor(AdjMatrix C) int s; s1=1; i=2; j=1; while(i4) i-; j=si+1; /變更棧頂區域顏色。

總結

以上是生活随笔為你收集整理的统考计算机2010年版,2010年计算机专业统考试题数据结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。