资源描述：
《数据结构期末试卷b》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构期末试卷B一、判断题：（共10分，每题1分）1、满二叉树也是完全二叉树。（）2、二叉树可以用0≤度≤2的有序树来表示。（）3、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（）4、带权连通图中某一顶点到图中另一顶点的最短路径不一定唯一。（）5、在n个结点的无向图中,若边数少于n-1,则该图必是非连通图。（）6、树的带权路径长度最小的二叉树中必定没有度为1的结点。（）7、哈希表的查找无需进行关键字的比较。（）8、折半查找方法可以用于按值
2、有序的线性链表的查找。（）9、对一个堆按层次遍历，不一定能得到一个有序序列。（）10、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。（）二、填空题：（共20分，每空2分）1、度数为0的结点，即没有子树的结点叫作________结点。同一个结点的儿子结点之间互称为________结点。2、在具有n个结点的二叉链表中，有_______个空链域。3、一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个______________。4、给定序列{100,86,48,73,35
3、,39,42,57,66,21},按堆结构的定义,则它是一个______堆。5、在进行直接插入排序时,其数据比较次数与数据的初始排列________关；而在进行直接选择排序时，其数据比较次数与数据的初始排列__________关。6、结点关键字转换为该结点存储单元地址的函数H称为_________或叫___________。7、对n个关键字的序列进行快速排序，平均情况下的空间复杂度为_______。三、选择题：（共20分，每题2分）1、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行
4、编号，根结点的编号为1，则编号为49的结点的左孩子的编号为______。A.98B.99C.50D.482、堆的形状是一棵_______。A.二叉排序树B.满二叉树C.完全二叉树D.平衡二叉树3、对于哈希函数H(key)=keyMOD13，被称为同义词的关键字是_______A.35和41B.23和39C.15和44D.25和514、指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找12，需做多少次比较。______A、2B、3C、4D、55、假设一个有n个顶
5、点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的边时间复杂度是：________A.O（n）B.O（e）C.O（n+e）D.O（n*e）6、从二叉排序树中查找一个元素时，其时间复杂度大致为________。A、O(n)B、O(1)C、O(log2n)D、O(n2)7、由权值分别为3,8,6,2,5的叶子结点生成一棵赫夫曼树，它的带权路径长度为________。A、24B、48C、72D、538、设有字符序列{Q、H、C、Y、P、A、M、S、R、D、F、X}，一趟排序的结果为{F、H、C、D
6、、P、A、M、Q、R、S、Y、X}，则是下列哪个排序算法。_____A、起泡排序B、初始步长为4的shell的排序C、二路归并排序D、以第一个元素为分界元素的快速排序9、一个无向连通图的生成树是含有该连通图的全部顶点的_______。A.极小连通子图B.极小子图C.极大连通子图D.极大子图10、图的广度优先遍历类似于二叉树的_______。A.先序遍历B.中序遍历C.后序遍历D.层次遍历四、应用题：（共28分，每题4分）1、如图所示的二叉树完成中序遍历、后序遍历、先序遍历，并画出中序线索化的二叉树。
7、ACBDEF2、请给出下图的邻接矩阵和邻接表，写出从顶点a出发对此图进行深度优先和广度优先进行遍历的顶点序列。abedcf3、对于下图请画出最小生成树。4、已知一表为(49，66，73，52，40，37，65，43)，使按表中元素的次序依次插入一棵初始为空的二叉排序树，画出表中元素构成的二叉排序树。5、已知一棵三阶的B-树如下图所示，假定依次删除关键字46，24，8，15请画出每次删除结点后树的情况：6、已知一组关键字为（19，14，23，01，68，20，84，27，55，11,10，79），则按
8、哈希函数H(key)=keyMOD13和线性探测法解决冲突构造这组关键字的哈希表。7、判断下面的序列是否是堆？如果不是，则把它调整为堆：（5，56，20，23，40，38，29，61，35，76，28，100）五、程序题（共22分）1、阅读下列算法，并回答下列问题：（4分）完善程序,并回答该算法完成什么功能？算法中r[n+1]的作用是什么？voidsort(elemtyper[],intn){intk,i;for(k=n-1;k>=1;k--)if(r[k]>r[k+
