2018年天津科技大学842自命题计算机学科专业基础综合之数据结构考研核心题库
● 摘要
目录
2018年天津科技大学842自命题计算机学科专业基础综合之数据结构考研核心题库（一） ... 2 2018年天津科技大学842自命题计算机学科专业基础综合之数据结构考研核心题库（二） . 10 2018年天津科技大学842自命题计算机学科专业基础综合之数据结构考研核心题库（三） . 21 2018年天津科技大学842自命题计算机学科专业基础综合之数据结构考研核心题库（四） . 31 2018年天津科技大学842自命题计算机学科专业基础综合之数据结构考研核心题库（五） . 40
一、单项选择题
1． 将森林F 转换为对应的二叉树T , F 中叶结点的个数等于（ ）
A.T 中叶结点的个数 B.T 中度为1的结点个数 C.T 中左孩子指针为空的结点个数 D.T 中右孩子指针为空的结点个数 【答案】C
【解析】森林转化为对应的二叉树是„孩子-兄弟‟存储的, 即左孩子指针指向当前节点的孩子节点, 右孩子指针指向当前节点的兄弟节点, 所以在T 中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以选C
2． 在文件的索引节点中存放直接索引指针10个, 一级二级索引指针各1个, 磁盘块大小为1KB 。每个索引指针占4个字节。若某个文件的索引节点已在内存中, 到把该文件的偏移量(按字节编址) 为1234和307400处所在的磁盘块读入内存。需访问的磁盘块个数分别是（ ）。
A.1, 2 B.1, 3 C.2, 3 D.2, 4
【答案】B
【解析】文件的索引结点的直接索引指针有10个, 因此直接索引的偏移量范围是0〜2559, 一级索引的偏移量范围是2560〜65791, 二级索引访问的偏移量范围是65792〜45183907。偏移量1234可以通过直接索引得到在磁盘块的地址, 因此需要一次访问, 307400需要通过二级索引查找其在磁盘的位置, 需要分别访问存放二级索引的两个索引块以及对应的数据块。
3． 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表 B. 双链表
C. 带头结点的双循环链表 D. 单循环链表 【答案】A
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进 行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。
4． 若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1, 则该平衡二叉树的结点总数为（ ）。
A.12 B.20 C.32 D.33
【答案】B 。
【解析】本题的实际问题是, 具有6层结点的平衡二叉树含有最少的结点数是多少。深度为h 的平衡二叉树中含有的最少结点数, 有
由此可得
。对应的平衡二叉树如下图所示。
表示
5． 就平均性能而言，目前最好的内排序方法是（ ）排序法。
A. 起泡 B. 希尔插入 C. 交换 D. 快速 【答案】D
【解析】快速排序的平均时间复杂度是nlogn 所需要的辅助存储为间复杂度也是注意
仅仅表示的是一个量级，比如
和
的量级都为
，虽然堆排序的时
。之所以说
，所需要的辅助存储为O(1)，看似堆排序比快速排序的性能好，但是需要
快排最好，是在综合考虑的情况下。
6． 下列关于无向连通图特性的叙述中，正确的是（ ）.
(1)所有的顶点的度之和为偶数 (2)边数大于顶点个数减1 (3)至少有一个顶点的度为1 A. 只有(1) B. 只有(2)
C. (1)和(2) D.(1)和(3) 【答案】A
【解析】在图中，
顶点的度
之和与边的数目满足关系式：
(n为图的
总结点数，e 为总边数) ，因此， (1)项正确. 对于(2)、(3)项中的特性不是一般无向连通图的特性，可以轻松地举出反例.“至少有一个顶点的度为1”的反例如下图1所示，“边数大于顶点个数减1”的反例如下图2所示
.
图
1
图2
体系结构中, 直接为ICMP 提供服务的协议是（ ）。
7． 在
A.PPP B.IP C.UDP D.TCP
【答案】B 。
【解析】首先明确ICMP 是网络层的协议, 由于服务必须是下一层向上一层提供服务的, 因此选项C 项中的UDP 和选项D 项中的TCP 属于传输层, 在网络层上面, 所以显然错误, 而PPP 协议是广域网数据链路层协议, 直接为网络层, 也就是IP 层提供服务, ICMP 协议是封装在网络层, 因此PPP 不能直接为ICMP 提供服务, ICMP 报文直接封装在IP 分组中, 故答案是B 。
8． 下列关于USB 总线特性的描述中, 错误的是（ ）。
A. 可实现外设的即插即用和热插拔 B. 可通过级联方式连接多台外设 C. 是一种通信总线, 可连接不同外设 D. 同时可传输2位数据, 数据传输率高 【答案】D 。
【解析】USB 总线即通用串行总线, 它的特点有:
(1)即插即用; (2)热插拔; (3)有很强的链接能力能将所有外设链接起来, 且不损失带宽; (4)有很好的可扩展性; (5)高速传输, 速度可达480Mbps 。
所有A , B , C 都符合USB 总线的特点。对于选项D , USB 是串行总线, 不能同时传输两位数据, 所以答案为D 。
相关内容
相关标签