电大文库【数据结构】形成性考核册答案 上一篇：《数据结构(专)》形成性考核册及 下一篇：暂无
注：本答案仅供参考，如有错误敬请指正
来源：【电大文库】http://www.diandawenku.com/
电大文库【数据结构】形考作业一：
一、单项选择题
1. A 2. D 3. B 4. D 5. C 6. A
7. C 8. A 9. A 10. A 11. D 12. D
二、填空题
1. 存储结构 2. 数据结构 3. 继承 4. 数据类型
5. 静态 6. LOC(0,0)+(i*n+j)*d 7. (2n-I-1)*I/2+J 8. 16
9. 删除 10. 不一定 11. 删除
三、判断题
1. 错 2. 错 3. 错 4. 对 5. 对 6. 错 7. 对 8. 对
四、运算题
1. (i - j) * (n - 1) * d
解释：
按行存储时与按列存储时，计算A[j]地址的公式分别为
LOC(i,j)=LOC(0,0)+(i*n+j)*d
及 LOC'(i,j)=LOC(0,0)+(j*n+i)*d
两者相减，得
LOC(i,j)-LOC'(i,j)=LOC(0,0)+(i*n+j)*d-LOC(0,0)-(j*n+i)*d
=(i-j)*(n-1)*d
2. 41
解释：
根据题意，矩阵A中当元素下标I与J满足I≥J时，任意元素A[I][J]在一维数组B中的存放位置为
I * (I + 1) / 2 + J
因此，A[8][5]在数组B中位置为
8 * (8 + 1) / 2 + 5 = 41
3. 1208
解释：
对于二维数组，若第一、第二维的元素个数为m和n，每个元素所占存储字数为d，首地址为LOC(0, 0)，则对于任一数组元素A[j]，它的存储地址为：
LOC(i, j) = LOC(0, 0) + (i * n + j) * d
根据题意，LOC(8, 4) = LOC(0, 0) + (8 * 6 + 4) * 4 = 1000 + 52 * 4 = 1208
4.
前序：A,B,D,G,C,E,F
中序：B,G,D,A,E,C,F
按层：A,B,C,D,E,F,G
5.
先根序列：a,b,c,d,e,f,g,h,i,j
五、算法分析题
1.
功能为： 矩阵相乘，即a[M][N]×b[N][L]→c[M][L]。
时间复杂性为：O(M×N×L)
2.
算法执行的结果是：函数返回值等于5。该算法即字符串的模式匹配。
3.
计算单链表的长度或计算单链表中结点的个数
4.
运行结果：stack
六、算法设计题
1.
template
void merge ( SeqList& A, SeqList& B, SeqList& C ) {
int m = A.Length( ), n = B.Length( ), mpn = m + n;
if ( mpn > C.maxLength( ) )
cerr << "合并后表的长度超出表C的最大允许长度" << endl;
exit (1);
int i=0, j=0, k=0, av=A.getData(i), bv=B.getData(j);
while(i
if(av>=bv)C.setData(k++, bv); bv=B.getData(++j);
}
if(i
2.
while ( p != NULL) {
if(p->data >= min && p->data <=max)
q->link=p->link; delete p; p=q->link;
else q=p; p=p->link;
}
3.
// 将x插入至队尾
if (Q.rear == Q.front && Q.tag == 1) return false;
Q.elem[Q.rear] = x;
Q.rear = (Q.rear+1) % M;
if (Q.rear == Q.front) Q.tag = 1;
return true;
// 删除队头元素
if (Q.front == Q.rear && Q.tag == 0) return false;
x = Q.elem[Q.front];
Q.front = (Q.front+1) % M;
if (Q.front == Q.rear) Q.tag = 0;
return true;
电大文库【数据结构】形考作业二：
一、单项选择题
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 = elogkmu = elogk80u = 3得：k3≥80。由此解得k≥5，即应取的归并路数至少为5。
(2) 设多路归并的归并路数为k，需要k个输入缓冲区和1个输出缓冲区。1个缓冲区对应1个文件，有k +1 = 15，因此k = 14，可做14路归并。由S = elogkmu = elog1480u = 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)
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
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