2017年武汉科技大学生物医学研究院856数据结构(C语言版)考研强化模拟题
● 摘要
一、选择题
1． 某网络的IP 地址空间为采用定长子网划分，子网掩码为则该网络的最大子网个数、每个子网内的最大可分配地址个数分别是（ ）。
A.32, 8
B.32, 6
C.8, 32
D.8, 30
【答案】B
【解析】子网号为5位，在CIDR 中可以表示个子网，主机号为3位，除去全0和全1的情况可以表示6个主机地址，答案为B 。
2． 某基于动态分区存储管理的计算机，，其主存容量为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 的碎片（空闲空间）
3． 已知字符串S 为“abaabaabacacaabaabcc ”，模式串t 为“abaabc ”，采用KMP 算法进行匹配，第一次出现“失配” （
A.i=l，j=0
B.i=5，j=0
C.i=5，j=2
D.i=6，j=2
【答案】C
【解析】模式匹配（KMP ）算法对普通的暴力匹配的改进在于：每当匹配过程中匹配失败时，主串（本题为S ）的指针（i ）不需要回溯，而是利用已经得到的“部分匹配”的结果将模式串（t ）向右“滑动”尽可能远的一段距离后，继续进行比较。模式串“滑动”的距离是由模式串（t ）本身决定的，即t
的子串中前缀串和后缀串相等的最长长度。本题中第一次失配i=5, 字串为
第 2 页，共 70 页 ，i=j = 5，则下次开始匹配时，i 和j 的值分别是（ ））。 “abaab”，其相等且最长的前后缀为“ab”，一次下一个j = 2。
4． 某主机的IP 地址为180.80.77.55, 子网掩码为255.255.252.0。若该主机向其所在子网发送广播分组，则目的地址可以是（ ）。
A.180.80.76.0
B.180.80.76.255
C.180.80.77.255
D.180.80.79.255
【答案】D 。
【解析】IPv4地址中的特殊地址，直接广播地址，也就是把主机位全部设置为1，这里77的二进制是01001101, 子网掩码252的二进制是11111100，由此可以看到77的前6位作为子网位，后四位作为主机位，由此可以知道 其广播地址是180.80.01001111.255，也就是180.80.79.255，因此答案是D 。
5． 已知串
A.0123
B.1123
C.1231
D.1211
【答案】A 其Next 数组值为（ ）。
【解析】KMP 算法的next 数组建立的原则
6． 下列有关总线定时的叙述中，错误的是（ ）。
A. 异步通信方式中，全互锁协议最慢
B. 异步通信方式中，非互锁协议的可靠性最差
C. 同步通信方式中，同步时钟信号可由多设备提供
D. 半同步通信方式中，握手信号的采样由同步时钟控制
【答案】C
【解析】A 项正确，异步通信方式中，全互锁协议最慢，主从模块都需要等待确认后才能撤销其信号；B 项正确，异步通信方式中，非互锁协议没有相互确认机制，因此可靠性最差；C 项错误，同步通信要遵循统一的时钟信号，不能由多设备提供；D 项正确，半同步通信方式中，握手信号的采样由同步时钟控制。
7． 下列选项中，不可能在用户态发生的事件是（ ）。
A. 系统调用
B. 外部中断
C. 进程切换
第 3 页，共 70 页
D. 缺页
【答案】C 。
【解析】我们在学习操作系统中知道，任何一个进程在现代操作系统中为了共享和保护，设
，在用户态运行用户的程序，在内核定了用户态和内核态（可以通过设置软、硬件标志位来实现）
运行系统的程序。所以，从选 项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控的，也会在任何时刻发生，缺页的发生也是不可控的，可以发生在用户代码之间；而进程切换却不会在用户态发生。我们可以考虑一下情形，进程切换是在什么时候发生的，进程切换前必定运行的是进程调度，只有进程调度选择了下一次被调度的进程，进程切换才可以进行。进程调度是scheduler , 进程切换是dispather , 这体现了现代操作系统策略与机制
，必定分离的设计思想。所以，进程切换必定不会在用户态发生（所谓发生指其起始的源头时刻）
是在内核态（进程调度）发生的。
8．
用户程序发出磁盘请求后，系统的处理系统的处理流程是：用户程序一系统调用处理程序一设备骆动程序一中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是（ ）
A. 用户程序
B. 系统调用处理程序
C. 设备驱动程序
D. 中断处理程序
【答案】C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的，所以答案选C 。
9． 一个TCP 连接总是以1KB 的最大段发送TCP 段，发送方有足够多的数据要发送。当拥塞窗口为16KB 时发生了超时，如果接下来的4个RTT （往返时间）时间内的TCP 段的传输都是成功的，那么当第4个RTT 时间内发送的所有TCP 段都得到肯定应答时，拥塞窗口大小是（ ）。
A.7KB
B.8KB
C.9KB
D.16KB
【答案】C
【解析】回顾TCP 流量控制和拥塞控制（慢启动）的知识点，从第一个MSS 开始，每次发送成功，拥塞窗口值翻倍，四次以后，应该为16, 但是由于拥塞阈值变为16/2=8, 故三次成功后为8, 以后为线性增长，故为8+1=9, 答案为C 。
10．从堆中删除一个元素的时间复杂度为（ ）。
【答案】B
【解析】堆中删除一个元素，需要重新调整堆，其时间复杂度为
第 4 页，共 70 页
相关内容
相关标签