2017年中北大学软件学院821数据结构与算法考研强化模拟题
● 摘要
一、选择题
1． 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。
A. 直接插入排序
B. 起泡排序
C. 简单选择排序
D. 快速排序
【答案】A
【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需趟排序，也即时间复杂度仍为而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时
；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即间复杂度为0（nlog2n ）
n-1趟，比较的时间复杂度由
降至
2． 如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为（ ）。
A.1条，1条
B.1条，多条
C. 多条，1条
D. 多条，多条
【答案】A
【解析】所谓递归查询方式就是：如果主机所询问的本地域名服务器不知道被查询域名的IP 地址，那么本地域名服务器就以DNS 客户的身份向其他服务器继续发出查询请求报文，而不是让该主机自行下一步的查询。所以主机只需向本地域名服务器发送一条域名请求，采用递归查询方法，本地域名服务器也只需向上一级的根域名服务器发送一条域名请求，然后依次递归。正确选项为A 。
3． 程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）。
A. 逻辑设备名
B. 物理设备名
C. 主设备号
D. 从设备号
【答案】A
【解析】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等。而操作系统内部管理设备使用的是设备编号。
4． 冯. 诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是（ ）。
A. 指令操作码的译码结果
B. 指令和数据的寻址方式
C. 指令周期的不同阶段
D. 指令和数据所在的存储单元
【答案】C
【解析】在冯•诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU 可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段（分析取数阶段、执行阶段）取出的是数据。所以，CPU 区分指令和数据的依据是指令周期的不同阶段。
5． 某容量为256M 的存储器，由若干
和数据引脚总数是：（ ）
A.19
B.22
C.30
D.36
【答案】A
【解析】DRAM 地址线复用，4M 为2的22次方，因此除2为11根，数据线8根。因此地址引脚和数据引脚总数为19根
6． 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。
A. 直接插入排序
B. 起泡排序
C. 基数排序
D. 快速排序
【答案】C
【解析】C 项，基数排序是采用分配和收集实现的，不需要进行关键字的比较。ABD 三项都依赖关键字的比较，不同的初始排列次序下元素移动的次数有很大变化，最好情况元素正序，则不用移动，最坏情况元素反序，则需要移动n （n-1） /2次（为元素个数）。
位的DRAM 芯片构成，该DRAM 芯片的地址引脚
7． 在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（ ）。
A. 机械特性
B. 功能特性
C. 过程特性
D. 电气特性
【答案】C 。
【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性；机械特性：主要定义物理连接的边界点，即接插装置；电气特性：规定传输二进制位时，线路上信号的电压高低、阻抗匹配、传输速率和距离限制；功能特性：主要定义各条物理线路的功能；规程特性：主要定义各条物理线路的工作规程和时序关系。而从题干可以 分析描述事件先后顺序的就是规程，也就是过程特性，答案是C 。
8． 下列各类存储器中，不采用随机存取方式的是（ ）。
A.EPROM
B.CDROM
C.DRAM
D.SRAM
【答案】B
【解析】随机存取方式是指存储器的任何一个存储单元的内容都可以存取，而且存取时间与存储单元的物理位置无关。CDROM 是只读的光盘存储器，采用串行存取方式而不是随机存取方式。
9． 下列有关总线定时的叙述中，错误的是（ ）。
A. 异步通信方式中，全互锁协议最慢
B. 异步通信方式中，非互锁协议的可靠性最差
C. 同步通信方式中，同步时钟信号可由多设备提供
D. 半同步通信方式中，握手信号的采样由同步时钟控制
【答案】C
【解析】A 项正确，异步通信方式中，全互锁协议最慢，主从模块都需要等待确认后才能撤销其信号；B 项正确，异步通信方式中，非互锁协议没有相互确认机制，因此可靠性最差；C 项错误，同步通信要遵循统一的时钟信号，不能由多设备提供；D 项正确，半同步通信方式中，握手信号的采样由同步时钟控制。
10．在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。
【答案】B
【解析】二分查找的时间复杂度为在一个用N 个元素的有序单链表中查找具有给定
相关内容
相关标签