中央广播电视大学2005—2006学年度第一学期“开放本科”期末考试计算机专业数据结构试题.doc

《中央广播电视大学2005—2006学年度第一学期“开放本科”期末考试计算机专业数据结构试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、___________________________________________________________________________________________中央广播电视大学2005—2006学年度第一学期“开放本科”期末考试计算机专业数据结构试题试卷代号：1010中央广播电视大学2005—2006学年度第一学期“开放本科”期末考试计算机专业数据结构试题2006年1月一、单项选择题，在括号内填写所选择的标号(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；15_____________________________________________________________________________________________________________________________________________________________________________________D．L一&g

3、t;1ink=L一>link一>link；CL＝L；D．L一>1ink=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．3C4D．57．在一个有向图的邻接矩阵表示中，删除一条边<vi，vj>需要的时间复杂度为()。A．O(1)B．O(i)CO(i)D·O(i+j

4、)8．在一棵高度为h的B树中，插入一个新关键码时，为搜索插入位置需读取()个结点。A．h一1B．hCh+115_____________________________________________________________________________________________________________________________________________________________________________________D．h+29．对存储有n个元素的长度为m的散列表进行搜索，平均搜索长度与()有关。A．nB．mC．n／

5、mD．n*m二、填空题，在横线处填写合适内容(12小题，每小题1分，共12分)1.抽象数据类型的特点是、信息隐蔽、使用与实现分离。2．利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和。3．在单链表中逻辑上相邻的结点而在物理位置上，相邻。4．向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给。5．迷宫问题是一个回溯控制的问题，最好使用的方法来解决。6．在一棵高度为3的四叉树中，最多含有个结点，假定树根结点的高度为0。15______________________________

6、_______________________________________________________________________________________________________________________________________________________7．在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n一1)，则它的右子女元素的下标为。8．根据一组记录(56，42，73，50，48，22)依次插入结点生成一棵AVL树时，当插入到值为的结点时才出现不平衡，需要进行旋转调整。9．在使用Kruskal算法构

7、造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个上，才会被加入到生成树中。10．在堆排序中，对n个记录建立初始堆需要调用次调整算法。11．在对n个数据对象的二路归并排序中，每趟归并的时间复杂度为。12．在一棵m阶B树上，每个非根结点的关键码数最少为个。三、判断题，在每小题前面打对号表示正确或打叉号表示错误(10小题，每小题1分，共10分)()1．多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。()2．若每次从队列中取出的是具有最高优先权的元素，则称这种队列为优先级队列。(15__________________