数据结构第二次作业答案

1、数据结构第二次作业答案一、单项选择题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. 先进先出 3. 栈顶指针 4. 队尾5. 一 6. 局部变量 7. 表尾 8. 重数9. 3 10. 6 11. 6 12. 2h+1-1三、判断题1. 错 2. 对 3. 对 4. 对 5. 错 6. 对 7. 对 8. 错 9. 错四、运算题1. 叶子结点数： 5 单分支结点数：3 两分支结点数：2 三分支结点数：12. 元素 34 56 58 63 94 比较次数 2 1 3 4 43. 左子

2、树为空的所有单支结点：15,23,42,44 右子树为空的所有单支结点：304. 插入时造成不平衡的结点个数：4 5. 结点 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. 利用"栈"作为辅助存储,将队列中的元素逆置（即相反次序放置）。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六、算法设计题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并结束递归 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); 数据结构第三次作业答案一、单项选择题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. 右单旋转 7. 2(n-1) 8. 2 9. n-1 10. 高 11. 直接插入三、判断题1. 错 2. 对 3. 对 4. 对 5. 错 6. 对 7. 错 8. 对四、运算题1. (1) 1,5,6,4,3,2 (2) 1,5,3,2,6,42. 顶点： 0 1 2 3 4 5 6 路径长度： 0 16 10 14 25 21 313. 拓扑序列：1,3,6,0,2,5,4,74. 所有关键活动：<0,1>5,<1,3>10

6、,<3,4>9,<4,5>12 关键路径长度：365. （1）归并路数：5 （2）需要归并躺数：2答案解释： (1) 设归并路数为k，初始归并段个数m = 80，根据归并趟数计算公式S = élogkmù = élogk80ù = 3得：k380。由此解得k5，即应取的归并路数至少为5。(2) 设多路归并的归并路数为k，需要k个输入缓冲区和1个输出缓冲区。1个缓冲区对应1个文件，有k +1 = 15，因此k = 14，可做14路归并。由S = élogkmù = élog1480ù = 2。

7、即至少需2趟归并可完成排序。五、算法分析题1. 算法功能：当BT中每个结点的左子女的值大于右子女的值则交换左右子树。2. (1) t (2) g (3) g (4) e3.35,54,42,73,80,38 4. 判断p2单链表所代表的集合是否为p1单链表所代表的集合的子集合，若是则返回1否则返回0。5. 算法功能：判断二叉树bt是否为一棵二叉搜索树，若是则返回1否则返回0。六、算法设计题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; /若根结点值相等并且左、右子树对应相等则两棵树相等 else if(T1->data=T2->data && BTreeEqual(T1->left, T2->left) && BTreeEqual(T1->right, T2->right) ) return 1; /若根结点值不等或左、右子树对应不等则两棵树不等 else return 0; 另一个参考答案： int BTreeEqual(BinTre

9、eNode* T1,BinTreeNode* T2) /若两棵树均为空或实际上是同一棵树时返回1表示相等 if(T1=T2) return 1; /若一棵为空一棵不为空则返回0表示不等 if(T1=NULL | T2=NULL) return 0; /若根结点值不等返回0表示不等 if(T1->data!=T2->data) return 0; /若根结点值相等则两棵树是否相等取决于它们的左、右子树是否对应相等 return BTreeEqual(T1->left, T2->left) && BTreeEqual(T1->right, T2->

10、;right); 2. BinTreeNode* BTreeCopy(BinTreeNode* BT) if(BT=NULL) return NULL; else /得到新结点 BinTreeNode* pt=new BinTreeNode; /复制根结点值 pt->data=BT->data; /复制左子树 pt->left=BTreeCopy(BT->left); /复制右子树 pt->right=BTreeCopy(BT->right); /返回新树的树根指针 return pt; 说明：函数体中的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; 数据结构第四次作业答案一、单项选择题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. 关键码 7. 稀疏 8. 500 9. n/m 10. 5 11. m-1三、判断题1. 错 2. 错 3. 对 4. 对 5. 对 6. 错 7. 错 8. 错四、运算题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答案说明： 已知要存储的表项数为n=150，搜索成功的平均搜索长度为ASLsucc £ 2，则有 ，解得 又有，则 m ³ 225 5. 单关键码结点数：1 双关键码结点数：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六、算法设计题1. int Insert(BinTreeNode*& BST, const ElemType& item) if(BS

15、T=NULL) /插入新结点 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+; 数据结构第四次作业答案一、单项选择题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. 关键码 7. 稀疏 8. 500 9. n/m 10. 5 11. m-1三、判断题1. 错 2. 错 3. 对 4. 对 5. 对 6. 错 7. 错 8. 错四、运算题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答案说明： 已知要存储的表项数为n=150，搜索成功的平均搜索长度为ASLsucc £ 2，则有 ，解得 又有，则 m ³ 225 5. 单关键码结点数：1 双关键码结点数：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六、算法设计题1. int Insert(BinTreeNode*& BST, const ElemType& item) if(BST=NULL) /插入新结点 BinTreeNode* p=ne