數(shù)據(jù)結(jié)構(gòu)第二次作業(yè)答案

1、數(shù)據(jù)結(jié)構(gòu)第二次作業(yè)答案一、單項(xiàng)選擇題1. C 2. B 3. A 4. A 5. D 6. A7. D 8. C 9. D 10. C 11. D 12. C 13. A二、填空題1. 存儲 2. 先進(jìn)先出 3. 棧頂指針 4. 隊(duì)尾5. 一 6. 局部變量 7. 表尾 8. 重數(shù)9. 3 10. 6 11. 6 12. 2h+1-1三、判斷題1. 錯 2. 對 3. 對 4. 對 5. 錯 6. 對 7. 對 8. 錯 9. 錯四、運(yùn)算題1. 葉子結(jié)點(diǎn)數(shù)： 5 單分支結(jié)點(diǎn)數(shù)：3 兩分支結(jié)點(diǎn)數(shù)：2 三分支結(jié)點(diǎn)數(shù)：12. 元素 34 56 58 63 94 比較次數(shù) 2 1 3 4 43. 左子

2、樹為空的所有單支結(jié)點(diǎn)：15,23,42,44 右子樹為空的所有單支結(jié)點(diǎn)：304. 插入時造成不平衡的結(jié)點(diǎn)個數(shù)：4 5. 結(jié)點(diǎn) a b c d e 出度 1 1 2 1 2 入度 2 2 1 1 16. (1) 1,3,4,6,5,2 (3分) (2) 1,3,2,4,5,6 (3分)五、算法分析題1. 利用"棧"作為輔助存儲,將隊(duì)列中的元素逆置（即相反次序放置）。2. (1) q = q->lLink (2) return 1 (3) return 03. 12 13 23 4. (1) return PT (2) (PT=ParentPtr(BT->right

3、,BT,X) (3) return NULL 或return 0六、算法設(shè)計題1. float poly(float x, float A, int n) if(!n) return A0; else return x*poly(x, A, n-1)+An;2. int BTreeHeight(BinTreeNode* BT) if(BT=NULL) /對于空樹，返回-1并結(jié)束遞歸 return 1; else /計算左子樹的高度 int h1=BTreeHeight(BT->left); /計算右子樹的高度 int h2=BTreeHeight(BT->right); /返回樹的

4、高度 if(h1>h2) return h1+1; else return h2+1; 3. int BTreeLeafCount(BinTreeNode* BT) if(BT=NULL) return 0; else if(BT->left=NULL && BT->right=NULL) return 1; else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right); 數(shù)據(jù)結(jié)構(gòu)第三次作業(yè)答案一、單項(xiàng)選擇題1. D 2. A 3. B 4. C 5. C 6. A7. B 8. C

5、9. C 10. A 11. A 12. D 13. C二、填空題1. 2i+1 2. 最大值 3. 20.5 4. 右子樹 5. 1 6. 右單旋轉(zhuǎn) 7. 2(n-1) 8. 2 9. n-1 10. 高 11. 直接插入三、判斷題1. 錯 2. 對 3. 對 4. 對 5. 錯 6. 對 7. 錯 8. 對四、運(yùn)算題1. (1) 1,5,6,4,3,2 (2) 1,5,3,2,6,42. 頂點(diǎn)： 0 1 2 3 4 5 6 路徑長度： 0 16 10 14 25 21 313. 拓?fù)湫蛄校?,3,6,0,2,5,4,74. 所有關(guān)鍵活動：<0,1>5,<1,3>10

6、,<3,4>9,<4,5>12 關(guān)鍵路徑長度：365. （1）歸并路數(shù)：5 （2）需要?dú)w并躺數(shù)：2答案解釋： (1) 設(shè)歸并路數(shù)為k，初始?xì)w并段個數(shù)m = 80，根據(jù)歸并趟數(shù)計算公式S = élogkmù = élogk80ù = 3得：k380。由此解得k5，即應(yīng)取的歸并路數(shù)至少為5。(2) 設(shè)多路歸并的歸并路數(shù)為k，需要k個輸入緩沖區(qū)和1個輸出緩沖區(qū)。1個緩沖區(qū)對應(yīng)1個文件，有k +1 = 15，因此k = 14，可做14路歸并。由S = élogkmù = élog1480ù = 2。

