2018年华北水利水电大学信息工程学院980计算机学科专业综合之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 下列选项中, 对正确接收到的数据帧进行确认的MAC 协议是（ ）。
A.CSMA B.CDMA C. D. 【答案】D
【解析】可采用排除法。CDMA 是码分多址复用, 是物理层的内容; CSMA/CD即带冲突检测的载波监听多路访问, 接收方并不需要确认; CSMA/CD是CSMA 的加强版, 故CSMA 也无确定; CSMA/CD是
中的协议, 其利用ACK 信号来避免冲突的发生, 也就是说, 只有当客户端收
到网络上返回的ACK 信号后才确认送出的数据已经正确到达目的地址, 因此答案是D 。
2． 假定用若干个位的芯片组成一个8K ×8位的存储器, 则地址0B1FH 所在芯片的最小地址是（ ）。
A.0000H B.0600H C.0700H D.0800H 【答案】D
【解析】由若干芯片构成存储器, 采用字和位同时扩展方法。8片组2个芯片, 各组芯片的地址分配分别为:
第1组, 第3组,
; 第2组, ; 第4组,
; 。
位的芯片分成4组, 每
地址0BIFH 处于第2组内, 其芯片的最小地址为0800H 。
3． 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
A. B.O(1) C.O(n) D. 【答案】B
【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为O(1)。
4． 设图的邻接矩阵A 如下所示, 各顶点的度依次是（ ）
A.1, 2, 1, 2 B.2, 2, 1, 1 C.3, 4, 2, 3 D.4, 4, 2, 2 【答案】C
【解析】当图用邻接矩阵存储时, 各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。
5． 某计算机有16个通用寄存器, 采用32位定长指令字操作码字段(含寻址方式位) 为8位, Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式, 若基址寄存器可使用任一通用寄存器, 且偏移量用补码表示, 则Store 指令中偏移量的取值范围是（ ）
A. B. C. D. 【答案】A
【解析】寄存器个数指令编址方式如下所示:
16位补码取值范围为 , 所以偏移量取值范围为 6． 有向带权图如下图图所示, 若采用迪杰斯特拉(Dijkstta)算法求从源点a 到其他各顶点的最短路径, 则得到的第一条最短路径的目标顶点是b , 第二条最短路径的目标顶点是c , 后续得到的其佘各最短路径的目标顶点依次是（ ）。
偏移量有32-8-4-4=16位
图 有向带权图
A.d , e , f
B.e , d , f C.f , d , e D.f , e , d
【答案】C 。
【解析】本题主要考查Dijkstta 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。执行Dijkstta 算法过程中各步的状态表, 故后续目标顶点依次为f , d , e 。
7． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A.0(n) B.0(n+e) C. D. 【答案】B
【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0(n+e)
8． 某计算机系统中有8台打印机，由K 个进程竞争使用，每个进程最多需要3台打印机. 该系统可能会发生死锁的K 最小值是（ ）.
A.2 B.3 C.4 D.5
【答案】C
【解析】死锁的抽屉原理一般描述是：将5个苹果放进4个抽屉，那么，必然有1个抽屉中至少有2个苹果. 计算机系统的资源分配充分体现了这一原理. 考察进程运行的特点，只要有一个进程能够运行，则运行结束后必然会归还资源，其余的进程也就会得到满足从而可以执行(这里考虑的资源主要是可重用的资源，不可重用的资源会消失，就不可用上述方法分析). 所以最少需要4个进程竞争使用，每个进程占用2台打印机，此时会产生死锁.
9． 有两个并发执行的进程P1和P2, 共享初值为1的变量x 。P1对x 加1, P2对x 减1。加1和减1操作的指令序列分别如下所示。