2018年武汉工程大学计算机科学与工程学院408计算机学科专业基础综合之数据结构考研核心题库-一、判断题1 设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为O(1)（ ）。【答案】 【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操作的时间复杂度是O(1)。 2 内排序要求数据一定要以顺序方式存储。（ ）【答案】【解析】由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类:一类 是内部排序；另一类是外部排序。因此，内部排序没有要求数据一定是以顺序方式存储。 3 AOE 网一定是有向无环图。（ ）【答案】【解析】在带权的有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，则称这种有向图表示活动的网络，简称为AOE 网。因此对AOE 网是否是有向无环图没有要求。 4 采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路) 。【答案】【解析】采用深度优先搜索算法主要是通过设置标志位可以判断出一个有向图中是否有环。采用拓扑排序算法，如果能够构成一个拓扑排序，则有向图中没有环，否则，有向图中有环。 5 m 阶B 树的任何一个结点的左右子树的高度都相等。（ ）【答案】【解析】由B 树的性质得知，叶子结点都处于同一层。因此，m 阶B 树的任何一个结点的左右子树的高度都相等。 6 最小生成树的Krusakl 算法是一种贪心法。（ ）【答案】【解析】在构建最小生成树常见的有三种贪心算法:第 2 页，共 42 页 。 二、单项选择题7 个进程的读磁区操作完成后, 操作系统针对该进程必做的是（ ）A. 修改进程状态为就绪态B. 降低进程优先级C. 进程分配用户内存空间D. 增加进程的时间片大小【答案】A【解析】进程等待的操作完成便会从等待状态转移到就绪状态。 8 组记录的关键码为(46，79，56，38，40，84) ，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84)D.(40，38，46，84，56，79)【答案】C【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。第一次比较:46比84小，不交换；第二次比较:40比46小，交换，此时为(40，79，56，38，46，84) ;第三次比较:46比79小，交换，此时为(40，46，56，38，79，84) ;第四次比较:38比46小，交换，此时为(40，38，56，46，79，84) ;第五次比较:56比46大，交换，此时为(40，38，46，56，79，84) ;一次划分结束。 9 已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆) ，插入关键字3，调整后的小根堆是（ ）.A.3， 5， 12， 8， 28， 20， 15， 22， 19B.3， 5， 12， 19， 20， 15， 22， 8， 28C.3， 8， 12， 5， 20， 15， 22， 28， 19D.3， 12， 5， 8， 28， 20， 15， 22， 19【答案】A【解析】在堆中插入或删除一个元素后，将不再满足堆的性质. 为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素. 具体过程如图(1)?(5)所示，(1)为原堆，(2)为插入3后，(3)、(4)为调整过程，(5)为调整后的小根堆.第 3 页，共 42 页 (3) (4) (5) 10假设磁头当前位于第105道，正在向磁道序号增加的方向移动. 现有一个磁道访问请求，序列为35，45，12，68，110，180，170，195，采用SCAN 调度(电梯调度) 算法得到的磁道访问序列是（ ）.A.110， 170， 180， 195， 68， 45， 35， 12B.110， 68， 45， 35， 12， 170， 180， 195C.110， 170， 180， 195， 12， 35， 45， 68D.12， 31， 45， 68， 110， 170， 180， 195【答案】A【解析】SCAN 算法类似电梯工作原理，即朝一个固定方向前进，经过的磁道有访问请求则第 4 页，共 42 页 -一、判断题-考研试题-