2018年江西农业大学计算机与信息工程学院908数据结构[专业硕士]考研核心题库
● 摘要
目录
2018年江西农业大学计算机与信息工程学院908数据结构[专业硕士]考研核心题库（一） .... 2
2018年江西农业大学计算机与信息工程学院908数据结构[专业硕士]考研核心题库（二） .. 13
2018年江西农业大学计算机与信息工程学院908数据结构[专业硕士]考研核心题库（三） .. 24
2018年江西农业大学计算机与信息工程学院908数据结构[专业硕士]考研核心题库（四） .. 36
2018年江西农业大学计算机与信息工程学院908数据结构[专业硕士]考研核心题库（五） .. 46
一、单项选择题
1． 下列关于UDP 协议的叙述中, 正确的是（ ）
Ⅰ提供无连接服务
Ⅱ提供复用/分用服务
Ⅲ通过差错校验, 保障可靠数据传输
A. 仅Ⅰ
B. 仅Ⅰ、Ⅱ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ、Ⅲ
【答案】B
UDP 无连接创建, 提供多路复用服务。【解析】虽然有差错检验, 但是不能保证可靠数据传输,
所以Ⅲ错误。
2． 某二叉树结点的中序序列为BDAECF ，后序序列为DBEFCA ，则该二叉树对应的森林包括（ ）棵树。
A.1
B.2
C.3
D.4
【答案】C
【解析】由两序列可知，A 为根节点，ECF 为右子树，C 为右子树的根，F 为C 的右孩子。再由二叉树和森林的对应关系可知该二叉树对应的森林包括3棵树。根据中序序列和后序序列画出二叉树，根据二叉树得出对应的森林包含的树的棵数。
3． 数据链路层采用选择重传协议(SR)传输数据, 发送方已发送了0H3号数据帧, 现已收到1号帧的确认, 而0、2号帧依次超时, 则此时需要重传的帧数是（ ）。
A.1
B.2
C.3
D.4
【答案】B
【解析】在选择重传协议中, 接收方逐个地确认正确接收的分组, 不管接收到的分组是否有序, 只要正确接收就发送选择ACK 分组进行确认。因此选择重传不支持累积确认, 要特别注意其与
GBN 协议的区别。本题收到1号帧的确认, 说明1号帧正确接收, 0和2号帧依次超时, 因此必须重传, 然而3号帧尚未超时, 是否正确接收未知, 故不用重传, 因此必须重传0和2号帧, 答案是B 。
4． 已知两个长度分别为m 和n 的升序链表, 若将它们合并为一个长度为m+n的降序链表, 则最坏情况下的时间复杂度是（ ） A. B. C. D.
【答案】D
m 和n 是两个升序链表长度分别为m 和n , 在合并过程中最坏的情况是两个链表中的【解析】
元素依次进行比较, 比较的次数是m 和n 中的最大值。
5． 已知小根堆为8, 15, 10, 21, 34, 16, 12, 删除关键字8之后需重建堆, 在此过程中, 关键字之间的比较数是（ ）。
A.1
B.2
C.3
D.4
【答案】C
【解析】堆排序中, 依次输出堆顶的最小值, 然后重新调整堆, 如此反复执行, 便得到一个有序序列。本题中, 删除堆顶元素8后将最后一个元素12置于堆顶, 然后调整堆:首先与15比较, 12小于15, 所以不用交换; 然后与10比较, 因为10小于12, 所以交换10和12的位置; 调整后12再与16比较, 12小于16, 调整堆过程结束。因此12共与15、10、16进行了三次比较。
6． 在有向图G 的拓扑序列中，若顶点在顶点之前，则下列情形不可能出现的是（ ）。
A.G 中有弧
C.G 中没有弧
【答案】D
【解析】若想实现图的一个拓扑排序，需要满足的一个条件为:若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到顶点A 的路径。又因为若G 中有一条从到的路径，则在拓扑序列中不可能在前。
7． 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
A.(100, 80, 90, 60, 120, 110, 130)
B.(100, 120, 110, 130, 80, 60，90)
C.(100, 60, 80, 90, 20, 110, 130)
D.(100, 80, 60, 90, 120, 130, 110)
B.G 中有一条从到的路径 D.G 中有一条从到的路径
【答案】C
【解析】二叉排序树:左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。
8． 若对如下无向图进行遍历, 则下列选项中, 不是广度优先遍历序列的是（ ）
A.h , c , a , b , d , e , g , f
B.e , a , f , g , b , h , c , d
C.d , b , c , a , h , e , f , g
D.a , b , c , d , h , e , f , g
【答案】D
【解析】根据广度优先遍历的定义, 可知选项A 、B 、C 都为广度优先遍历, 而选项D 是深度优先遍历而不是广度优先遍历, 故答案为D 。
9． 某计算机存储器按字节编址, 采用小端方式存放数据。假定编译器规定int 和short 型长度分别为32位和16位, 并且数据按边界对齐存储。某C 语言程序段如下:
若record 变量的首地址为0xC008, 则地址中内容及的地址分别为（ ）。 A. B. C. D.
【答案】D 。
32位整数a 需要占4个字节, 16位整数c 需要占2个字节, 而字符数据b 占一个字节。【解析】
a=273, 转换成十六进制是111H , 采用小端方式存放数据, 地址
边界对齐存储,
地址
中存放c 。
中存放a ,
地址中的内容为11H 。由于数据按中存放b ,
地址中空闲,
地址
相关内容
相关标签