2018年佳木斯大学信息电子技术学院816数据结构考研核心题库
● 摘要
一、单项选择题
1． 若磁盘转速为7200转/分, 平均寻道时间为8ms , 每个磁道包含1000个扇区, 则访问一个扇区的平均存取时间大约是（ ）。 A. B. C. D.
【答案】B
【解析】磁盘的平均寻址时间包括平均寻道时间和平均等待时间。平均寻道时间为8ms , 平均等待时间与磁盘转速有关, 为
。
磁盘的存取一个扇区的时间为
因此总的时间为:
。
2． 某基于动态分区存储管理的计算机，，其主存容量为55MB(初始为空闲）采用最佳适配(BestFit)算法，分配和释放的顺序为:分配15MB 、分配30MB 、释放15MB 、分配8MB 、分配6MB ，此时主存中最大空闲分，区的大小是（ ）.
A.7MB
B.9MB
C.10MB
D.15MB
【答案】B
【解析】对于简单分区内存分配，需要将进程的所有代码和数据装入内存. 故55MB 先分配15MB 余40MB ，再分配30MB 后余10MB ，释放15MB 后出现一个15MB 和一个10MB 的空闲空间，分配8MB 时按最佳适配(BestFit)算法应该使用10MB 的空闲块，余2MB 的碎片，分配6MB 时占用15MB 的空间余9MB 的碎片(空闲空间），因此最大空闲区为9MB.
3． 某磁盘的转速为10, 000转/分, 平均寻道时间是6ms , 磁盘传输速率是
为, 读取一个4KB 的扇区所需平均时间约为（ ）
A.9ms B.
C.12ms D.
第 2 页，共 78 页 , 磁盘控制器延迟
【答案】B
【解析】磁盘转速是10000转/分钟, 平均转一转的时间是6ms , 因此平均查询扇区的时间是3ms , 平均寻道时间是6ms , 读取4KB
扇区信息的时间为
。
4． 在一个文件被用户进程首次打开的过程中, 操作系统需做的是（ ）
A. 将文件内容读到内存中
B. 将文件控制块读到内存中
C. 修改文件控制块中的读写权限
D. 将文件的数据缓冲区首指针返回给用户进程
【答案】B
【解析】概念
5． n 个结点的完全有向图含有边的数目（ ）。
A.n*n
B.n(n+1)
C.n/2
D.n*(n－1)
【答案】D
【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有条边。如是有向图，需要在无向图的最多边的基础上乘以2，则为n(n－1) 。
6． 下列关于AOE 网的叙述中，不正确的是（ ）。
A. 关键活动不按期完成就会影响整个工程的完成时间
B. 任何一个关键活动提前完成，那么整个工程将会提前完成
C. 所有的关键活动提前完成，那么整个工程将会提前完成
D. 某些关键活动若提前完成，那么整个工程将会提前完成
【答案】B
【解析】关键路径是指从有向图的源点到汇点的最长路径。某些关键活动提前完成，那么整个工程将会提前完成，但不是任何一个关键活动提前完成，就能保证整个工程将会提前完成。
7． 下列有关浮点数加减运算的叙述中, 正确的是（ ）。
Ⅰ. 对阶操作不会引起阶码上溢或下溢
Ⅱ. 右规和尾数舍入都可能引起阶码上溢
Ⅲ. 左规时可能引起阶码下溢
Ⅳ. 尾数溢出时结果不一定溢出
第 3 页，共 78 页 , 信息延迟的时间为0.2ms ,
总时间为
A. 仅Ⅱ Ⅲ
B. 仅Ⅰ Ⅱ Ⅳ
C. 仅Ⅰ Ⅲ Ⅳ
D. Ⅰ Ⅱ ⅢⅣ
【答案】D
【解析】浮点数的加减运算步骤包括:①对阶, 使两个操作数的小数点位置对齐, 阶码小的尾数右移, 可能产生溢出, 但是阶码不会溢出; ②尾数求和, 将对阶后的尾数按定点数加(减) 运算规则运算; ③规格化, 包括左规和右规, 左规时阶码减少, 可能出现阶码下溢, 而右规时, 阶码增加可能出现阶码上溢; ④舍入, 该过程可能需要右规调整, 因此可能出现阶码上溢; ⑤溢出判断, 浮点数的溢出与否是由阶码的符号决定的, 而不是由尾数溢出判断的, 因此尾数溢出时结果不一定溢出。因此Ⅰ Ⅱ Ⅲ Ⅳ均正确。
8． 在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。
A.O(1)
B.O(N)
C.O(N2) D.
【答案】B
【解析】二分查找的时间复杂度为。在一个用N 个元素的有序单链表中查找具有给定
关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，因此时间复杂度为0(N)。
9． 下列程常段的时间复杂度是（ ）
A.O()
B.O(n) C.O() D.O()
【答案】C
【解析】外部循环的退出条件是k>n, 而对于k , 每次循环都执行
内部循环的退出条件是j>n, 对于j , 每次循环都执行
) , 即选C 。 段的时间复杂度为O(
10．已知串其Next 数组值为（ ）。
A.0123
B.1123
C.1231
D.1211
第 4 页，共 78 页 , 所以循环次数为; , 所以每次循环次数为n 次。所以此程序
相关内容
相关标签