中國海洋大學2012-2013學年期末考試試題及參考答案學年第2學期試題名稱:數據結構（A卷）專業年級：計算機學號姓名授課教師名分數一、解答下列各題（40分，每小題8分）1.已知下圖為廣義表的存儲結構圖，寫出該圖表示的廣義表，并求該廣義表的長度和深度。listlist2?對下圖所示有向圖，利用Dijkstra算法求出從頂點A到其它各頂點的最短路徑及距離。已知一棵3階B-樹如下圖所示，分別畫出插入關鍵字20后和刪除關鍵字150后得到的B-樹。

已知序列｛503，87，512，61，908，170，897，275，653，462｝將其調整為堆(大堆頂，即K>=K,K>=K)。i2ii2i+1將下列森林轉換為相應的二叉樹，并加上指向前驅和后繼的中序線索。C8J二、判斷題：正確的打"，錯誤的打X(每題1分，共15分)1、線性表采用鏈表存儲時，結點和結點內部的存儲空間可以是不連續的。()2．在線性表的順序存儲結構中，插入和刪除元素時，移動元素的個數與該元素的位置有關。()3．順序存儲的線性表可以隨機存取。()4．若一個廣義表的表頭為空表，則此廣義表亦為空表。()5．任何一個非空廣義表，其表頭可能是單元素或廣義表，其表尾必定是廣義表。()6．廣義表是由零或多個原子或子表所組成的有限序列，所以廣義表可能為空表。()7．用樹的前序遍歷和中序遍歷可以導出樹的后序遍歷。()8．在哈夫曼編碼中，當兩個字符出現的頻率相同時，其編碼也相同，對于這種情況應特殊處理。()9．將一棵樹轉換成二叉樹后，根結點沒有左子樹。()10.在n個結點的無向圖中，若邊數〉n-1，則該圖必是連通圖。()11．一個圖的廣度優先遍歷生成樹是唯一的()12．對兩棵具有相同關鍵字集合而形狀不同的二叉排序樹，按中序遍歷它們得到的順序是一樣的。()13．負載因子(裝填因子)是散列表的一個重要參數，它反映散列表的裝滿程度。()14．對一個堆，按二叉樹層次進行遍歷可以得到一個有序序列。()15.對于n個記錄的集合進行冒泡排序，在最壞情況下所需要的時間是O(n2)。()三＞(15分)已知一棵度為M的樹中有n1個度為1的結點，2個度為的2結點，???nm個度為m的結點，證明其葉結點個數為1+￡(i-1)ni。i=1四、(15分)試編寫一個高效算法，查找未排序文件A(1..n)中的第K個最小的元素，并分析你的算法的時間復雜度。注：第K個最小的元素：若M是A(1),A(2),…,A(n)中的第K個最小的元素，則A(1),A(2),…,A(n)中至少有K個元素小于等于M，并且最多有K-1個元素小于M。五、(15分)試寫一個判定所給定二叉樹是否為二叉排序樹的算法，設此二叉樹以二叉鏈表為存儲結構，且樹中結點的關鍵字均不同。期末考試試題參考答案科目名稱：數據結構、1.廣義表為：list=(((a,b,()),()),(a,(b)),())長度為3深度為32、從頂點A到其他個頂點的最短路徑及距離為：C:A>C15B:A>C>B19F:A—>C-->F25E:A-->c-一〉B——>E29D:A-->c-->F-—>D293?①插入(20)后的3階B-樹如圖所示。②再刪除(150)后的3階B-樹如下圖所示。4.初始堆為：”908、/653、897、/503、462170/5122756187Z5.對應二叉樹為:二、答案：X2.V3.V4.X5.V6.V7.V8.X9.X10.XTOC\o"1-5"\h\zX12.V13.V14.X15.V三、答案依題意：設n為總的節點個數，叫為葉子結點(即度為0的結點)的個數,則有：°n=n+n+n+…+口①012m又有：n-1=度的總數，即：n-1=n*l+n*2+???+n*m②12m①-②式得：1=n-n-2n-(m-1)n012m則有：n=1+n+2n???+(mT)n023m=1+￡(i-1)nii=1共共4頁第3頁四、思想：調用一趟快速排序以后，有P-1(P:軸元素位置)個元素小于等于軸元素，且n-P個元素大于等于軸元素，若KvP,則第K個最小元素在A(1..P-1)中；若心卩，則A(P)就是第K個最小元素；若K>P,則A(1..n)中的第K個最小元素就是A(P+1..n)中的第(K-P)個最小元素。PROCEDUREqpass(R:listtype;lqw,hig:integer;vardivinteger)Begini=low;j:=hig;x:=R[I];whileI<jdo[while(i<j)and(R[j]>x)doj:=j-1R[i]:=R[j];While(i<j)and(R[i]<=x)doI:=i+1R[j]:=R[i]]R[I]:=x;div:=I;End;proceduresearch_k(ls:listtype,l,h,k:iinteger;varkey:integer)BeginIfl=hthenkey:=ls(l)Else[qpass(ls,l,h,p)Ifk<=p-1thensearch_k(ls,l,p-1,k,key)Elseifk=pthenkey=ls(p)Elsesearch_k(ls,p+l,h,k-p,key)]End.五、解答：為判定二叉樹是否為二叉排序樹同樣是建立在中序遍歷的框架基礎下，遍歷中附設一指針pre指向當前訪問結點的中序直接前驅，每訪問一個結點便比較前驅結點pre和此結點是否有序，若遍歷結束后各結點和其中序直接前驅均滿足有序，則此二叉樹為二叉排序樹；否則只要有一個結點不滿足，那么此二叉樹就不是二叉排序樹。VoidBisortTree(BiTreeT,BiTree&pre,bool&flag){〃初始時pre=NULL,flag=true；若結束時flag為true,則此二叉樹是二叉排序樹if(T&&flag){BiSortTree(T->lchild,pre,flag);If(pre==NULL){〃訪問中序序列的一個結點，不需要比較Flag=true;Pre=T;}else{//比較T與中序直接前驅pre的大小，這里假定沒有相同的關鍵