2017年合肥工业大学计算机与信息学院850计算机科学与技术学科专业基础综合之数据结构考研冲刺密押题
● 摘要
一、填空题
1． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
2． 二进制地址为011011110000，大小为和块的伙伴地址分别为：_____
【答案】011011110100；011011100000
011011110000是块的起始地址，
【解析】大小分别为式如下：
当大小为4时，起始地址
为
3． —个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
4． 一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
5． 在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。 6． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】树。故结点个数为
和其伙伴块的起始地址计算公
当大小为16时，起始地址为
：
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉
7． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】
完全二叉树的高度
8． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
9． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
10．设有两个算法在同一机器上运行，其执行时闻分别为要使前者快于后者，n 至少为_____。
【答案】15 【解析】当
时，
而，
时，
二、判断题
11．平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。（ ）
【答案】×
【解析】平衡因子定义为该结点的左子树的深度减去右子树的深度，一个平衡二叉树中，某节点的左右孩子的平衡因子为0，说明左孩子的左子树和右子数的深度相同，而且右子树的左子树和右子数的深度相同，但这不能说明该节点的左子树和右子树的深度相同。
12．任何二叉树的后序线索树进行后序遍历时都必须用栈。（ ）
【答案】×
【解析】任何结点至多只有左子树的二叉树的遍历就不需要栈。
13．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。（ ）
【答案】×
【解析】单链表不能使用折半查找方法。折半查找主要用于数据元素有序且存储方式为顺序存储的表。
14．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（ ）
【答案】√
【解析】二叉排序树是的父结点和左右子树的值的大小是确定的。
15．m 阶B 树的任何一个结点的左右子树的高度都相等。（ ）
【答案】√
【解析】由B 树的性质得知，叶子结点都处于同一层。因此，m 阶B 树的任何一个结点的左右子树的高度都相等。
16．堆肯定是一棵平衡二叉树。（ ）
【答案】×
【解析】堆是n 个元素的序列，可以看成是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。
17．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）
【答案】×
【解析】排序的稳定性指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，
且ri 在rj 之前，而在排序后的
序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。
18．若一个有向图无环，则它一定有唯一的拓扑序列。（ ）
【答案】×
【解析】有向图无环说明它一定有拓扑序列，但这个拓扑序列不唯一。如果在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，在做拓扑排序时，则排序的结果是唯一的，即它有唯一的拓扑序列。
19．数据结构的抽象操作的定义与具体实现有关。（ ）
【答案】
【解析】数据结构的抽象操作定义取决于客观存在的一组逻辑特性，与其在计算机内具体表示和实现无关。