IB Computer Science HL · HL extension
Abstract Data Structures
Stacks, queues, linked lists, binary trees and recursion — HL-only, and recursive-trace questions are where students most often lose marks by evaluating the base case correctly but mis-tracking the call stack on the way back up.
5.1 Abstract data structures
- Identify a situation that requires the use of recursive thinking.
- Identify recursive thinking in a specified problem solution.
- Trace a recursive algorithm to express a solution to a problem.
- Describe the characteristics of a two-dimensional array.
- Construct algorithms using two-dimensional arrays.
- Describe the characteristics and applications of a stack.
- Construct algorithms using the access methods of a stack (push, pop, isEmpty).
- Describe the characteristics and applications of a queue.
- Construct algorithms using the access methods of a queue (enqueue, dequeue, isEmpty).
- Explain the use of arrays as static stacks and queues.
- Describe the features and characteristics of a dynamic data structure.
- Describe how linked lists operate logically.
- Sketch linked lists (single, double and circular).
- Describe how trees operate logically (both binary and non-binary).
- Define the terms: parent, left-child, right-child, subtree, root and leaf.
- State the result of inorder, postorder and preorder tree traversal.
- Sketch binary trees.
- Define the term dynamic data structure.
- Compare the use of static and dynamic data structures.
- Suggest a suitable structure for a given situation.
Practice this topic
ExamEdge generates fresh, exam-authentic abstract data structures questions, marks every answer, and tells you exactly why a mark was lost — concept gap, reading load, or answer format.