数据结构考试题目及答案.docx

数据结构考试题目及答案

第一篇：数据结构考试题目及答案数据结构试题6一、单项选择题（每小题3分，共30分）1．设栈的输入序列是1、2、3、4，则______不可能是其出栈序列。（）[A]1234[B]2134[C]1432[D]43122．在一个具有n个结点的线性链表中查找某个结点，若查找成功，需要平均比较_____个结点。（）[A]n[B]n/2[C](n+1)/2[D](n-1)/23．设每个字符占一个字节，二维数组A中每个元素有6个字符组成，其行下标从0到9，列下标从0到3，元素_____当A按行优先存储起始地址与当A按列优先存储的起始地址相同。（）[A]A[3][0][B]A[3][1][C]A[3][2][D]A[2][3]4．具有2000个结点的非空二叉树的最小深度为_______。（）[A]9[B]10[C]11[D]125．已知某二叉树的后根序列是dabec，中根序列是debac，则先根序列是_____。（）[A]acbed[B]decab[C]deabc[D]cedba6.无向图中所有边的数目等于所有顶点的度数之和的_____倍。（）[A]1[B]2[C]1/2[D]不一定7．递归函数F(n)=F(n-1)+n+1(n>1)的递归体是_______。（）[A]F(0)=0[B]F(1)=1[C]F(n)=n+1[D]F(n)=F(n-1)+n+18.若需要在O(nlog2n)的时间内完成对n个元素的排序，且要求排序是稳定的,则可选择的排序方法是_______。（）[A]快速排序[B]堆排序[C]归并排序[D]直接插入排序9．在对n个元素的序列进行排序时,堆排序所需要的附加存储空间是__。（）[A]O(1)[B]O(log2n)[C]O(n)[D]O(nlog2n)10．假定有K个关键字互为同义词，若用线性探查法把这K个关键字存入散列表中，则总的探查次数至少为______。()[A]K-1[B]K[C]K+1[D]K（K+1）/22二、填空题（每小题2分，共20分）1．对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为______，在表尾插入元素的时间复杂度为________。2.在一棵二叉树中，第5层(根结点为1层)上的结点数最多为____________。3.一棵高度为h的理想平衡树中，最少含有______个结点，最多含有________个结点。4.在一个小根堆中，堆顶结点的值是所有结点中的_________，在一个大根堆中，堆顶结点的值是所有结点中的_________。5.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要_________条边。6．假定一个图具有n个顶点和e条边，贝采用邻接矩阵、邻接表表示时，其相应的空间复杂度分别为__________和___________。7．以二分查找方法查找一个线性表时，此线性表必须是_________存储的________表。8．在线性表的散列存储中，处理冲突有___________和___________两种方法。9．快速排序在平均情况下的空间复杂度为_____，在最坏情况下的空间复杂度为_____。10．在一棵20阶B_树中，每个非树根结点的关键字数目最少为_______个,最多为____。三、判断题（认为对的，在题后的括号内打“√”，错的打“ⅹ”，每小题１分，共１０）1．线性表中，每个结点都有一个前驱和一个后继。（）2．有向图的邻接表和逆邻接表中的结点数一定相同。（）3.单链表中要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。（）4.在快速排序、归并排序和shell排序中，稳定的是shell排序。（）5.对不同的存储结构，检索的方法不同。（）6.在散列表中，负载因子值越小则存元素时发生冲突的可能性就越大。（）7.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树。（）8.若一棵二叉树的树叶是某子树对称序周游序列中的第一个结点，则它必是该子树后序周游序列中的第一个结点。（）9.二叉树按线索化后，任一结点均有指向其前驱和后继的线索。（）10.在采用线性探查法处理冲突的散列表中，所有同义词在表中相邻。（）四、简答题（每题10分，共60分）1．说明数组和链表的区别，各有何优缺点？2．回答下列关于堆的一些问题：（1）堆的定义是什么？（2）存储表示是顺序的，还是链式的？（3）设有一个最小堆，其具有最小值、最大值的元素分别可能在什么地方？3．完全二叉树用什么数据结构实现最合适，为什么？4.在直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序和归并排序中，哪些易于在链表（包括各种单、双、循环链表）上实现？5．用下列三种表示法画出下图G的存储结构（1）相邻矩阵（2）邻接表（3）邻接多重表6．已知序列（70