不定项选择(2014年腾讯公司校园招聘)

下列排序算法中,哪些时间复杂度不会超过nlogn【 】。

A、快速排序

B、堆排序

C、归并排序

D、冒泡排序

答案解析

BC

讨论

下列哪两个数据结构,同时具有较高的查找和删除性能【 】

已知一棵二叉树,如果先序遍历的顺序是ADCEFGHB,中序遍历的顺序是CDFEGHAB,则后序遍历的结果为【 】。

若二叉树采用二叉链表存储结构,要交换其所有分支结点左右子树的位置,利用【 】遍历方法最合适。

对二叉排序树进行【 】遍历,可以得到该二叉树所有结点构成的排序序列。

证明一棵二叉树无论进行先序、中序、后序遍历,其叶子结点的相对次序不发生改变。

对于二叉树T 的两个结点 n1 和 n2 ,我们应该选择树 T 结点的前序、中序和后序中哪两个序列来判断结点 n1 必定是结点 n2的祖先,并给出判断的方法。不需证明判断方法的正确性。

一棵二叉树按中序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序能否唯一确定这棵二叉树的结构?为什么?若已知一棵二叉树按先序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序,能否唯一确定这棵二叉树的结构?为什么?

用一维数组存放的一棵完全二叉树如下:A、B、C、D、E、F、G、H、I、J、K、L写出后序遍历该二叉树时访问结点的顺序。

已知一棵二叉树的前序遍历结果是ADCEBFIHGJ,中序遍历结果是CDEBAFHGIJ,试画出这棵二叉树。

证明,由一棵二叉树的前序序列和中序序列可唯一地确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH,中序序列为DGBEAFHC,试画出该二叉树。

对长度为10的线性表进行冒泡排序,最坏情况下需要比较的次数为__________。

初始序列为1 8 6 2 5 4 7 3一组数采用堆排序,当建堆(小根堆)完毕时,堆所对应的二叉树中序遍历序列为【 】。

下列排序算法中,不稳定的是【 】。Ⅰ. 希尔排序Ⅱ. 归并排序Ⅲ. 快速排序Ⅳ. 堆排序Ⅴ. 基数排序

使用快速排序算法对数据进行升序排序, 若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88,则该次划分的轴枢【】。

下述排序算法中,所需辅助存储量最多的是__________,所需辅助存储量最少的是__________,平均速度最快的是__________。A. 快速排序 B. 归并排序 C. 堆排序

搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过255 字节。假设目前有一千万个查询记录(重复度比较高,其实互异的查询串不超过三百万个;显然,一个查询串的重复度越高,说明查询它的用户越多,也就是越热门)。现要统计最热门的 10 个查询串,且要求使用的内存不能超过 1GB。以下各方法中,可行且效率最高的方法是【 】。

采用【 】算法对序列{18,12,10,11,23,2,7}进行一趟递增排序后,其元素的排列变为{12,10,11,18,2,7,23}。

在起泡(冒泡)排序过程中,有的关键字在某趟排序中可能朝着与最终排序相反的方向移动,请举例说明之。快速排序过程中有没有这种现象?

若需在O(log2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是【 】。

在文件“局部有序”或文件长度较小的情况下,最佳内部排序的方法是【 】。

#tis_2#