数据结构网上教学活动文本（2006.9.26）欢迎老师和学生在今天下午3：00-4：30参加数据结构本科课程的网络答疑活动!课程资源情况：1.主教材《数据结构》殷人昆主编清华大学出版社出版；2.实验教材《数据结构实验（本科）》徐孝凯主编中央广播电视大学出版社出版；3.录像教材《数据结构（本科）》录像殷人昆主讲中央广播电视大学出版社出版；4.数据结构形成性考核册中央电大教育杂志社出版发行；5.数据结构（本科）期末复习指导；6.IP课件和CAI课件正在制作中。考试改革情况：1.从本学期开始，该课程的期末闭卷考试时间由150分钟改为120分钟；2.题型没有变化，题量有减少，但减少幅度不大，而题的难度有所降低，主要考察基本知识。贺桂英：考试题量会减少多少?徐孝凯：题量大致减少百分之20，考试改革主要体现在降低难度上.陈庆平：徐老师，考试时间包括哪几部分？徐孝凯：陈老师好!机考时间不变，这里讲的是期末卷面考试时间由150分改为120分.陈庆平：徐老师，试题题型和重点考核内容有变化吗？徐孝凯：题型：单选（9个）、填空（7个）、判断（7个）、运算（5个）、功能（2个）、编程（2个）。考试内容：仍在该课程的期末复习指导的练习题范围内，对平衡二叉树、B树外排序的内容减少了，只要求概念，对基本内容，如二叉树和图的遍历的内容增加了。请参考往届试卷，新试卷都是由它们派生的。徐孝凯：贺老师、陈老师好！非常感谢你们参加网上聚会讨论问题。附往届试卷：中央广播电视大学计算机科学与技术专业数据结构试题（6）2004年9月题号一二三四五六总分得分2006年1月考一、单项选择题，在括号内填写所选择的标号（9小题，每小题2分，共18分）1.一种抽象数据类型包括数据和()两个部分。A.数据类型B.操作C.数据抽象D.类型说明2.在一个长度为n的顺序表的表尾插入一个新元素的时间复杂度为（）。A.O(1)B.O(n)C.O(n2)D.O(log2n)3.已知L是带表头附加结点的单链表,删除第一个结点的语句是（）。A.L=L->link;B.L->link=L->link->link;C.L=L;D.L->link=L;4.下列广义表中的线性表是（）。A．E(a,(b,c))B．E(a,E)C．E(a,b)D．E(a,())5.在一棵树的左子女-右兄弟表示法中，一个结点的右子女是该结点的()结点。A.兄弟B.父子C.祖先D.子孙6.向一棵AVL树插入元素时，可能引起对最小不平衡子树的双向旋转的调整过程，此时需要修改相关()个指针域的值。A.2B.3C.4D.57.在一个有向图的邻接矩阵表示中，删除一条边<vi,vj>需要的时间复杂度为()。A．O(1)B．O(i)C．O(j)D．O(i+j)8.在一棵高度为h的B树中，插入一个新关键码时，为搜索插入位置需读取（）个结点。A.h-1B.hC.h+1D.h+29.对存储有n个元素的长度为m的散列表进行搜索，平均搜索长度与（）有关。A.nB.mC.n/mD.n*m二、填空题，在横线处填写合适内容（12小题，每小题1分，共12分）1.抽象数据类型的特点是________、信息隐蔽、使用与实现分离。2.利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和_________。3.在单链表中逻辑上相邻的结点而在物理位置上_______相邻。4.向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给________。5.迷宫问题是一个回溯控制的问题，最好使用__________的方法来解决。6.在一棵高度为3的四叉树中，最多含有________个结点，假定树根结点的高度为0。7.在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的右子女元素的下标为________。8.根据一组记录(56,42,73,50,48,22)依次插入结点生成一棵AVL树时，当插入到值为_______的结点时才出现不平衡，需要进行旋转调整。9.在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个________上，才会被加入到生成树中。10.在堆排序中，对n个记录建立初始堆需要调用__________次调整算法。11.在对n个数据对象的二路归并排序中，每趟归并的时间复杂度为____________。12.在一棵m阶B树上，每个非根结点的关键码数最少为__________个。三、判断题，在每小题前面打对号表示正确或打叉号表示错误（10小题，每小题1分