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 * +.
- 2 × 3 = 6; 5 × 4 = 20.
- 6 + 20 = 26.
Answer: 26
Example: Convert A + B * C to postfix.
- * has higher precedence, so B * C is done first.
- A B C * +.
Answer: ABC*+
Example: At most how many comparisons does binary search need for 1024 sorted items?
- ⌊log₂1024⌋ + 1.
- = 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.
- In-order (left, root, right): 20 30 40 50 60 70 80.
- 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?
- 2⁴ − 1.
- = 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?
- n(n − 1)/2 = 10 × 9/2.
- = 45.
Answer: 45
Example: With h(k) = k mod 7, where does key 50 go?
- 50 = 7 × 7 + 1.
- 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
- FIFO
- LIFO
- random order
- priority only
Show the answer
Answer: B. LIFO Last in, first out.
A queue follows
- FIFO
- LIFO
- random order
- none
Show the answer
Answer: A. FIFO First in, first out.
Binary search requires
- sorted data
- linked lists
- unique keys only
- small size
Show the answer
Answer: A. sorted data Divides range.
Worst case of quick sort is
- O(n)
- O(n log n)
- O(n²)
- O(log n)
Show the answer
Answer: C. O(n²) Bad pivots.
Merge sort’s complexity is
- O(n)
- O(n log n)
- O(n²)
- O(1)
Show the answer
Answer: B. O(n log n) Divide and conquer.
In-order traversal of a BST gives
- sorted order
- reverse levels
- random order
- postfix
Show the answer
Answer: A. sorted order Left-root-right.
BFS uses a
- stack
- queue
- tree only
- heap only
Show the answer
Answer: B. queue Level by level.
DFS uses a
- stack
- queue
- hash
- array only
Show the answer
Answer: A. stack Or recursion.
Evaluating postfix expressions uses a
- stack
- queue
- graph
- hash
Show the answer
Answer: A. stack Operands pushed.
Hashing has average lookup
- O(1)
- O(n)
- O(n²)
- O(log n)
Show the answer
Answer: A. O(1) Direct address.
Which sort is fastest on nearly sorted data?
- insertion
- selection
- quick
- 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.