B.S.W.E. Bachelor of Software Engineering Algorithms & Data Structures 3

Question 1

What is Dijkstra's algorithm used for?

Accepted Answer

Finding the shortest path from a source to all nodes in a weighted graph

Answer

Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights.

Question 2

What is a heap data structure?

Accepted Answer

A complete binary tree satisfying the heap property where each parent is greater or smaller than its children

Answer

A heap is a complete binary tree where each parent is greater (max-heap) or smaller (min-heap) than its children, commonly used to implement priority queues.

Question 3

What is the space complexity of recursive DFS on a graph with n nodes?

Accepted Answer

O(n)

Answer

Recursive DFS uses O(n) call stack space in the worst case because the recursion depth can equal the total number of nodes in a path graph.

Question 4

How does random access time differ between an array and a linked list?

Accepted Answer

Array supports O(1) random access; linked list requires O(n) traversal

Answer

Arrays support O(1) random access because index arithmetic directly computes the memory address, while linked lists require traversal from the head.

Question 5

What is memoization in algorithm design?

Accepted Answer

Caching the results of function calls to avoid redundant computation on repeated inputs

Answer

Memoization stores the results of expensive function calls so that when the same inputs occur again, the cached result is returned immediately.

B.S.W.E. Bachelor of Software Engineering Practice Test

B.S.W.E. Bachelor of Software Engineering Practice Test

B.S.W.E. Bachelor of Software Engineering Algorithms & Data Structures 3