2018年西安交通大学软件学院814计算机基础综合之数据结构考研强化五套模拟题
● 摘要
目录
2018年西安交通大学软件学院814计算机基础综合之数据结构考研强化五套模拟题（一） ... 2 2018年西安交通大学软件学院814计算机基础综合之数据结构考研强化五套模拟题（二） . 12 2018年西安交通大学软件学院814计算机基础综合之数据结构考研强化五套模拟题（三） . 22 2018年西安交通大学软件学院814计算机基础综合之数据结构考研强化五套模拟题（四） . 32 2018年西安交通大学软件学院814计算机基础综合之数据结构考研强化五套模拟题（五） . 43
一、单项选择题
1． 已知串
A.0123
B.1123
C.1231
D.1211
【答案】A 其Next 数组值为（ ）。
【解析】KMP 算法的next 数组建立的原则
2． 某二叉树结点的中序序列为BDAECF ，后序序列为DBEFCA ，则该二叉树对应的森林包括（ ）棵树。
A.1
B.2
C.3
D.4
【答案】C
【解析】由两序列可知，A 为根节点，ECF 为右子树，C 为右子树的根，F 为C 的右孩子。再由二叉树和森林的对应关系可知该二叉树对应的森林包括3棵树。根据中序序列和后序序列画出二叉树，根据二叉树得出对应的森林包含的树的棵数。
3． 某网络的IP 地址空间为采用定长子网划分，子网掩码为
网络的最大子网个数、每个子网内的最大可分配地址个数分别是（ ）.
A.32， 8
B.32， 6
C.8， 32
D.8， 30
【答案】B
【解析】子网号为5位，在CIDR 中可以表示2＝32个子网，主机号为3位，除去全0和全5则该
1的情况可以表示6个主机地址，答案为B.
4． 程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）.
A. 逻辑设备名
B. 物理设备名
C. 主设备号
D. 从设备号
【答案】A
【解析】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等. 而操作系统内部管理设备使用的是设备编号.
5． float 类型(即IEEE754单精度浮点数格式) 能表示的最大正整数是（ ）。 A. B. C. D.
【答案】D 。
【解析】IEEE754单精度浮点数尾数采用隐藏位策略的原码表示, 且阶码用移码表示的浮点数。规格化的短浮点数的真值为:
故float 类型能表示的最大整数是
。
6． 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据. 该缓冲区的逻辑结构应该是（ ）.
A. 找
B. 队列
C. 树
D. 图
【答案】B
【解析】这类问题一般都先分析题目中的数据具有什么操作特性或是结构特性比如“先进后“先进先出”等再判断其逻辑结构. 栈和队列是操作受限的线性表，出”、栈具有先进后出的特性而队列具有先进先出的特性. 由于本题中先进入打印数据缓冲区的文件先被打印，因此打印数据缓冲区具有先进先出性，则它的逻辑结构应该是队列.
7． 下列排序算法中，占用辅助空间最多的是（ ）。
A. 归并排序
B. 快速排序
, S 为符号位, E 的取值为, f 为23位;
C. 希尔排序
D. 堆排序
【答案】A
【解析】归并排序的辅助空间为O(n)，快速排序所占用的辅助空间为，堆排序所占用的辅助空间为O(1)。
8． 哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（ ）方法是哈希文件的关键。
A. 哈希函数
B. 除余法中的质数
C. 冲突处理
D. 哈希函数和冲突处理
【答案】D
【解析】哈希表是根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。
9． 为实现快速排序算法, 待排序序列宜采用的存储方式是（ ）。
A. 顺序存储
B. 散列存储
C. 链式存储
D. 索引存储
【答案】A
【解析】对绝大部分内部排序而言, 只适用于顺序存储结构, 快速排序在排序过程中, 既要从后向前查找, 也要从前向后查找, 因此宜采用顺序存储。
10．已知一棵完全二叉树的第6层(设根为第1层) 有8个叶结点，则该完全二叉树的结点个数最多是（ ）.
A.39
B.52
C.111
D.119
【答案】C
【解析】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下层. 题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度. 根据题意，一棵完全二叉树的第6层(设根为第1层) 有8个叶结点，可知此二叉树的高度是6或7. 题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7. 由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是
. 又根据二叉树的性质1可知，题
相关内容
相关标签