Data Structures & Algorithms Flashcards

Which data structure uses LIFO (Last In, First Out) ordering?

Answer: Stack

A stack follows LIFO ordering where the last element pushed is the first one popped.

What is the worst-case time complexity of binary search on a sorted array of n elements?

Answer: O(log n)

Binary search halves the search space each step, yielding O(log n) worst-case time.

In a singly linked list, inserting a node at the head takes how much time?

Answer: O(1)

Head insertion requires only pointer updates regardless of list length, so it is O(1).

Which traversal of a binary search tree visits nodes in ascending sorted order?

Answer: In-order

In-order traversal (left → root → right) on a BST yields keys in ascending sorted order.

What is the space complexity of merge sort?

Answer: O(n)

Merge sort requires O(n) auxiliary space for the temporary arrays used during merging.

A hash table collision resolution strategy that places all colliding keys in a linked list at the same bucket is called:

Answer: Separate chaining

Separate chaining stores colliding elements in a linked list (or other structure) at each bucket.

Which algorithm is best suited for finding the shortest path in an unweighted graph?

Answer: Breadth-first search

BFS explores nodes level by level, guaranteeing the shortest path (fewest edges) in an unweighted graph.