发布时间 : 星期三 文章数据结构期终复习更新完毕开始阅读5f435cfcce84b9d528ea81c758f5f61fb6362842
（9）快速排序在最坏情况下的时间复杂度为（ ）。
A）O(log2n) B）O(nlog2n) C）O(n) D）O(n2) （10）从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）。
A）O(n) B）O(1) C）O(log2n) D）O(n2) 二、（本题8分）
已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 三、（本题8分）
请画出如下图所示的邻接矩阵和邻接表。
四、（每小题4分，共8分）
设有如下图所示的AOE网（其中vi（i=l，2，…，6）表示事件，有向边上的权值表示活动的天数）。
v26v14v48217v311v693v5 （1）找出所有的关键路径。
（2）v3事件的最早开始时间是多少。 五、（本题8分）
一棵非空的有向树中恰有一个顶点入度为0，其他顶点入度为1。但一个恰有一个顶点入度为0、其他顶点入度为1的有向图却不一定是一棵有向树。请举例说明之。
六、（本题8分）
假设把n个元素的序列（a1,a2,…an）满足条件ak 七、（本题8分） 带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法： ①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点； ②选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v； ③重复步骤②，直到u是目标顶点时为止。 请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。 八、（本题8分） H(key)=key MOD 已知一组关键字为（19,14,23,1,68,20,84,27,55,11,10,79），哈希函数： 13，哈希地址空间为0~12，请构造用链地址法处理冲突的哈希表，并求平均查找长度。 九、（本题9分） 已知关键字序列{23，13，5，28，14，25}，试构造二叉排序树。 十、（本题15分） 编写一个算法求二又树的深度。 模拟试题（三）参考答案 一、单项选择题（每小题 2 分，共20分） （1）A （2）A （3）B （4）C （5）B （6）B （7）D （8）B （9）D （10）C 二、（本题8分） 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 三、（本题8分） 邻接矩阵： ?0?1??1??1??01110? 0101??1011??0101?1110??邻接表如下图所示： 12345211123323345454∧∧∧∧5∧ 四、（每小题4分，共8分） （1）找出所有的关键路径有：v1→v2→v3→v5→v6，以及v1→v4→v6。 （2）v3事件的最早开始时间是13。 五、（本题8分） 如下图所示的有向图，只有一个顶点的入度为0外，其他每个顶点的入度都为1，因为非连通，所以此图却不是有向树。 六、（本题8分） 不对，例如序列｛3、3、4、2、l｝的“逆序元素”个数是2，2和1是“逆序元素”；但是将第二个3和2交换后，成为｛3、2、4、3、l｝，此时“逆序元素”个数是3，2、3和1是“逆序元素”。然而交换后一定减少的是“逆序对”的个数，例如上例中｛3、3、4、2、l｝的逆序对的个数是 7，交换第二个 3和2后，｛3、2、4、3、1｝的逆序对的个数是6。 七、（每小题4分，共8分） 该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从A到C的最短路径为A→B→C，事实上其最短路径为 A→D→C。 A2D31B10C 八、（本题8分） 用链地址法处理冲突的哈希表如下图所示： ASL= 1(1*6+2*4+3*1+4*1)=1.75 12九、（本题9分） 构造二叉排序树的过程如下图所示。 构造的二叉排序树如下图所示： 十、（本题15分） 若二叉树为空，深度为0；若二叉树不空，则二叉树的深度为左右子树深度的最大值加1。本题最简单算法是递归算法。 具体算法实现如下： // 文件路径名:exam3\\alg.h template int DepthHelp(BinTreeNode template int Depth(BinaryTree