Cognizant Cognizant Data Structures and Algorithms 1 — Questions and Answers
Question 1: What is the time complexity of binary search on a sorted array of n elements?
- O(n)
- O(log n) (Correct answer)
- O(n log n)
- O(1)
Correct answer: O(log n)
Binary search halves the search space each step, resulting in O(log n) time complexity.
Question 2: Which data structure uses LIFO (Last In, First Out) order?
- Queue
- Stack (Correct answer)
- Linked List
- Heap
Correct answer: Stack
A stack follows LIFO — the last element pushed is the first one popped.
Question 3: What is the worst-case time complexity of QuickSort?
- O(n log n)
- O(n²) (Correct answer)
- O(log n)
- O(n)
Correct answer: O(n²)
QuickSort degrades to O(n²) when the pivot is always the smallest or largest element.
Question 4: Which traversal of a Binary Search Tree produces elements in sorted order?
- Pre-order
- Post-order
- In-order (Correct answer)
- Level-order
Correct answer: In-order
In-order traversal (left → root → right) of a BST visits nodes in ascending sorted order.
Question 5: What data structure is best suited for implementing a BFS (Breadth-First Search)?
- Stack
- Queue (Correct answer)
- Priority Queue
- Hash Map
Correct answer: Queue
BFS processes nodes level by level using a FIFO queue to track nodes to visit next.
Question 6: What is the space complexity of a recursive function that calls itself n times without tail-call optimization?
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(n²)
Correct answer: O(n)
Each recursive call adds a frame to the call stack, so n calls require O(n) stack space.
Cognizant Cognizant Data Structures and Algorithms 1
What is the time complexity of binary search on a sorted array of n elements?