【正文】 } p=pnextarc。 //找與頂點w鄰接的第一個頂點while (p!=NULL){ if (visited[padjvex]==0) //若當(dāng)前鄰接頂點未被訪問 {printf(”%2d”, padjvex)。 Qu[rear]=v。 i++) visited[i]=0。 int Qu[MAXV]，front=0, rear=0。 //調(diào)用DFS算法num++。 i++)visited[i]=0。 p=pnextarc。 visited[v]=1。顯然，把醫(yī)院建在村莊3時總體交通代價最少。abcdegf152846910453125. 已知加權(quán)有向圖G的鄰接矩陣如下：畫出該有向圖G試?yán)肈ijkstra算法求G中從頂點a到其他各頂點間的最短路徑，并給出求解過程。3. 對一個圖進行遍歷可以得到不同的遍歷序列，那么導(dǎo)致得到的遍歷序列不唯一的因素有哪些？答：遍歷不唯一的因素有：開始遍歷的頂點不同；存儲結(jié)構(gòu)不同；在鄰接表情況下鄰接點的順序不同。 將圖中所有邊按權(quán)重從大到小排序為（e1,e2,…,em） i:=1 WHILE (所剩邊數(shù) =頂點數(shù))BEGIN 從圖中刪去ei 若圖不再連通，則恢復(fù)ei i:=i+1END.試證明這個算法所得的圖是原圖的最小代價生成樹。A．第i行中值為1的元素個數(shù) B. 所有值為1的元素個數(shù)C．第i行及第i列中值為1的元素總個數(shù)D．第i列中值為1的元素個數(shù)若一個具有n個結(jié)點、k條邊的非連通無向圖是一個森林（nk），則該森林中必有（ C ）棵樹。若無向圖G有n個結(jié)點，其鄰接矩陣為A[1…n,1…n]，且壓縮存儲在B[1…k]，則k的值至少為（ D ）。練習(xí)題：（一）選擇題：下列哪一種圖的鄰接矩陣是對稱矩陣？（ B ）A. 有向圖 B. 無向圖 C. AOV網(wǎng) D. AOE網(wǎng)當(dāng)各邊上的權(quán)值（ A ）時，廣度優(yōu)先遍歷算法可用來解決單源最短路徑問題。最短路徑問題分為兩種：一是求從某一點出發(fā)到其余各點的最短路徑；二是求圖中每一對頂點之間的最短路徑。熟練掌握求解的過程和步驟。用拓?fù)渑判蚝蜕疃葍?yōu)先遍歷都可判斷圖是否存在環(huán)路。拓?fù)渑判蚴窃谟邢驁D上對入度（先、后）為零的頂點的一種排序，通常結(jié)果不唯一。又如，“求最長的最短路徑問題”和“判斷兩頂點間是否存在長為K的簡單路徑問題”，就用到了廣度遍歷和深度遍歷算法。熟練掌握圖的兩種遍歷算法：深度遍歷和廣度遍歷。掌握與這些概念相聯(lián)系的相關(guān)計算題。 //路徑長度增1Longpath(blchild,path,pathlen,longpath,longpathlen)。i) longpath[i]=path[i]。題目解析：采用path數(shù)組保存掃描到當(dāng)前結(jié)點的路徑， pathlen保存掃描到當(dāng)前結(jié)點的路徑長度，longpath數(shù)組保存最長的路徑， longpathlen保存最長路徑長度。 //路徑長度增1 Allpath(blchild,path,pathlen)。i) printf (“%c”,path[i])。amp。} return(bt)。else{bt=(BiTree)malloc(sizeof(BiNode))。 exchange(btrchild)。解：void exchange(BiTree bt) {BiTree s；if(bt){s=btlchild。參數(shù)BT初始指向這棵二叉樹的根點。amp。i++) printf(“%d”,stack[i]data)。 q=qlchild。while ((q||top)amp。 }4．設(shè)計算法， 已知一棵以二叉鏈表存儲的二叉樹，root指向根結(jié)點，p指向二叉樹中任一結(jié)點，編寫算法求從根結(jié)點到p所指結(jié)點之間的路徑（要求輸出該路徑上每個結(jié)點的數(shù)據(jù)）。case ‘*’: value=lv*rv。 // 求右子樹表示的子表達式的值switch(btoptr){case ‘+’: value=lv+rv。 //只取‘+’， ‘’， ‘*’，‘/’struct node *lchild，*rchild }BiNode,*BiTree。若能先分別求出左子樹和右子樹表示的子表達式的值，最后就可以根據(jù)根結(jié)點的運算符的要求，計算出表達式的最后結(jié)果。flag) Is_BSTree(Trchild)。 if(Tdatalast) flag=0。函數(shù)原型如下：int Is_BSTree（BiTree T）；答：int last=0,flag=1。 } pop(S,p)。 while(!StackEmpty(S)) { while(Gettop(S,p)amp。（三）算法設(shè)計題1．請利用棧的基本操作寫出先序遍歷二叉樹的非遞歸形式的算法。因為前序序列的第一個元素是根結(jié)點，該元素將二叉樹中序序列分成兩部分，左邊（設(shè)l個元素）表示左子樹，若左邊無元素，則說明左子樹為空；右邊（設(shè)r個元素）是右子樹，若為空，則右子樹為空。若不能，請給出反例。WPL = 3*4+7*3+8*3+2*4+6*3+10*2+14*2 = 131給定字母a,b,c,d,。（最下層結(jié)點數(shù)=2）。log2n249。log2(2n)若某二叉樹共有n個結(jié)點，采用三叉鏈表存儲時，每個結(jié)點的數(shù)據(jù)域需要d個字節(jié)，每個指針域占用4個字節(jié)，若采用順序存儲，則最后一個結(jié)點下標(biāo)為k（起始下標(biāo)為1），那么（ A ）時采用順序存儲更節(jié)省空間。A. 8 B. 9 C. 10 D. 11樹中所有結(jié)點的度等于所有結(jié)點數(shù)加（ C ）。10. 哈夫曼樹為了解決特定問題引出的特殊二叉樹結(jié)構(gòu)，它的前提是給二叉樹的每條邊賦予了權(quán)值，這樣形成的二叉樹按權(quán)相加之和是最小的，一般來說，哈夫曼樹的形態(tài)不是唯一的。二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應(yīng)關(guān)系的：先根遍歷對應(yīng)二叉樹的先序遍歷，而后根遍歷對應(yīng)二叉樹的中序遍歷。熟練掌握其建立、查找、插入和刪除算法，以及判斷某棵二叉樹是否二叉排序樹這一問題的遞歸與非遞歸算法。二叉樹線索化的實質(zhì)是建立結(jié)點在相應(yīng)序列中與其前驅(qū)和后繼之間的直接聯(lián)系。{DeQueue(Q,p)。InitQueue(Q)。3. 熟練掌握二叉樹的先序，中序和后序遍歷算法以及按層次遍歷二叉樹的先序、中序和后序三種遍歷算法，劃分的依據(jù)是視其每個算法中對根結(jié)點數(shù)據(jù)的訪問順序而定。（3）滿二叉樹和完全二叉樹的概念。（2）理解二叉樹與普通雙分支樹的區(qū)別。} printf(“輸出r進制的各位數(shù)字：”)； s=head。 sdata=n。void trans(int num,int r){ link *head=NULL,*s。要求算法中用到的棧采用線性鏈表存儲結(jié)構(gòu)（1r10）。j++) sum+=[(m+j)%k]。i++) { m=i%k。ik。kk1。}}（三）算法設(shè)計題1． 試?yán)醚h(huán)隊列編寫求k階斐波那契序列中前n+1項（）的算法，要求滿足且，其中max為某個約定的常數(shù)。 initstack(t)。n。arr[64]。隊列（包括循環(huán)隊列）是一個邏輯概念，而鏈表是一個存儲概念，一個隊列是否是循環(huán)隊列。用十字鏈表作存儲結(jié)構(gòu)自然失去了隨機存取的功能。A. N[2][4] B. N[3][4] C. N[3][5] D. N[4][4]6. 設(shè)有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)以列為主序存放時，元素A[5,8]的存儲首地址是（ B ）A. BA+141 B. BA+180 C. BA+222 D. BA+2257. 遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（ C ）的數(shù)據(jù)結(jié)構(gòu)。練習(xí)題：（一）選擇題：1. 一個棧的輸入序列為1 2 3 4，則（ D ）不可能是其出棧序列。這些方面的應(yīng)用應(yīng)重點掌握。6． 循環(huán)隊列隊空及隊滿的條件。了解在數(shù)值表達式的求解、括號的配對等問題中應(yīng)用棧的工作原理。3． 如何將中綴表達式轉(zhuǎn)換成前綴、后綴表達式，了解對兩種表達式求值的方法。}二、棧、隊列和數(shù)組大綱要求：（一） 棧和隊列的基本概念 （二） 棧和隊列的順序存儲結(jié)構(gòu) （三） 棧和隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu) （四） 棧和隊列的應(yīng)用 （五） 特殊矩陣的壓縮存儲 知識點：1． 棧、隊列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，包括：順序棧、鏈棧、循環(huán)隊列、鏈隊列等。Bnext=C。Anext=C。Bnext=C。Anext=C。C=null。}8. 設(shè)A和B是兩個單鏈表，其表中元素遞增有序。}}list1data=len1。}else{rnext=p。；q=list1；r=list2；len1=0；len2=0；mark=1；while (p!=null){if(mark=1){qnext=p。其中,線性表中序號為偶數(shù)的元素分解到第一個循環(huán)鏈表中,序號為奇數(shù)的元素分解到第二個循環(huán)鏈表中。 pnext=qnext；∥p的后繼指向原p后繼的后繼。if（pnext==null）printf（“p無后繼結(jié)點\n”）。pre=head； ∥pre是前驅(qū)結(jié)點指針，指向q的前驅(qū)。這樣才能在p與其后繼結(jié)點交換后，由原p結(jié)點的前驅(qū)來指向原p結(jié)點的后繼結(jié)點。 //將q結(jié)點插到鏈表最前面 Lnext=q。 q=pnext。L){ p=Lnext。}5．寫一算法，將帶有頭結(jié)點的非空單鏈表中數(shù)據(jù)域值最小的那個結(jié)點移到鏈表的最前面。s=snext。pnext=NULL。L){ LinkList p,q,s。 return 1。 k++。k=1。 else prevnext=qnext。klen) { q=qnext。 q=p。ki) { prev=p。 k=1。lb,int i,int j,int len){ int k。函數(shù)原型如下：int DeleteAndInsertSub(LinkList amp。 } /*while(qnext)*/ p=pnext。 while (qnext) /* 從*p的后繼開始找重復(fù)結(jié)點*/ { if (qnextdata==pdata) { r=qnext。算法如下：解：void pur_LinkList(LinkList H) { LNode *p,*q,*r。 I++。 listnode *p。（2）選順序存儲結(jié)構(gòu)。3. 線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外，尚需建立一個索引表，索引表中索引指示存儲結(jié)點的存儲位置（下標(biāo)）或存儲區(qū)間端點（下標(biāo)），兼有靜態(tài)和動態(tài)特性。每個存儲結(jié)點除包含數(shù)據(jù)元素信息外還包含一組（至少一個）指針。數(shù)據(jù)元素順序存放，每個存儲結(jié)點只含一個元素。C．在進行刪除操作后，能保證鏈表不斷開。已知指針q所指點是指針p所指結(jié)點的直接前驅(qū)，若在*q與*p之間插入結(jié)點*s，則應(yīng)執(zhí)行下列哪一個操作？（ B ）。A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的基本單位B．?dāng)?shù)據(jù)項是數(shù)據(jù)中不可分割的最小可標(biāo)識單位C．?dāng)?shù)據(jù)可由若干個數(shù)據(jù)元素構(gòu)成D．?dāng)?shù)據(jù)項可由若干個數(shù)據(jù)元素構(gòu)成6．連續(xù)存儲設(shè)計時，存儲單元的地址（ A ）。通?！拜^穩(wěn)定”的線性表選擇順序存儲，而頻繁做插入刪除的即動態(tài)性較強的線性表宜選擇鏈?zhǔn)酱鎯ΑＴ趯嶋H中怎樣選取存儲結(jié)構(gòu)呢？（1）基于存儲的考慮對線性表的長度或存儲規(guī)模難以估計時，不宜采用順序表；鏈表不用事先估計存儲規(guī)模，但鏈表的存儲密度較低，顯然鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲密度是小于１的。（3）順序表具有按元素序號隨機訪問的特點。并能夠設(shè)計出實現(xiàn)線性表其它運算的算法。鏈表操作中應(yīng)注意不要使鏈意外“斷開”。要理解頭指針、頭結(jié)點、首元結(jié)點和元素結(jié)點的差別。4． 順序存儲結(jié)構(gòu)用向量（一維數(shù)組）表示，給定下標(biāo)，可以存取相應(yīng)元素，屬于隨機存取的存儲結(jié)構(gòu)。以下六種計算算法時間的多項式是最常用的。 2. 掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM行設(shè)計與分析。 學(xué)習(xí)方法 對于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，難在其中的算法及實現(xiàn)。 最后，就是要掌握內(nèi)部排序算法的基本應(yīng)用，以及算法的實現(xiàn)。在這一部分中，主要要掌握直接插入排序、折半插入排序、冒泡排序(bubble sort)、簡單選擇排序、希爾排序(shell sort)、快速排序、堆排序、二路歸并排序(merge sort)、基數(shù)排序的基本概念和方法?？嫉谋容^多的是折半查找和散列表，我們要掌握它們的基本概念和方法，例如散列表的碰撞如何解決，裝載因子的概念等。