资源描述：
《数据结构网上教学活动文本(2006511).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构网上教学活动文本（2006.5.11）徐孝凯：欢迎大家积极参加计算机科学与技术专业数据结构课程网络答疑活动贺桂英：徐老师，能否请您将刚考过的试题(06年1月已考)上传给我们，供学习和复习参考!谢谢您!徐孝凯：上学期试卷供参考！中央广播电视大学计算机科学与技术专业数据结构试题（6）2004年9月题号一二三四五六总分得分一、单项选择题，在括号内填写所选择的标号（9小题，每小题2分，共18分）1.一种抽象数据类型包括数据和()两个部分。A.数据类型B.操作C.数据抽象D.类型说明2.在一个长度为n的顺序
2、表的表尾插入一个新元素的时间复杂度为（）。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树插入元素
3、时，可能引起对最小不平衡子树的双向旋转的调整过程，此时需要修改相关()个指针域的值。A.2B.3C.4D.57.在一个有向图的邻接矩阵表示中，删除一条边需要的时间复杂度为()。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小题，每小
4、题1分，共12分）1.抽象数据类型的特点是________、信息隐蔽、使用与实现分离。2.利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和_________。3.在单链表中逻辑上相邻的结点而在物理位置上_______相邻。4.向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给________。5.迷宫问题是一个回溯控制的问题，最好使用__________的方法来解决。6.在一棵高度为3的四叉树中，最多含有_____
5、___个结点，假定树根结点的高度为0。7.在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的右子女元素的下标为________。8.根据一组记录(56,42,73,50,48,22)依次插入结点生成一棵AVL树时，当插入到值为_______的结点时才出现不平衡，需要进行旋转调整。9.在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个________上，才会被加入到生成树中。10.在堆排序中，对n个记录建立初始堆需要调用__________次调整算法。
6、11.在对n个数据对象的二路归并排序中，每趟归并的时间复杂度为____________。12.在一棵m阶B树上，每个非根结点的关键码数最少为__________个。三、判断题，在每小题前面打对号表示正确或打叉号表示错误（10小题，每小题1分，共10分）1.多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。2.若每次从队列中取出的是具有最高优先权的元素,则称这种队列为优先级队列。3.递归定义的数据结构通常不需要用递归的算法来实现对它的操作。4.当从一个最小堆中删除一个元素时，需要把堆
7、尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。5.对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。6.对于同一组记录，生成二叉搜索树的形态与插入记录的次序无关。7.在每个AOE网络中只有一条关键路径。8.图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。9.装载因子是散列表的一个重要参数，它反映了散列表的装满程度。10.在一棵B树中，所有叶结点都处在同一层上，所有叶结点中空指针数等于所有关键码的总数加1。四、运算题（5小题，
8、每小题6分，共30分）1.假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行中序、后序、按层遍历的结果。中序：后序：按层：2.一个一维数组a[10]中存储着有序表(15,26,34,39,45,56,58,63,74,76)，根据折半搜索所对应的判定树，写出该判定树中度为1的结点个数，并求出在等概率情况下进行成功搜索时的平均搜索长度。度为1的结点个数：平均搜索长度：3.假定一个线性序列为(38,42,55
