2005-2006学年第2学期数据结构a卷含答案

《2005-2006学年第2学期数据结构a卷含答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、专业班级：姓名：学号：…………………………密………………………………封………………………………线…………………………黄淮学院2005-2006学年第2学期期末考试《数据结构》（计算机科学系）A卷题号一二三四总分核分人得分得分评卷人一、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，每小题2分，共30分）1.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为()。(1≤i≤n+1)(1)O(0)(2)O(1)(3)O(n)(4)O(n2)2.在单链表中p所指结点后插入s所指结点,则下列语句正确的是

2、()(1)p→next=s;s→next=p;(2)s→next=p→next;p→next=s;(3)s→next=p;p→next=s;(4)p→next=s→next;s→next=p;3.设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是()（1）A，B，C，D（2）D，C，B，A（3）A，C，D，B（4）D，A，B，C4.若由树林转化得到的二叉树是非空的二叉树，则二叉树形状是（）（1）根结点无右子树的二叉树（2）根结点无左子树的二叉树（3）根结点可能有左二叉树和右二叉树（4）根结点只有一个孩子结点的二叉树5．设二叉树的根为第一层，则深度为i

3、的二叉树结点数最多为（）（1）２i（2）２i+1（3）２i-１（4）２i-16.首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为(　　　)（1）前序遍历（2）后序遍历（3）中序遍历（4）层次遍历7．给定下列有向图，从顶点1出发，其广度优先搜索序列为（）（1）12534（2）12435（3）14325（4）123458．散列表中的冲突是指（）（1）  两个元素具有相同的序号（2）两个元素的关键字相同，而其他属性相同（3）不同的关键字对应相同的存储地址（4）数据元素的地址相同9.线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（）（1）必须是

4、连续的（2）部分地址必须是连续的（3）一定是不连续的（4）连续或不连续都可以10．下面程序段的时间复杂度为（）for(inti=1;i

5、址（）（1）必须大于等于原散列地址（2）必须小于等于原散列地址（3）可以大于或小于但不等于原散列地址（4）对地址在何处没有限制14．栈的插入和删除操作在（）进行。（1）栈顶（2）栈底（3）任意位置（4）指定位置15．在一个顺序存储的循环队列中，对头指针指向队列的（）位置。（1）前一个（2）后一个（3）当前（4）后面得分评卷人二、填空题（每空1分，共20分）1.数据的逻辑结构被分为_____________，________________，_________________，________________。2.单链表与循环链表的区别是__________________

6、_____________。3.在一个循环队列中，判断对空的条件是串是____________________，判断对满的条件是串是_______________________________4.从有序表（12，18，30，43，56，78，82，95）中一次折半搜索43和56元素是，其比较次数分别为_______和_______。5.与哈西表的平均查找长度有关的三个因素分别是_____________________________，____________________，_____________________。《数据结构》试卷第3页（共3页）6.对于一个具有n

7、个顶点和e条边的连通图，其生成树中的顶点数个边数分别为_________和__________。7.在二叉排序树中，左子树所有结点的关键字值都________该结点的关键码值，而右子树中所有结点的关键字值都_________该结点的关键码值。8.在一个小顶堆中，堆顶元素的值是所有结点中的______________，在一个大顶堆中，堆顶元素的值是所有结点中的______________。9.假定一组纪录的关键字为（46，79，56，38，40，80），对其进行快速排序的一次划分的结果为_____________________