AMCAT Computer Programming: Data Structures 2 — Questions and Answers
Question 1: Which data structure is best suited for implementing a browser's back button (visit history)?
- Queue
- Stack (Correct answer)
- Linked List
- Binary Tree
Correct answer: Stack
A stack (LIFO) is ideal for browser history: push each new page, pop to go back to the previous page.
The browser back button uses LIFO semantics: the last-visited page is the first to return to. A Stack naturally provides this with push (visit new page) and pop (go back).
Question 2: What is the time complexity of searching for an element in a balanced Binary Search Tree (BST)?
- O(1)
- O(log n) (Correct answer)
- O(n)
- O(n squared)
Correct answer: O(log n)
A balanced BST has height O(log n), so searching requires at most O(log n) comparisons.
In a balanced BST with n nodes, the height is floor(log2 n). Searching traverses from root to leaf, making at most O(log n) comparisons. An unbalanced BST degrades to O(n) in the worst case.
Question 3: In a doubly linked list, each node contains:
- Data and one pointer
- Data and two pointers (prev, next) (Correct answer)
- Only pointers
- Data, prev, next, and parent pointers
Correct answer: Data and two pointers (prev, next)
A doubly linked list node has a data field and two pointers: prev and next.
A doubly linked list node: [prev | data | next]. The prev pointer enables reverse traversal, and next enables forward traversal. This allows O(1) deletion given a pointer to any node.
Question 4: What is the output of an inorder traversal of a Binary Search Tree?
- Random order
- Sorted ascending order (Correct answer)
- Reverse sorted order
- Level-by-level order
Correct answer: Sorted ascending order
Inorder traversal (Left-Root-Right) of a BST visits nodes in ascending sorted order due to the BST property.
BST property ensures left subtree values < root < right subtree values. Inorder traversal visits left, then root, then right. This produces elements in non-decreasing order.
Question 5: Which of the following operations is NOT O(1) for a hash table on average?
- Insert
- Delete
- Search
- Sort all elements (Correct answer)
Correct answer: Sort all elements
Insert, delete, and search are O(1) average in a hash table. Sorting all elements requires O(n log n).
Hash tables provide O(1) average for insert, delete, and lookup. To sort all n elements, you must extract them and sort — O(n log n). Sorting is not a native hash table operation.
Question 6: What is the maximum number of nodes in a binary tree of height h (root at height 0)?
- 2h
- 2^h minus 1
- 2^(h+1) minus 1 (Correct answer)
- h squared
Correct answer: 2^(h+1) minus 1
A full binary tree of height h has 2^(h+1) − 1 nodes (sum of 1 + 2 + 4 + ... + 2^h).
Level 0 (root): 1 node. Level 1: 2. Level 2: 4. ... Level h: 2^h. Total = 1 + 2 + ... + 2^h = 2^(h+1) − 1.
AMCAT Computer Programming: Data Structures 2
Which data structure is best suited for implementing a browser's back button (visit history)?