《2018年江西中医药大学经济与管理学院804法理学之数据结构考研强化五套模拟题.doc》由会员分享，可在线阅读，更多相关《2018年江西中医药大学经济与管理学院804法理学之数据结构考研强化五套模拟题.doc（5页珍藏版）》请在金锄头文库上搜索。
1、2018年江西中医药大学经济与管理学院804法理学之数据结构考研强化五套模拟题-目录 2018年江西中医药大学经济与管理学院804法理学之数据结构考研强化五套模拟题（一） . 2 2018年江西中医药大学经济与管理学院804法理学之数据结构考研强化五套模拟题（二） . 10 2018年江西中医药大学经济与管理学院804法理学之数据结构考研强化五套模拟题（三） . 18 2018年江西中医药大学经济与管理学院804法理学之数据结构考研强化五套模拟题（四） . 27 2018年江西中医药大学经济与管理学院804法理学之数据结构考研强化五套模拟题（五） . 36第 1 页，共 44 页一、填空题1
2、从平均时间性能而言，_排序最佳。【答案】快速【解析】快速算法的平均时间复杂度为nlogn 。2 若用n 表示图中顶点数目，则有_条边的无向图成为完全图。【答案】 【解析】无向完全图中任意一个顶点都和其他n 1个顶点都有一条边，即为n(n1) 。又因. 。 为每条边重复出现两次，所有无向完全图的边数为 3 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 h 为附加头结点指针 (_)_； 【答案】(1)p!NULL /链表未到尾就一直进行 (2)q /将当前结点作为头结点后的第一元素结点插入4 建立索引文件的目的是_。【答案】提高查找速度 5 检索是为了在文件中寻找满足一
3、定条件的记录而设置的操作。检索可以按_检索。也可以按_检索；按_检索又可以有检索和_检索。【答案】关键字；记录号；记录号；顺序；直接 6 已知有序表为(12，18，24，35，47，50，62，83，90，115，134) 当用二分法查找90时，需次查找成功，查找47时_成功，查找100时，需_次才能确定不成功。【答案】2; 4; 3【解析】二分法查找元素次数列表第 2 页，共 44 页 查找100是找到115就停止了。7 在单链表L 中，指针P 所指结点有后继结点的条件是_【答案】P next! NULL【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。8 个有20
4、01个结点的完全二叉树的高度是_。【答案】11【解析】完全二叉树的高度 9 应用prim 算法求解连通网络的最小生成树问题。(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值) (2)下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。 的值在图的顶点数，应由用户定义用二维数组作为邻接矩阵表示生成树的边结点边的起点与终点边上的权值 最小生成树定义 从顶点rt 出发构造图G 的最小生成树T , rt 成为树的根结点 初始化最小生成树T第 3 页，共 44 页 中 依次求MST 的候选边 遍历当前候选边集合选具有最小
5、权值的候选边 图不连通，出错处理 修改候选边集合 【答案】(1)(2)【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设是N 上最小生成树边的集合。算法从属于的边为止。 10设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_，又称P 为_。【答案】模式匹配；模式串，属于E 中找一条代价最小的边加入集合是连通图，v ，直到开始，重复执行下述操作:在所有u 属于，同时将并入二、判断题11内排序要求数据一定要以顺序方式存储。（ ）【答案】【解析】由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类:一类 是内部排序；另一类是外部排序。因此，内部排序没有要求数据一定是以顺序方式存储。122，n ，a 2，a n若，桟的输入序列是1，输出序列是a 1，（ ）【答案】 【解析】出找序列不一定满足a 1a i+1. a n ，比如1进栈，然后出找，a 11。 13拓扑排序的有向图中，最多存在一条环路。（ ）【答案】【解析】要进行拓扑排序，需要满足一个条件为:若顶点A 在序列中排在顶点B 的前面，则第 4 页，共 44 页 则有:。-考研试题-
