【文章內容簡介】 rintf((%d,%d),i,degree)。 } }(2)本題的算法思想是：計算出整個鄰接表中所具有的結點為i的結點數(shù)，這就是i頂點的入度。求頂點的入度數(shù)的算法：int indegree(adjlist adj,int n,int v){ int i,j,degree。 edgenode *p。 for(i=0。in。i++) { p=adj[i].link。 while(p!=NULL){ if(padjvex==v) degree++。 p=pnext。 } } return degree。} void printin(adjlist adj,int n){ int i,degree。 printf(The indegrees are:\n)。 for(i=0。in。i++) { degree=indegree(adj,n,i)。 printf((%d,%d),i,degree)。 }}(3)求最大出度的算法：void maxoutdegree(adjlist adj,int n){ int maxdegree=0,maxv=0, degree, i。 for(i=0。in。i++) { degree=outdegree(adj,i)。if(degreemaxdegree) { maxdegree=degree。 maxv=i。 } } printf(maxoutdegree = %d, maxvertex = %d,maxdegree,maxv)。}(4)求出度數(shù)為0的頂點數(shù)的算法： int outzero(adjlist adj,int n){ int num=0,i。 for(i=0。in。i++) { if(outdegree(adj,i)==0) num++。 } return num。}第六章一、基礎知識題1. ： 1）哪個是根結點？ 2）哪些是葉子結點？ 3）哪個是E的父結點？ 4）哪些是E的子孫結點？ 5）哪些是E的兄弟結點？哪些是C的兄弟結點？ 6）結點B和結點I的層數(shù)分別是多少？ 7）樹的深度是多少？ 8）以結點G為根的子樹的深度是多少？ 9）樹的度是多少？答：1）A是根結點2）D、H、I、J、F、G是葉子結點3）B是E的父結點4）H、I、J是E的子孫結點5）D是E的兄弟結點，B是C的兄弟結點6）B的層數(shù)是2，I的層數(shù)是47）樹的深度是48）以結點G為根的子樹的深度是19）樹的度是3 。答：3個結點的樹： 3個結點的二叉樹：3. 高度為h的完全二叉樹至少有多少個結點？最多有多少個結點？答：高度為h的完全二叉樹至少有個結點，最多有個結點。4. 。答：該二叉樹的順序存儲：該二叉樹的鏈式存儲：5. 、中序和后序遍歷序列。圖22答：先序遍歷序列：9中序遍歷序列：9后序遍歷序列：1 。 1)已知一個二叉樹的中序和后序遍歷序列分別為GDHBAECIF和GHDBEIFCA，請畫出此二叉樹。 2)已知一個二叉樹的前序和中序分別為ABCDEFGH和BDCEAFHG，請畫出此二叉樹。答：7. ,分別寫出其前序、中序、后序的遍歷序列。答：先序遍歷序列：A、B、D、E、F、C、G中序遍歷序列：D、F、E、B、A、G、C后序遍歷序列：F、E、D、B、G、C、A {55,34,18,88,119,11,76,9,97,99,46}，試構造一個二叉排序樹。9. 有一份電文中共使用5個字符：a、b、c、d、e，它們的出現(xiàn)頻率依次為4。試畫出對應的哈夫曼樹，并求出每個字符的哈夫曼編碼。第8題 各字符對應的哈夫曼編碼如下： a: 10, b: 001, c: 000, d: 11, e: 01二、算法設計題答案 ，分別給出求二叉樹結點總數(shù)和葉子結點總數(shù)的算法。解：求二叉樹結點總數(shù)的算法如下： int CountNode(btree *t,int num) /*num初值為0*/{ if(t!=NULL) 36 { num++。 num=CountNode(tleft,num)。 num=CountNode(tright,num)。 } return num。}求二叉樹葉子結點總數(shù)的算法如下：int CountLeaf(btree *t,int num) /*num初值為0*/{ if(t!=NULL) { if(tleft==NULL amp。amp。 tright==NULL) num++。 num=CountLeaf(tleft,num)。 num=CountLeaf(tright,num)。 } return num。}2. 2. 一個二叉樹以鏈式結構存儲，寫出在二叉樹中查找值為x的結點的算法。解：本題可以用先序、中序和后序遍歷中的任意一種遍歷，只要將遍歷算法中的訪問根結點改為判斷其值是否等于x。下面是用中序遍歷求解的算法，函數(shù)返回值為x的結點的地址，若沒有找到則返回空。 btree *search(btree *t,int x,btree p) /*p的初值為NULL*/ { if(t!=NULL) { p=search(tleft,x,p)。 if(tdata==x) p=t。 /*找到x的地址放在p中*/ p=search(tright,x,p)。 } return p。}3. 設計一個算法將一個以鏈式存儲結構的二叉樹，按順序方式存儲到一維數(shù)組中。解：這是一個遞歸算法，如下： void create(btree *t,int tree[],int i) { if(t!=NULL) { tree[i]=tdata。 create(tleft,tree,2*i)。 create(tright,tree,2*i+1)。 }}4. 假設二叉排序樹t的各元素值均不相同，設計一個算法按遞增次序打印各元素值。解：按中序序列遍歷二叉排序樹即按遞增次序遍歷，所以遞增打印二叉排序樹各元素值的函數(shù)如下： void inorder(btree *t) { if(t!=NULL) { inorder(tleft)。 printf(%d,tdata)。 inorder(tright)。 } }5. 已知一個中序線索二叉樹，試編寫中序遍歷的非遞歸算法。解：在中序線索二叉樹中進行非遞歸中序遍歷，只要從頭結點出發(fā)，反復找到結點的后繼，直至結束即可。在中序線索二叉樹中求結點后繼的算法如下： tbtree *succ(tbtree *p) { btree *q。 if(prtag==1) return (pright)。else { q=pright。 while(qltag==0) q=qleft。 return(q)。 }}由此得到中序遍歷線索二叉樹的非遞歸算法如下： void thinorder(tbtree *p) { if(p!=NULL) { while(pltag==0) p=pleft。 do{ printf(%d,pdata)。 p=succ(p)。 }while(p!=NULL)。 }}第五章A[10][20]采用列為主序存儲,每個元素占1個單元,A[0][0]的地址為200,則A[6][12]的地址是多少? 3262. 稀疏矩陣mn采用三元組順序表存儲結構,非零元個數(shù)tu滿足什么條件時,該存儲結構才有意義?tum*n/33. 二維數(shù)組A[10..20][5..10]采用行為主序存儲,每個元素占4個單元,A[10][5]的地址為1000,則A[18][9]的地址是多少?(1208)4. 稀疏矩陣的三元組順序表存儲結構是隨機存儲結構嗎?為什么?(不是)5. 廣義表((a,b,c,d))的表頭和表尾分別是什么?（(a,b,c,d)?？毡恚?. 廣義表((a),((b),c),(((d))))的長度和深度分別是多少? （3，4）第一章數(shù)據(jù)物理結構 算法 二、簡答 一、名詞解釋數(shù)據(jù)：就是一切能夠由計算機接受和處理的對象。數(shù)據(jù)項：是數(shù)據(jù)的不可分割的最小單位，在有些場合下，數(shù)據(jù)項又稱為字段或域。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在程序中作為一個整體加以考慮和處理，也稱為元素、頂點或記錄。它可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)結構：指的是數(shù)據(jù)之間的相互關系，即數(shù)據(jù)的組織形式，它包括數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構和數(shù)據(jù)的運算三個方面的內容。數(shù)據(jù)邏輯結構：是指數(shù)據(jù)元素之間的邏輯關系，是從邏輯上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關，獨立于計算機。數(shù)據(jù)物理結構：是指數(shù)據(jù)元素及其關系在計算機存儲器內的表示，是數(shù)據(jù)的邏輯結構用計算機語言的實現(xiàn)，是依賴于計算機語言的。算法：是對特定問題求解步驟的一種描述。它是一個有窮的規(guī)則序列，這些規(guī)則決定了解決某一特定問題的一系列運算。由此問題相關的一定輸入，計算機依照這些規(guī)則進行計算和處理，經(jīng)過有限的計算步驟后能得到一定的輸出。算法的時間復雜性：是該算法的時間耗費，它是該算法所求解問題規(guī)模n的函數(shù)。當n趨向無窮大時，我們把時間復雜性T(n)的數(shù)量級稱為算法的漸進時間復雜性。二、簡答題1. 算法分析的目的是什么？ 答：對算法進行分析的目的有兩個：第一個目的是可以從解決同一問題的不同算法中區(qū)分相對優(yōu)劣，選出較為適用的一種；第二個目的是有助于設計人員考慮對現(xiàn)有算法進行改進或設計出新的算法。2. 什么是算法的最壞和平均時間復雜性？ 答：算法的最壞時間復雜性是研究各種輸入中運算最慢的一種情況下的運算時間；平均時間復雜性是研究同樣的n值時各種可能的輸入，取它們運算時間的平均值。三、答案1．三、分析下列算法的時間復雜性: 1．sum=0。 for (i=1。i=n。i++) { sum=sum+i。 } 答：該程序段的時間復雜性為T(n)=O(n)。2．2．i=1。 while(i=n) i=i*10。 1*10 for(j=0。jn。j++) 答：該程序段的時間復雜性T(n)=O(log10n)。3．3．sum=0。 for(i=0。in。i++) sum=sum+Array[i][j]。 答：該程序段的時間復雜性(n)=O(n2)。第二章一、基礎知識題一、基本知識題答案1． 1. 試比較順序表與鏈表的優(yōu)缺點。的操作。 答：順序表用結點物理位置的相鄰性來反映結點間的邏輯關系，其優(yōu)點是：節(jié)省存儲、隨機存取，當表長變化較小，主要操作是進行查找時，宜采用順序表。鏈表用附加的指針來反映結點間的邏輯關系，插入和刪除操作相對比較方便，當表長變化較大，主要操作是進行插入和刪除時，宜采用鏈表。2. 2. 試分析單鏈表與雙鏈表的優(yōu)缺點。 答：雙鏈表比單鏈表多增加了一個指針域以指向結點的直接前趨，它是一種對稱結構，因此在已知某個結點之前或之后插入一個新結點、刪除該結點或其直接后繼都同樣方便,操作的時間復雜度為O(1)；而單鏈表是單向結構，對于找一個結點的直接前趨的操作要從開始結點找起，其時間復雜度為O(n)。3. 3. 為什么在單循環(huán)鏈表中設置尾指針比設置頭指針更好？ 答：由于對表的操作常常在表的兩端進行，所以對單循環(huán)鏈表，當知道尾指針rear后，其另一端的頭指針是rearnextnext（表中帶頭結點）。這會使操作變的更加容易。 4. 4. 寫出在循環(huán)雙鏈表中的p所指結點之后插入