2016年新疆大学建筑工程学院数据结构复试笔试仿真模拟题
● 摘要
一、选择题
1． 某基于动态分区存储管理的计算机，，其主存容量为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 的碎片（空闲空间）
2． 下列有关接口的叙述中错误的是：（ ）
A. 状态端口和控制端口可以合用同一寄存器 B.
接口中CPU 可访问寄存器，称为
端口
端口
指令，
C. 采用独立编址方式时，【答案】D
【解析】采用统一编码方式，存储器和
端口共用统一的地址空间，不需要专用的
任何对存储器数据进行操作的指令都可用于端口的数据操作。所以D 错误
3． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
【答案】D
【解析】至少探测次数
4． 某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别为90ns 、80ns 、70ns 和60ns , 则该计算机的CPU 时钟周期至少是（ ）。
A.90ns B.80ns C.70ns D.60ns 【答案】A
端口地址和主存地址可能相同
D. 采用统一编址方式时，CPU 不能用访存指令访问
【解析】对于各功能段执行时间不同的指令流水线，计算机的CPU 时钟周期应当以最长的功能段执行时间为准。
5． 设栈S 和队列Q 的初始状态为空，元素
依次通过栈S ，一个元素出栈
后即进队列Q ，若6个元素出队的序列是则栈S 的容量至少应该是（ ）。
A.6 B.4 C.3 D.2
【答案】C
6． 已知三叉树T 中6个叶结点的权分别是2，3, 4, 5，6，7, T的带权（外部）路径长度最小是（ ）
A.27 B.46 C.54 D.56
【答案】B
【解析】利用三叉树的6个叶子结点的权构建最小带权生成树，
最小的带权路径长度为
7． 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.N B.2N-1 C.2N D.N-1
【答案】A
【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂 度为
8． 下列选项中，不可能在用户态发生的事件是（ ）。
A. 系统调用 B. 外部中断 C. 进程切换 D. 缺页 【答案】C 。
【解析】我们在学习操作系统中知道，任何一个进程在现代操作系统中为了共享和保护，设，在用户态运行用户的程序，在内核定了用户态和内核态（可以通过设置软、硬件标志位来实现）
运行系统的程序。所以，从选 项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控的，也会在任何时刻发生，缺页的发生也是不可控的，可以发生在
用户代码之间；而进程切换却不会在用户态发生。我们可以考虑一下情形，进程切换是在什么时候发生的，进程切换前必定运行的是进程调度，只有进程调度选择了下一次被调度的进程，进程切换才可以进行。进程调度是scheduler , 进程切换是dispather , 这体现了现代操作系统策略与机制，必定分离的设计思想。所以，进程切换必定不会在用户态发生（所谓发生指其起始的源头时刻）是在内核态（进程调度）发生的。
9． 单处理机系统中，可并行的是（ ）。
I. 进程与进程 II. 处理机与设备 III. 处理机与通道 IV. 设备与设备 A.I 、II 和III B.I 、II 和IV C.I 、III 和IV D.II 、III 和IV 【答案】D
【解析】注意区分并发和并行。在单处理机系统中，进程只能并发。微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的。通道是独立于CPU 控制的输入/输出的设备，处理机与通道两者是可以并行。显然，设备和设备之间也是可以并行的。
10．设置当前工作目录的主要目的是（ ）。
A. 节省外存空间 B. 节省内存空间 C. 加快文件的检索速度 D. 加快文件的读/写速度 【答案】C
【解析】工作目录只是指出了当前操作的默认目录，使得在每次访问的时候不需要由根目录 一层一层地解析，在文件路径比较长时，可以节省许多解析的时间，从而加快了文件的检索速度。
二、填空题
11．栈是_____的线性表，其运算遵循_____的原则。
；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）
12．
设单链表的结点结构为
为指针域，已知指针px 指向单链表中data 为x 的结
_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：
_____;
【答案】