2018年安徽理工大学计算机科学与技术841数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 下列关于无向连通图特性的叙述中，正确的是（ ）.
(1)所有的顶点的度之和为偶数
(2)边数大于顶点个数减1
(3)至少有一个顶点的度为1
A. 只有(1)
B. 只有(2)
C. (1)和(2)
D.(1)和(3)
【答案】A
【解析】在图中，
顶点的度之和与边的数目满足关系式：(n为图的总结点数，e 为总边数) ，因此， (1)项正确. 对于(2)、(3)项中的特性不是一般无向连通图的特性，可以轻松地举出反例.“至少有一个顶点的度为1”的反例如下图1所示，“边数大于顶点个数减1”的反例如下图2所示
.
图
1
图2
2． 下列关于IP 路由器功能的描述中, 正确的是（ ）。
Ⅰ. 运行路由协议, 设置路由表;
Ⅱ. 监测到拥塞时, 合理丢弃IP 分组;
Ⅲ. 对收到的IP 分组头进行差错校验, 确保传输的IP 分组不丢失;
Ⅳ. 根据收到的IP 分组的目的IP 地址, 将其转发到合适的输出线路上。
A. 仅Ⅲ、Ⅳ
B. 仅Ⅰ、Ⅱ、Ⅲ
C. 仅Ⅰ、Ⅱ、Ⅳ
D. Ⅰ、Ⅱ、Ⅲ、Ⅳ
【答案】C 。
【解析】路由器的主要功能是路由和转发, 因此Ⅰ和Ⅳ是正确的, 而针对Ⅱ和Ⅲ, 可以从ICMP 协议的差错控制出发, 注意检测到拥塞时, 合理丢弃IP 分组, 并回传ICMP 源抑制报文, Ⅱ是正确的, 而Ⅲ对收到的IP 分组头进行差错校验, 确保传输的IP 分组不丢失, 差错校验是正确的, 但网络层不
保证IP 分组不丢失, 也就是不可靠的, 因此Ⅲ的说法错误, 正确的说法仅Ⅰ、Ⅱ、Ⅳ, 因此答案是C 。
3． 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中, 正确的是（ ）。
A. 递归次数与初始数据的排列次序无关
B. 每次划分后, 先处理较长的分区可以减少递归次数
C. 每次划分后, 先处理较短的分区可以减少递归次数
D. 递归次数与每次划分后得到的分区的处理顺序无关
【答案】D
【解析】快速排序是递归的, 递归过程可用一棵二叉树给出, 递归调用层次数与二叉树的深度一致。例如:待排序列{48, 62, 35, 77, 55, 14, 35, 98) , 采用快速排序方法, 其对应递归调用过程的二叉树如下图所示。
图
在最坏情况下, 若初始序列按关键码有序或基本有序时, 快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关, 即先处理较长的分区或先处理较短的分区都不影响递归次数。
4． 执行完下列语句段后，f 值为（ ）。
A.2
B.4
C.8
D. 无限递归
【答案】B
【解析】该程序使用了递归调用，由题知，:f(0)＝2；f(l)＝l*f(0)＝2；f(2)＝2*f(l)＝4；所以结果为4。
5． 站点A 、B 、C 通过CDMA 共享链路, A 、B 、C 的码片序列(chippingsequence)分别是(1, 1, 1, 1) 、(1, -1, 1, -1) 和(1, 1, -1, -1) , 若C 从链路上收到的序列是(2, 0, 2, 0, 0, -2, 0, -2, 0, 2, 0, 2) , 则C 收到A 发送的数据是（ ）
A.000
B.101
C.110
D.111
【答案】B
【解析】用A 的码片与信息做内积运算
6． 静态链表中指针表示的是（ ）。
A. 下一元素的地址
B. 内存储器的地址
C. 下一元素在数组中的位置
D. 左链或右链指向的元素的地址
【答案】C
【解析】静态链表的一般结构为:struct static_list{ElemType data；int next；}
这种结构是预先分配一个较大的空间，类似于一次申请一个较大的数组，但是元素的增删操作都不会移动元素，只需要移动next 成员就行。因此，静态链表中的指针实际上表示的就是下一个元素在数组中的位置。
7． 下列有关总线定时的叙述中, 错误的是（ ）。
A. 异步通信方式中, 全互锁协议最慢
B. 异步通信方式中, 非互锁协议的可靠性最差
C. 同步通信方式中, 同步时钟信号可由多设备提供
D. 半同步通信方式中, 握手信号的采样由同步时钟控制
【答案】C
A 项正确, 异步通信方式中, 全互锁协议最慢, 主从模块都需要等待确认后才能撤销其【解析】
信号; B 项正确, 异步通信方式中, 非互锁协议没有相互确认机制, 因此可靠性最差; C 项错误, 同步通信要遵循统一的时钟信号, 不能由多设备提供; D 项正确, 半同步通信方式中, 握手信号的采样由同步时钟控制。
8．
操作系统的
A. 用户级
B. 用户级
C. 用户级子系统通常由四个层次组成, 每一层明确定义了与邻近层次的接口。其合理软件、设备无关软件、设备驱动程序、中断处理程序 软件、设备无关软件、中断处理程序、设备驱动程序 软件、设备驱动程序、设备无关软件、中断处理程序
的层次组织排列顺序是（ ）。