2018年塔里木大学信息工程学院813数电与数据结构之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 以太网交换机进行转发决策时使用的PDU 地址是（ ）.
A. 目的物理地址
B. 目的IP 地址
C. 源物理地址
D. 源IP 地址
【答案】A
【解析】交换机会监测发送到每个端口的数据帧，通过数据帧中的有关信息(源结点的MAC 地址、目的结点的MAC 地址) ，就会得到与每个端口所连接结点的MAC 地址，并在交换机的内部建立一个“
端口地址”映射表. 建立映射表后，当某个端口接收到数据帧后，交换机会读取出该帧中的目的结点的MAC 地址，并通过“端口-MAC 地址”的对应关系，迅速将数据帧转发到相应的端口，注意这里的交换机工作在数据链路层，因此关于IP 地址的选项是不对的，因此答案为
A.
2． 相对于微程序控制器，硬布线控制器的特点是（ ）.
A. 指令执行速度慢，指令功能的修改和扩展容易
B. 指令执行速度慢，指令功能的修改和扩展难
C. 指令执行速度快，指令功能的修改和扩展容易
D. 指令执行速度快，指令功能的修改和扩展难
【答案】D
【解析】在同样的半导体工艺条件下，硬布线(组合逻辑) 控制器的速度比微程序控制器的速度快. 这是因为硬布线控制器的速度主要取决于逻辑电路的延迟，而微程序控制器增加了一级控制存储器，执行的每条微指令都要从控制存储器中读取，影响了速度. 由于硬布线控制器一旦设计完成就很难改变，所以指令功能的修改和扩
3． 若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（ ）。
A. 对称矩阵
B. 稀疏矩阵
C. 三角矩阵
D. —般矩阵
【答案】C
【解析】在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为改图的一个拓扑排序:①每个顶点出现且出现一次；②若顶点在序列中排在顶点B 的前面，则在图
中不存在从顶点B 到顶点A 的路径。由拓扑排序的性质知，有向图的邻接矩阵必定为三角矩阵。
4． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A.0(n)
B.0(n+e) C. D.
【答案】B
【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0(n+e)
5． 用户程序发出磁盘请求后, 系统的处理系统的处理流程是:用户程序一系统调用处理程序—设备骆动程序一中断处理程序。其中, 计算数据所在磁盘的柱面号、磁头号、扇区号的程序是（ ）
A. 用户程序
B. 系统调用处理程序
C. 设备驱动程序
D. 中断处理程序
【答案】C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的, 所以答案选C 。
6． 下列关于图的叙述中, 正确的是（ ）。
Ⅰ. 回路是简单路径
Ⅱ. 存储稀疏图, 用邻接矩阵比邻接表更省空间
Ⅲ. 若有向图中存在拓扑序列, 则该图不存在回路
A. 仅Ⅱ
B. 仅Ⅰ、Ⅱ
C. 仅Ⅲ
D. 仅Ⅰ、Ⅲ
【答案】C
【解析】第一个顶点和最后一个顶点相同的路径称为回路; 序列中顶点不重复出现的路径称为简单路径; 回路显然不是简单路径, 所以选项Ⅰ错误。稀疏图用邻接表表示比邻接矩阵节省存储空间, 稠密图适合用邻接矩阵的存储表示, 所以选项Ⅱ错误。利用拓扑排序算法可以判断图中是否存在回路, 即在拓扑排序输出结束后所余下的顶点都有前驱, 则说明了只得到了部分顶点的拓扑有序序列, 图中存在回路。所以选项Ⅲ正确。
7． 下列序列中，（ ）是执行第一趟快速排序后所得的序列。 A. B. C. D.
【答案】C
【解析】快速排序将数据划分成两部分，其中一部分关键字比另一部分关键字小。
8． 向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行（ ）。
A.h ﹣＞next ＝s ；
B.s ﹣＞next ＝h ；
C.s ﹣＞next ＝h ；h ﹣＞next ＝s ；
D.s ﹣＞next ＝h ﹣next ；h ﹣＞next ＝s ；
【答案】D
【解析】本题是向一个链栈中插入结点，可从头结点后插入。先将s 结点指向第一个头结点之后的结点之前，再将头结点指向s 结点。
9． 某主机的IP 地址为, 子网掩码为
分组, 则目的地址可以是（ ）。 A. B. C. D.
【答案】D 。
【解析IPv4地址中的特殊地址, 直接广播地址, 也就是把主机位全部设置为1, 这里77的二进制是01001101, 子网掩码252的二进制是11111100, 由此可以看到77的前6位作为子网位, 后四位
, 也就是作为主机位, 由此可以知道其广播地址是
10．下列关于进程和线程的叙述中, 正确的是（ ）。
A. 不管系统是否支持线程, 进程都是资源分配的基本单位
B. 线程是资源分配的基本单位, 进程是调度的基本单位
C. 系统级线程和用户级线程的切换都需要内核的支持
D. 同一进程中的各个线程拥有各自不同的地址空间
【答案】A 。
【解析】利用排除法来确定正确答案:“线程是资源分配的基本单位, 进程是调度的基本单位”这句话说反了, 明显错误。“系统级线程和用户级线程的切换都需要内核的支持”也不正确, 因为用户级线程的切换由用户编写的RimtimeSystem 执行的, 内核并不感知。“同一进程中的各个线程拥有各自不同的地址空间”明显错误, 引入线程的目的就是为了同一进程的所有线程能共享
。若该主机向其所在子网发送广播, 因此答案是D 。