2018年大连海事大学交通运输管理学院813管理信息系统与数据结构之数据结构考研核心题库
● 摘要
一、填空题
1． 一棵有11个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端) 结点和_____个叶子，该满二叉树的深度为_____。 【答案】或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
2． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
3． 在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】P ﹣＞next! ＝NULL
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
4． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
:_____:
{_____)
(_____、
:_____；_____；p ＝u ；
【答案】(1)L﹣＞next ＝NULL //置空链表，然后将原链表结点逐个插入到有序表中
(2)p!＝NULL //当链表尚未到尾，p 为工作指针
(3)q!＝NULL //查P 结点在链表中的插入位置，这时q 是工作指针
(4)p﹣＞next ＝r ﹣＞next //将P 结点链入链表中
(5)r﹣＞next ＝p //r是q 的前驱，u 是下个待插入结点的指针
5．
【答案】5
6． 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺序查找效率一样为。
7． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
8． 设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。
【答案】15
2n 【解析】当时，100n2>2n，而，时，100n ＜2
9． VSAM 系统是由_____、_____、_____构成的。 ＝_____
【答案】索引集；顺序集；数据集
10．堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。
【答案】选择；完全二叉树；
；O(1)；满足堆的性质
二、判断题
11．直接访问文件也能顺序访问，只是一般效率不高。（ ）
【答案】×
【解析】直接访问文件不能进行顺序访问，只能按关键字随机存取。在ISAM 文件上检索记录时，先从主索引出发找到相应的柱面索引，再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至找到为止。
12．静态链表就是一直不发生变化的链表。（ ）
【答案】 ×
【解析】用数组描述的链表，即称为静态链表。仍具有链式存储结构的主要优点。不是指不发生变化的的链表。
13．若一个广义表的表头为空表，则此广义表亦为空表。（ ）
【答案】 ×
【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。
14．对于有n 个结点的二叉树，其高度为log 2n 。（ ）
【答案】 ×
【解析】例如n 结点的单枝树，高度就为n 。
15．稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）
【答案】 √
【解析】稀疏矩阵在压缩存储后，必回失去随机存储的功能。因为在这个矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。
16．十字链表是无向图的一种存储结构。（ ）
【答案】×
【解析】十字链表是有向图的另一种链式存储结构。在十字链表中，对应于有向图的每条弧有一个结点，对应于每个顶点也有一个结点。类似于邻接表是无向图的一种链式存储结构。
17．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）
【答案】X
【解析】数据的逻辑结构是指数据元素之间的逻辑关系。
18．为提高排序速度，进行外排序时，必须选用最快的内排序算法。（ ）
【答案】×
【解析】外部排序算法最常用的是多路归并，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对己经排序的子文件进行归并排序。
19．树中的结点和图中的顶点就是指数据结构中的数据元素。（ ）
【答案】√
【解析】树中的结点和图中的顶点就是指数据结构中的数据元素，而它们的边指的是元素之