数据结构第二次作业答案
- 格式：doc
- 大小：49.00 KB
- 文档页数：9
数据结构第二次作业答案
一、单项选择题
1. C 2. B 3. A 4. A 5. D 6. A
7. 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
三分支结点数：1
2.
元素 34 56 58 63 94
比较次数 2 1 3 4 4
3.
左子树为空的所有单支结点：15,23,42,44
右子树为空的所有单支结点：30
4.
插入时造成不平衡的结点个数：4
5.
结点 a b c d e
出度 1 1 2 1 2
入度 2 2 1 1 1
6.
(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 0
3.
1→2
1→3
2→3
4.
(1) return PT
(2) (PT=ParentPtr(BT->right,BT,X))
(3) return NULL 或return 0
六、算法设计题
1.
float poly(float x, float A[], int n) {
if(!n) return A[0];
else return x*poly(x, A, n-1)+A[n];
}
2.
int BTreeHeight(BinTreeNode* BT)
{
if(BT==NULL)
//对于空树，返回-1并结束递归
return –1;
else
{
//计算左子树的高度
int h1=BTreeHeight(BT->left);
//计算右子树的高度
int h2=BTreeHeight(BT->right);
//返回树的高度
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. A
7. B 8. C 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,4
2.
顶点： 0 1 2 3 4 5 6
路径长度： 0 16 10 14 25 21 31
3.
拓扑序列：1,3,6,0,2,5,4,7
4.
所有关键活动：<0,1>5,<1,3>10,<3,4>9,<4,5>12
关键路径长度：36
5.
（1）归并路数：5 （2）需要归并躺数：2
答案解释：
(1) 设归并路数为k，初始归并段个数m = 80，根据归并趟数计算公式S = logkm =
logk80 = 3得：k3≥80。由此解得k≥5，即应取的归并路数至少为5。
(2) 设多路归并的归并路数为k，需要k个输入缓冲区和1个输出缓冲区。1个缓冲区对应1个文件，有k +1 = 15，因此k = 14，可做14路归并。由S = logkm = log1480 =
2。即至少需2趟归并可完成排序。
五、算法分析题 1.
算法功能：当BT中每个结点的左子女的值大于右子女的值则交换左右子树。
2.
(1) ’t’
(2) ’g’
(3) ’g’
(4) ’e’
3.
{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) return 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(BinTreeNode* 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->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(ElemType R[], int n, KeyType K)
{
int low=0, high=n-1;
while(low<=high)
{
int mid=(low+high)/2;
if(K==R[mid].key) return mid;
else if(K
else low=mid+1;
}
return -1;
}
数据结构第四次作业答案
一、单项选择题
1. C 2. B 3. A 4. C 5. C 6. C
