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

《数据结构期末考试复习题及答案.docx》由会员分享，可在线阅读，更多相关《数据结构期末考试复习题及答案.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1. 什么是最小生成树？简述最小生成树的Prime算法的思想。答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。普里姆算法(Prim)的根本思想： 从连通网络 N = V, E 中的某一顶点 u0 动身，选择与它关联的具有最小权值的边(u0, v)，将其顶点参与到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点参与到集合U中。如此接着下去，直到网络中的全部顶点都参与到生成树顶点集合U中为止。2. 简述AOV网络中为何不能出现回路，如何推断AOV网络是否有回路？答：在AOV网络中，假如活动vi必需在vj之前进展，

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

3、要采纳循环队列？n个空间的循环队列，最多存储多少个元素？为什么？答：循环队列以克制依次队列的假上溢现象，能够使存储队列的向量空间得到充分的利用，所以采纳循环队列。n个空间的循环队列，最多存储n-1个元素，那是为了区分循环队列的队空和队满的条件。队空的条件是Q.front=Q.rear，而队满的条件是(Q.rear+1)%N=Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。4. 简述堆的删除算法，其删除的是那个值？答：堆的删除算法：首先，移除根节点的元素并把根节点作为当前结点比拟当前结点的两个孩子结点

4、的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比拟当前结点的孩子的大小，以此循环，直到最终一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，那么退出循环。最终把最终叶子结点的元素移给当前结点。在堆的算法里面，删除的值为根值。5. 线索二叉树中，什么是线索，它是否唯一？可有依据什么依次得到？答：指向干脆前驱结点和指向干脆后续结点的指针被称为线索Thread，加了线索的二叉树称为线索二叉树。线索二叉树是唯一的，因为知道先序遍历后，第一个根是唯一确定的，然后在中序遍历里这个根将它分为两个局部，第一个根的两棵子树的根也会唯一确定，

5、依次此类推，全部子树的根都唯一确定,二叉树就是唯一的。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,请给

6、出干脆插入排序作升序排序每一趟的结果和快速排序作为升序排序时一趟的结果。答：干脆插入排序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

7、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答： 12.DFS: 0-1-3-

8、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

9、”号结点为源结点。按提示图表给出每一步计算时最短路径的改变。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.完成下面二叉搜寻树查找插入程序

10、说明含义。此程序运用的是什么算法依据给出的结点图给出结点类的数据成员描述。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_r

11、oot-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 用堆排序方法将以下数据从小到大排序。以树的形式给出前两趟排序结果。6分35, 57,23,78, 6, 11答：A:输入数值 B:初始堆7835 2357235711356116783557231135236116a堆大小=5b堆大小=4已排序=78已排序=57,7823116611A 堆大小=3b堆大小=2已排序=35,57,78已排序=23,35,57,78