2018年北京市培养单位数学与系统科学研究院863计算机学科综合(专业)之数据结构考研基础五套测试题
● 摘要
一、填空题
1． 设有N 个结点的完全二叉树顺序存放在向量
【答案】 中，其下标值最大的分支结点为_____。
【解析】最大的分支结点是最后一个叶子结点的父结点。
2． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。
【答案】顺序
【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。
3． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关，即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
4． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉树。故结点个数为。
5． 在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】P ﹣＞next! ＝NULL
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
6． 实现字符串拷贝的函数strcpv 为:
(_____)
【答案】s++＝*t++或(*s++＝*t++)!＝'\0’
7． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】O(1)；O(n)
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
8． 二进制地址为011011110000, 大小为和块的伙伴地址分别为:_____
【答案】011011110100；011011100000
【解析】011011110000是块的起始地址，大小分别为算公式如下:
当大小为4时，起始地址为011011110000+0100。当大小为16时，起始地址为:011011110000-010000。
9． 完善算法:求KMP 算法.next 数组。
k :＝_____；next[1]:＝0；
k :＝_____；
END ；
【答案】0；next[k]
10．属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
和其伙伴块的起始地址计
二、判断题
11．用希尔(Shell)方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ）
【答案】×
【解析】希尔排序的基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
12．若一个广义表的表头为空表，则此广义表亦为空表。（ ）
【答案】 ×
【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。
13．对于有n 个结点的二叉树，其高度为log 2n 。（ ）
【答案】 ×
【解析】例如n 结点的单枝树，高度就为n 。
14．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）
【答案】√
【解析】由最小生成树的构建过程知，在确定根结点之后，因为连通图上各边权值均不相同，下一个结点的选择是唯一的，所以该图的最小生成树是唯一的。
15．在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（ ）
【答案】√
【解析】最佳适配法:将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户；最先适配法:从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户；从适配法选择上可以看出最佳适配法会增加闲置空间。
16．哈希函数越复杂越好，因为这样随机性好，冲突概率小。（ ）
【答案】×
【解析】随机性好和冲突概率小跟哈希函数的复杂程度无关，是根据具体情况而定的，跟实际的数据有很大关系。
17．m 阶B 树的任何一个结点的左右子树的高度都相等。（ ）
【答案】√
【解析】由B 树的性质得知，叶子结点都处于同一层。因此，m 阶B 树的任何一个结点的左右子树的高度都相等。
18．即使有向无环图的拓扑序列唯一，也不能唯一确定该图。（ ）
【答案】×
【解析】如果有向无环图的拓扑序列唯一，则能够确定每个结点的唯一前驱和后继，因此能够确定该图。
19．归并排序辅助存储为O(1)（ ）
【答案】×
【解析】归并排序的辅助存储是O Cn)o
20．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（ ）
【答案】×
相关内容
相关标签