7、即至少需2趟歸并可完成排序。五、算法分析題1. 算法功能：當(dāng)BT中每個結(jié)點(diǎn)的左子女的值大于右子女的值則交換左右子樹。2. (1) t (2) g (3) g (4) e3.35,54,42,73,80,38 4. 判斷p2單鏈表所代表的集合是否為p1單鏈表所代表的集合的子集合，若是則返回1否則返回0。5. 算法功能：判斷二叉樹bt是否為一棵二叉搜索樹，若是則返回1否則返回0。六、算法設(shè)計題1. int BTreeEqual(BinTreeNode* T1,BinTreeNode* T2) /若兩棵樹均為空則返回1表示相等 if(T1=NULL && T2=NULL) retur

8、n 1; /若一棵為空一棵不為空則返回0表示不等 else if(T1=NULL | T2=NULL) return 0; /若根結(jié)點(diǎn)值相等并且左、右子樹對應(yīng)相等則兩棵樹相等 else if(T1->data=T2->data && BTreeEqual(T1->left, T2->left) && BTreeEqual(T1->right, T2->right) ) return 1; /若根結(jié)點(diǎn)值不等或左、右子樹對應(yīng)不等則兩棵樹不等 else return 0; 另一個參考答案： int BTreeEqual(BinTre

9、eNode* T1,BinTreeNode* T2) /若兩棵樹均為空或?qū)嶋H上是同一棵樹時返回1表示相等 if(T1=T2) return 1; /若一棵為空一棵不為空則返回0表示不等 if(T1=NULL | T2=NULL) return 0; /若根結(jié)點(diǎn)值不等返回0表示不等 if(T1->data!=T2->data) return 0; /若根結(jié)點(diǎn)值相等則兩棵樹是否相等取決于它們的左、右子樹是否對應(yīng)相等 return BTreeEqual(T1->left, T2->left) && BTreeEqual(T1->right, T2->

10、;right); 2. BinTreeNode* BTreeCopy(BinTreeNode* BT) if(BT=NULL) return NULL; else /得到新結(jié)點(diǎn) BinTreeNode* pt=new BinTreeNode; /復(fù)制根結(jié)點(diǎn)值 pt->data=BT->data; /復(fù)制左子樹 pt->left=BTreeCopy(BT->left); /復(fù)制右子樹 pt->right=BTreeCopy(BT->right); /返回新樹的樹根指針 return pt; 說明：函數(shù)體中的else可以沒有3. int BinSearch(El

11、emType R, int n, KeyType K) int low=0, high=n-1; while(low<=high) int mid=(low+high)/2; if(K=Rmid.key) return mid; else if(K<Rmid.key) high=mid-1; else low=mid+1; return -1; 數(shù)據(jù)結(jié)構(gòu)第四次作業(yè)答案一、單項(xiàng)選擇題1. C 2. B 3. A 4. C 5. C 6. C 7. C 8. C 9. B 10. D 11. C 12. C二、填空題1. 二路歸并 2. n/2 3. O(nlog2n) 4. O(n2

12、) 5. 36. 關(guān)鍵碼 7. 稀疏 8. 500 9. n/m 10. 5 11. m-1三、判斷題1. 錯 2. 錯 3. 對 4. 對 5. 對 6. 錯 7. 錯 8. 錯四、運(yùn)算題1. (0) 36 25 25* 62 40 53 (1) 25* 25 36 62 40 53 (2) 25* 25 36 53 40 62 (3) 25* 25 36 40 53 622. (0) 30 18 20 15 38 12 44 53 46 18* 26 86 (1) 18 3015 2012 3844 5318* 4626 86 (2) 15 18 20 3012 38 44 5318* 2

