中文（繁體）
中文（简体）
English
S6 ICT: Data Structures – Practice Paper 4 (Error Retry, 10 Questions)
S6 ICT: Data Structures – Practice Paper 4 (Error Retry, 10 Questions)
Paper four repairs the six most common slips: writing the element count as the largest index, calling a stack first in first out, forgetting to add one in a circular queue, and over-counting one comparison when merging lists, each corrected with concrete numbers.
Quick answer The largest index is 5 rather than 6; pushes of 3, 7 and 1 pop as 1, 7 and 3; a circular queue of size 8 with front 2 and rear 5 holds 4; merging 8 and 5 costs at most 12 comparisons; a balanced tree of 1 400 nodes needs 11 against 1 400; 50 vertices and 120 edges need 240 entries, saving 90.4 percent.
01 Paper details (check answers afterwards)
| Item | Detail |
|---|---|
| Questions | 10 questions |
| Suggested time | about 18 minutes |
| Difficulty mix | Foundation 2 · Intermediate 2 · Challenge 2 · Error redo 4 |
| Chapter | Chapter: S6 ICT | Data Structures: Arrays, Linked Lists, Stacks, Queues, Trees and Graphs |
| Level | Error retry |
02 Questions (10 items)
- FoundationFor the array D = [24, 6, 18, 91, 7, 45], what is D[4] and what is the largest index?
- FoundationA stack receives push 12, push 5 and push 9, then one pop. What is popped and what is the new top?
- IntermediateInsert 60, 40, 80, 30, 50, 70 and 90 in order into an empty binary search tree. What is the in order traversal, and how many comparisons find 50?
- IntermediateA circular queue of size ten has front at index seven and rear at index two. How many items are stored?
- ChallengeA balanced binary search tree holds 1 400 nodes. What is the worst case comparison count, and what would a linear search cost on the same data?
- ChallengeAn undirected graph with 50 vertices and 120 edges needs 2 500 cells as an adjacency matrix. How many entries does an adjacency list need, and what percentage is saved?
- Error redoError retry: a student wrote that the largest index of a six element array is six. What is correct, and by how much is it wrong?
- Error redoError retry: a student called a stack first in first out. With pushes of 3, 7 and 1, what is the correct pop order?
- Error redoError retry: a student counted a circular queue as rear minus front and answered three for size eight, front two and rear five. What is correct?
- Error redoError retry: a student said merging sorted lists of length eight and five costs at most thirteen comparisons. What is the correct bound?
03 Answers and one-line notes
| # | Answer | One-line note |
|---|---|---|
| 1 | D[4] is 7 and the largest index is 5. | Indexing starts at zero, so the fifth element sits at index four and six elements end at index five. |
| 2 | Nine is popped and five becomes the top. | A stack is last in first out, so the most recent item nine leaves first and five takes its place with two items left. |
| 3 | The traversal is 30, 40, 50, 60, 70, 80, 90 and finding 50 takes three comparisons. | An in order traversal is always ascending, and the search path runs through 60 then 40 then 50. |
| 4 | Six. | Counting from seven to two crosses the wrap and covers six slots: seven, eight, nine, zero, one and two. |
| 5 | Eleven comparisons for the tree against 1 400 for a linear search. | Log base two of 1 401 is about 10.45 which rounds up to eleven, while a linear search may scan every one of the 1 400 nodes. |
| 6 | 240 entries, saving 90.4 percent. | Each undirected edge is stored at both ends so 120 times two is 240, and 2 260 of the 2 500 cells are saved. |
| 7 | The largest index is five, so the answer is one too high. | A six element array runs from index zero to index five, and index six lies out of range. |
| 8 | Last in first out, so the pops are 1, 7 and 3. | A stack has a single opening, so the latest item leaves first and the order is reversed. |
| 9 | Four items. | Both the front and the rear slots hold items so one must be added, and the range two to five covers four slots. |
| 10 | Twelve comparisons. | One item is taken per comparison and the last remaining item is appended without a comparison, so the bound is m plus n minus one. |
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.