数据结构期末考试复习题及答案

1、精品文档 1. 什么是最小生成树？简述最小生成树的 Prime 算法的思想。 答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。 普里姆算法 （Prim） 的基本思想： 从连通网络 N = V, E 中的某一顶点 u0 出发，选择与它关联的具有最小权值的边 （u0, v）， 将其顶点加入到生成树的顶点集合 U 中。以后每一步从一个顶点在 U 中，而另一个顶点不 在 U 中的各条边中选择权值最小的边 （u, v）, 把它的顶点加入到集合 U 中。如此继续下去， 直 到网络中的所有顶点都加入到生成树顶点集合 U 中为止。 2. 简述 AOV 网络中为何不能出现回路，如何判断 AOV 网

2、络是否有回路？ 答：在 AOV 网络中，如果活动 vi 必须在 vj 之前进行，则称为存在有向边；在 AOV 网络中 不能出现有向回路，如果出现了，则意味着某项活动应以自己作为先决条件。 如何检查AOV网是否存在有向环： 检测有向环的一种方法是对 AOV网络构造它的拓扑有序序列。即将各个顶点（代表各个活动） 排列成一个线性有序的序列，使得 AOV网络中所有应存在的前驱和后继关系都能得到满足。 （1 ）这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 （2 ）如果通过拓扑排序能将 AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV 网络中必定不会出现有向环；相反，如果得不到

3、满足要求的拓扑有序序列， 则说明AOV网络 中存在有向环，此 AOV网络所代表的工程是不可行的。 3. 为何需要采用循环队列？ n 个空间的循环队列，最多存储多少个元素？为什 么？ 答：循环队列以克服顺序队列的 假上溢 现象，能够使存储队列的向量空间得到充分的利用， 所以采用循环队列。 n 个空间的循环队列，最多存储 n-1 个元素，那是为了区别循环队列的队空和队满的条件。 队空的条件是 Q.front=Q.rear ，而队满的条件是 （Q.rear+1）%N=Q.front（N 是数组中单元的总 数），因此， Q.rear 所指向的数组单元处于未用状态。所以说， N 个单元的数组所存放的循

4、环队列最大长度是 N-1 。 4. 简述堆的删除算法，其删除的是那个值？ 答：堆的删除算法 ：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结 点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的 孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶 子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数， 则退出循环。最后把最后叶子结点的元素移给当前结点。 在堆的算法里面，删除的值为根值 。 5. 线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？ 答：指向直接前驱结点和指向直接后续结点的指针被称为线索（

5、Thread）,加了线索的二叉 树称为线索二叉树。线索二叉树是唯一的，因为知道先序遍历后，第一个根是唯一确定的， 然后在中序遍历里这个根将它分为两个部分，第一个根的两棵子树的根也会唯一确定，依次 此类推，所有子树的根都唯一确定，二叉树就是唯一的。 6. 链式插入排序对比直接插入排序有何优点和缺点？ 答:链式插入排序优 点是速度极快，特别是在数据量大的时候效果尤为明显；其|缺点是在数据量少的情况 下内存相对消耗较多。直接插入排序优点是排序比较简单，稳定性高；缺点是在数据量很大的情况下效率 很低。 所以链式插入排序适合数据量大的情况，直接插入排序适合数据量少的情况。 7. 画出该图的邻接矩阵和邻接

6、表。根据邻接表从A开始求DFS（深度优先搜索） DFS: A-C-F-E-D-B BFS: A-C-B-F-D-E 8. 已知序列70,73,69,23,93,18,11,68请给出直接插入排序作升序排序每一趟的 结果和快速排序作为升序排序时一趟的结果。 答： 直接插入排序 70 73 69 23 93 18 11 68 70 73 69 23 93 18 11 68 69 70 73 23 93 18 11 68 23 69 70 73 93 18 11 68 23 69 70 73 9318 11 68 18 23 69 70 73 9311 68 11 18 23 69 70 73 93

7、68 11 18 23 68 69 70 73 93 快速排序 R1 R2 R3 R4 R5 R6 R7 R8 left right 70 73 69 23 93 18 11 68 1 10 68 11 69 23 18 70 93 73 1 5 18 11 23 68 69 70 93 73 1 3 11 18 23 68 69 70 93 73 7 8 11 18 23 68 69 70 73 93 9下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边 上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的 n-1条公路，画出所有可能的方案。 10.已知一个无向图的邻接表如下图所示: 精品文档 （1）画出这个图。 以V1为出发点，对图