2017年北京市培养单位工程科学学院863计算机学科综合(专业)之数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
2． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
3． 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2；4；3
【解析】二分法查找元素次数列表
查
找100是找到115就停止了。
4． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。
5． 空格串是指_____，其长度等于_____。
【答案】由空格字符（
值32）所组成的字符串；空格个数
6． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
7． 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺 序查找效率一样为
8． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
9． 完善算法：求KMP 算法.next 数组。
END ； 【答案】
10．设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; （10，7，-9，0，47，23，1，8，98，36）
二、判断题
11．树形结构中元素之间存在一对多的关系。（ ）
【答案】√
【解析】树形结构是非线性结构，存在一对多的关系。
12．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）
【答案】×
【解析】例如起泡排序是稳定排序，将4，3，2，1按起泡排序排成升序序列，第一趟变成3，2，1，4，此时3就朝向最终位置的相反方向移动。
13．顺序存储结构的主要缺点是不利于插入或删除操作。（ ）
【答案】
【解析】因为顺序表的插入删除会移动大量的元素。
14．归并排序辅助存储为（ ）
【答案】×
【解析】归并排序的辅助存储是
15．一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第的最多结点数为
【答案】√
【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为 层具有最大的结点数为
16．无环有向图才能进行拓扑排序。（ ）
【答案】√
【解析】在图论中，由一个有向无环图的顶点组成的序列，才能进行拓扑排序。
17．即使有向无环图的拓扑序列唯一，也不能唯一确定该图。（ ）
【答案】×
余下的
个结点在第k 层的任一位置上。（ ）
层具有
层全满时，
此时从根结点到第
【解析】如果有向无环图的拓扑序列唯一，则能够确定每个结点的唯一前驱和后继，因此能够确定该图。
18．从逻辑结构上看，n 维数组的每个元素均属于n 个向量。（ ）
【答案】√
【解析】对于每一维，都有一个向量共用这个元素，比如我们最常见的二维数组，对于每个元素，在行和列都有一个向量共用这个元素。
19．循环队列也存在空间溢出问题。（ ）
【答案】
【解析】循环队列的存储空间也是有限的，因此也存在空间溢出问题。
20．负载因子（装填因子）是哈希表的一个重要参数，它反映哈希表的装满程度。（ ）
【答案】√
【解析】查找过程中需和给定值进行比较的关键字的个数取决于三个因素：哈希函数，处理冲突的方法和哈希表的装填因子。其中装填因子标志哈希表的装满程度。
三、算法设计题
21．写算法将单链表11拆成二个链表，其中以11为头的链表保持原来向后的链接，另一个链表的头为12，其链接方向与11相反，11包含原链表的奇数序号的结点，12包含原链表的偶数序号的结点。
【答案】算法如下：