• Wrong document? Swap it for free
  • Written by students who passed
  • Immediately available after payment
  • Read online or as PDF
Sell
Where do you study
Your language
Start selling Create your account
Document preview thumbnail
Preview 2 out of 7 pages
Summary

Summary WJEC A Level Computer science Unit 3 Data structures - Binary trees and linked lists

Document preview thumbnail
Preview 2 out of 7 pages

Past paper questions and mark scheme answers for WJEC A Level Computer science Unit 3 Data structures - Binary trees and linked lists

Content preview

Binary trees
A car dealership’s stock control system stores details of cars in a binary tree structure. The tree
structure uses manufacturers’ names as key values.
(a) Draw a representation of the binary tree using the following key values in this order:
Peugeot, Ford, Vauxhall, Mercedes, BMW, Audi, Renault, Toyota. [3]
(b) Add Jaguar to the binary tree. [1]
(c) List the key values sorted in the order that a post-order traversal of the tree would produce. [2]




A binary tree structure is designed to contain strings and uses the following rules:
● The left pointer indicates the condition “earlier or at the same position in the alphabet”
● The right pointer indicates the condition “later in the alphabet”

Construct a binary tree using these rules and the data entered in the following order:
Goat, Duck, Fox, Bear, Ant, Cat, Leopard, Owl, Mayfly, Insect, Jaguar, Emu.




(b) Carry out a pre-order traversal of the tree and give one use of pre-order traversals. [2]
● GDBACFELIJOM
● Use



7

, ○ Clone a tree
○ Count the number of leaves
○ Convert expression tree to prefix notation

(c) Carry out an in-order traversal of the tree and give one use of in-order traversals. [2]
● ABCDEFGIJLMO
● Sort/search a binary tree

(d) Carry out a post-order traversal of the tree and give one use of post-order traversals. [2]
● ACBEFDJIMOLG
● Use
○ Deleting / Undo a binary tree
○ Stack-based programming
○ Convert postfix notation to expression tree

A cloud storage solution uses binary trees for its file system. The file structures can be traversed
using a variety of methods. Describe the following methods of traversal and give an example of
how each method could be used in the file system.
In-order traversal [3] - In-order traversal is applied by visiting the left subtree first, then root and
finally the right subtree. This method could be when searching for a file in the file system
Post-order traversal [3] - Post-order traversal is applied by visiting the left subtree first, then right
subtree and finally the root. This method could be used to delete all files in the file system.
Pre-order traversal - Pre-order traversal is applied by visiting the root first, then left subtree and
finally the right subtree. This method could be used to create copy files in the file system.

Draw a representation of a binary tree using the data items from question 11(b) as key values. [3]




8

Document information

Study Level
Uploaded on
April 10, 2023
Number of pages
7
Written in
2022/2023
Type
Summary
£3.49

Wrong document? Swap it for free Within 14 days of purchase and before downloading, you can choose a different document. You can simply spend the amount again.
Written by students who passed
Immediately available after payment
Read online or as PDF

Sold
0
Followers
0
Items
3
Last sold
-



Why students choose Stuvia

Created by fellow students, verified by reviews

Quality you can trust: written by students who passed their exams and reviewed by others who've used these revision notes.

Didn't get what you expected? Choose another document

No problem! You can straightaway pick a different document that better suits what you're after.

Pay as you like, start learning straight away

No subscription, no commitments. Pay the way you're used to via credit card and download your PDF document instantly.

Student with book image

“Bought, downloaded, and smashed it. It really can be that simple.”

Alisha Student

Working on your references?

Create accurate citations in APA, MLA and Harvard with our free citation generator.

Working on your references?

Frequently asked questions