1.8数算总复习PART2

?

?

?

?

?

B?

?

结构?

?

有序表是指关键字有序的线性表，仅描述元素之间的逻辑关系，既可以顺序存储（使用数组）也可以链式存储（使用指针），不受存储结构制约，由于有序受到逻辑制约，属于逻辑结构。
哈希表，是个大数组，顺序存储。?

?

?

?

?

?

区分线性表与顺序表?

?

?

?

就是判断是否又能链式存储又能顺序存储，如果是的话就是逻辑结构，不然就是指定的某种存储结构?

?

?

?

?

但是向BST中插入一个结点，就不一定是叶子节点?

?

?

3.二叉搜索树（二叉排序树）的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无 右孩子。
对?

5.从二叉搜索树的根结点一直沿右儿子向下找不一定能找到树中值最大的结点。
错

?

?

一共还有7个空位置，注意再向下比较时由于是空的，所以比不了了，不能比了，所以就是2*2?

?

答案 D.最大值一定在叶结点上

首先我们从知道，比根节点大的放在右边，比根节点小的放在左边，那么有一种情况就是，比根节点大的放在左边，然后这个根节点又没有右孩子。如下图

很简单的例子，那么这棵树中最大值应该是9，而它不是叶子节点。

那么再看B选项，我们假设最小值不在叶节点，而同时我们不要忘了题目要求，是个完全二叉树，那么也就是说，整棵树的左下角，要么是从左到右有部分节点有孩子，要么都没有，那么根据假设条件，这个最小值不是叶节点，它必须有左孩子，那就说明它不是最小值，与假设相反。所以最小值一定在叶节点。最后是C选项，依然是完全二叉树的问题，如果是一棵满二叉树，那么中位值肯定在根节点上，因为左右子树节点数相同。而如果右子树不满，那么左子树的节点数多，所以中位数自然在左子树里。

?

?

?

用哈希（散列）表?散列表查找法的特点是平均查找长度与结点个数n无关；?

?

注意即使7上存了元素，也不能去算他，因为初始算出来的Index就在0~6之间?

?

对于II，非同义词也可能挤占冲突后的同义词地方?

?

?

就是第i层的元素个数，是2^(n-1)

?

?

虽然某个具体的元素的查找长度改变了，但是总和依旧没变，因为是从头开始找的，就总是1~n，那么平均时间是相同的?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

?

折半查找就是形成严格的完全二叉树，1，2，4，8个元素，搜索路径总和为1+2*2+4*3+8*4=1+4+12+32=49,故B?

?

下标从0开始时，左孩子是2*i+1,从1开始时，左孩子是2*i?

若先序遍历x在y之前，则不能说明x是y的父节点，因为还可能是y的左兄弟，如果在后序中，x也在y之后，那才确定x是Y的父节点，但是依然不能确定y是x的什么孩子，会出现两种情况

在序列当中，由于是只能有一个孩子，所以这俩必定是粘在一起的，即紧邻的一层

?

后序是左右根，这样的话就能保证左<右<根，就是说编号大小顺序，和结点遍历出现的次序相匹配?

?

?

画图模拟?

?

最少的话，就是每层都只有2个结点，根节点除外，根节点那层一个结点，然后向下是两个，选择一个继续向下延申两个，一共H层，就是2h-1,减去的1就是根节点所在那一层?

?

?

n个结点,那么每个结点除了根节点，都有一个链域，有n个结点，就有nd个链域，有用的就n-1个，故为nd-n+1=n(d-1)+1个空链域?

?

?

?

如果是反着叙述，即两两合并的话，就是归并排序?

?

?

说明就是保持着最小结点数的最高平衡二叉树，如果非叶子结点的平衡因子均为1?

?

?

?

?

?

?

在树中，没有孩子没有右兄弟、转到二叉树就是叶子结点，没有孩子有右兄弟是度为1的结点，且只有右孩子，有孩子没有右兄弟是度为1的结点，且只含左孩子，有孩子有右兄弟是度为2的结点

这题的关键在于把树拆分成4部分，依据是否有孩子以及兄弟?

且在树中。没有孩子结点就是叶子结点

就是说，无子无兄的树结点和二叉树的叶子结点，有子有兄的树节点和度为2的二叉树结点是一一对应的，而且N0与N2之间满足关系，即无子无兄与有子有兄的树结点之间满足关系?

?

?

解答：B
将森林转换成二叉树的步骤：1、树中所有相邻兄弟结点之间架一条连线；2、对树中的每个结点，只保留其与第一个孩子结点之间的连线，删除其他连线；3、调整树的形态和角度。
因此，如果在二叉树中结点u是结点v的父结点的父结点，那么在森林中结点u和结点v是兄弟结点；结点u是结点v的双亲结点
?

2、判断：若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空指针域。

解答：对
n个节点的二叉链表一共有2n个链域，n个节点，分支数为n-1（除了根节点每个结点都有一个分支进入），即非空链域有n-1个，那么空链域有2n-(n-1)=n+1个

?

?

7、在单链表中设置头结点的作用是什么？

（1）便于首元结点的处理。首元结点的地址保存在了头结点的指针域中，则对链表的第一个数据元素的操作就可以和其他数据元素的操作一样，无需特殊化处理。 （2）便于空表和非空表的统一处理。无论是空表还是非空表，头指针都是指向头节点的非空指针。?

?

插入尾结点是O1的复杂度，但删除尾结点，由于是单链表，所以要不断往后找到尾结点的前驱才能删，是ON的复杂度?

?

1. 堆的形状是一棵（ 完全二叉树 ）

?

?

希尔排序的基本思想是：取一个小于n的整数d1作为第一个增量，
把文件的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中。
首先在各组内进行直接插入排序；然后，取第二个增量d2＜d1重复上述的分组和排序，直至所取的增量dt=1(dt＜dt-1＜…＜d2＜d1)，
即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
根据希尔排序的基本思想，题目中给出了增量是3，
而关键字序列(56，23，78，92，88，67，19，34)中的元素个数是8，
其分成的分组分别是(56，92，19)(23，88，34)(78，67)，
对各个分组进行直接插入排序后得到的是(19，56，92)(23，34，88)(67，78)，再将各排好序的分组放到原序列各分组相应的位置，
可以得到(19，23，67，56，34，78，92，88)。
?

?

也可能只有一棵，因为这个无向连通图本身就是生成树，那么就只能构成它自己

?

?

?

注意完全的概念?

?

横向搜索，增加分支数、减小高度，就是说，增加每层的结点个数，从而减少层数，从而到达高度最小的目的，一旦联通了就终止，那么此时BFS的结果就一定是高度最小的?

?

这是要让二叉树变为一棵树，如果二叉树有右孩子，那么就会转化出多棵树称为森林?