IITIAN1997 STUDIO

Data structures

JLEE CSE · 11 practice questions with answers

Practise and take a mock test →

Stacks, queues, lists, trees, graphs, sorting, searching

Topics: Algorithm complexity; arrays; stacks and their applications; queues and circular queues; linked lists; trees, binary search trees, traversals; graphs, BFS and DFS; searching and sorting; hashing.

Complexity and stacks

Big-O describes how running time grows: O(1) constant, O(log n) binary search, O(n) linear search, O(n log n) merge sort, O(n²) bubble sort. A stack is last-in first-out (push, pop); it evaluates postfix expressions, checks brackets, and supports recursion and undo.

Infix to postfix: operands go out directly; operators wait on the stack until one of lower precedence arrives.

  • Binary search: at most ⌊log₂n⌋ + 1 comparisons
  • Stack: LIFO
  • A + B × C → A B C × +

Example: Evaluate the postfix expression 2 3 * 5 4 * +.

  1. 2 × 3 = 6; 5 × 4 = 20.
  2. 6 + 20 = 26.

Answer: 26

Example: Convert A + B * C to postfix.

  1. * has higher precedence, so B * C is done first.
  2. A B C * +.

Answer: ABC*+

Example: At most how many comparisons does binary search need for 1024 sorted items?

  1. ⌊log₂1024⌋ + 1.
  2. = 11.

Answer: 11

Queues, linked lists and trees

A queue is first-in first-out; a circular queue of size n is full when (rear + 1) mod n = front. Linked lists grow dynamically, with O(1) insertion at a known node but O(n) access by position.

Binary trees: a tree of height h has at most 2ʰ − 1 nodes; in any binary tree, leaves = nodes with two children + 1. A binary search tree keeps smaller keys on the left and larger on the right, so an in-order traversal lists keys in sorted order. Pre-order visits the root first, post-order last.

  • Queue: FIFO
  • Max nodes = 2ʰ − 1
  • BST in-order = sorted

Example: Insert 50, 30, 70, 20, 40, 60, 80 into a BST. Give the in-order and pre-order traversals.

  1. In-order (left, root, right): 20 30 40 50 60 70 80.
  2. Pre-order (root, left, right): 50 30 20 40 70 60 80.

Answer: In: 20…80; Pre: 50 30 20 40 70 60 80

Example: What is the maximum number of nodes in a binary tree of height 4?

  1. 2⁴ − 1.
  2. = 15.

Answer: 15

Graphs, sorting and hashing

Graphs are stored as adjacency matrices or lists. Breadth-first search uses a queue and finds shortest paths in unweighted graphs; depth-first search uses a stack (or recursion). Sorting: bubble, selection and insertion are O(n²); merge sort O(n log n) always; quicksort O(n log n) on average but O(n²) in the worst case. Hashing maps keys to slots, e.g. h(k) = k mod m; collisions are resolved by chaining or probing.

  • BFS: queue; DFS: stack
  • Bubble sort comparisons: n(n − 1)/2
  • h(k) = k mod m

Example: How many comparisons does a simple bubble sort make on 10 items?

  1. n(n − 1)/2 = 10 × 9/2.
  2. = 45.

Answer: 45

Example: With h(k) = k mod 7, where does key 50 go?

  1. 50 = 7 × 7 + 1.
  2. Slot 1.

Answer: Slot 1

A stack is LIFO (push and pop at the top, used in recursion and expression evaluation) and a queue is FIFO. A singly linked list has O(1) insert at the head, and arrays give O(1) access by index. A binary tree of height h has at most 2^(h+1) − 1 nodes; in-order traversal of a BST gives sorted order. BFS uses a queue and DFS a stack. Binary search needs a sorted array and runs in O(log n). Bubble, selection and insertion sorts are O(n²); merge sort is O(n log n) always; quick sort is O(n log n) on average, O(n²) in the worst case. Hashing averages O(1) lookup, with collisions handled by chaining or probing.

  • Preorder: root, left, right. Inorder: left, root, right. Postorder: left, right, root.
  • Postfix evaluation uses a stack.
  • Complete binary tree with n nodes has height ⌊log₂n⌋.
  • Heap sort is O(n log n).
  • Insertion sort is O(n) on nearly sorted data.

Key formulas

  • max nodes = 2^(h+1) − 1
  • binary search: ⌈log₂(n + 1)⌉ comparisons
  • merge sort O(n log n)

Practice questions

A stack follows

  1. FIFO
  2. LIFO
  3. random order
  4. priority only
Show the answer

Answer: B. LIFO Last in, first out.

A queue follows

  1. FIFO
  2. LIFO
  3. random order
  4. none
Show the answer

Answer: A. FIFO First in, first out.

Binary search requires

  1. sorted data
  2. linked lists
  3. unique keys only
  4. small size
Show the answer

Answer: A. sorted data Divides range.

Worst case of quick sort is

  1. O(n)
  2. O(n log n)
  3. O(n²)
  4. O(log n)
Show the answer

Answer: C. O(n²) Bad pivots.

Merge sort’s complexity is

  1. O(n)
  2. O(n log n)
  3. O(n²)
  4. O(1)
Show the answer

Answer: B. O(n log n) Divide and conquer.

In-order traversal of a BST gives

  1. sorted order
  2. reverse levels
  3. random order
  4. postfix
Show the answer

Answer: A. sorted order Left-root-right.

BFS uses a

  1. stack
  2. queue
  3. tree only
  4. heap only
Show the answer

Answer: B. queue Level by level.

DFS uses a

  1. stack
  2. queue
  3. hash
  4. array only
Show the answer

Answer: A. stack Or recursion.

Evaluating postfix expressions uses a

  1. stack
  2. queue
  3. graph
  4. hash
Show the answer

Answer: A. stack Operands pushed.

Hashing has average lookup

  1. O(1)
  2. O(n)
  3. O(n²)
  4. O(log n)
Show the answer

Answer: A. O(1) Direct address.

Which sort is fastest on nearly sorted data?

  1. insertion
  2. selection
  3. quick
  4. heap
Show the answer

Answer: A. insertion O(n).

The practice questions were written for this studio; they are not copied from ASTU papers. ASTU publishes no topic syllabus for these exams, so the topics are an informed guide based on diploma courses, not an official list.

Practise and take a mock test →