1、第12-13作業 B B+樹以及圖10.8 給出把值55與46插入下圖的2-3樹中的結果。第十二次作業-圖10.9給定一組記錄，其關鍵碼值是字母，記錄按照下面的順序插入：C,S,D,T,A,M,P,B,W,N,G,U,R,K,E,H,O,L,J給出插入這些記錄后的2-3樹。 10.11給出把值55插入圖10.17中B樹的結果。10.12給出把值1,2,3,4,5,6(按照這個順序)插入圖10.16中B+樹的結果。 10.13給出把值18,19和20(按照這個順序)插入圖10.2(b)的B+樹中刪除的結果。10.15假定有一個B+樹，它的內部節點，可以存儲多達100個子女，葉節點可以存儲多達15

2、條記錄，對于1,2,3,4,和5層B+樹，能夠存儲的最大記錄數和最小記錄數是多少？ 那么：內部節點的孩子節點個數為：50,100 葉子節點的記錄數為1,15當層數為1時，根節點充當葉子節點，最少記錄數為0，最多記錄數為15；當再來一個記錄時，根節點要分裂為兩層，變為內部節點，此時記錄數16是層數為2時最少的情況，最多的即為根節點和葉子節點均存滿;以此類推分析：B+樹中所有葉子節點在同一層，根節點最少有兩棵子樹，其余分支節點的子樹個數為m/2到m;也就是題目中的階數m為100;期中考試：算法設計題：利用棧，判斷一個字符串s是否是回文，若是返回1,否則返回0;回文是指第一 個字符與最后一個相同，第

3、二個字符與倒數第二個相同，依此類推。如：“abba”是回文，“abab”不是回文。空串和長度為1的串都是回文。可以直接使用如下定義中的基本操作。棧的ADT定義如下： template class Stack public: void clear();bool push(const T item);bool pop(T&);bool topValue(T&);bool isEmpty();bool isFull(); 層數層數最少記錄數最少記錄數最大記錄數最大記錄數101521615*100316*5015*(100*100)416*(50*50)15*(100*100*100)

4、516*(50*50*50)15*(100*100*100*100)中期代碼：bool checkString(string s)Stack T;string s1=; for(int i=0;ileftchild=null)return 1;for(TreeNode *temp=root-LeftChild;temp;temp=temp-RightSibling)count+=leavesCount(temp);return count11.8對于11.26中的圖，給出從頂點4開始出發，使用Dijkstra最短路徑算法產生的最短路徑表，請向圖11.19所示一樣，每處理一個頂點時給出相應D值。

5、第十四次作業-圖Dijkstra算法的流程為： 初始狀態下，源頂點為4，除了頂點4，其余各個頂點的最短路徑長度初值均為無窮大； 處理完頂點4后，其相鄰頂點的最短路徑長度被更新為到4的直接距離； 再選定當前離4最近的頂點作為下一個頂點，再更新余下頂點的值； 依次類推；結果如下所示：11.17對于11.26中的圖，給出從頂點3開始使用Prim的MST(最小支撐樹：包含所有頂點以及一部分邊的樹，保證連通且所有權重最小)算法時各個邊的訪問順序，并且給出最終的MST。Prim的MST的流程為： 從圖中任意一個頂點N開始，題目中是指定頂點3即N為3，初始化MST為N，選出與N相關聯的邊中權值最小的一條邊，

6、其起始頂點則為N，M，則將(N,M)加入MST； 再選擇與頂點N,M相關聯的邊中權值最小的一條邊，連接的新頂點為S,將S以及新邊加入MST中； 依次類推；結果如下所示：最終的MST為：（，）（，）（，）（，）（，）以下為圖的補充作業一、單項選擇題1下面（B）可以判斷出一個有向圖中是否有環（回路）？A）求關鍵路徑B）拓撲排序C）求最短路徑D）前面都不正確二、綜合題1設有帶權無向圖G如下圖所示：(講解)試給出： （1）從V1開始的深度優先遍歷；（2）從V1開始的廣度優先遍歷；（3）從V1開始執行的普里姆（Prim）算法過程中所選邊的序列。答案：（1）深度優先類似二叉樹的根左右遍歷，遍歷結果為V1,

7、V2,V4,V8,V5,V3,V6,V7（2）廣度優先類似二叉樹的層次遍歷，遍歷結果為V1,V2,V3,V4,V5,V6,V7,V8（3）所選邊的序列為：(V1,V3),(V3,V6)(V3,V7)(V1,V2)(V2,V5),(V2,V4)(V5,V8)2給出如下圖所示的所有拓撲有序序列。答案：A-C-B-D-E不唯一 3.對于有n個頂點的無向圖，采用鄰接矩陣表示，如何判斷以下問題： 圖中有多少條邊？任意兩個頂點i和j之間是否有邊相連？任意一個頂點的度是多少？答案：(1)無線圖的鄰接矩陣一定是對稱的，那么矩陣的主對角線以上部分中有多少元素就代表圖中的邊樹。設m為矩陣中非零元素的個數 無向圖的邊數=m/2(2)對于無向圖，在矩陣