中文（繁體）
中文（简体）
English
S6 ICT: Data Structures – Practice Paper 2 (Advanced, 10 Questions)
S6 ICT: Data Structures – Practice Paper 2 (Advanced, 10 Questions)
Paper two works on operations and costs: in order traversal gives ascending keys, a four level full binary tree holds fifteen nodes, head insertion is O(1) against O(n) in the middle of an array, and a circular queue holds four items, with answers and a note each.
Quick answer In order traversal gives 20 to 80; searching 40 takes three comparisons; the height is three; level three holds four nodes; a four level full tree has fifteen nodes; head insertion is O(1) but array insertion is O(n); a circular queue from two to five holds four items; a thousand nodes average five hundred comparisons; breadth first uses a queue and depth first a stack.
01 Paper details (check answers afterwards)
| Item | Detail |
|---|---|
| Questions | 10 questions |
| Suggested time | about 20 minutes |
| Difficulty mix | Foundation 2 · Intermediate 3 · Challenge 3 · Error redo 2 |
| Chapter | Chapter: S6 ICT | Data Structures: Arrays, Linked Lists, Stacks, Queues, Trees and Graphs |
| Level | Advanced |
02 Questions (10 items)
- FoundationInsert 50, 30, 70, 20, 40, 60, 80 into a binary search tree in that order. What is the in-order traversal?
- FoundationSearching the same tree for 40 visits how many nodes?
- IntermediateWhat is the height of this seven node tree, counting levels of nodes?
- IntermediateIn a full binary tree the deepest level holds four nodes. Which level is it?
- IntermediateHow many nodes does a full binary tree with four levels contain?
- ChallengeWhat is the time complexity of inserting at the head of a linked list, and of inserting in the middle of an array?
- ChallengeA circular queue has size eight, front at index two and rear at index five. How many items are stored?
- ChallengeA linear search runs on a linked list of one thousand nodes. On average how many nodes are compared?
- Error redoError retry: a student wrote that breadth first search is implemented with a stack. What is correct?
- Error redoError retry: a student wrote that inserting into the middle of an array costs O(1). What is correct?
03 Answers and one-line notes
| # | Answer | One-line note |
|---|---|---|
| 1 | 20, 30, 40, 50, 60, 70, 80. | An in-order traversal of a binary search tree always returns the keys in ascending order. |
| 2 | 3. | The path is 50 then 30 then 40, so three comparisons are needed. |
| 3 | 3. | The root is level one, 30 and 70 are level two, and 20, 40, 60 and 80 are level three. |
| 4 | Level 3. | Level n holds at most two to the power n minus one nodes, and two squared is four. |
| 5 | 15. | Two to the fourth power minus one is fifteen, that is one plus two plus four plus eight. |
| 6 | O(1) for the linked list and O(n) for the array. | A linked list only rewires one pointer, while an array must shift every following element. |
| 7 | 4. | Counting from index two to index five covers four slots: two, three, four and five. |
| 8 | 500. | On average the target sits in the middle, so one thousand divided by two gives five hundred. |
| 9 | Breadth first search uses a queue; depth first search uses a stack. | Breadth first search visits level by level in arrival order, while depth first search backtracks with last in first out. |
| 10 | O(n). | Every element after the insertion point must shift right, which is n moves in the worst case. |
04 What to do after marking
- After marking, redo only the wrong items and write down which step went wrong (formula, unit, or misread number).
- Repeat the same item two days later; move to the next paper only when both attempts are correct.
- Parents only need the answer and note columns; there is no need to explain every item.
Find a tutor freeTutor Registration →
Questions and answers are written originally by the TutorZone team and are not taken from any school, publisher or examination authority paper. Every value is checked by computer.