2018年中北大学计算机与控制工程学院820数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 在一个文件被用户进程首次打开的过程中, 操作系统需做的是（ ）
A. 将文件内容读到内存中
B. 将文件控制块读到内存中
C. 修改文件控制块中的读写权限
D. 将文件的数据缓冲区首指针返回给用户进程
【答案】B
【解析】概念
2． 设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作（ ）。
A. 求子串
B. 判断是否相等
C. 模型匹配
D. 连接
【答案】C
【解析】常用的串的基本操作有七种，INDEX(s，t) 是其中的定位函数，这种运算就是所说的模式匹配。
3． 设无向图的顶点个数为m 则该图最多有（ ）条边。
A.n-1 B. C.
D.0E.n2
【答案】B
【解析】在数据结构中仅讨论简单图，在计算无向图的最多边时，不考虑顶点与顶点的边。因此边数最多时，构成的是无向完全图。此时的边数为。
4． 基于比较方法的n 个数据的内部排序。 最坏情况下的时间复杂度能达到的最好下界是（ ）。
A. B.
C. O (n) D.
【答案】A
【解析】在内部排序中，最坏情况下的时间复杂度为
第 2 页，共 76 页 。
5． 下列选项中, 在用户态执行的是（ ）。
A. 命令解释程序
B. 缺页处理程序
C. 进程调度程序
D. 时钟中断处理程序
【答案】A
【解析】题目是问用户态执行, 可见是有关操作系统基本概念的问题。四个选项中, 用户唯一能面对的是命令解释程序, 缺页处理程序和时钟中断都属于中断, 在核心态执行, 而进城调度属于系统调用在核心态执行。只有命令解释程序属于命令接口, 可以运行在用户态, 接受用户的命令操作控制。
6． 若某文件系统索引结点(inode)中有直接地址项和间接地址项, 则下列选项中, 与单个文件长度无关的因素是（ ）
A. 索引结点的总数
B. 间接地址索引的级数
C. 地址项的个数
D. 文件块大小
【答案】A
【解析】根据文件长度与索引结构的关系可知, 只有选项A 是与单个文件长度无关的。
7． 将一棵树t 转换为孩子兄弟链表表示的二叉树h ，则t 的后序遍历是h 的（ ）。
A. 前序遍历
B. 中序遍历
C. 后序遍历
【答案】B
【解析】树的后序遍历恰好对应于二叉树的中序遍历。
8． 可以用（ ）定义一个完整的数据结构。
A. 数据元素
B. 数据对象
C. 数据关系
D 抽象数据类型
【答案】D
【解析】抽象数据类型可以定义一个完整的数据结构。包括数据元素，数据元素之间的关系，以及可以进行的操作。
第 3 页，共 76 页
9． 程序P 在机器M 上的执行时间是20秒, 编译优化后, P 执行的指令数减少到原来的70%而CPI 增加到原来的
A.
B.
D. 秒 秒 秒 倍, 则P 在M 上的执行时间是（ ） C.14秒 【答案】D 【解析】
10．下面关于B 和B+树的叙述中，不正确的是（ ）
A.B 树和B+树都是平衡的多叉树
B.B 树和B+树都可用于文件的索引结构
C.B 树和B+树都能有效地支持顺序检索
D.B 树和B+树都能有效地支持随机检索
【答案】C
【解析】B 树是一种平衡的多分树，通常我们说m 阶的B 树，它必须满足如下条件:①每个结点至多有m 个子结点；②除根结点和叶结点外，其它每个结点至少有个子结点；③若根结点不是叶子结点，则至少有两个子结点；④所有的叶结点在同一层；⑤有k 个子结点的非根结点恰好包含k －1个关键码。B+树是B 树的一种变形树，它与B 树的差异在于:有k 个子结点的结点必然有k 个关键码；非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。其中B 树适合与随即检索，不适合于顺序检索，所以C 项错误。
11．某计算机存储器按字节编址, 主存地址空间大小为64MB ,
现用
32MB 的主存储器, 则存储器地址寄存器MAR 的位数至少是（ ）。
A.22位
B.23位
C.25位
D.26位
【答案】D
【解析】虽然实际的主存储器(RAM区) 只有32MB , 但不排除还有ROM 区, 考虑到存储器扩展的需要, MAR 应保证能访问到整个主存地址空间。因为主存的地址空间大小为64MB , 所以MAR 的位数至少需要26位。
12．某磁盘的转速为10, 000转/分, 平均寻道时间是6ms , 磁盘传输速率是
为, 读取一个4KB 的扇区所需平均时间约为（ ）
A.9ms B.
第 4 页，共 76 页 位的RAM 芯片组成, 磁盘控制器延迟
相关内容
相关标签