2018年河北大学计算机科学与技术学院862数据结构(计)考研强化五套模拟题
● 摘要
一、单选题
1． 下列排序算法中，其中（ ）是稳定的。
A. 堆排序，起泡排序
B. 快速排序，堆排序
C. 直接选择排序，归并排序
D. 归并排序，起泡排序
【答案】D
2． 设无向图的顶点个数为m 则该图最多有（ ）条边。
A.n-1 B. C.
D.0E.n2
【答案】B
【解析】在数据结构中仅讨论简单图，在计算无向图的最多边时，不考虑顶点与顶点的边。因此边数最多时，构成的是无向完全图。此时的边数为
3． 4个圆盘的Hanoi 塔，总的移动次数为（ ）。
A.7 B.
C.15
D.16
【答案】C 。
【解析】Hanoi 问题总移动次数为:2M 次。
4． 下列选项中, 对正确接收到的数据帧进行确认的MAC 协议是（ ）。
A.CSMA
B.CDMA C. D.
【答案】D
【解析】可采用排除法。CDMA 是码分多址复用, 是物理层的内容; CSMA/CD即带冲突检测的载波监听多路访问, 接收方并不需要确认; CSMA/CD是CSMA 的加强版, 故CSMA 也无确定; CSMA/CD是中的协议, 其利用ACK 信号来避免冲突的发生, 也就是说, 只有当客户端收到网络上返回的ACK 信号后才确认送出的数据已经正确到达目的地址, 因此答案是D 。
5． 某系统有n 台互斥使用的同类设备, 3个并发进程需要3, 4, 5台设备, 可确保系统不发生死锁的设备数n 最小为（ ）
A.9
B.10
C.11
D.12
【答案】B 【解析】
6． 若一个用户进程通过read 系统调用读取一个磁盘文件中的数据, 则下列关于此过程的叙述中, 正确的是（ ）。
Ⅰ. 若该文件的数据不在内存, 则该进程进入睡眠等待状态;
Ⅱ. 请求read 系统调用会导致CPU 从用户态切换到核心态;
Ⅲ.read 系统调用的参数应包含文件的名称
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】A
【解析】对于Ⅰ, 当所读文件的数据不再内存时, 产生中断(缺页中断、缺段中断) , 原进程进入睡眠等待状态(阻塞状态) , 直到所需数据从外村调入内存后, 将该进程唤醒, 使其变为就绪状态。对于Ⅱ, read 系统调用cpu 将从用户态切换到核心态, 从而获取操作系统提供的服务。对于Ⅲ, 在操作
Open 系统调用的参数需要包含文件的系统中, 要读一个文件首先要open 系统调用将该文件打开。
路径名与文件名, 而read 系统调用只需使用open 返回的文件描述符, 并不使用文件名作为参数。Read 系统调用要求用户提供三个输入参数:
①文件描述符; ②buf 缓冲区首址; ③传送的字节数n 。
read 系统调用的功能是试图从fd 所指示的文件中读入n 个字节的数据, 并将它们送至由指针buf 所指示的缓冲区中。
7． 用邻接表存储图所用的空间大小（ ）。
A. 与图的顶点数和边数都有关
B. 只与图的边数有关
C. 只与图的顶点数有关
D. 与边数的平方有关
【答案】A
【解析】邻接表就是对图G 中的每个顶点建立一个单链表，第i 个单链表中的结点表示依
附于顶点的边，这个单链表就称为顶点的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。
8． 假定有4个整数用8位补码分别表示为
放在一个8位寄存器中, 则下列运算会发生溢出的是（ ）。 A. B. C. D.
【答案】B
【解析】用补码表示时8位寄存器所能表示的整数范围为
数
, , 在4个选项中, 只有。现在4个整数都是负, 结果溢出, 其余3个算式结果。若将运算结果存都未超过127, 不发生溢出
9． 假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz ，则总线带宽是（ ）.
A.10MB/s
B.20MB/S
C.40MB/S
D.80MB/S
【答案】B
【解析】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送. 总线时钟频率为10MHz ，时钟周期为，总线周期占用2个时钟周期，为＝一个总线周期中并行传输4字节信息，则总线带宽是＝20MB/s.
10．下列措施中, 能加快虚实地址转换的是1增大快表(TLB)2让页表常驻内存3增大交换区（ ）
A. 仅1
B. 仅2
C. 仅1, 2
D. 仅2, 3
【答案】C
【解析】加大快表能增加快表的命中率, 即减少了访问内存的次数; 让页表常驻内存能够使cpu 不用访问内存找页表, 从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用, 对虚实地址转换并无影响
11．在子网
A.0
B.1
C.2 中, 能接收目的地址为的IP 分组的最大主机数是（ ）。