2018年北京市培养单位电子电气与通信工程学院863计算机学科综合(专业)之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。 【答案】
【解析】哈夫曼树只有度为0和2的节点。
2． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称增
量序列) 依次是4， 2， 1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; (10，7，-9，0，47，23，1，8，98，36)
3． —个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
4． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
5． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
6． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】
树。故结点个数为
7． 在哈希函数 。 中，p 值最好取_____。 【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
8． 一个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
9． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】O(1)；O(n)
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
10．假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素在B 中的存储位置k ＝_____。(注:矩阵元素下标从1开始)
【答案】93
【解析】对于上三角矩阵，k ＝(i﹣l)(2n﹣i ＋2)/2＋(j﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。
二、判断题
11．若一个广义表的表头为空表，则此广义表亦为空表。（ ）
【答案】 ×
【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。
12．哈希函数越复杂越好，因为这样随机性好，冲突概率小。（ ）
【答案】×
【解析】随机性好和冲突概率小跟哈希函数的复杂程度无关，是根据具体情况而定的，跟实际的数据有很大关系。
13．哈希表的结点中只包含数据元素自身的信息，不包含任何指针。（ ）
【答案】×
【解析】哈希表的结点中可以包括指针，指向其元素。如哈希链表。
14．m 阶B 树的任何一个结点的左右子树的高度都相等。（ ）
【答案】√
【解析】由B 树的性质得知，叶子结点都处于同一层。因此，m 阶B 树的任何一个结点的左右子树的高度都相等。
15．—个有向图的邻接表和逆邻接表中的结点个数一定相等。（ ）
【答案】√
【解析】图的邻接表表示法类似于树的孩子链表示法。对于图G 中的每个顶点，该方法把所以邻接于顶点
的
为逆邻接表示法。
链接成一个带头。在有向图中，为图中每个顶点建立一个入边表的方法称
16．算法的优劣与算法描述语言无关，但与所用计算机有关。（ ）
【答案】 ×
【解析】算法的优劣和它的时间复杂度和空间复杂度有关，与算法描述语言和所用计算机都无关。
17．串长度是指串中不同字符的个数。（ ）
【答案】 ×
【解析】不是，串长度是指串中字符的总个数。需要注意的是，在计算字符串的长度时，不要漏掉了空格。
18．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ ）
【答案】 ×
【解析】对于链式存储，数据元素之间的存储地址不一定是相邻的，即结点的存储空间可以是不连续的。而结点内部的存储空间需要是连续的，因为它是一个完整的数据。
19．在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（ ）
【答案】 ×
【解析】必须从头指针开始，查找到尾指针所指结点的前驱结点的指针。
20．即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（ ）
【答案】 ×
【解析】栈只是一种先入后出的存储结构。对于出栈、入栈的元素不进行修改，因此，输入序列的元素不相同，不可能得到相同的输出序列。
三、算法设计题
21．已知关键字序列(
试写出一算法将(
利用(1)的算法写一个建大根堆的算法。
【答案】(1)算法如下:
''
假设 是大堆，本算法把
) 是大根堆。 ) 调整为大根堆； 调成大堆