数据结构试题3参考答案.doc

数据结构期未试卷 2 参考答案 数据结构自测试题三 参考解答及评分标准 一、单项选择题，在括号内填写所选择的标号（每小题 2 分，共 20 分） 1. B 2. C 3. C 4. D 5. B 6. D 7. B 8. C 9. D 10. D 二、填空题，在横线处填写合适内容（每小题 1 分，共 12 分） 1. 链接 2. 动态 3. 删除 4. 后出先进 5. 递归 6. 3 7. 右 8. 左子树 9. 2 10. 交换 11. O(log2n) 12. 500 三、判断题，在每小题前面打对号或打叉号（每小题 1 分，共 10 分） 1. 对 2. 对 3. 错 4. 错 5. 对 6. 对 7. 错 8. 错 9. 错 10. 错. 四、运算题（前 2 小题，每小题 6 分，后 3 小题，每小题 8 分，共 36 分） 1. A[6][2]的存储字地址：322 //6 分 答案说明： 按行存储时，计算 A[i][j]地址的公式为 LOC(i,j)=LOC(0,0)+(i*n+j)*d 其中首地址 LOC(0,0)=200, 每个数组元素的存储占用数 d=1, 二维数组的列数 n=20，根据题 意，元素 A[6][2]的存储地址为 LOC(6,2)=200+(6*20+2)*1=322 2. 高度：4 度为 2 的结点数：3 度为 1 的结点数：3 度为 0 的结点数：4 //2 分 //2 分 //1 分 //1 分 3. 左单旋转结点个数：1 右单旋转结点个数：0 先左后右双旋转结点个数：1 先右后左双旋转结点个数：0 不调整结点个数：6 //2 分 //2 分 //2 分 //1 分 //1 分 第 1 页 共 3 页 数据结构期未试卷 2 参考答案 4. 错 1 个数值扣 2 分，最多扣全部 8 分。 顶点： 0 1 2 3 4 0 16 10 14 5. (0) [36 25 25* 62 (1) [25* 25] 36 [62 (2) 25* 25 36 [53 (3) 25* 25 36 40 25 21 40 53] 40 53] 40] 62 53 62 31 5 6 路径长度： //3 分 //3 分 //2 分 五、算法分析题（每小题 6 分，共 18 分） 1. 功能为：矩阵相乘，即 a[M][N]×b[N][L]→c[M][L]。//3 分 时间复杂性为：O(M×N×L)。 //3 分 2. 1→2 1→3 2→3 //2 分 //2 分 //2 分 3. (1) 2 (2) 4 (3) 3 //2 分 //2 分 //2 分 六、算法设计题（每小题 6，共 12 分） 1. 请根据完整程度酌情给分 #include “SeqList.h” template void FindMaxMin(SeqList& A, int& Max, int& Min) { Max=Min=A.getData(0); for(int i=1; iMax) Max=A.getData(i); else if(A.getData(i)data==T2->data && BTreeEqual(T1->left, T2->left) && BTreeEqual(T1->right, T2->right) ) return 1; //5 分 //若根结点值不等或左、右子树对应不等则两棵树不等 else return 0; //6 分 } 另一个参考答案： int BTreeEqual(BinTreeNode* T1,BinTreeNode* T2) { //若两棵树均为空或实际上是同一棵树时返回 1 表示相等 if(T1==T2) return 1; //1 分 //若一棵为空一棵不为空则返回 0 表示不等 if(T1==NULL || T2==NULL) return 0; //2 分 //若根结点值不等返回 0 表示不等 if(T1->data!=T2->data) return 0; //3 分 //若根结点值相等则两棵树是否相等取决于它们的左、右子树是否对应相等 return BTreeEqual(T1->left, T2->left) && BTreeEqual(T1->right, T2->right); //6 分 } 第 3 页 共 3 页