• ¿Documento equivocado? Cámbialo gratis
  • Escrito por estudiantes que aprobaron
  • Inmediatamente disponible después del pago
  • Leer en línea o como PDF
Vender
¿Dónde estudias?
Tu idioma
Document preview thumbnail
Vista previa 2 fuera de 7 páginas
Resumen

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

Document preview thumbnail
Vista previa 2 fuera de 7 páginas

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

Vista previa del contenido

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

Información del documento

Nivel de Estudio
Tema
Subido en
10 de abril de 2023
Número de páginas
7
Escrito en
2022/2023
Tipo
Resumen
$4.70

¿Documento equivocado? Cámbialo gratis Dentro de los 14 días posteriores a la compra y antes de descargarlo, puedes elegir otro documento. Puedes gastar el importe de nuevo.
Escrito por estudiantes que aprobaron
Inmediatamente disponible después del pago
Leer en línea o como PDF

Vendido
0
Seguidores
0
Artículos
3
Última venta
-



Por qué los estudiantes eligen Stuvia

Creado por compañeros estudiantes, verificado por reseñas

Calidad en la que puedes confiar: escrito por estudiantes que aprobaron y evaluado por otros que han usado estos resúmenes.

¿No estás satisfecho? Elige otro documento

¡No te preocupes! Puedes elegir directamente otro documento que se ajuste mejor a lo que buscas.

Paga como quieras, empieza a estudiar al instante

Sin suscripción, sin compromisos. Paga como estés acostumbrado con tarjeta de crédito y descarga tu documento PDF inmediatamente.

Student with book image

“Comprado, descargado y aprobado. Así de fácil puede ser.”

Alisha Student

Preguntas frecuentes