赞
踩
正确答案:B
二分查找的最坏时间复杂度为O(log n),把n等于1000带入得到,log1000>9,<10,取整那么至少10
冒泡排序 快速排序 堆排序 简单选择排序
正确答案:B
- 快排采用分治的思想,第一次循环结束时,它实际上会产生一个轴,轴左边的都小于轴值,右边的都大于轴值,这样通过轴就分成了两个子序列,再对两个子序列递归快排,最终得到排好序的序列。
- 快排对越混乱的数据,排序效果越好,现在说一下为什么对一个基本有序的却更复杂,那是因为这样会导致每次轴划分出的两个子序列,一个趋近于1的数量级,一个趋近于n数量级,那么递归快排就近似总是对n做排序,时间复杂度O(n²),而且非常不符合快排的思想。比较好的情况是每次递归大致平分成两个n/2数量级的子序列,时间复杂度O(nlogn)
正确答案:错误
正确答案:正确
堆的空间复杂度为1,快速排序为log2(n),归并为n
正确答案:错
就是内存放不下, 才要外排的。 中间会涉及很多写文件的操作
正确答案:6-5-3-2-4-1-7
原数组已经是一个大顶堆,可直接开始排序。
(大顶堆:每个节点的值都不小于自己两个左右子节的完全二叉树)
每轮输出堆顶元素后,以堆中最后一个元素代替之(由于此题要求原地排序,即不产生额外的空间,堆顶元素与最后一个元素交换)。再将新的顶点元素不断与其子节点中大于该元素的较大者交换,直到该元素大于其左右两个子节点,或成为叶子节点。此时将剩余元素调整成一个新的大顶推。
7 2 6 6
/ \ / \ / \ / \
6 3 ==> 6 3 ==> 2 3 ==> 5 3
/ \ / \ / \ / / \ / / \ /
5 4 1 2 5 4 1 7 5 4 1 7 2 4 1 7
由此得出,第一轮结束后的顺序是:6,5,3,2,4,1,7。
正确答案:0,1,1,2,3,1,2,2,3
O(n) O(nlogn) O(n^2) O(logn)
正确答案:A
思想类似于两端向中间扫描
1、设定两个指针P1、P2,分别指向数组开始和结尾,即P1指向最小值,P2指向最大值;
2、计算 *P1+*P2 的值为 SUM,与 sum 比较,记录它们的差值 DIF 和 SUM,若 SUM<sum,P1++,若SUM>sum,P2--;
3、重复以上过程直到DIF最小
直接选择排序是一种稳定的排序方法 哈弗曼树带权路径长度最短的树,路径上权值较大的结点离根较近
拓扑排序是指结点值得有序排序
当从一个最小堆中删除一个元素时,需要把堆尾元素填补到堆顶位置,然后再按条件把它逐层向下调整到合适位置
正确答案:B D
A:直接选择排序中存在着不相邻元素之间的互换,因此,直接选择排序是一种不稳定的排序方法。 A错
B:哈夫曼树定义 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。B对
C:我查找资料说有序指的是 不是结点的值有序,是结点的逻辑先后关系保持有序 C错
D:属于堆排序过程 D对
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。