数据结构试卷a.doc

《数据结构试卷a.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、...专业班级：姓名：学号：…………………………密………………………………封………………………………线…………………………河南理工大学万方学院2006-2007学年第2学期专业班级：姓名：学号：…………………………密………………………………封………………………………线…………………………《数据结构》试卷（A卷）考试方式：闭卷本试卷考试分数占学生总评成绩的80%总分题号一二三四核分人得分复查总分总复查人得分评卷人毋小省一、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，每小题

2、2分，共30分）1.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为()。(1≤i≤n+1)(1)O(0)(2)O(1)(3)O(n)(4)O(n2)2.在单链表中p所指结点后插入s所指结点,则下列语句正确的是()(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

3、）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的二叉树结点数最多为（）（1）２i（2）２i+1（3）２i-１（4）２i-16.首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为(　　　)z.....（1）前序遍历（2）后序遍历（3）中序遍历（4

4、）层次遍历7．给定下列有向图，从顶点1出发，其广度优先搜索序列为（）（1）12534（2）12435（3）14325（4）123458．散列表中的冲突是指（）（1）  两个元素具有相同的序号（2）两个元素的关键字相同，而其他属性相同（3）不同的关键字对应相同的存储地址（4）数据元素的地址相同9.线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（）（1）必须是连续的（2）部分地址必须是连续的（3）一定是不连续的（4）连续或不连续都可以10．下面程序段的时间复杂度为（）for(inti=1;i

5、r(intj=1;j

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

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

8、有n个顶点和e条边的连通图，其生成树中的顶点数个边数分别为_________和__________。7.在二叉排序树中，左子树所有结点的关键字值都________该结点的关键码值，而右子树中所有结点的关键字值都_________该结点的关键码值。8.在一个小顶堆中，堆顶元素的值是所有结点中的______________，在一个大顶堆中，堆顶元素