2017年上海市培养单位上海天文台862计算机学科综合(非专业)之数据结构考研强化模拟题
● 摘要
一、填空题
1． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____
，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））
【答案】归并；堆
2． 索引顺序文件既可以顺序存取，也可以_____存取。
【答案】随机
3． 设数组
储，则元素
为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，
则它的存储地址为
若以列序为主存储顺序，则它的存储地址为
4． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法
，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）
中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。
Prior （node , x ）
{ if（node !=null）
If （ （1） ） *x=node->right；else * x-node->left;
}
next （bt , node, x ）/*bt是二叉树的树根*/
{ （2） ;
if （node->rflag）（3）;
else {do t=*x；;
while （*x==node ）;
*x=t;
}
}
【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）
的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存的存储地址为_____；若以列序为主序顺序存储，则元素的存储地址
5． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。 【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
6． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度
【答案】完全；只有一个叶结点的二叉树
7． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
8． 一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
9． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。 【答案】
【解析】哈夫曼树只有度为0和2的节点。
10．文件由_____组成；记录由_____组成。
【答案】记录；数据项
11．抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
12．顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
二、选择题
13．有
A.
B.
C.
D. 个分支结点的满二叉树的深度是（ ）。
【答案】C
【解析】满二叉树的结点总数=分支的结点总数+非分支的结点总数。由于此树为满二叉树，所以非分支的结点总数为1，所以满二叉树共有个结点，所以满二叉树的深度为
14．一棵3阶B-树中含有2047个关键字，包括叶结点层，该树的最大深度为（ ）。
A.11
B.12
C.13
D.14
【答案】B
15．下列有关RAM 和ROM 的叙述中，正确的是（ ）。
I.RAM 是易失性存储器，ROM 是非易失性存储器
II.RAM 和ROM 都采用随机存取方式进行信息访问
III.RAM 和ROM 都可用作Cache
IV .RAM 和ROM 都需要进行刷新
A. 仅I 和II
B. 仅II 和III
C. 仅 I 、II 和IV
D. 仅II 、III 和IV
【答案】A
RAM 中的内容断电后即丢失ROM 中的内容断电后不会丢失，，【解析】（易失性）（非易失性）
，区别在同时RAM 和ROM 都采用随机存取方式（即CPU 对任何一个存储单元的存取时间相同）
于RAM 可读可写，ROM 只读不写。而ROM 显然不可用作Cache , 也不需要刷新，所以III 和IV 的叙述都是错误的。
16．—个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms 到达。它们的计算和
P1:计算60ms ，作顺序如下：计算
计算计算
虑调度和切换时间，则完成两个作业需要的时间最少是（ ）。
A.240ms
B.260ms
C.340ms
D.360ms
【答案】B 。
【解析】考查处理系统的性能计算，由于P2比PI 晚5ms 到达，PI 先占用CPU ，根据PI 和P2的执行过程，作业运行的甘特图如下所示，故答案为B 。 操若不考