《2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研冲刺密押题.doc》由会员分享，可在线阅读，更多相关《2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研冲刺密押题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年吉林农业大学信息技术学院829数据结构与计算机网络之数据结构考研冲刺密押题一、填空题1 应用prim 算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。始顶点号，终顶点号，权值） （2）下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。 的值在limits ?h中 /图的顶点数，应由用户定义/用二维数组作为邻接矩阵表示/生成树的边结点/边的起点与终点 /边上的权值 /最小生成树定义 /从顶点rt 出发构造图G 的最小生成树T ，rt 成为树的根结点 /初始化最小生成树T /依次求MST 的候选
2、边 /遍历当前候选边集合/选具有最小权值的候选边 /图不连通，出错处理 /修改候选边集合 【答案】（1）（0，3，1）; （3，5, 4）; （5，2，2）; （3，1, 5）; （1，4，3） （2）Tk; tovex=imin=Maxintmispos=iexit （O ）Ti; fromvex=v【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设N=V，E是连通图，是N上最小生成树边的集合。算法从属于为止。2 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_; 对于有向图来说等于该顶点的_。【答案】度；出度 3 克鲁斯卡尔算
3、法的时间复杂度为_，它对_图较为适合。【答案】O （eloge ）; 边稀疏4 深度为H 的完全二叉树至少有_个结点; 至多有_个结点; H 和结点总数N 之间的关系是_。【答案】 5 顺序存储结构是通过_表示元素之间的关系的；链式存储结构是通过_表示元素之间的关系的。【答案】物理上相邻；指针【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。6E T 开始，重复执行下述操作：在所有u属于加入集合同时将并入v直到的边（u ，v ）属于E中找一条代价最小的边求REPLACE （S ，V , m ）=_。已 知【答案】 7 起始地址为480，大小为8的块
4、，其伙伴块的起始地址是_；若块大小为32，则其伙伴块的起始地址为_。【答案】 【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下： 根据上述公式起始地址就为488。8 若用n 表示图中顶点数目，则有_条边的无向图成为完全图。【答案】n （n-l ）/2【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。9 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_次探测。【答案】 【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字
5、冲突，这个时候需要探测 的次数最小。总次数为 10在有n 个顶点的有向图中，每个顶点的度最大可达。【答案】2（n-l ）【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。11有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_。（3在4之前出栈）【答案】3个【解析】以3, 4先出栈的序列有34521、34215、34251共3个。 12设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_，又称P 为_。【答案】模式匹配；模式串二、选择题13下列关于图的叙述中，正确的是（ ）。I. 回路是简单路径II. 存储稀疏图，用邻接矩阵比邻接表更省空间 III. 若有向图中存在拓扑序列，则该图不存在回路 A. 仅 II一、填空题考研试题
