数据结构第二次作业答案

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. 310. 611. 612. 2h+1-1三、判断题1.错 2. 对 3.对 4. 对5. 错6. 对 7. 对 8.错 9四、运算题1.叶子结点数：5单分支结点数：3两分支结点数：2三分支结点数：12.元素 3456 58 6394比较次数2 1 3 44错3.左子树为空的所有单支结点： 15,23,42,44右子树为空的所有单

2、支结点： 304.插入时造成不平衡的结点个数： 45.结点a bcde出度1 1212入度2 21116.(1) 1,3,46,5,2(3分）(2) 1,3,24,5,6(3分）五、算法分析题1.利用"栈"作为辅助存储 , 将队列中的元素逆置（即相反次序放置）2.(1) q = q->lLink(2) return 1(3) return 03.1 t 21 t 32 t34.(1) return PT(2) (PT=ParentPtr(BT->right,BT,X)(3) return NULL 或 return 0六、算法设计题1.float poly(fl

3、oat 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 ;else/ 计算左子树的高度int h1=BTreeHeight(BT->left);/计算右子树的高度int h2=BTreeHeight(BT->right);/返回树的高度if(h1>h2) return h1+1; else return h2+1;int BTreeLeafCoun

4、t(BinTreeNode* BT)if(BT=NULL) return 0;3.else if(BT->left=NULL && BT->right=NULL) return 1;else return BTreeLeafCou nt(BT->left)+BTreeLeafCou nt(BT->right);数据结构第三次作业答案、单项选择题1. D 2. A 3. B4. C 5. C 6. A7. B 8. C 9. C10. A 11. A 12. D 13. C二、填空题1.2i+12.最大值 3. 20.54.右子树 5. 16. 右单旋转

5、7. 2(n-1) 8. 29. n-110.高 11.直接插入三、判断题1. 错 2. 对 3. 对 4. 对 5. 错 6. 对 7. 错 8. 对四、运算题1.(1) 1,5,6,4,3,2(2) 1,5,326,42.顶点:路径长度：016 10142521313.拓扑序列：1,3,6,025,4,74.所有关键活动：<0,1>5,<1,3>10,<3,4>9,<4,5>12关键路径长度：365.(1) 归并路数：5( 2 )需要归并躺数：2 答案解释：(1) 设归并路数为k，初始归并段个数 m = 80 ,根据归并趟数计算公式S = l

6、og km =logk80 = 3得：k3>80。由此解得k>5，即应取的归并路数至少为5。(2) 设多路归并的归并路数为 k,需要k个输入缓冲区和1个输出缓冲区。1个缓冲区 对应1个文件，有 k +1 = 15，因此k = 14，可做14路归并。由 S = log km =丨log仏80 =2。即至少需2趟归并可完成排序。五、算法分析题1.算法功能：当BT中每个结点的左子女的值大于右子女的值则交换左右子树。2.(1)'t '(2)'g'(3)'g'(4)'e'3.35,54,42,73,80,38 4.判断 p2 单

7、链表所代表的集合是否为 p1 单链表所代表的集合的子集合，若是则返回 1 否则返回 0。5. 算法功能：判断二叉树 bt 是否为一棵二叉搜索树，若是则返回 1 否则返回 0。六、算法设计题1.int BTreeEqual(BinTreeNode* T1,BinTreeNode* T2)/ 若两棵树均为空则返回 1 表示相等 if(T1=NULL && T2=NULL) return 1;/若一棵为空一棵不为空则返回 0 表示不等else if(T1=NULL | T2=NULL) return 0;/若根结点值相等并且左、右子树对应相等则两棵树相等else if(T1->

8、data=T2->data && BTreeEqual(T1->left, T2->left) &&BTreeEqual(T1->right, T2->right) ) return 1;/ 若根结点值不等或左、右子树对应不等则两棵树不等 elsereturn 0;另一个参考答案：int BTreeEqual(BinTreeNode* T1,BinTreeNode* T2)/若两棵树均为空或实际上是同一棵树时返回1 表示相等if(T1=T2) return 1;/若一棵为空一棵不为空则返回 0 表示不等if(T1=NULL | T2

9、=NULL) return 0;/ 若根结点值不等返回 0 表示不等 if(T1->data!=T2->data) return 0;/ 若根结点值相等则两棵树是否相等取决于它们的左、右子树是否对应相等 return BTreeEqual(T1->left, T2->left) &&BTreeEqual(T1->right, T2->right);2.BinTreeNode* BTreeCopy(BinTreeNode* BT) if(BT=NULL) return NULL; else / 得到新结点 BinTreeNode* pt=new

10、 BinTreeNode;/复制根结点值pt->data=BT->data;/复制左子树pt->left=BTreeCopy(BT->left);/复制右子树pt->right=BTreeCopy(BT->right);/返回新树的树根指针return pt; 说明：函数体中的 else 可以没有3.int BinSearch(ElemType 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

11、;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. C7. C 8. C 9. B 10. D 11. C 12. C二、填空题1.二路归并2.n/23. 0( nlog6.关键码7.稀疏 8. 500三、判断题1.错2.错3.对 4.对2n) 4. O(n2)5. 39. n/m10. 511.m-15.对6.错7.错 8四、运算题1.(0) 36 25 25* 62 40 53(1) 25* 25 36 62 40 53(2) 2

12、5* 25 36 53 40 62(3) 25*25 36 40 53 622.(0) 30182015 38124453 46 18* 2686(1) 183015201238445318* 462686(2) 151820301238445318* 26 4686(3) 12151820 3038445318* 26 468612151818* 20263038 44 46 5386 3.(1) (1*4+2*3+3)/8=13/8(2) (3+4+2+1 + 1+3+1+1 + 1 + 1+1)/11=19/114.散列表长度m至少为：225答案说明：，则有已知要存储的表项数为n=150

13、，搜索成功的平均搜索长度为ASLsuccASLsucc 二1 1 -2，解得2 I 1 -口丿3又有G =n =色兰2，则m > 225mm35.单关键码结点数：1双关键码结点数：3五、算法分析题1.(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

14、) 10 20 30 40 50 60六、算法设计题1.int Insert(BinTreeNode*& BST, const ElemType& item)插入新结点不插入返回 向左子树插入元素向右子树插入元素 if(BST=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

15、Insert(BST->left, item);else / Insert(BST->right, item);2. c=0; for(j=0; j<size; j+) if(srcj<srci) c+;数据结构第四次作业答案、单项选择题1. C 2. B 3. A 4. C 5. C 6. C7. C 8. C 9. B 10. D 11. C 12. C二、填空题1.二路归并2.n/23. 0( nlog6.关键码7.稀疏 8. 500三、判断题1.错2.错3.对 4.对2n) 4. O(n2)5. 39. n/m10. 511.m-15.对6.错7.错 8四、运算

16、题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) 30182015 38124453 46 18* 2686(1) 183015201238445318* 462686(2) 151820301238445318* 26 4686(3) 12151820 3038445318* 26 468612151818* 20263038 44 46 5386 3.(1) (1*4+2*3+3)/8=13/8(2) (3+4+2+1 + 1+3+1+1 + 1 +

17、 1+1)/11=19/114.散列表长度m至少为：225答案说明：，则有已知要存储的表项数为n=150，搜索成功的平均搜索长度为ASLsuccASLsucc 二1 1 -2，解得2 I 1 -口丿3又有G =n =色兰2，则m > 225mm35.单关键码结点数：1双关键码结点数：3五、算法分析题1.(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=new BinTree