2017年云南大学信息学院831数据结构与操作系统考研仿真模拟题
● 摘要
一、填空题
1． 设二维数组A 的行和列的下标范围分别为
【答案】
当其值为
和
每个元素占2个单元，按行优先顺处的元素为_____。
序存储，第一个元素的存储起始位置为b ，则存储位置为
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是
时，则i=2，j=3。
2． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
3． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】
完全二叉树的高度
4． 如下的算法分别是后序线索二叉树求给定结点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 ）
5． 空格串是指_____，其长度等于_____。
【答案】由空格字符（
值32）所组成的字符串；空格个数
6． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
7． 假定查找有序表
【答案】37/12
【解析】折半查找时每个的次数如表所示：
表
平均查找次数为
8． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
9． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
10．完善算法：求KMP 算法.next 数组。
END ； 【答案】
11．在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
中每个元素的概率相等，则进行折半查找时的平均查找长度为_____
12．如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺 序查找效率一样为
13．对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度
【答案】完全；只有一个叶结点的二叉树
14．二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
15．一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
二、判断题
16．对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（ ）
【答案】√
【解析】可以有长度无穷大的广义表，只是在计算机中不能实现。
17．数组是同类型值的集合。（ ）
【答案】×
【解析】数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。因此，可以说数组是元素值和下标构成的偶对的有穷集合。
18．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ）
【答案】
【解析】算法的健壮性是指当输入数据非法时，算法能作适当的处理并作出反应，而不应死机或输出异常结果。
19．哈希函数越复杂越好，因为这样随机性好，冲突概率小。（ ）
【答案】×
【解析】随机性好和冲突概率小跟哈希函数的复杂程度无关，是根据具体情况而定的，跟实际的数据有很大
关系。