2017年北京市培养单位光电研究院863计算机学科综合(专业)之数据结构考研强化模拟题
● 摘要
一、填空题
1． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
2． 设单链表的结点结构为为指针域，已知指针px 指向单链表中data 为x 的结
_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：
_____; 【答案】
3 已
知
．
求REPLACE （S ，V , m ）=_____。 【答案】
4． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。 【答案】
5． 文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
6． 以下是用类C 语言写山的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶
head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针，试填充算法中的空格，使算法完整。
void leafchain（BiTree Abt）
{p={BiTree）malloc （sizeof （BiTNode ））;
If （!p ）{print£（“OVERFLOW\n”; exit （1）; }
head=p; top=0;
if （bt ）
{top++; stack[top]=bt;
while （top ）
{t=stack[top]; top--;
if （it->Lchild && !t->Rchild）{ （1） ; （2） ; （3） ; }
else {if（ （4） ）{top++; stack[top]= （5） ; }
if （ （6） ）{top++; stack[top]= （5） ; }
}
}
（8） ; （9） ; } }
【答案】
p->Rchild=t:t->Lchild=p:p=t: t->Rchild!=null:t->Rchild:
p->Rchild=head:head->Lchild=p
7． 在二叉树中，指针p 所指结点为叶结点的条件是_____。 【答案】
【解析】叶子节点的左右孩子都不存在。
8． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
9． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
10．数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
t->Lchild!=null: t->Lchild:
二、判断题
11．哈希表的平均查找长度与处理冲突的方法无关。（ ）
【答案】×
【解析】常见的处理冲突的方法：开放地址法；再哈希法；链地址法；建立一个公共的溢出区。选取不同的处理冲突的方法，哈希表的平均查找长度可能不同。
12．十字链表是无向图的一种存储结构。（ ）
【答案】×
【解析】十字链表是有向图的另一种链式存储结构。在十字链表中，对应于有向图的每条弧有一个结点，对应于每个顶点也有一个结点。类似于邻接表是无向图的一种链式存储结构。
13．设栈采用顺序存储结构。若已有个元素入栈，则将第i 个元素入栈时，入栈算法的时间复杂性为（ ）
【答案】
【解析】由于该栈采用顺序存储结构，时间复杂度应该为0（1）。
14．堆是满二叉树。（ ）
【答案】×
【解析】堆的定义：
n 个关键字序列
且
且 称为堆，当且仅当该序列满足如下性质（简称为堆性质）：
小根堆：满足第①种情况的堆；
大根堆：满足第②种情况的堆。
因此并不能保证堆是满二叉树。
15．为了很方便的插入和删除数据，可以使用双向链表存放数据。（ ） 【答案】
【解析】链式存储结构便于数据的插入和删除，但只能顺序访问表中的元素。
16．强连通分量是无向图的极大强连通子图。（ ）
【答案】×
【解析】强连通分量是对有向图而言的，一般在无向图中讨论连通性。
17．为提高排序速度，进行外排序时，必须选用最快的内排序算法。（ ）
【答案】×
【解析】外部排序算法最常用的是多路归并，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。
18．若一个有向图无环，则它一定有唯一的拓扑序列。（ ）
【答案】×
【解析】有向图无环说明它一定有拓扑序列，但这个拓扑序列不唯一。如果在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，在做拓扑排序时，则排序的结果是唯一的，即它有唯一的拓扑序列。
19．在初始数据表已经有序时，快速排序算法的时间复杂度为
【答案】×
【解析】当初始数据表有序，此时快速排序所需要比较的次数最多，快速排序算法的时间复杂度为〇（n2）。
20．KMP 算法的特点是在模式匹配时指示主串的指针不会变小。（ ） 【答案】
（ ）
相关内容
相关标签