2018年江苏大学理学院851数据结构之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1. 在对n 个元素的序列进行排序时,堆排序所需要的附加存储空间是( )。 A.
B.O(1)
C.O(n) D.
【答案】B
【解析】堆排序需要一个空间用于交换,因此堆排序所需要的附加存储空间为O(1)。
2. 在一个采用CSMA/CD协议的网络中,传输介质是一根完整的电缆,传输速率为1Gbps ,电缆中的信号传播速度是200000km/s.若最小数据帧长度减少800bit ,则最远的两个站点之间的距离至少需要( ).
A. 增加160m
B. 增加80m
C. 减少160m
D. 减少80m
【答案】D
【解析】以太网采用CSMA/CD访问协议,在发送的同时要进行冲突检测,这就要求在能检测出冲突的最大时间内数据包不能够发送完毕,否则冲突检测不能有效地工作。所以,当发送的数据包太短时必须进行填充。最小帧长度=碰撞窗口大小×报文发送速率,本题最小数据帧长度
89减少800b , 那么碰撞的窗口也要减少,因此距离也要减少,从而(800×2×l0)/(l×l0) =160m ,由于
时间延时存在两倍的关系,因此减少的距离为80m 。
3. 假设某计算机按字编址, Cache 有4个行, Cache 和主存之间交换的块大小为1个字。若Cache 的内容初始为空, 采用2路组相联映射方式和LRU 替换算法, 当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4, 8时, 命中Cache 的次数是( )。
A.1
B.2
C.3
D.4
【答案】C 。
【解析】Cache 有4个行, 2路组相联, 即Cache 被分成2组, 每组2行。主存地址为0〜1、4〜5、8〜9可映射到第0组Cache 中, 主存地址为2〜3、6〜7可映射到第1组Cache 中。Cache 初始为空, 采用LRU 替换算法, 当访问主存的10个地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4, 8时, 命中
Cache 的次数共有3次, 分别发生在第7、8和10步时。
4. 下列选项中, 用于提高RAID 可靠性的措施有( )
Ⅰ. 磁盘镜像
Ⅱ. 条带化
Ⅲ. 奇偶校验
Ⅳ. 增加Cache 机制
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅰ、Ⅲ和Ⅳ
D. 仅Ⅱ、Ⅲ和Ⅳ
【答案】B
【解析】能够提高RAID 可靠性的措施主要是对磁盘进行镜像处理和进行奇偶校验。其余选项不符合条件。
5. 某计算机有16个通用寄存器, 采用32位定长指令字操作码字段(含寻址方式位) 为8位, Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式, 若基址寄存器可使用任一通用寄存器, 且偏移量用补码表示, 则Store 指令中偏移量的取值范围是( ) A. B. C. D.
【答案】A
【解析】寄存器个数
指令编址方式如下所示:
16位补码取值范围为 , 所以偏移量取值范围为
6. 若对如下的二叉树进行中序线索化, 则结点x 的左、右线索指向的结点分别是( )
A.e , c
B.e , a
C.d , c
D.b , a 偏移量有32-8-4-4=16位
【答案】D
【解析】此二叉树的中序遍历序列为:debxac , 由于节点x 左右孩子都为空, 所有进行中序线索化时, 它的左右孩子指针分别指向它的中序遍历序列的直接前驱结点b 和直接后继结点a , 所以选D
7. n 个结点的线索二叉树上含有的线索数为( )。
A.2n
B.n ﹣1
C.n +1
D.n
【答案】C
【解析】线索二叉树是利用二叉树的空链域加上线索,n 个结点的二叉树有n +1个空链域。
8. 某网络拓扑如下图所示, 路由器R1
只有到达子网的路由。为使R1可以将IP 分组正确地路由到图中所有子网, 则在R1中需要增加一条路由(目的网络, 子网掩码, 下一跳) 是( )。
A.
B.
C.
D.