FREE Bachelor of Science in Computer Science: Algorithms and Data Structures Questions and Answers

Question 1

Which of the provided expressions definitively indicates the validity of the assertion f(n) = Ω(g(n))?

Accepted Answer

f(n) ≥ 4g(n) for all n ≥ 136

Answer

f(n) ≤ 4g(n) for all n ≥ 1

Answer

Both A & B

Answer

none of the above

Question 2

If we let k represent the degree of polynomial p(n) and l represent the degree of polynomial q(n), what must be true when p(n) = o(q(n))?

Accepted Answer

k < l.

Answer

k = l.

Answer

k > l.

Answer

none of the above

Question 3

If both f(n) = O(g(n)) and f(n) = Ω(g(n)), what is a consistent and definite conclusion that can be drawn?

Accepted Answer

f(n) = Θ(g(n)).

Answer

f(n) = o(g(n)).

Answer

f(n) = ω(g(n)).

Answer

both a) and b) are always true

Question 4

both a) and b) are always true
When a separate-chaining hash table possesses a load factor λ of 5, what value does the average chain length assume?

Accepted Answer

5

Answer

log 5.

Answer

5 log 5.

Answer

log(log 5).

Question 5

Flawless hashing technique

Accepted Answer

all of the above

Answer

represents one of the most efficient ways of retrieving data.

Answer

may be applied to static hash tables.

Answer

means there are no collisions when retrieving data from the hash table.

Question 6

Among the listed algorithms, which one can be efficiently implemented without the need for a heap data structure?

Accepted Answer

Kruskal’s algorithm

Answer

Prim’s algorithm

Answer

Huffman’s algorithm

Answer

Dijkstra’s algorithm

Question 7

Which of the subsequent graph-related issues cannot be resolved within a time frame that scales linearly concerning the total number of vertices and edges within the graph (i.e., O(m + n))?

Accepted Answer

determining a minimum spanning tree for a connected weighted graph

Answer

determining a topological sort of the vertices for a directed acyclic graph

Answer

determining if a simple graph is connected

Answer

determining if a simple graph is bipartite

Question 8

A binary search tree T is considered balanced when, for every node n present in T.

Accepted Answer

n’s left and right subtrees have heights that differ by at most one.

Answer

n’s left and right subtrees have sizes that differ by at most one.

Answer

n’s left and right subtrees have equal height.

Answer

n’s left and right subtrees have equal size.

Question 9

As long as the pivot is chosen in a certain way, Quicksort is assured to operate within a time complexity of O(n log n).

Accepted Answer

set to the median of the array.

Answer

set to the median of the first, middle, and last array element.

Answer

randomly selected.

Answer

none of the above

Question 10

In Kruskal's algorithm, the decision that follows a greedy approach is to

Accepted Answer

add the edge of least cost to the forest so long as its addition does not create a cycle.

Answer

add the vertex having least connection cost to the current tree.

Answer

remove the vertex having greatest connection cost from the tree.

Answer

remove the edge of greatest cost from the graph so long as its removal does not disconnect the graph.