2018年江西理工大学信息工程学院873数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆) ，插入关键字3，调整后的小根堆是（ ）.
A.3， 5， 12， 8， 28， 20， 15， 22， 19 B.3， 5， 12， 19， 20， 15， 22， 8， 28 C.3， 8， 12， 5， 20， 15， 22， 28， 19 D.3， 12， 5， 8， 28， 20， 15， 22， 19
【答案】A
【解析】在堆中插入或删除一个元素后，将不再满足堆的性质. 为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素. 具体过程如图(1)〜(5)所示，(1)为原堆，(2)为插入3后，(3)、(4)为调整过程，(5)为调整后的小根堆
.
(3)
(4)
2． 下列选项中, 用于设备和控制器(
A.PCI B.USB C.AGP D. 【答案】B
(5)
接口) 之间互连的接口标准是（ ）
【解析】设备和设备控制器之间的接口是USB 接口, 其余选项不符合, 故答案为B 。
3． 单级中断系统中, 中断服务程序内的执行顺序是（ ）。
Ⅰ保护现场; Ⅱ开中断; Ⅲ关中断; Ⅳ保存断点; Ⅴ中断事件处理; Ⅵ恢复现场; Ⅶ中断返回 A. B. C. D. 【答案】A
【解析】程序中断有单级中断和多级中断之分, 单级中断在CPU 执行中断服务程序的过程中不能被打断, 即不允许中断嵌套。保存断点与关中断的任务是由硬件(中断隐指令) 完成的, 所以在单级中断系统中, 中断服务程序内应完成的任务有:
①保存现场; ②中断事件处理; ③恢复现场; ④开中断; ⑤中断返回。
4． 图中有关路径的定义正确的是（ ）。
A. 由顶点和相邻顶点构成的边所形成的序列 B. 由不同顶点所形成的序列 C. 由不同边所形成的序列 D. 上述定义都不是 【答案】A 【解析】顶点
到顶点
之间的一条路径是指顶点序列
。路径上边的
数目称为路径的长度。
5． 对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。
A.n B.n ﹣2
C.n ﹣1 D.n ＋1 【答案】c
【解析】每个结点(除根节点外) 都是一个分支，即所有结点的度数之和等于分支个数等于总的结点数减一，即n ﹣1。
6． 用户程序发出磁盘请求后, 系统的处理系统的处理流程是:用户程序一系统调用处理程序—设备骆动程序一中断处理程序。其中, 计算数据所在磁盘的柱面号、磁头号、扇区号的程序是（ ）
A. 用户程序 B. 系统调用处理程序 C. 设备驱动程序 D. 中断处理程序 【答案】C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的, 所以答案选C 。
7． 主机甲通过1个路由器个路由器(存储转发方式) 与主机乙互联, 两段链路的数据传输速率均为10Mbps , 主机甲分别采用报文交换和组大小为10kb 的分组交换向主机乙发送1个大小为8Mb(1M=106)的报文。若忽略链路传播延迟、分组头开销和拆装时间, 则两种交换方式完成该报文传输所需的总时间分别为（ ）
A.800ms>1600ms B.801ms 、1600ms
C.1600ms 、800ms D.1600ms 、801ms 【答案】D
【解析】不进行分组时, 发送一个报文的时延是
的时延也是800ms 共计1600ms 。进行分组后发送一个报文的时延是总时间为801ms 。
8． 算法的计算量的大小称为计算的（ ）。
A. 效率 B. 复杂性 C. 现实性 D. 难度 【答案】B
, 在接收端接收此报文件
, 接收一个
报文的时延也是1ms , 但是在发送第二个报文时, 第一个报文已经开始接收。共计有800个分组,
相关内容
相关标签