数据结构试卷a

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

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

2、分〕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，那么借助一个栈所得到的输出序列不可能是()-.word.zl-

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

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

5、for(intj=1;j

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

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

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