2017年上海海洋大学中国水产科学研究院(联合培养)919计算机基础综合之数据结构考研仿真模拟题
● 摘要
一、填空题
1． 已知一循环队列的存储空间为环队列判满的条件是（ ） 【答案】
2． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。 【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
3． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
4． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。 【答案】
5． 空格串是指_____，其长度等于_____。
【答案】由空格字符（值32）所组成的字符串；空格个数
6． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
7． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。
；算法 【答案】逻辑结构；物理结构；操作（运算）
8． 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_____。 【答案】
【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，
所以
第 2 页，共 64 页 其中队头和队尾指针分别为front 和rear , 则此循
二、选择题
9． 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。
A.4
B.5
C.6
D.7
【答案】C
【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个
全二叉树的高度为
叉树的高度为
10．下列有关
B. 或或 结点的完由完全二叉树类推到完全三叉树可知，n 个结点的完全三接口的叙述中错误的是：（ ） 端口
端口
指令，A. 状态端口和控制端口可以合用同一寄存器 接口中CPU 可访问寄存器，称为C. 采用独立编址方式时，【答案】D 【解析】采用统一编码方式，存储器和端口共用统一的地址空间，不需要专用的
任何对存储器数据进行操作的指令都可用于端口的数据操作。所以D 错误
11．某数采用IEEE754单精度浮点数格式表示为C640 0000H, 则该数的值是（ ） A. B. C. D.
【答案】A
IEEE754单精度浮点数格式为C640 0000H表示为二进制格式为1100 0110 0100 0000 【解析】
0000 0000 0000 0000, 转换为标准的格式为：
. 因此，浮点数的值为
12．下面关于串的叙述中，不正确的是（ ）。
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
【答案】B
第 3 页，共 64 页 端口地址和主存地址可能相同 D. 采用统一编址方式时，CPU 不能用访存指令访问
【解析】
空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。
13．数据序列
结果。
A. 选择排序
B. 起泡排序
C. 插入排序
D. 堆排序
【答案】C
【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。
14．n 个结点的线索二叉树上含有的线索数为（ ）。
【答案】C
【解析】线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有n+1个空链域。
15．组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。 A. B. C. D.
【答案】B
【解析】因组与组之间已有序，故将个组分别排序即可，基于比较的排序方法每组的时
间下界为
0全部时间下界为
16．下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。
A. 二叉排序树
B. 哈夫曼树 C.
D. 堆
【答案】D
【解析】堆的定义：
n 个关键字序列
（1）且或
第 4 页，共 64 页 只能是下列排序算法中的（ ）的两趟排序后的树 称为堆，当且仅当该序列满足如下性质（简称为堆性质）：
相关内容
相关标签