2018年中央民族大学信息工程学院856计算机学科专业综合之数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 下列哪一种图的邻接矩阵是对称矩阵？（ ）
A. 有向图
B. 无向图
C.AOV 网
D.AOE 网
【答案】B
【解析】邻接矩阵存储，就是用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间关系的二维数组称为邻接矩阵。因为无向图中边是没有方向的，
所以
，所以无向图的邻接矩阵是对称矩阵。
2． 在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。
A.O(1)
B.O(N)
C.O(N2) D.
【答案】B
【解析】二分查找的时间复杂度为。在一个用N 个元素的有序单链表中查找具有给定
关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，因此时间复杂度为0(N)。
3． 某磁盘的转速为10, 000转/分, 平均寻道时间是6ms , 磁盘传输速率是, 磁盘控制器延迟
为, 读取一个4KB 的扇区所需平均时间约为（ ）
A.9ms B.
C.12ms D.
【答案】B
【解析】磁盘转速是10000转/分钟, 平均转一转的时间是6ms , 因此平均查询扇区的时间是3ms , 平均寻道时间是6ms , 读取4KB
扇区信息的时间为
。
, 信息延迟的时间为0.2ms ,
总时间为
4． 下列四个序列中，哪一个是堆（ ）?
A.75，65，30，15，25，45，20，10
B.75，65，45，10，30，25，20，15
C.75，45，65，30，15，25，20，10
D.75，45，65，10，25，30，20，15
【答案】C
【解析】堆的定义:
n 个关键字序列
①②且且 称为堆，当且仅当该序列满足如下性质(简称为堆性质) : 小根堆:满足第①种情况的堆；
大根堆:满足第②种情况的堆。
根据堆定义即可得出答案。
5． 程序P 在机器M 上的执行时间是20秒, 编译优化后, P 执行的指令数减少到原来的70%而CPI 增加到原来的
A.
B.
D. 秒 秒 秒 倍, 则P 在M 上的执行时间是（ ） C.14秒 【答案】D 【解析】
6． 以太网交换机进行转发决策时使用的PDU 地址是（ ）.
A. 目的物理地址
B. 目的IP 地址
C. 源物理地址
D. 源IP 地址
【答案】A
【解析】交换机会监测发送到每个端口的数据帧，通过数据帧中的有关信息(源结点的MAC 地址、目的结点的MAC 地址) ，就会得到与每个端口所连接结点的MAC 地址，并在交换机的内部建立一个“
端口地址”映射表. 建立映射表后，当某个端口接收到数据帧后，交换机会读取出该帧中的目的结点的MAC 地址，并通过“端口-MAC 地址”的对应关系，迅速将数据帧转发到相应的端口，注意这里的交换机工作在数据链路层，因此关于IP 地址的选项是不对的，因此答案为
A.
7． 某计算机有五级中断
的顺序为
A.11110
B.01101
C.00011
D.01010
【答案】D , 则, 中断屏蔽字为表示对级中断进行
屏蔽。若中断响应优先级从高到低的顺序是, 且要求中断处理优先级从高到低的中断处理程序中设置的中断屏蔽字是（ ）。
B
排除掉。【解析】由于L 2的中断处理优先级下降, 屏蔽字中需要3个0, 所以可以将选项A 、
需要对开放, 所以相应位应该为“0”, 即为01010。
8． 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A.rear ＝rear ＋l
B.rear ＝(rear＋1)mod(m﹣1)
C.rear ＝(rear＋1)modm
D.rear ＝(rear＋1)mod(m＋1)
【答案】D
9． 假定下列指令已装入指令寄存器。则执行时不可能导致CPU 从用户态变为内核态(系统态) 的是（ ）。 A.
B. ; 产生软中断 C. ; 寄存器R0的内容取非 D.MOVRO , addr ; 把地址处的内存数据放入寄存器RO 中
【答案】C
【解析】A 项, 除法操作出现除数为零的情况时, 会产生内中断, CPU 切换为内核态进行中断处理; B 项, 直接产生中断, 会切换到内核态; D 项, addr 出现非法地址, 会出现中断, 进而切换到内核态。
10．在含有n 个关键字的小根堆(堆顶元素最小) 中，关键字最大的记录有可能存储在（ ）位置上。 A. B.
C.1 D.
【答案】D
【解析】小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于Ln/2」的结点上。
相关内容
相关标签