《2018年北京市培养单位空间应用工程与技术中心863计算机学科综合(专业)之数据结构考研强化五套模拟题.doc》由会员分享，可在线阅读，更多相关《2018年北京市培养单位空间应用工程与技术中心863计算机学科综合(专业)之数据结构考研强化五套模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2018年北京市培养单位空间应用工程与技术中心863计算机学科综合(专业)之数据结构考研强化五套模拟题一、填空题1 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_存储结构。【答案】顺序【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。 2 数组的存储结构采用_存储方式。【答案】顺序存储结构【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。3 一个算法具有5个特性: _、_、_、有零个或多
2、个输入、有一个或多个输出。【答案】有穷性；确定性；可行性 4 应用prim 算法求解连通网络的最小生成树问题。(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值) (2)下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。 的值在图的顶点数，应由用户定义用二维数组作为邻接矩阵表示第 2 页，共 63 页中 生成树的边结点边的起点与终点边上的权值 最小生成树定义 从顶点rt 出发构造图G 的最小生成树T , rt 成为树的根结点 初始化最小生成树T 依次求MST 的候选边 遍历当前候选边集合选具有最小权值的候选边
3、图不连通，出错处理 修改候选边集合 【答案】(1)(2)【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设是N 上最小生成树边的集合。算法从属于的边为止。 5 建立索引文件的目的是_。【答案】提高查找速度 6 在单链表中设置头结点的作用是_。【答案】方便运算 7 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_的排序方法。【答案】稳定第 3 页，共 63 页 是连通图，v ，直到，开始，重复执行下述操作:在所有u 属于加入集合，同时将并入属于E 中找一条代价最小的边8 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则
4、最省时间的是_算法，最费时间的是_算法。【答案】起泡；快速【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，2而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。 9 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_。【答案】69【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。10模式串的next 函数值序列为_。【答案】01122312二、判断题11设模式串的长度为m ，目标串的长度为n ，当n m 且处理只匹配一次的模式时，朴素的匹配(即子串定位函数) 算法所花的时
5、间代价可能会更为节省。（ ）【答案】 【解析】因为两个字符串的长度几乎相等，因此，在进行相应的匹配时，只需要定位父串的前几位即可。12 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）【答案】 【解析】数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。 13线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ ）【答案】 【解析】对于链式存储，数据元素之间的存储地址不一定是相邻的，即结点的存储空间可以是不连续的。而结点内部的存储空间需要是连续的，因为它是一个完整的数据。 14树形结构中元素之间存在一对多的关系。（ ）【答案】【解析】树形结构是非线性结构，存在一对多的关系。15若一个有向图无环，则它一定有唯一的拓扑序列。（ ）【答案】【解析】有向图无环说明它一定有拓扑序列，但这个拓扑序列不唯一。如果在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，在做拓扑排序时，则排序的结果是唯一的，即它有第 4 页，共 63 页一、填空题考研试题
