《数据结构》网上教学活动文本（2004.doc

数据结构网上教学活动文本（数据结构网上教学活动文本（2004.10.22）问：问：老师，你好！这门课太难学了？请问有什么好方法吗？上课听不懂 徐孝凯：徐孝凯：请参考实验教材中的内容学习，可能容易些。问：问：什么是抽象数据类型？ 徐孝凯：徐孝凯：抽象数据类型同 C+中类的概念相似。徐孝凯：徐孝凯：如何学好这门课 1.认真听面授辅导课； 2.认真做好平时作业； 3.认真按实验教材要求做好每个实验； 4.有问题请教面授课老师和身边的同学； 5.不抠难题怪题，掌握基本概念和算法。 徐孝凯：徐孝凯：如何加强练习 1.按照该课程期末复习指导的要求，掌握教学内容； 2.做好该复习指导中的练习题； 3.做好形成性作业中的每次作业； 4.做好实验教材后面附录中所给的全部综合练习题，特别是选择、填空、判断等题型。 5.参考以前考过的试卷，做会其中的考题。 问：问：殷老师，徐老师，下面题怎么解 设 L 链表中数据为 12,24,30,90,84,36,n 的初值为 0,写出 unknown(L.first,n)调用后的结果,指 出算法功能 float unknown(ListNode *f,int else n+; return unknown(f->getLink(),n)+f->getData()/n; 徐孝凯：徐孝凯：返回 6 个数的平均值。因为当最后每次递归返回时，n 的值不变，即为链表中数 据的个数，每次都使一个数据除以 6，整个算法是每个数除以 6 之和。 徐孝凯：徐孝凯：数据结构课程教学如何，是太难了呢？以后会好写，因为考题难度在下降，并且 在实验教材中给出了综合练习题。 赵永虹：试题有一定难度。 问：问：请问数据结构这门课程的学习重点在哪里？它是开卷考试还是闭卷考试？题目有哪些 类型？ 徐孝凯：徐孝凯： 1.为闭卷考试，时间为 150 分钟。2.题目类型有选择、填空、判断、运算、算法分析、算法设计等。 3.请参考往届考试试卷。 4.请按照实验教材后面给出的综合练习题的范围掌握教学要求和难易程度。 徐孝凯：徐孝凯：四川电大赵老师，你认为数据结构考试难度如何，应如何改进？ 赵永虹：这样经过几次考试,可能好一些 问：问：老师这门课程很难我们应怎样才能考好这门课呢？能否出题简单点？ 徐孝凯：徐孝凯： 1.为闭卷考试，时间为 150 分钟。 2.题目类型有选择、填空、判断、运算、算法分析、算法设计等。 3.请参考往届考试试卷。 4.请按照实验教材后面给出的综合练习题的范围掌握教学要求和难易程度。 5.现在试题难道有所降低，和实验教材后的综合练习题难易相当，也许更容易写。 徐孝凯：徐孝凯：参考以前试卷：中央广播电视大学计算机科学与技术专业数据结构试题（计算机科学与技术专业数据结构试题（2 2）2003 年 8 月题 号一二三四五六总 分得 分一、单项选择题，在括号内填写所选择的标号（每小题一、单项选择题，在括号内填写所选择的标号（每小题 1 1 分，共分，共 1212 分）分）1. 若需要利用形参直接访问实参，则应把形参变量说明为( )参数。A. 指针 B. 引用 C. 传值 D. 常值2. 以下说法错误的是（ ） 。 A. 抽象数据类型具有封装性。 B. 抽象数据类型具有信息隐蔽性。 C. 使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。 D. 抽象数据类型的一个特点是使用与实现分离。3. 设有一个 nn 的对称矩阵 A，将其上三角部分按行存放在一个一维数组 B 中，A0 0存放于 B0中，那么第 i 行的对角元素 Aii存放于 B 中（ ）处。A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2D. (2n-i-1)*i/24. 已知单链表 A 长度为 m，单链表 B 长度为 n，若将 B 联接在 A 的末尾，其时间复杂 度应为（ ） 。A. O(1) B. O(m) C. O(n) D. O(m+n)5. 假定一个链式队列的队头和队尾指针分别为 front 和 rear，则判断队空的条件为( )。A. front = rearB. front != NULLC. rear != NULL D. front = NULL6. 设有一个递归算法如下int fact(int n) /n 大于等于 0if(n,，从顶点 1 出发，对 图 G 进行广度优先搜索的序列有_种。10. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置， 这种排序方法叫做_排序。11. 快速排序在平均情况下的空间复杂度为_。12. 若对长度 n=10000 的线性表进行二级索引存储，每级索引表中的索引项是下一级 20 个表项的索引，则一级索引表的长度为_。三、判断题，在每小题前面打对号表示正确或打叉号表示失败（每小题三、判断题，在每小题前面打对号表示正确或打叉号表示失败（每小题 1 1 分，共分，共 1010 分）分）1. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。2. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。3. 在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。4. 用非递归方法实现递归算法时一定要使用递归工作栈。5. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历 和后序遍历，则具有相同的结果。6. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率 的降序排列存放，则可得到最小的平均搜索长度。7. 在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近， 则得到的是最优二叉搜索树。8. 对于 AOE 网络，加速任一关键活动都能使整个工程提前完成。9. 直接选择排序是一种稳定的排序方法。10. 闭散列法通常比开散列法时间效率更高。四、运算题（前四、运算题（前 2 2 小题，每小题小题，每小题 6 6 分，后分，后 3 3 小题，每小题小题，每小题 8 8 分，共分，共 3636 分）分）1. 设有一个二维数组 A1020，按行存放于一个连续的存储空间中，A00的存 储地址是 200，每个数组元素占 1 个存储字，则 A62的存储字地址是多少。A62的存储字地址：2. 已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为- 1）和度为 2、度为 1 及度为 0 的结点个数。中序序列：c,b,d,e,a,g,i,h,j,f后序序列：c,e,d,b,i,j,h,g,f,a高度： 度为 2 的结点数：度为 1 的结点数： 度为 0 的结点数：3. 假定一组记录为(36,75,83,54,12,67,60,40)，将按次序把每个结点插入到初始为 空的一棵 AVL 树中，请回答在插入时需进行“左单旋转” 、 “右单旋转” 、 “先左后右双旋转” 、 “先右后左双旋转” ， “不调整”的结点数各是多少？左单旋转结点个数： 右单旋转结点个数：先左后右双旋转结点个数： 先右后左双旋转结点个数：不调整结点个数：4. 已知一个带权图的顶点集 V 和边集 G 分别为：V=0,1,2,3,4,5,6;E=(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,(4,5)6,(4,6)6,(5,6)12;试根据迪克斯特拉(Dijkstra)算法求出从顶点 0 到其余各顶点的最短路径，在下面填 写对应的路径长度。顶点： 0 1 2 3 4 5 60路径长度：5. 已知一个数据表为36,25,25*,62,40,53，请写出在进行快速排序的过程中每次划 分后数据表的变化。(0) 36 25 25* 62 40 53(1) (2) (3) 五、算法分析题（每小题五、算法分析题（每小题 6 6 分，共分，共 1818 分）分）1. 指出下面算法的功能并求出其时间复杂度。void matrimult(int aMN, int bNL, int cML) /M、N、L 均为全局整型量int i, j, k;for(i=0; idata=X) return 1; else if(t->data>X) return 1+LN(t->left,X); else return 1+LN(t->right,X); (1) (2) (3)六、算法设计题（每小题六、算法设计题（每小题 6 6 分，共分，共 1212 分）分）1. 试编写一个函数，在一个顺序表 A 中查找出具有最大值和最小值的整数。函数的原型如下所示，原型的参数表中给出顺序表对象为 A，通过算法执行，从参数 表中的引用参数 Max 中得到表中的最大整数，Min 中得到表中的最小整数。 注意，函数中可使用顺序表的如下两个公有函数：int Length( ); 求表的长度；int getData(int k); 提取第 k 个元素的值。#include “SeqList.h”template void FindMaxMin(SeqList2. 已知二叉树中的结点类型 BinTreeNode 定义为:struct BinTreeNode char data; BinTreeNode *left, *right;其中 data 为结点值域，left 和 right 分别为指向左、右子女结点的指针域，根据下 面函数声明编写出判断两棵二叉树是否相等的算法，若相等则返回 1 否则返回 0。算法中 参数 T1 和 T2 为分别指向这两棵二叉树根结点的指针。当两棵树的结构完全相同并且对应 结点的值也相同时才被认为相等。int BTreeEqual(BinTreeNode* T1,BinTreeNode* T2);中央广播电视大学计算机科学与技术专业数据结构试题（2）参考解答及评分标准2003 年 8 月一、单项选择题，在括号内填写所选择的标号（每小题一、单项选择题，在括号内填写所选择的标号（每小题 1 1 分，共分，共 1212 分）分）1. B 2. C 3. C 4. C 5. D 6. B7. D 8. C 9. B 10. C 11. D 12. D二、填空题，在横线处填写合适内容（每小题二、填空题，在横线处填写合适内容（每小题 1 1 分，共分，共 1212 分）分）1. 链接 2. 动态 3. 删除 4. 后出先进5. 递归 6. 3 7. 右 8. 左子树 9. 2 10. 交换 11. O(log2n) 12. 500三、判断题，在每小题前面打对号或打叉号（每小题三、判断题，在每小题前面打对号或打叉号（每小题 1 1 分，共分，共 1010 分）分）1. 对 2. 对 3. 错 4. 错 5. 对6. 对 7. 错 8. 错 9. 错 10. 错.四、运算题（前四、运算题（前 2 2 小题，每小题小题，每小题 6 6 分，后分，后 3 3 小题，每小题小题，每小题 8 8 分，共分，共 3636 分）分）1. A62的存储字地址：322 /6 分 答案说明：按行存储时，计算 Aij地址的公式为LOC(i,j)=LOC(0,0)+(i*n+j)*d 其中首地址 LOC(0,0)=200, 每个数组元素的存储占用数 d=1, 二维数组的列数 n=20， 根据题意，元素 A62的存储地址为LOC(6,2)=200+(6*20+2)*1=3222. 高度：4 /2 分 度为 2 的结点数：3 /2 分度为 1 的结点数：3 /1 分度为 0 的结点数：4 /1 分3.左单旋转结点个数：1 /2 分右单旋转结点个数：0 /2 分先左后右双旋转结点个数：1 /2 分先右后左双旋转结点个数：0 /1 分不调整结点个数：6 /1 分4. 错 1 个数值扣 2 分，最多扣全部 8 分。顶点： 0 1 2 3 4 5 6路径长度： 5.(0) 36 25 25* 62 40 53(1) 25* 25 36 62 40 53 /3 分(2) 25* 25 36 53 40 62 /3 分(3) 25* 25 36 40 53 62 /2 分五、算法分析题（每小题五、算法分析题（每小题 6 6 分，共分，共 1818 分）分）1. 功能为： 矩阵相乘，即 aMN×bNLcML。/3 分时间复杂性为：O(M×N×L)。 /3 分2.12 /2 分13 /2 分23 /2 分3. (1) 2 /2 分(2) 4 /2 分(3) 3 /2 分六、算法设计题（每小题六、算法设计题（每小题 6 6，共，共 1212 分）分）1. 请根据完整程度酌情给分#include “SeqList.h”template void FindMaxMin(SeqListfor(int i=1; iMax) Max=A.getData(i);else if(A.getData(i)data=T2->data /5 分/若根结点值不等或左、右子树对应不等则两棵树不等elsereturn 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) /6 分中央广播电视大学计算机科学与技术专业数据结构试题（计算机科学与技术专业数据结构试题（3 3）2003 年 8 月题 号一二三四五六总 分得 分一、单项选择题，在括号内填写所选择的标号（每小题一、单项选择题，在括号内填写所选择的标号（每小题 1 1 分，共分，共 1212 分）分）1. 下面程序段的时间复杂度为( )。for(int i=0; ilink=s;B. s->link=top->link; top->link=s;C. s->link=top; top=s; D. s->link=top; top=top->link;6. 设有一个递归算法如下int X(int n) if(n void unknown(T A, int n) int free=0; for(int i=0; itemp? An-1 : temp;返回结果：算法功能：3. 已知二叉树中的结点类型 BinTreeNode 定义为:struct BinTreeNode ElemType data;BinTreeNode *left, *right; 其中 data 为结点值域，left 和 right 分别为指向左、右子女结点的指针域。参数 bt 指向 一棵二叉树，引用参数 x 一开始具有的值小于树中所有结点的值。试根据下面的函数定义 指出此算法的功能。int JB(BinTreeNode* bt, ElemTypeelse if(JB(bt->left,x)=0) return 0;if(bt->datadata;if(JB(bt->right,x)=0) return 0;else return 1;算法功能：六、算法设计题（每小题六、算法设计题（每小题 6 6 分，共分，共 1212 分）分）1. 设有两个整数类型的顺序表 A（有 m 个元素）和 B（有 n 个元素） ，其元素均以升序 排列。把下面函数补充完整，将这两个顺序表合并成一个顺序表 C，要求 C 的元素也以升 序排列（表中允许元素重复） 。函数中的参数表给出参加运算的三个顺序表 A、B 与 C。从 C 中得到执行结果。函数中 用到顺序表的 4 个公有函数：Length( ) 求表的当前长度；maxLength( ) 求表的最大允许长度；getData(int k) 提取第 k 个元素的值；setData(int k, int val) 修改第 k 个元素的值为 val。templatevoid merge(SeqListif(mpn>C.maxLength() cerrllink 5. 一 6. 2 7. 2 8. 右子树9. 4 10. 直接选择 11. O(n2) 12. 11三、判断题，在每小题前面打对号或打叉号（每小题三、判断题，在每小题前面打对号或打叉号（每小题 1 1 分，共分，共 1010 分）分）1. 错 2. 错 3. 对 4. 对 5. 错6. 对 7. 对 8. 对 9. 错 10. 错四、运算题（前四、运算题（前 2 2 小题，每小题小题，每小题 6 6 分，后分，后 3 3 小题，每小题小题，每小题 8 8 分，共分，共 3636 分）分）1. 226 /6 分 答案说明：按列存储时，计算 Aij地址的公式为LOC(i,j)=LOC(0,0)+(j*m+i)*d其中首地址 LOC(0,0)=200, 每个数组元素的存储占用数 d=1, 二维数组的行数 m=10， 则数组元素 A62的存储地址为LOC(6,2)=200+(2*10+6)*1=2262.前序序列：20,8,5,15,10,18,46,30,35 /2 分中序序列：5,8,10,15,18,20,30,35,46 /2 分后序序列：5,10,18,15,8,35,30,46,20 /2 分3.度为 2 的结点个数：4 /3 分度为 1 的结点个数：1 /3 分度为 0 的结点个数：5 /2 分4. 每错一条最短路径扣 2 分，最多扣 8 分。012345600,2,10,20,30,2,40,2,1,50,2,4,6顶点： 最短路径：5.(0) 75 75* 60 18(1) 75* 18 60 75 /3 分(2) 60 18 75* 75 /3 分(3) 18 60 75* 75 /2 分五、算法分析题（每小题五、算法分析题（每小题 6 6 分，共分，共 1818 分）分）1. 完全正确得 6 分，否则酌情给分。算法执行的结果：A=12,24,38,29,45,0,0,0,0,0,0,0; /6 分2.返回结果：95 /3 分算法功能：求存放于整数数组 An中 n 个数据的最大值。 /3 分 3. /6 分算法功能：判断二叉树 bt 是否为一棵二叉搜索树，若是则返回 1 否则返回 0。六、算法设计题（每小题六、算法设计题（每小题 6 6 分，共分，共 1212 分）分）1. 渐进给分while(i=bv) C.setData(k+, bv); bv=B.getData(+j);if(ileft); /2 分/递归删除右子树ClearBTree(BT->right); /2 分/回收根结点delete BT; /1 分/置根指针为空BT=NULL; /1 分