2017年中国人民公安大学安全工程823计算机学科专业基础综合[专业硕士]之数据结构考研冲刺密押题
● 摘要
一、填空题
1． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
2． 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m
阶个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；
3． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
4． 设二维数组A 的行和列的下标范围分别为
【答案】
当其值为
和
每个元素占2个单元，按行优先顺处的元素为_____。
树每个结点至多有_____个儿子，除
根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____
序存储，第一个元素的存储起始位置为b ，则存储位置为
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是
时，则i=2，j=3。
5． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
6． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。 7． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。free_tree在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；
首
先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。
【答案】
8． VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
9． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
10．
每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。
【答案】前序是
。
.
，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的
【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的
二、判断题
11．归并排序辅助存储为
【答案】×
【解析】归并排序的辅助存储是
12．算法的优劣与算法描述语言无关，但与所用计算机有关。（ ）
【答案】
【解析】算法的优劣和它的时间复杂度和空间复杂度有关，与算法描述语言和所用计算机都无关。
13．AOE 网一定是有向无环图。（ ）
【答案】×
【解析】在带权的有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，则称 这种有向图表示活动的网络，简称为AOE 网。因此对AOE 网是否是有向无环图没有要求。
14．哈希函数越复杂越好，因为这样随机性好，冲突概率小。（ ）
【答案】×
【解析】随机性好和冲突概率小跟哈希函数的复杂程度无关，是根据具体情况而定的，跟实际的数据有很大
关系。
15．最小生成树的Krusakl 算法是一种贪心法。（ ）
【答案】√
【解析】在构建最小生成树常见的有三种贪心算法：kruskal , prim , soilion 。
16．通常使用队列来处理函数或过程的调用。（ ）
【答案】
【解析】经常使用栈来处理函数或过程的调用。
17．若一个有向图无环，则它一定有唯一的拓扑序列。（ ）
【答案】×
【解析】有向图无环说明它一定有拓扑序列，但这个拓扑序列不唯一。如果在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，在做拓扑排序时，则排序的结果是唯一的，即它有唯一的拓扑序列。
（ ）