2018年东北石油大学计算机与信息技术学院702教育技术学之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 用邻接表存储图所用的空间大小（ ）。
A. 与图的顶点数和边数都有关
B. 只与图的边数有关
C. 只与图的顶点数有关
D. 与边数的平方有关
【答案】A
【解析】邻接表就是对图G 中的每个顶点建立一个单链表，第i 个单链表中的结点表示依附于顶点的边，这个单链表就称为顶点的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。
2． 用户程序发出磁盘
（ ）
A. 用户程序
B. 系统调用处理程序
C. 设备驱动程序
D. 中断处理程序
【答案】C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的, 所以答案选C 。
3． 一棵3阶B-树中含有2047个关键字，包括叶结点层，该树的最大深度为（ ）。
A.11
B.12
C.13
D.14
【答案】B
4． 下列网络设备中，能够抑制广播风暴的是（ ）.
(1)中继器
(2)集线器
(3)网桥
第 2 页，共 71 页 请求后, 系统的处理系统的处理流程是:用户程序一系统调用处理程序—设备骆动程序一中断处理程序。其中, 计算数据所在磁盘的柱面号、磁头号、扇区号的程序是
(4)路由器
A. 仅(1)和(2)
B. 仅(3)
C. 仅(3)和(4)
D. 仅(4)
【答案】D
【解析】中继器和集线器工作在物理层，不能抑制网络风暴. 为了解决冲突域的问题，提高共享介质的利用率，通常利用网桥和交换机来分隔互联网的各个网段中的通信量，以建立多个分离的冲突域. 但是，当网桥和交换机接收到一个未知转发信息的数据帧时，为了保证该帧能被目的结点正确接收，将该帧从所有的端口广播出去. 于是可以看出，网桥和交换机的冲突域等于端口的个数，广播域为1. 因此网桥不能抑制网络风暴.
5． 可以用（ ）定义一个完整的数据结构。
A. 数据元素
B. 数据对象
C. 数据关系
D 抽象数据类型
【答案】D
【解析】抽象数据类型可以定义一个完整的数据结构。包括数据元素，数据元素之间的关系，以及可以进行的操作。
6． 设有一棵3阶B 树, 如下图所示。删除关键字78得到一棵新B 树, 其最右叶结点所含的关键字是（ ）。
图 3二叉树图
A.60
B.60, 62
C.62, 65
D.65
【答案】D 。
【解析】本题主要考查B 树删除操作。即被删关键字所在的结点中的关键字个数等于
而与该结点相邻的右兄弟(或左兄弟) 结点中的关键字数目大于
(或最大) 的关键字上移至双亲结点中, 而将双亲结点中小于(或大于) 且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B 树如下, 其最右叶结点所含的
第 3 页，共 71 页 , , 则需将其兄弟结点中最小
关键字是65。
7． —个栈的入栈序列为1, 2, 3, ……, n , 其出栈序列是
取值的个数是（ ） A. B. C.
D. 无法确定
【答案】C 。若, 则, 则可能
【解析】除了3本身以外, 其他的值均可以取到, 因此可能取值的个数为n-1。
8． float 型整数据常用IEEE754单精度浮点格式表示, 假设两个float 型变量x 和Y 分别在32为寄存器f 1和f 2中, 若(f1) =CC900000H, (f2) =BOCOOOOOH, 则x 和y 之间的关系为:（ ）
A. x B. x C. x>y且符号相同 D. x>y且符号不同 【答案】A 【解析】两个数对应的IEEE754的标准形式为; 将IEEE754单精度形式的二进制转化为浮点数公式为 由于f1, f2的符号位都是1, 所以f1, f2符号相同, 而阶码上f1>f2, 所以f1>f2, 所以f1的绝对值比f2大, 而他们都是负数, 所以f1 9． 下列选项中, 在总线的数据线上传输的信息包括（ ）。 Ⅰ. Ⅱ. 接口中的命令字 接口中的状态字 Ⅲ. 中断类型号 A. 仅Ⅰ、Ⅱ B. 仅Ⅰ、Ⅲ C. 仅Ⅱ、Ⅲ 第 4 页，共 71 页