day24—选择题
文章目录
- 1.将N条长度均为M的有序链表进行合并，合并以后的链表也保持有序，时间复杂度为（A）
- 2.已知某个哈希表的n个关键字具有相同的哈希值，如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行（E）次探测
- 3.下列选项中，不可能是快速排序第2趟排序结果的是 （C）
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
思路：每进行一次快排，标定点一定在最终的位置上，二次快排结束，就一定有两个元素一定处于最终所在的位置上