13、6 46 86 (3) 12 15 18 20 30 38 44 5318* 26 46 86 (4) 12 15 18 18* 20 26 30 38 44 46 53 86 3. (1) (1*4+2*3+3)/8=13/8 (2) (3+4+2+1+1+3+1+1+1+1+1)/11=19/11 4. 散列表長度m至少為：225答案說明： 已知要存儲的表項(xiàng)數(shù)為n=150，搜索成功的平均搜索長度為ASLsucc £ 2，則有 ，解得 又有，則 m ³ 225 5. 單關(guān)鍵碼結(jié)點(diǎn)數(shù)：1 雙關(guān)鍵碼結(jié)點(diǎn)數(shù)：3 五、算法分析題1. (1) 0 (2) p=p->link

14、(3) Degreep->dest+ 2. (1) sj=temp (2) seqi<pivot (3) Exchange(seq, low, pivotpos)3. (1) dataList<T> (2) currentSize (3) k=j4. (0) 30 20 40 10 60 50 (1) 20 30 10 40 50 60 (2) 20 10 30 40 50 60 (3) 10 20 30 40 50 60六、算法設(shè)計題1. int Insert(BinTreeNode*& BST, const ElemType& item) if(BS

15、T=NULL) /插入新結(jié)點(diǎn) BinTreeNode* p=new BinTreeNode; p->data=item; p->left=p->right=NULL; BST=p; return 1; else if(item=BST->data) return 0; /不插入返回 else if(item<BST->data) /向左子樹插入元素 return Insert(BST->left, item); else /向右子樹插入元素 Insert(BST->right, item); 2. c=0; for(j=0; j<size;

16、 j+) if(srcj<srci) c+; 數(shù)據(jù)結(jié)構(gòu)第四次作業(yè)答案一、單項(xiàng)選擇題1. C 2. B 3. A 4. C 5. C 6. C 7. C 8. C 9. B 10. D 11. C 12. C二、填空題1. 二路歸并 2. n/2 3. O(nlog2n) 4. O(n2) 5. 36. 關(guān)鍵碼 7. 稀疏 8. 500 9. n/m 10. 5 11. m-1三、判斷題1. 錯 2. 錯 3. 對 4. 對 5. 對 6. 錯 7. 錯 8. 錯四、運(yùn)算題1. (0) 36 25 25* 62 40 53 (1) 25* 25 36 62 40 53 (2) 25* 25

17、 36 53 40 62 (3) 25* 25 36 40 53 622. (0) 30 18 20 15 38 12 44 53 46 18* 26 86 (1) 18 3015 2012 3844 5318* 4626 86 (2) 15 18 20 3012 38 44 5318* 26 46 86 (3) 12 15 18 20 30 38 44 5318* 26 46 86 (4) 12 15 18 18* 20 26 30 38 44 46 53 86 3. (1) (1*4+2*3+3)/8=13/8 (2) (3+4+2+1+1+3+1+1+1+1+1)/11=19/11 4.

18、 散列表長度m至少為：225答案說明： 已知要存儲的表項(xiàng)數(shù)為n=150，搜索成功的平均搜索長度為ASLsucc £ 2，則有 ，解得 又有，則 m ³ 225 5. 單關(guān)鍵碼結(jié)點(diǎn)數(shù)：1 雙關(guān)鍵碼結(jié)點(diǎn)數(shù)：3 五、算法分析題1. (1) 0 (2) p=p->link (3) Degreep->dest+ 2. (1) sj=temp (2) seqi<pivot (3) Exchange(seq, low, pivotpos)3. (1) dataList<T> (2) currentSize (3) k=j4. (0) 30 20 40 10 60 50 (1) 20 30 10 40 50 60 (2) 20 10 30 40 50 60 (3) 10 20 30 40 50 60六、算法設(shè)計題1. int Insert(BinTreeNode*& BST, const ElemType& item) if(BST=NULL) /插入新結(jié)點(diǎn) BinTreeNode* p=ne