【数据结构期末试卷一、判断题：每题1分）1、满二叉树也是完全二叉树.（）2、二叉树可以用0≤度≤2的有序树来表示.（）3、在只有度为0和度为k的结点的k叉树中,设度为0的结点有n0个,度为k】

　　数据结构期末试卷

　　一、判断题：每题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、折半查找方法可以用于按值有序的线性链表的查找.（）9、对一个堆按层次遍历,不一定能得到一个有序序列.（）10、由于希尔排序的最后一趟与直接插入排序过程相同,因此前者一定比后者花费的时间多.（）二、填空题：每空2分）1、x05度数为0的结点,即没有子树的结点叫作________结点.同一个结点的儿子结点之间互称为________结点.2、x05在具有n个结点的二叉链表中,有_______个空链域.3、x05一个无向图采用邻接矩阵存储方法,其邻接矩阵一定是一个______________.4、给定序列{100,86,48,73,35,39,42,57,66,21},按堆结构的定义,则它是一个______堆.5、在进行直接插入排序时,其数据比较次数与数据的初始排列________关；而在进行直接选择排序时,其数据比较次数与数据的初始排列__________关.6、结点关键字转换为该结点存储单元地址的函数H称为_________或叫___________.7、对n个关键字的序列进行快速排序,平均情况下的空间复杂度为_______.每题2分）1、将一棵有100个结点的完全二叉树从上到下,从左到右依次对结点进行编号,根结点的编号为1,则编号为49的结点的左孩子的编号为______.A.98x05x05B.99C.50x05x05D.482、堆的形状是一棵_______.A.二叉排序树B.满二叉树C.完全二叉树x05D.平衡二叉树3、对于哈希函数H(key)=keyMOD13,被称为同义词的关键字是_______A.35和41x05x05B.23和39x05x05C.15和44x05x05D.25和514、指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中,用二分法查找12,需做多少次比较.______A、2B、3C、4D、55、假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的边时间复杂度是：________A.O（n）x05x05B.O（e）x05x05C.O（n+e）x05x05D.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、P、A、M、Q、R、S、Y、X},则是下列哪个排序算法._____A、起泡排序x05x05x05x05x05B、初始步长为4的shell的排序C、二路归并排序x05x05x05x05D、以第一个元素为分界元素的快速排序9、一个无向连通图的生成树是含有该连通图的全部顶点的_______.A.极小连通子图x05B.极小子图x05C.极大连通子图x05D.极大子图10、图的广度优先遍历类似于二叉树的_______.A.先序遍历x05x05B.中序遍历x05C.后序遍历x05x05D.层次遍历四、应用题：（共28分,每题4分）1、如图所示的二