资讯详情

①、算法

最坏情况下时间复杂度为O(nlogn)的排序算法有( )

A：基数排序

B：归并排序

C：堆排序

D：快速排序

答案：BC

解析：基数排序是考虑多个关键字的排序方法，同样关键字内可以选择任意一种合适的排序，关键字之间再次排序，时间复杂度可以写成O(n*r)，其中，n为数据数目，r为基的数目。归并排序是基于分治策略的方法，其基本点是合并两个有序的队列，其最坏，平均和最好的时间复杂度都是 O(nlogn)，但是需要一个辅助的空间。堆排序是借助于堆的排序，利用堆的性质，堆排序最坏，平均和最好时间复杂度都是 O(nlogn)。快速排序也是基于分治策略的方法，最坏情况的时间复杂度是O(n^2)，平均时间和最好时间复杂度是O(nlogn)。

②、数据结构

以下说法正确的有( )

A：在m阶B-树中，所有的非终端节点至少包含m/2个节点

B：若一个叶节点是某二叉树中的中序遍历的最后一个节点，同时它也是该二叉树前序遍历的最后一个节点

C：插入排序，堆排序，快速排序算法中，快速排序的速度是最快的，所需的附加空间也是最少的

D：n个数中已知有k个关键字hash值相同，若用线性探测法将他们存入散列表中，至少需要进行k(k+1)/2次探测

答案：B

解析：B-树是一种多叉平衡查找树。一个m阶的B树中，根节点至少有2个孩子;除了根节点和叶子节点外，其他内部节点至少包含 m/2个孩子节点。若考虑根节点可以只有2个孩子，则选项A不正确。二叉树中序遍历的顺序是左子树-根-右子树，前序遍历的顺序是根-左子树-右子树。若中序遍历的最后结点是叶结点，则它的父结点是它的前驱遍历结点，该叶结点是父节点的右孩子;因此在前序遍历时，该叶节点必然仍然是最后遍历的。快速排序需要辅助空间，最好和平均情况下的空间复杂度为O(logn)。在哈希表中存入第一个同义关键字后，后面至少连续有k-1个单元为空，故按照线性探测法可以依次存入剩余的k-1个关键字，至少需要1+2+ ...+ k-1= k(k-1)/2 次。