数据结构期末7.docVIP

班级： 专业： 姓名： 考号： 密 封 装 订 线 信息技术学院2006-2007学年第二学期期末考试 数据结构 试卷17（适用班级： ） （答题时间：120分钟，满分：100分） （考生须知：） 题　号 第一部分 第二部分 第三部分 第四部分 第五部分 总　分 核分人 得　分 得　分 评卷人 一、判断题：（共10分，每题1分） 1、哈夫曼树一定是满二叉树。0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（ ） 4、带权连通中某一顶点到图中另一的最短路径不一定唯一。n个顶点的连通图的生成树具有n-1条边（ ） 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,v1,v4, v4,v2},画出该有向图，画出相应的邻接矩阵、邻接表。 2、已知树T的中序遍历序列为GDBHEIACF，先序遍历序列为ABDGEHICF，请画出树T，写出后序遍历序列。 3、用序列（46，88，45，39，70，58，101，10，66，34）建立一个二叉排序树，画出该树。考虑下图：根据普里姆（Prim）算法