数据结构期终复习 下载本文

(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)满足条件akaj(i

七、(本题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 *r) // 操作结果:求二叉树的深度 { if (r == NULL) { // 空二叉树 return 0; // 空二叉树的深度为0 } else { // 非空二叉树 int lDepth = DepthHelp(r->leftChild); // 左子树的深度 int rDepth = DepthHelp(r->rightChild); // 右子树的深度 return ((lDepth > rDepth) ? lDepth : rDepth) + 1; // 返回左右子树的深度最大值加1 } }

template

int Depth(BinaryTree &bt) // 操作结果:求二叉树的深度 { return DepthHelp(bt.GetRoot()); // 调用辅助函数求二叉树的深度