1. What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?
B. B. Θ(n log n)
C. C. Θ(n^2)
D. D. Θ(1)
A.
Θ(∣E∣
+ ∣V∣)
B.
Θ(∣E∣.∣V∣)
C.
Θ(E∣
log ∣V∣)
D.
Θ(∣V∣)
3. Let G=(V,E) be a directed, weighted graph with weight function
w:E→R. For some function f:V→R, for each edge (u,v)∈E, define w′(u,v) as
w(u,v)+f(u)−f(v). Which one of the options completes the following sentence so
that it is TRUE ? “The shortest paths in G under w are shortest paths under w′
too, _________”.
A.
for
every f:V→R
B.
if
and only if ∀u∈V, f(u) is
positive
C.
if
and only if ∀u∈V, f(u) is negative
D.
if
and only if f(u) is the distance from s to u in the graph obtained by adding a
new vertex s to G and edges of zero weight from s to every vertex of G
4. In
a balanced binary search tree with n elements, what is the worst case time
complexity of reporting all elements in range [a,b] ? Assume that the number of
reported elements is k.
A.
Θ(log
n)
B.
Θ(log(n)+k)
C.
Θ(k
log n)
D.
Θ(n
log k)
5. Consider the array representation of a
binary min-heap containing 1023 elements. The minimum number of comparisons
required to find the maximum in the heap is _________ .
A.
510
B.
511
C.
512
D.
255
6. Consider a graph G=(V, E), where V = { v1,v2,…,v100 }, E={ (vi, vj) ∣ 1≤ii, vj) is ∣i–j∣. The weight of minimum spanning tree of G is ________
A.
99
B.
100
C.
98
D.
101
7. Graph G is obtained by adding vertex s to K3,4 and making s adjacent to every vertex of K3,4. The minimum number of colours required to edge-colour G is _________ .
A.
2
B.
3
C.
5
D.
7
0 Comments