AQA A Level · Computer Science 7517

Trees (including binary trees): Practice Questions

5 multiple-choice questions marked as you go, and 5 written questions with worked solutions. All on Trees (including binary trees).

10 questions25 marksFree, no account

Question 1

1 mark

Which of the following properties uniquely defines a tree in graph theory terms?

Question 2

1 mark

Consider a binary tree where every internal node has exactly two children. If the tree has \(n\) leaf nodes, how many internal nodes (including the root) does it have?

Question 3

1 mark

A binary search tree is constructed by inserting the following keys in order: 50, 30, 70, 20, 40, 60, 80. After these insertions, the key 50 is deleted and replaced by its in-order successor. What is the new root of the tree?

Question 4

1 mark

In a binary search tree (BST), if we want to output the data values in ascending order, which traversal algorithm should be used?

Question 5

1 mark

Which statement correctly describes the difference between static and dynamic implementation of a tree data structure?

Question 6

3 marks

Identify the specific type of tree traversal required to output the contents of a binary search tree in ascending numerical order.

Write your answer out first, then check it against the worked solution.

Question 7

5 marks

In graph theory, a tree is defined as a connected, undirected graph with no cycles. If a tree has \( V \) vertices, exactly how many edges must it have, and why would adding one more edge between any two existing vertices violate the tree property?

Write your answer out first, then check it against the worked solution.

Question 8

3 marks

Identify the specific tree traversal that would be used to produce a prefix expression from an expression tree and describe the order in which the root and its children are visited.

Write your answer out first, then check it against the worked solution.

Question 9

4 marks

A Binary Search Tree (BST) is constructed by inserting the following keys in order: 50, 30, 70, 20, 40, 90.

a. Identify the root node and its immediate left and right children. (1 point)
b. Perform an In-order traversal of this tree and list the resulting sequence. (2 points)
c. Explain why an In-order traversal is particularly useful when applied to a Binary Search Tree. (1 point)

Write your answer out first, then check it against the worked solution.

Question 10

5 marks

A binary search tree (BST) is a specific type of tree structure.

(a) Define the mathematical properties of a tree and explain what makes a tree a rooted tree.
(b) Identify the maximum number of children any node can have in a binary tree.
(c) A BST is constructed with the following keys inserted in order: 40, 20, 10, 30, 60, 50, 70. Describe the steps to find the key 50 and state how many comparisons are required.

Write your answer out first, then check it against the worked solution.

* The content provided by thinka is generated by AI and may not always be accurate or up-to-date. Please use it as a supplementary resource and verify with official materials.

You've seen the model answer. Now get yours marked.

This page can show you how a good answer looks. It cannot tell you what your answer was missing. thinka marks your written work against the real mark scheme in about 15 seconds.

Get My Answers Marked Back to the notes

Want more questions like these? Get a fresh set on this topic, marked as you go.