2016年常州大学信息学院、数理学院数据结构(同等学力加试)考研复试题库
● 摘要
一、选择题
1． 对于100Mbps 的以太网交换机，当输出端口无排队直通（cut-throughswitching ）方式转发一个以太网帧（不包括前导码）时，引入的转发延迟至少是（ ） A. B. C. D.
答:B
【解析】直通交换方式是指以太网交换机可以在各端口间交换数据。它在输入端口检测到一个数据包时，检查该包的包头，获取包的目的地址，启动内部的动态查找表转换成相应的输出端口，在输入与输出交叉处接通，把数据包直通到相应的端口，实现交换功能。通常情况下，直通交换方式只检查数据包的包头即前14个字节，由于不需要考虑前导码，只需要检测目的地址的6B ，
所以最短的传输延迟是
2． 从堆中删除一个元素的时间复杂度为（ ）。
答:B
【解析】堆中删除一个元素，需要重新调整堆，其时间复杂度为
3． 若某文件系统索引结点（inode ）中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是（ ）
A. 索引结点的总数
B. 间接地址索引的级数
C. 地址项的个数
D. 文件块大小
答:A
【解析】根据文件长度与索引结构的关系可知，只有选项A 是与单个文件长度无关的。
4． 某基于动态分区存储管理的计算机，，其主存容量为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 的碎片（空闲空间）
5． 若线性表最常用的操作是存取第I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。
A. 单链表
B. 双向链表
C. 单循环链表
D. 顺序表
答:D
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素。
6． 某机器有一个标志寄存器，其中有进位/借位标志CF 、零标志ZF 、符号标志SF 和溢出标志OF ，条件转移指令bgt （无符号整数比较大于时转移）的转移条件是（ ）。
A.CF+OF=0
B.SF+ZF=0
C.CF+ZF=0
D.CF+SF=0
答:C
【解析】判断无符号整数A>B成立，满足的条件是结果不等于0, 即零标志ZF=0, 且不发生进位，即进位/借位标志CF=0。所以正确选项为C 。其余选项中用到了符号标志SF 和溢出标志OF , 显然可以排除掉。
7． 在一个文件被用户进程首次打开的过程中，操作系统需做的是（ ）
A. 将文件内容读到内存中
B. 将文件控制块读到内存中
C. 修改文件控制块中的读写权限
D. 将文件的数据缓冲区首指针返回给用户进程
答:B
【解析】概念
8． FTP 客户和服务器间传递FTP 命令时，使用的连接是（ ）。
A. 建立在TCP 之上的控制连接
B. 建立在TCP 之上的数据连接
C. 建立在UDP 之上的控制连接
D. 建立在UDP 之上的数据连接