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

1. 什么是最小生成树？简述最小生成树的Prime算法的思想。答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。普里姆算法(Prim)的基本思想： 从连通网络 N = V, E 中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。2. 简述AOV网络中为何不能出现回路，如何判断AOV网络是否有回路？答：在AOV网络中，如果活动vi必须在vj之前进行，则称为存在有向边；在AOV网络中不能出现有向回路，如果出现了，则意味着某项活动应以自己作为先决条件。如何检查AOV网是否存在有向环：检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。 （1）这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 （2）如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。 3. 为何需要采用循环队列？n个空间的循环队列，最多存储多少个元素？为什么？答：循环队列以克服顺序队列的假上溢现象，能够使存储队列的向量空间得到充分的利用，所以采用循环队列。n个空间的循环队列，最多存储n-1个元素，那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front=Q.rear，而队满的条件是(Q.rear+1)%N=Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。4. 简述堆的删除算法，其删除的是那个值？答：堆的删除算法：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，则退出循环。最后把最后叶子结点的元素移给当前结点。在堆的算法里面，删除的值为根值。5. 线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？答：指向直接前驱结点和指向直接后续结点的指针被称为线索（Thread），加了线索的二叉树称为线索二叉树。线索二叉树是唯一的，因为知道先序遍历后，第一个根是唯一确定的，然后在中序遍历里这个根将它分为两个部分，第一个根的两棵子树的根也会唯一确定，依次此类推，所有子树的根都唯一确定,二叉树就是唯一的。6. 链式插入排序对比直接插入排序有何优点和缺点？答：链式插入排序优点是速度极快，特别是在数据量大的时候效果尤为明显；其缺点是在数据量少的情况下内存相对消耗较多。直接插入排序优点是排序比较简单，稳定性高；缺点是在数据量很大的情况下效率很低。所以链式插入排序适合数据量大的情况，直接插入排序适合数据量少的情况。7. 画出该图的邻接矩阵和邻接表。根据邻接表从A开始求DFS（深度优先搜索）和BFS（广度优先搜索）序列。ABCDEF答：DFS：A-C-F-E-D-BBFS: A-C-B-F-D-E8. 已知序列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 93 18 11 68 18 23 69 70 73 93 11 68 11 18 23 69 70 73 93 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 1068 11 69 23 18 70 93 73 1 518 11 23 68 69 70 93 73 1 311 18 23 68 69 70 93 73 7 811 18 23 68 69 70 73 93 9下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。答：2113645111510. 已知一个无向图的邻接表如下图所示： (1) 画出这个图。(2) 以v1为出发点，对图进行广度优先搜索和深度优先搜索。给出搜索的结点序列。523104答： （1）（2）.DFS: 0-1-3-4-5-2BFS: 0-1-2-3-5-411. 设有一组关键字（70,73,69,23,93,18,11,68）,设提供的散列表长度为12，用除留余数法设计散列函数，取的较恰当除数应为多少。采用线性探测方法解决散列冲突，请构造其散列表并将所有关键字入表。答：因为散列表长度为12，且除数应尽量取基数；所以为11.经检验：70%11=4；73%11=7；69%11=3；23%11=1; 93%11=3; 18%11=7; 11%11=0; 18%11=2;采用线性探测的哈希表（12个桶，每个桶一个槽）112318697093731812. 用最短路径算法Dijkstra计算单源多目标最短路径。图中的“1”号结点为源结点。按提示图表给出每一步计算时最短路径的变化。10432101003050206010510答：dist6存放从顶点v0到其他各顶点的当前最短路径。Path6存放在最短路径上该定点的前一顶点。S6存放以求得的在最短路径上的定点集合V6存放所有顶点012345SV-SDistpath150111110,2,3,4,5Distpath6021111,20,3,4,5Distpath900160011,2,03,4,5Distpath150311031,2,0,34,5Distpath12051,2,0,3,54Distpath1,2,0,3,5,413.完成下面二叉搜索树查找插入程序（说明含义）。此程序使用的是什么算法?根据给出的结点图给出结点类的数据成员描述。LchilddataRchildtemplate bool BST:search_and_insert( Binnode *&sub_root, const Elem &new_data) if (sub_root = NULL) sub_root = new Binnode(new_data); return ture; else if (new_data data) return search_and_insert(sub_root-lchild, new_data); else if (new_data sub_root-data)return search_and_insert(sub_root-rchild, new_data); else return false; 算法：在该函数中引用一个指向Binnode指针sub_root和指向ELEM类型的指针new_data，如果指向Binonode的指针sub_root为空，则该指针指向一个带ELEM类型数据的新结点。如果sub_root所指向的不为空，则比较sub_root-data与new-data的大小，当new_datadata,则递归调用该函数，并把sub_root-lchild作为引用指针；如果sub_root-datanew_data，则sub_rchild作为引用指针。2 用堆排序方法将下