2018年中国农业科学院农业信息所808数据结构考研核心题库
● 摘要
一、单项选择题
1． 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear ，front 的值分别为多少？（ ）
A.1和5
B.2和4
C.4和2
D.5和1
【答案】B
【解析】入队操作的主要步骤:rear ＝(rear+1)%6，加入一个后，rear ＝(0+1)%6＝1，再加入一个后，rear ＝(1+1)%6＝2。出队操作的主要步骤:front ＝(front+1)%6。删除一个后，front ＝(3+1)%6＝4。
2． 关键路径是AOE 网中（ ）。
A. 从始点到终点的最短路径
B. 从始点到终点的最长路径
C. 从始点到终点的边数最多的路径
D. 从始点到终点的边数最少的路径
【答案】B
【解析】在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目) 。路径长度最长的路径称作关键路径(critical path)。
3． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
A.O(2n)
B.O(n)
C.O(n2)
D.O(log2n )
【答案】C
2【解析】两个循环嵌套，那么语句x :＝x+l:则被执行了n 次。
4． 用海明码对长度为8位的数据进行检/纠错时, 若能纠正一位错, 则校验位数至少为（ ）
A.2
B.3
C.4
D.5
【答案】C
【解析】设校验位的位数为k , 数据位的位数为n , 根据海明码编码k 和n 应满足下述关系。
。
n=8, 当k=4时, , 符合要求, 校验位至少是4位, 故答案为C 。
5． 当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）。
A. 必定快
B. 不一定
C. 在大部分情况下要快
D. 取决于表递增还是递减
【答案】C
【解析】对于有序顺序存储表折半查找的效率较高，但是不是所有情况下都是如此，比如要查找的元素就是第一个时，用顺序查找比它就快的多了。这类情况外折半都高于顺序查找。
6． 下列措施中, 能加快虚实地址转换的是1增大快表(TLB)2让页表常驻内存3增大交换区（ ）
A. 仅1
B. 仅2
C. 仅1, 2
D. 仅2, 3
【答案】C
【解析】加大快表能增加快表的命中率, 即减少了访问内存的次数; 让页表常驻内存能够使cpu 不用访问内存找页表, 从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用, 对虚实地址转换并无影响
7． 有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（ ）。
A.543612
B.453126
C.346521
D.234156
【答案】C
【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5
在6之上，所以出栈时5要比6先出枝。
8． 在物理层接口特性中, 用于描述完成每种功能的事件发生顺序的是（ ）。
A. 机械特性
B. 功能特性
C. 过程特性
D. 电气特性
【答案】C 。
【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性; 机械特性:主要定义物理连接的边界点, 即接插装置; 电气特性:规定传输二进制位时, 线路上信号的电压高低、阻抗匹配、传输速率和距离限制; 功能特性:主要定义各条物理线路的功能; 规程特性:主要定义各条物理线路的工作规程和时序关系。而从题干可以分析描述事件先后顺序的就是规程, 也就是过程特性, 答案是C 。
9． 某计算机主频为1.2GHz , 其指令分为4类, 它们在基准程序中所占比例及CPI 如下表所示。
该机的MIPS 数是（ ）
A.100
B.200
C.400
D.600
【答案】C
【解析】基准程序的
。 , 为1200MHz , 该机器的MIPS 为计算机的主频为。
10．设被排序的结点序列共有N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（ ）。 A. B. | C. D.
【答案】C
【解析】因为该序列中的结点己经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为O(N)。对于采用归并法，它是一种稳定的排序方法，它
相关内容
相关标签