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

《数据结构 期末考试复习题及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、扑有序的序列中，则该AOV网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。3.为何需要采用循环队列？n个空间的循环队列，最多存储多少个元素？为什么？答：循环队列以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用，所以采用循环队列。n个空间的循环队列，最多存储n-1个元素，那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front==Q.rear，而队满的条件是(Q.rear+1)%N==

4、Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。4.简述堆的删除算法，其删除的是那个值？答：堆的删除算法：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，则退出循环。最

5、后把最后叶子结点的元素移给当前结点。在堆的算法里面，删除的值为根值。5.线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？答：指向直接前驱结点和指向直接后续结点的指针被称为线索（Thread），加了线索的二叉树称为线索二叉树。线索二叉树是唯一的，因为知道先序遍历后，第一个根是唯一确定的，然后在中序遍历里这个根将它分为两个部分，第一个根的两棵子树的根也会唯一确定，依次此类推，所有子树的根都唯一确定,二叉树就是唯一的。1.链式插入排序对比直接插入排序有何优点和缺点？答：链式插入排序优点是速度

6、极快，特别是在数据量大的时候效果尤为明显；其缺点是在数据量少的情况下内存相对消耗较多。直接插入排序优点是排序比较简单，稳定性高；缺点是在数据量很大的情况下效率很低。所以链式插入排序适合数据量大的情况，直接插入排序适合数据量少的情况。2.画出该图的邻接矩阵和邻接表。根据邻接表从A开始求DFS（深度优先搜索）和BFS（广度优先搜索）序列。ABCDEF答：DFS：A->C->F->E->D->BBFS:A->C->B->F->D->E3.已知序列[70,73,69,23,93,18,11,68],请给出

7、直接插入排序作升序排序每一趟的结果和快速排序作为升序排序时一趟的结果。答：直接插入排序70736923931811687073692393181168697073239318116823697073931811682369707393181168182369707393116811182369707393681118236869707393快速排序R1R2R3R4R5R6R7R8leftright[7073692393181168]110[6811692318]70[9373]15[181123]

8、68[69]70[9373]13[11]18[23]68[69]70[9373]78[111823686970[7393]9．下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。答：2113645111510.已知一个无向图的邻接表如下图所示：(1)画出这个图。(2)以v1为出发点，对图进行广度优先搜索和深度优先搜索。给出搜索的结点序列。523104答：（1）（2）.