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

Question

数据结构期末试卷
一、判断题：每题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.98 \x05\x05B.99 C.50 \x05\x05D.482、堆的形状是一棵_______.A.二叉排序树 B.满二叉树 C.完全二叉树 \x05 D.平衡二叉树3、对于哈希函数H(key)=key MOD 13,被称为同义词的关键字是_______A.35和41\x05\x05 B.23和39\x05\x05C.15和44\x05\x05 D.25和514、指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中,用二分法查找12,需做多少次比较.______A、2 B、3 C、4 D、55、假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的边时间复杂度是：________A.O（n）\x05\x05 B.O（e）\x05\x05C.O（n+e）\x05\x05 D.O（n*e）6、从二叉排序树中查找一个元素时,其时间复杂度大致为________.A、 O(n) B、 O(1) C、 O(log2n) D、 O(n2)7、由权值分别为3,8,6,2,5的叶子结点生成一棵赫夫曼树,它的带权路径长度为________.A、 24 B、 48 C、 72 D、 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、起泡排序 \x05\x05\x05\x05\x05B、初始步长为4的shell的排序C、二路归并排序 \x05\x05\x05\x05D、以第一个元素为分界元素的快速排序9、一个无向连通图的生成树是含有该连通图的全部顶点的_______.A.极小连通子图 \x05 B.极小子图 \x05C.极大连通子图 \x05 D.极大子图10、图的广度优先遍历类似于二叉树的_______.A.先序遍历 \x05\x05 B.中序遍历 \x05C.后序遍历 \x05\x05 D.层次遍历四、应用题：（共28分,每题4分）1、如图所示的二

Answer 1

期末考试结束了吧.