1.将N条长度均为M的有序链表进行合并,合并以后的链表也保持有序,时间复杂度为(A)
A O(N * M * logN)
B O(N*M)
C O(N)
D O(M)
建立一个长度为N的最大/最小堆:将这N条链表的第一个元素拿出来建立最大/小堆,时间复杂度为O(N);依次从最小堆中取出堆顶元素,此时堆顶就是当前集合的最小值,将链表的其他元素放入堆中,调整堆的时间复杂度(O(logN)),总共还需要入堆的元素个数,O(NMlogN);建堆+不断调整堆(不断取出堆顶素)O(N)+o(NMlogN)
2.已知某个哈希表的n个关键字具有相同的哈希值,如果使用二次探测再散列法将这n个关键字存入哈希表,至少要进行(E)次探测
A n-1
B n
C n+1
D n(n+1)
E n(n+1)/2
F 1+n(n+1)/2
思路:第一个关键字探测次数为1;第二个关键字探测次数为2……第n个关键字探测次数为n;探测次数之和为1+2+……+n = n(n+1)/2
3.下列选项中,不可能是快速排序第2趟排序结果的是 (C)
A 2,3,5,4,6,7,9
B 2,7,5,6,4,3,9
C 3,2,5,4,7,6,9
D 4,2,3,5,7,6,9文章来源:https://www.toymoban.com/news/detail-417579.html
思路:每进行一次快排,标定点一定在最终的位置上,二次快排结束,就一定有两个元素一定处于最终所在的位置上文章来源地址https://www.toymoban.com/news/detail-417579.html
到了这里,关于day24—选择题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!