Doctor of Philosophy in Computer Science (PhD CS) Admission - Bahria University

Question 1

What is the amortized time complexity of the 'delete-min' operation in a Fibonacci Heap?

Accepted Answer

O(log n)

Answer

O(1)

Answer

O(n)

Answer

O(n log n)

Question 2

Which algorithm is best suited for finding the shortest path in a graph with negative edge weights but no negative cycles?

Accepted Answer

Bellman-Ford Algorithm

Answer

Dijkstra's Algorithm

Answer

Prim's Algorithm

Answer

Kruskal's Algorithm

Question 3

In a B-tree of order m, what is the minimum number of children a non-root internal node must have?

Accepted Answer

ceil(m/2)

Answer

m/2

Answer

floor(m/2)

Answer

m-1

Question 4

Which data structure is most efficient for implementing a priority queue where priority decreases over time?

Accepted Answer

Van Emde Boas Tree

Answer

Binary Max-Heap

Answer

Pairing Heap

Answer

Sorted Linked List

Question 5

What is the worst-case time complexity of the QuickSort algorithm when the pivot is consistently the smallest or largest element?

Accepted Answer

O(n^2)

Answer

O(n log n)

Answer

O(n)

Answer

O(log n)

AR Test-preparations exam — B9bfbe62 Ee1b 42f0 987b 082a9d849a18 MCQs