2017年北京市培养单位工程科学学院863计算机学科综合(专业)之数据结构考研强化模拟题
● 摘要
一、填空题
1． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
2． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
3． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
4． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
5． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
6． 模式串
的next 函数值序列为_____。
【答案】01122312
7． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ） 而快速排序算法需要比较的次数达到最大，时间复杂度为
8． 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2；4；3
【解析】二分法查找元素次数列表
查
找100是找到115就停止了。
9． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
10．阅读下列程序，指出其功能，并写出空格处应填上的语句。
的元素，如该元素已在哈希表中，报告出错。
【答案】
【解析】本题是在哈希表ht[]中插入值为
二、判断题
11．堆是满二叉树。（ ）
【答案】× 【解析】堆的定义： n 个关键字序列
且
且
称为堆，当且仅当该序列满足如下性质（简称为堆性质）：
小根堆：满足第①种情况的堆； 大根堆：满足第②种情况的堆。
因此并不能保证堆是满二叉树。
12．有向图中顶点V 度等于其邻接矩阵中第V 行中的1的个数。（ ）
【答案】×
【解析】有向图顶点V 的出度等于其邻接矩阵第V 行中的1的个数，而有向图中V 的度等
于其邻接矩阵中边表出现的V 的个数。
13．任何二叉树的后序线索树进行后序遍历时都必须用栈。（ ）
【答案】×
【解析】任何结点至多只有左子树的二叉树的遍历就不需要栈。
14．在外部排序过程中，对长度为n 的初始序列进行“置换-选择”排序时，可以得到的最大初始有序段的长度不超过
【答案】×
【解析】当输入文件以关键字的升序排序时，只能得到一个长度为文件长度的初始归并段
15．算法的优劣与算法描述语言无关，但与所用计算机有关。（ ）
【答案】
【解析】算法的优劣和它的时间复杂度和空间复杂度有关，与算法描述语言和所用计算机都无关。
16．用希尔（Shell ）方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ）
【答案】×
【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
17．两个长度不相同的串有可能相等。（ ）
【答案】
【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才相等。
18．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ）
【答案】
【解析】前者正确，后者错误。顺序存储方式在插入、删除元素时需要挪动大量的元素，执行效率较低。
19．队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）
【答案】
【解析】栈只能在一端进行操作，队列可以在表的两端进行运算。
20．二叉树中序线索化后，不存在空指针域。（ ）
【答案】×
【解析】非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱
（ ）