B CompE Bachelor of Computer Engineering Bachelor of Computer Engineering Data Structure 5

Question 1

Which algorithm finds the minimum spanning tree of a graph by always adding the globally cheapest edge that doesn't form a cycle?

Accepted Answer

Kruskal's algorithm

Answer

Kruskal's algorithm sorts edges by weight and greedily adds the smallest safe edge using a Union-Find structure.

Question 2

What abstract data type is used internally by Dijkstra's shortest-path algorithm for efficiently selecting the next vertex to process?

Accepted Answer

Min-priority queue

Answer

Dijkstra's algorithm uses a min-priority queue to always extract the unvisited vertex with the smallest tentative distance.

Question 3

What is amortized time complexity?

Accepted Answer

The average cost per operation over a sequence of operations

Answer

Amortized analysis averages the cost over a sequence of operations, smoothing out occasional expensive operations.

Question 4

In a circular linked list, what distinguishes it from a standard singly linked list?

Accepted Answer

The last node points back to the first node

Answer

In a circular linked list, the tail node's next pointer points back to the head, forming a cycle.

Question 5

Which data structure is used to implement function call management in most programming languages?

Accepted Answer

Stack

Answer

The call stack uses LIFO ordering so that the most recently called function is the first to return.

B CompE Bachelor of Computer Engineering Practice Test