DSA Quick Kit: 16 MCQs with answers

Big O (O)

Big O notation describes the worst-case upper bound, ensuring the algorithm's time does not exceed this limit.

Binary Search

Binary Search works by repeatedly dividing the sorted array in half, so it requires a sorted array to function correctly.

Doubly Linked List

A doubly linked list has two pointers per node (next and previous), enabling bidirectional traversal.

BFS

BFS (Breadth-First Search) uses a queue to explore vertices level by level.

True

Space complexity quantifies the total memory required by an algorithm, including input and auxiliary space.

False

A stack follows LIFO (Last In First Out), so the last inserted element is removed first.

O(log n)

Binary Search halves the search space each step, leading to logarithmic time complexity O(log n) in the worst case.

Stack

A stack is used to hold operators and parentheses during infix to postfix conversion, following precedence rules.

(rear + 1) % size == front

In a circular queue, the queue is full when the next position of rear (using modulo) equals front, indicating no empty slot.

Inorder

Inorder traversal of a BST visits left subtree, root, then right subtree, which yields elements in ascending order.

LL rotation

An LL imbalance occurs when the left child's left subtree is taller, requiring a single right rotation to balance.

Bubble Sort

Bubble Sort has O(n) best-case when the array is already sorted, as it can stop early after one pass without swaps.

O(n²)

Quick Sort degrades to O(n²) when the pivot is always the smallest or largest element, causing unbalanced partitions.

Linear Probing

Linear probing resolves collisions by sequentially checking the next slot until an empty one is found.

Adjacency List

Adjacency list uses memory proportional to vertices plus edges, which is better for sparse graphs compared to matrix's V² space.

Quick Sort

Quick Sort is typically not stable because partitioning can reorder equal elements relative to each other.