数据结构期末8.docVIP

班级： 专业： 姓名： 考号： 密 封 装 订 线 信息技术学院2006-2007学年第二学期期末考试 数据结构 试卷18（适用班级： ） （答题时间：120分钟，满分：100分） （考生须知：） 题　号 第一部分 第二部分 第三部分 第四部分 第五部分 总　分 核分人 得　分 得　分 评卷人 一、判断题：（共10分，每题1分） 1、深度为h的非空二叉树的第i层最多有2i-1 个结点。（ ） 2、在完全二叉树中,若某结点无左孩子,则它必是叶结点。（ ） 3、一组权值，可以唯一构造出一棵赫夫曼树。( ) 4、在n个结点的无向图中,若边数多于n-1,则该图必是连通图。（ ） 5、对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。（ ） 6、无向图的邻接矩阵是对称的，有向图的邻接矩阵是不对称的。（ ） 7、折半查找只适用于有序表，包括有序的顺序表和有序的链表。（ ） 8、一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（ ） 9、在初始数据为逆序时，冒泡排序所执行的比较次数最多。（ ） 10、希尔排序在效率上较直接插入排序有较大的改进。但是不稳定的。（ ） 得　分 评卷人 二、填空题：（共20分，每空2分） 1、深度为k的二叉树具有的结点数目，最少为最多为。A到顶点B存在_______，则称A与B之间是连通的。 6、一个连通图的生成树是该图的连通子图。若这个连通图有n个顶点, 则它的生成树有条边。_____ 。 8、若要对某二叉排序树进行遍历，保证输出所有结点的值序列按增序排列，应对该二叉排序树采用_________遍历法。 得　分 评卷人 三、选择题：（共20分，每题2分） 1、二叉树中第5层上的结点个数最多为________ A.8 B.15 C.16 D.32 2、设有100个元素，用折半查找法进行查找时，在查找成功的情况下，最大比较次数是_____ 。 A.100 B.50 C.99 D.7 3、适于对动态查找表进行高效率查找的组织结构是________ A.有序表 B.分块有序表 C.二叉排序树 D.线性链表 4、如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是_______ A.有向完全图 B.连通图 C.强连通图 D.有向无环图 5、图的深度优先遍历类似于树的_______。 A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 6、将一棵有50个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为16的结点的右孩子的编号为______。 A.30 B.31 C.32 D.33 7、堆的形状是一棵_______。 A.二叉排序树 B.满二叉树 C.完全二叉树 D.平衡二叉树 8、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为________。 A、 24 B、 48 C、 72 D、 53 9、设有字符序列{Q、H、C、Y、P、A、M、S、R、D、F、X}，向新序列{F、H、C、D、P、A、M、Q、R、S、Y、X}是下列哪个排序算法一趟扫描的结果。起泡排序 B、初始步长为4的shell的排序C、二路归并排序 D、以第一个元素为分界元素的快速排序 评卷人 四、应用题：（共24分，每题4分） 1、设一个有向图为G=(V,E),其中V={v1,v2,v3,v4}，E={v2,v1,v2,v3,v4,v1,v3,v1, v4,v2,v5,v3},画出该有向图，画出相应的邻接表，并对此图进行拓扑排序。 2、已知树T的中序遍历序列为BDCAIFJGHE，先序遍历序列为ABCDEF