AMCAT Data Structures and Algorithms 1 — Questions and Answers
Question 1: Which data structure operates on a Last In, First Out (LIFO) principle?
- Queue
- Stack (Correct answer)
- Linked List
- Tree
Correct answer: Stack
A stack follows LIFO, where the last element added is the first one removed.
Question 2: What is the worst-case time complexity of Binary Search?
- O(1)
- O(n)
- O(log n) (Correct answer)
- O(n log n)
Correct answer: O(log n)
Binary Search repeatedly halves the search space, giving O(log n) worst-case complexity.
Question 3: Which traversal of a Binary Search Tree visits nodes in sorted ascending order?
- Pre-order
- Post-order
- In-order (Correct answer)
- Level-order
Correct answer: In-order
In-order traversal (left-root-right) visits BST nodes in ascending sorted order.
Question 4: What is the maximum number of nodes in a binary tree of height h?
- 2h
- 2h − 1
- 2^h − 1
- 2^(h+1) − 1 (Correct answer)
Correct answer: 2^(h+1) − 1
A full binary tree of height h has at most 2^(h+1) − 1 nodes.
Question 5: Which data structure is best suited for implementing a priority queue?
- Array
- Linked List
- Heap (Correct answer)
- Stack
Correct answer: Heap
A heap efficiently supports insertion and extraction of the minimum/maximum element in O(log n).
Question 6: In a singly linked list, what does the last node's 'next' pointer point to?
- The first node
- Itself
- NULL (Correct answer)
- The previous node
Correct answer: NULL
The last node's 'next' pointer is set to NULL to indicate the end of the list.
AMCAT Data Structures and Algorithms 1
Which data structure operates on a Last In, First Out (LIFO) principle?