2016年山西农业大学信息科学与工程学院数据结构(同等学力加试)考研复试题库
● 摘要
目录
2016年山西农业大学信息科学与工程学院数据结构（同等学力加试）考研复试题库（一） . .... 2
2016年山西农业大学信息科学与工程学院数据结构（同等学力加试）考研复试题库（二） . .. 10
2016年山西农业大学信息科学与工程学院数据结构（同等学力加试）考研复试题库（三） . .. 18
2016年山西农业大学信息科学与工程学院数据结构（同等学力加试）考研复试题库（四） . .. 26
2016年山西农业大学信息科学与工程学院数据结构（同等学力加试）考研复试题库（五） . .. 33
第 1 页，共 43 页
一、选择题
1． 程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）。
A. 逻辑设备名
B. 物理设备名
C. 主设备号
D. 从设备号
答:A
【解析】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等。而操作系统内部管理设备使用的是设备编号。
2． —棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有（ ）个结点。
A.2h B. C. D.
答:B
【解析】此树满足哈夫曼树，除根节点外每层有两个节点。
3． 下列选项中，导致创建新进程的操作是（ ）。
用户登录成功
设备分配
启动程序执行
A. 仅和
B. 仅和
C. 仅和
D.
答:C
【解析】进程创建是需要填写PCB 表的，其中唯一不需要的是II 。考察一个进程创建的过程是这样的：当进程被创建，可以是用户创建，例如双击相关图标；也可以由父进程创建，例如lock （ ）时，操作系统首先到PCB 表区搜索空闲的表格，若无则直接拒绝创建进程，若有则填
，许多操写PCB 表创建进程。通常填写PCB 表的过程有一段时间（主要涉及资源分配需要协调）
，也有的操作系统不设这个中间状态。此时操作系作系统为此设立了一个中间状态称为“初始化”
第 2 页，共 43 页
和
统填写进程ID 号、处理机参数、进程参数（状态、特权、优先级）、分配内存（若是虚拟存储就分配虚拟地址）、映射文件等，一切就绪，将控制权交给系统进行下一步调度。设备分配可能引起进程状态的改变，但不会创建新进程，用户登录成功和启动程序执行都会创建新的进程，所以本题答案为C 。
4． 设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，
储地址为1，每个元素占一个地址空间，则
A.13
B.33
C.18
D.40
答:B
【解析】对于对称矩阵，的地址为（ ）。 为第一元素，其存为了节省存储空间，为多个相同的元素只分配一个存储空间。
时，当时，其对于对称矩阵，元素下表之间的对应关系为：当
中k 相当于地址空间的标号，i 为行号，j 为列号。因为第一个元素存储地址为1，所以最后计算
的k 需要加1。所以
的存储位置为
5． 某基于动态分区存储管理的计算机，，其主存容量为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
，因此最大空闲区为9MB 。 时占用15MB 的空间余9MB 的碎片（空闲空间）
6． 一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。
A.107
B.108
C.214
D.215
答:B
【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有
以
7． 先序序列为a , b，c , d的不同二叉树的个数是（ ）。
A.13
第 3 页，共 43 页 所
也就是说若对其进行哈夫曼编码，共能得到108个码字。