超星 - 并查集 - 查题吧

单选题

在并查集问题中，已知集合元素0~8所有对应的父结点编号值分别是{1,-4,1,1,-3,4,4,8,-2}（注：−n表示树根且对应集合大小为n），那么将元素6和8所在的集合合并（要求必须将小集合并到大集合）后，该集合对应的树根和父结点编号值分别是多少？

A. 1和-6
B. 4和-5
C. 8和-5
D. 8和-6

单选题

已知不相交集合用数组表示为{4, 6, 5, 2,-3,-4, 3}。若集合元素从1到7编号，则调用Union(Find(7),Find(1))(按规模求并并且带路径压缩后的结果数组为。

A. {4,6,5,2,6,-7,3}
B. {4,6,5,2,-7,5,3}
C. {6,6,5,6,-7,5,5}
D. {6,6,5,6,6,-7,5}

单选题

若并查集用树表示，其中有n个结点，查找一个元素所属集合的算法的时间复杂度为____。

A. O(logn)
B. O(n)
C. O(n2)
D. O(nlogn)

单选题

LetTbe a tree ofNnodes created by union-by-size without path compression, then the minimum depth ofTmay be

A. 1
B. logN
C. N−1
D. N/2

单选题

In a disjoint set problem, given a set ofmelementsS= { 1, 2, 3, ...,m} andn(0
A. at leatstm
B. exactlyn
C. exactlym−n
D. at leastm−n
查看答案

1