2016年广东技术师范学院电子与信息学院J235数据结构(同等学力加试)复试笔试仿真模拟题
● 摘要
一、选择题
1． 排序算法的稳定性是指（ ）。
A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变
B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变
C. 算法的排序性能与被排序元素的数量关系不大
D. 算法的排序性能与被排序元素的数量关系密切
【答案】A
【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，
且在之前，而在排序后的序列中，仍在之前，则称这种排序算法是稳定的；否则称为不稳定的。
2． 为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。
A. 顺序存储
B. 散列存储
C. 链式存储
D. 索引存储
【答案】A
【解析】对绝大部分内部排序而言，只适用于顺序存储结构，快速排序在排序过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。
3． 下列选项中会导致进程从执行态变为就绪态的事件是（ ）。
A. 执行P （wait ）操作
B. 申请内存失败
C. 启动I/O设备
D. 被尚优先级进程抢占
【答案】D
【解析】D 项，被高优先级进程抢占，进程会由执行态变为就绪态。ABC 三项，程序由于缺少资源而由执行态转为阻塞态。
4． 若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度为（ ）。
【答案】C
【解析】最快查找一次成功，最慢查找n
次成功。平均查找次数为
那么
5． 某系统有n 台互斥使用的同类设备，3个并发进程需要3, 4, 5台设备，可确保系统不发生死锁的设备数n 最小为（ ）
A.9
B.10
C.11
D.12
【答案】B
【解析】2+3+4+1 = 10
6． 程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）。
A. 逻辑设备名
B. 物理设备名
C. 主设备号
D. 从设备号
【答案】A
【解析】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等。而操作系统内部管理设备使用的是设备编号。
7． 下列存储器中，在工作期间需要周期性刷新的是（ ）。
A.SRAM
B.SDRAM
C.ROM
D.FLASH
【答案】B
【解析】动态随机存储器（DRAM ）是利用存储元电路中栅极电容上的电荷来存储信息的，电容上的电荷一般只能维持因此即使电源不掉电，信息也会自动消失。为此，每隔一定时间必须刷新。
8． 假定用若干个2Kx4位的芯片组成一个8Kx8位的存储器，则地址0B1FH 所在芯片的最小地址是（ ）。
A.0000H
B.0600H
C.0700H
D.0800H
【答案】D
【解析】由若干芯片构成存储器，采用字和位同时扩展方法。8片2Kx4位的芯片分成4组，
每组2个芯片，各组芯片的地址分配分别为：第1组，0000H 〜07FFH ; 第2组，0800H 〜0FFFH ; 第3组，1000H 〜17FFH ; 第4组，1800H 〜1FFFH 。地址0BIFH 处于第2组内，其芯片的最小地址为0800H 。
9． 分区分配内存管理方式的主要保护措施是（ ）。
A. 界地址保护
B. 程序代码保护
C. 数据保护
D. 栈保护
【答案】A
【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护。通常的界地址保护方法采用软硬件结合的方法。考生要注意本题与虚拟存储方法的区别。
10．下面关于串的叙述中，不正确的是（ ）。
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
【答案】B
【解析】
空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。
二、填空题
11．栈是_____的线性表，其运算遵循_____的原则。
；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）
12．VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
13．假定查找有序表
【答案】37/12
【解析】折半查找时每个的次数如表所示：
表
平均查找次数为
中每个元素的概率相等，则进行折半查找时的平均查找长度为_____