牛客网选择题整理20190624

排序

外排中使用置换选择排序的目的,是为了增加初始归并段的长度。√
插入排序：需要有一个对比查找过程；选择排序直接插入指定位置。
快速排序中，第i趟排序结果至少确定i个元素的位置。
使用堆排序方法排序（45,78,57,25,41,89），初始堆为89,78,57,25,41,45。
将两个各有n个元素的有序表归并成一个有序表,最少的比较次数是n，最多是2n-1。

解析：
方法：
1. 首先将所有元素按照初始顺序填充到一个完全二叉树中
2. 从“最后一个非终端节点”开始，调用siftdown方法，调整堆的结构，直到根节点为止。
图示：

对于冒泡排序和插入排序来说，每一趟都能确定一个元素的最终位置。
设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。

解析：序列分为了5组：25,50；15,35；80,85；20,40；36,70。对前两组进行归并，得到：15,25,35,50；对第3、4组归并得到：20,40,80,85；第5组直接输出：36，70。所以最后结果是：15,25,35,50,20,40,80,85,36,70。

图

连通图上各边权值均不相同，则改图的最少生成树是唯一的。
拓扑排序反映的是一个工程能否顺利进行的问题。表示工程的有向图，顶点表示活动，弧表示活动之间的优先关系，AOV网（Activity On Vertex Network）排序算法：从AOV网中选择入度为0的顶点输出，然后删除此顶点，并删除以此顶点为尾的弧，重复直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。采用的图的数据结构：邻接表，加一个存储入度的空间。
关键路径：从源点到汇点的最长路径。
AOE（activity on Edge）以弧表示活动。AOV（activity on vertex network）以顶点表示活动。
在一个无向图中，所有顶点的度数之和等于图的边数的2倍。
拓扑序列和有向无环图的结构不是一一对应的。
设某无向图中有n个顶点e条边，则该无向图中所有顶点的度之和为2e。
已知无向图G有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是11。

解析：已知图G有16条边，所以其度为32。由于计算顶点个数最少为多少，所以假设剩余的顶点度为2，这样才能保证顶点个数最少。假设度为2的顶点有x个，则可得出：4×3+3×4+x×2=32，解之得x=4。所以顶点个数为3+4+4=11个。

树

将森林转换为对应的二叉树，若在二叉树结点中，结点m是结点n的双亲结点的双亲结点，则在原来的森林中，m和n可能具有的关系是____。
1.父子关系
2.m的双亲结点与n的双亲结点是兄弟关系
3.兄弟关系

解析：若在深林中m的父结点和n的父结点是兄弟关系。那么变成二叉树后，他们形成单边右斜关系，而u和v分别在他们各自的左子树内，不可能在一条路径上，所以2是不可能的。
对于1、3来说，分别如下图：

m阶B树的定义：
二叉树的线索化：对于二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点左，右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。
前驱（pre）:以中序线索二叉树的建立为例，指针pre指向中序遍历时上一个刚刚访问过的结点。
若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为((n-1)/(m-1))

解析：哈夫曼树并不是局限于二叉树，可能也存在于多叉树。对于二叉树来说，哈夫曼树是最优二叉树（严格二叉树）；对于m叉树来说，是最优m叉树（严格m叉树）。
对于度为m的哈夫曼树来说，节点的度要么为0，要么为m。设度不为零的点有a个，则总结点数为a+n。
由于除根节点外，其余每一个结点都有一个分支连向一个节点，对于度为m的每个节点都有m个分支，而度为0的节点是没有分支的，所以从分支角度来看，总的结点数是am+1。
am+1=a+n，所以a=(n-1)/(m-1)。

网络流

图示是一个网络流从s到t的某时刻快照。此时t处一共接收到10+13+16=39单位流量。每条横线上的数字表示当前流量和管道的容量。那么，该网络最大的流量是多少？41。

解析：
第一层为s，朝着重点最大输出为11+22+10=43。
第二层为结点1,2,3：节点一最多输出10，这是受了结点4的限制；结点2最多17，因为结点5发出最大为23；结点3最多为14，这是被结点3的入度所限制了，入度为14。所以总体是10+17+14=41。
第三层为结点4,5,6：输出为10+16+16=42。
min(43,41,42)=41。