2017年北京市培养单位自动化研究所863计算机学科综合(专业)之数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。 【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为
2． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。 【答案】
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
3． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
4． 设广义表则 是_____tail（L ）是_____；L 的长度是_____；深度是_____。
；；2；2 【答案】（ ）（（ ））
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
5． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法
，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）
中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。
Prior （node , x ）
{ if（node !=null）
If （ （1） ） *x=node->right；else * x-node->left;
}
next （bt , node, x ）/*bt是二叉树的树根*/
{ （2） ;
if （node->rflag）（3）;
else {do t=*x；;
while （*x==node ）;
*x=t;
}
}
【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）
6． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
7． 表达式
【答案】的后缀表达式是_____。
8． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
9． —个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
10．高度为h 的堆中，最多有_____元素，最少有_____个元素。 【答案】
当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，
元素个数为一个元素时，此时堆的元素个数最少，元素个数为
二、判断题
11．AOE 网一定是有向无环图。（ ）
【答案】×
【解析】在带权的有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，则称 这种有向图表示活动的网络，简称为AOE 网。因此对AOE 网是否是有向无环图没有要求。
12．用希尔（Shell ）方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ）
【答案】×
【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
13．二元查找树的任何结点的左右子树都是二元查找树。（ ）
【答案】√
【解析】二元查找树也称作二元排序树。二元查找树的性质：①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树所有结点的值均大于它的根结点的值；③左右子树也分别为二元查找树。
14．对磁带机而言，ISAM 是一种方便的文件组织方法。（ ）
【答案】×
【解析】ISAM 是一种专为磁盘存取设计的文件组织方式。
15．程序一定是算法。（ ） 【答案】
【解析】一个程序不一定满足有穷性。而算法是对问题的解，用程序设计语言来实现来描述，这时算法就是一个程序。
16．二叉树中除叶结点外，任一结点点的值大于等于该结点
【答案】×
【解析】二叉排序树按中序遍历的结点序列是从小到大的因为某结点的左子树根结点不一定是它的中序前驱，可能会出现某结点的左子树根结点的右子树上的值大于这个结点；其右子树根结点也不一定是它的中序后继。可能会出现右子树根结点的左子树的值小于这个结点。
17．倒排序文件的优点是维护简单。（ ）
【答案】×
【解析】倒排文件的优点是检索记录较快。特别是对某些询问，不用读取记录，就可得到解答。
18．在待排数据基本有序的情况下，快速排序效果最好。（ ）
【答案】×
【解析】在待排数据基本有序的情况下，插入排序效果最好。
19．二叉树中序线索化后，不存在空指针域。（ ）
【答案】×
【解析】非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。
20．数组是同类型值的集合。（ ）
【答案】×
【解析】数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数组是元素值和下标构成的偶对的有穷集合。
其左子树根结点的值小于该结点的值；其右子树根结的值，则此二叉树一定是二叉排序树。（ ）
相关内容
相关标签