中文（繁體）
中文（简体）
English
S6 ICT: Data Structures – Practice Paper 3 (Challenge, 10 Questions)
S6 ICT: Data Structures – Practice Paper 3 (Challenge, 10 Questions)
Paper three tests scale and efficiency: a hundred vertex adjacency matrix needs ten thousand cells, three hundred edges give six hundred list entries, a degenerate tree costs ten comparisons, and merging lists of five hundred and three hundred costs at most seven hundred and ninety nine, with answers and notes.
Quick answer A hundred by hundred matrix gives ten thousand cells; three hundred undirected edges need six hundred entries; a degenerate tree is ten deep; a balanced tree of a thousand nodes needs ten comparisons; thirty one nodes fill five levels; merging costs at most seven hundred and ninety nine; the load factor is one; eight minus three plus two is seven; a million against nine thousand nine hundred and sixty six; ten comparisons against nine hundred and ninety nine.
01 Paper details (check answers afterwards)
| Item | Detail |
|---|---|
| Questions | 10 questions |
| Suggested time | about 25 minutes |
| Difficulty mix | Foundation 1 · Intermediate 2 · Challenge 3 · Error redo 4 |
| Chapter | Chapter: S6 ICT | Data Structures: Arrays, Linked Lists, Stacks, Queues, Trees and Graphs |
| Level | Challenge |
02 Questions (10 items)
- FoundationA graph with one hundred vertices is stored as an adjacency matrix. How many cells are needed?
- IntermediateAn undirected graph with one hundred vertices and three hundred edges is stored as an adjacency list. How many entries are needed?
- IntermediateInsert 10, 20, 30 up to 100 in order into a binary search tree. What is the height and the worst case number of comparisons?
- ChallengeA balanced binary search tree holds one thousand nodes. How many comparisons in the worst case?
- ChallengeA full binary tree has thirty one nodes. How many levels does it have?
- ChallengeTwo sorted lists of length five hundred and three hundred are merged. What is the maximum number of comparisons?
- Error redoError retry: one thousand records are stored in a hash table with one thousand buckets. What is the load factor?
- Error redoError retry: eight pushes, then three pops, then two more pushes. How many items are on the stack?
- Error redoError retry: a student claimed an O(n squared) algorithm is faster than an O(n log n) one on one thousand items. Show why with numbers.
- Error redoError retry: a student wrote that linear search and binary search on a sorted array are both O(n). What is correct?
03 Answers and one-line notes
| # | Answer | One-line note |
|---|---|---|
| 1 | 10 000. | An adjacency matrix is n by n, so one hundred times one hundred is ten thousand. |
| 2 | 600. | Each undirected edge is recorded at both ends, so three hundred times two is six hundred. |
| 3 | Height 10, worst case 10 comparisons. | Every insert goes right, so the tree degenerates into a chain and behaves like a linear search. |
| 4 | 10. | The height is about log base two of one thousand and one, which rounds up to ten. |
| 5 | 5. | Two to the fifth power minus one is thirty one, which is exactly five levels. |
| 6 | 799. | In the worst case one item is taken per comparison, and the final item needs no comparison. |
| 7 | 1.0. | The load factor is records divided by buckets, and one thousand over one thousand is one. |
| 8 | 7. | Eight minus three plus two is seven, since each push or pop changes the count by one. |
| 9 | About 1 000 000 operations against about 9 966, so roughly one hundred times slower. | One thousand squared is a million, while one thousand times log base two of one thousand is about nine thousand nine hundred and sixty six. |
| 10 | Linear search is O(n) with up to 999 comparisons, binary search is O(log n) with about 10. | Binary search halves the range at every step, so one thousand items need only about ten comparisons. |
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.