2017年中国石油大学(北京)地球物理与信息工程学院955数据结构[专业硕士]考研冲刺密押题
● 摘要
一、填空题
1． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
。
2． 设二维数组A 的行和列的下标范围分别为
【答案】
当其值为
和
每个元素占2个单元，按行优先顺处的元素为_____。
，
则结点
和
在同一层上的条件是
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
序存储，第一个元素的存储起始位置为b ，则存储位置为
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是
时，则i=2，j=3。
3． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。
；算法 【答案】逻辑结构；物理结构；操作（运算）
4． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
5． 设单链表的结点结构为为指针域，已知指针px 指向单链表中data 为x 的结_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：_____;
【答案】
第 2 页，共 41 页
6． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。
【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
7． 组成串的数据元素只能是_____。
【答案】字符
8． 在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。
9． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
【答案】（1）（2）（3）（4）（5）
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针
10．VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
二、判断题
11．若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（ ）
【答案】×
【解析】在含有N 个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也叫做最优二叉树。关键字有序，可能叶子结点部分的关键字最大，根结点的关键字部分最小，此时就不是哈夫曼树。
第 3 页，共 41 页
12．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（ ）
【答案】√
【解析】从哈希表删除一个记录，不是将这个记录的位置置空，而是设置一个标记，标记这个元素是无效的了。
13．在任何情况下，归并排序都比简单插入排序快。（ ）
【答案】×
【解析】错误。待排序序列为正序时，简单插入排序比归并排序快。
14．采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环（回路）。
【答案】√
【解析】采用深度优先搜索算法主要是通过设置标志位可以判断出一个有向图中是否有环。采用拓扑排序算法，如果能够构成一个拓扑排序，则有向图中没有环，否则，有向图中有环。
15．对于有n 个结点的二叉树，其高度为（ ）
【答案】×
【解析】例如n 结点的单枝树，高度就为n 。
16．
快速排序和归并排序在最坏情况下的比较次数都是
【答案】×
【解析】快速排序最坏的情况下比较次数是
17．两个长度不相同的串有可能相等。（ ）
【答案】
【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才相等。
18．取线性表的第i 个元素的时间同i 的大小有关。（ ）
【答案】
【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是0（1）。
19．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）
【答案】√
，使其n 个元素的最大（小）【解析】堆排序：基本思想先将原始序列构造成一个堆（初始堆）值处于序列的第一个位置；然后交换序列第一个元素与最后一个元素的位置。
第 4 页，共 41 页
（ ）