Trees and binary search trees

An ordered binary search tree contains the following data:

Add the following data items in the given order to the binary search tree above. 5 30 53 57 90

A balanced binary search tree has data consistently at each level, for example:

An unbalanced binary search tree is uneven, for example:

Describe the drawback of an unbalanced binary search tree when searching for a value.

A different binary search tree stores the following data:

Give the output that will be produced from a depth-first (post-order) traversal and a breadth-first traversal of this binary search tree.

Depth-first (post-order)........

Write a line of program code or pseudocode to declare the array towns.

In the 2-dimensional array towns:

• the first column contains a pointer to the left side

• the second column contains the data

• the third column contains a pointer to the right side.

Leaf nodes have the pointer null. Complete the table showing the contents of the towns array to store the binary search tree shown in Fig. 8.

Four more towns are added to the binary search tree shown in Fig. 8 in this order:

Mallow

Cavan

Tuam

Wexford

Complete this binary search tree by adding the new towns to it.

A computer game stores tasks that the player has requested. Each task has:

• an identification (ID) number e.g. Task A

• a real number to be processed e.g. 123456.789

• an integer number to represent the order the tasks should be accessed e.g. 1.

The task that needs to be processed the earliest is given the order number 1.

Two or more tasks can have the same order number. For example, two tasks can have an order number 1.

The data about each task needs to be stored. This will store the ID number, data value and order number for a task.

Explain why a record data structure is suitable for this data.

The tasks will be stored in a binary search tree before they are processed. They are stored in ascending order by their order number.

Give two characteristics of a binary search tree.

Give an advantage of storing the tasks in a binary search tree instead of a 1-dimensional array.

The tasks currently stored in the binary search tree are shown here.

When a new task is inserted with the same order number as a pre-existing task, it is classed as having a higher order number.

For example, task G has the same order number as task A. Since task G was inserted after task A it is classed as a higher number.

Change the diagram to show the contents of the binary search tree after the following tasks are inserted in the order given:

• Task X with order number 12

• Task Y with order number 7

• Task Z with order number 11

A tree is one example of a data structure.

Give two characteristics of a tree data structure.

The following data is entered into a binary search tree.

22 13 5 36 55 14 8

Draw the binary search tree when the given data is entered in the order given.

Describe how a leaf node is deleted from a binary search tree.

Describe how a binary search tree can be searched for a value.

Identify the order that the nodes will be visited in a depth-first (post-order) traversal of this binary search tree.

Explain how backtracking is used in depth-first (post-order) traversals.

A computer program is being written to store data about students.

Fig. 2 shows a binary search tree that stores data about students.

Each student is represented by their ID number. The current contents of the binary search tree are:

Fig. 2

Identify the root node in the binary tree shown in Fig. 2.

Identify two leaf nodes in the binary tree shown in Fig. 2.

Four more students are added to the binary search tree shown in Fig. 2 in this order:

1420 2050 2780 2600

Complete the binary search tree here by adding the new students to it.

* A programmer would like to traverse the binary search tree shown in Fig. 2.

Compare the use of a breadth-first traversal and a depth-first (post-order) traversal on the binary search tree.

You should include the following in your answer:

• how each traversal works

• the order of the return values for each traversal.

A business uses an array with the identifier wNames to store workers’ names. A variable with the identifier top is used to store the index of the last element to be added to the array, which is also the element which will next be removed.

State the name of the type of data structure described above.

Using pseudocode, write an algorithm that allows the user to enter a name which is then pushed onto the data structure above, checking first that the data structure is not full.

The same workers’ names are stored in a binary search tree which is ordered alphabetically.

Kirstie is set as the root node, with Martyn, Louise, Alex and Anna added one by one.

Complete the tree diagram above to show where Martyn, Louise, Alex and Anna would

be added to this binary search tree.

Describe the process of using the binary search tree above to search for the name “Zoe”.

Compare the efficiency of a binary search tree to a linked list when searching for data.

Compare the efficiency of a binary search tree to a hash table when searching for data.

An object oriented system is implemented to organise further information about each worker’s attendance. Classes, objects, methods and attributes are used in this system.

State the meaning of each of the following terms:

Object........

Method........

Attribute........

Each worker has a name and an attendance figure which can be between 0 and 100.

Write a definition for a fully encapsulated customer class, providing both get and set methods for all attributes. You do not have to write code for the constructor method.

Taylor is creating an online multiplayer game where users can create accounts and build their own circus. Each circus will contain characters such as clowns, animals, magicians and dancers.

Users can set up a new circus in the online world, purchase new characters and visit other users’ circuses.

Taylor uses computational methods to analyse the problem including abstraction.

Describe how Taylor could use abstraction in the design of his online circus game.

Taylor will make use of concurrent processing within his circus game.

Describe what is meant by the term ‘concurrent processing’.

Explain why concurrent processing is needed to allow multiple users to log in and interact with game elements at the same time.

Some of the characters in the game will move and interact independently. Taylor is going to use graphs to plan the movements that each character can take within the game.

DancerGold is one character. The graph shown in Fig. 1 shows the possible movements that DancerGold can make.

DancerGold’s starting state is represented by node A. DancerGold can take any of the paths to reach the end state represented by node G.

The number on each path represents the number of seconds each movement takes.

The number in bold below each node is the heuristic value from A.

Define the term heuristic in relation to the A* algorithm.

Perform an A* algorithm on the graph shown in Fig. 1 to find the shortest path from the starting node to the end node. Show your working, the nodes visited and the distance. You may choose to use the table below to give your answer.

A breadth-first traversal can be performed on both a tree and a graph.

Show how a breadth-first traversal is performed on the following binary tree.

* The game will have thousands of users. Taylor will store data about the users and their actions while playing the game in a large database.

Evaluate how Taylor can use data mining to inform future changes to improve his circus game.

Kira is creating a computer game where the user can play against the computer.

In each turn, each character can make one move from a selection of possible moves.

Kira uses a tree data structure shown in Fig. 1 to identify the range of possible moves the computer can make from starting position A. Each connection is a move, with each node representing the result of the move.

State what is meant by the term ‘abstraction’ and describe how Kira has used abstraction in her design of the tree.

State why the tree shown in Fig. 1 is not an example of a binary search tree.

State what type of pointers are used to store nodes I, F, J and H so they do not point to any other nodes.

Kira wants the program to traverse the tree to evaluate the range of possible moves. She is considering using a breadth-first traversal or a depth-first (post-order) traversal.

Show how a breadth-first traversal would traverse the tree shown in Fig. 1.

Kira wants to make some changes to the data that is stored in the tree structure shown in Fig. 1.

The move represented by node ‘E’ needs to be deleted.

Describe the steps an algorithm will follow to delete node ‘E’ from the tree.

The move represented by the node ‘K’ needs to be added. Node ‘K’ needs to be joined to node ‘G.’

Describe the steps the algorithm will follow to add node ‘K’ to the right of node ‘G’.

Kira could have used a graph data structure to represent the moves in her game.

Give two similarities and two differences between a tree and a graph data structure.

A program needs to store the names of plants that are in a garden, so they can be easily found and accessed in alphabetical order.

The data is stored in a tree structure. Part of the tree is shown.

State the type of tree shown in Fig. 2.1.

Show the output of a breadth-first traversal of the tree shown in Fig. 2.1.

Explain how backtracking is used in a depth-first (post-order) traversal. Use the tree in Fig. 2.1 in your explanation.

The elements in the tree in Fig. 2.1 are read into a linked list producing an alphabetised list.

Complete the following table to show the linked list for the data.

A new plant, Lavender, needs adding to the linked list. The linked list needs to retain its alphabetical order.

Complete the table to show the linked list after Lavender is added.

Hosta needs removing from the linked list.

Explain how a data item is removed from a linked list. Use the removal of Hosta in your answer.

The linked list is stored as a 2D array with the identifier plantList. The index of the first element of the linked list is stored in the identifier firstElement.

All contents of the linked list need to be output in alphabetical order.

Write an algorithm to follow the pointers to output the contents of the linked list in alphabetical order.

Add comments to explain your code.

A software company is producing software that allows users with severe mobility issues to input data into a computer.

The software flashes up letters on the screen one at a time. The user sends a signal to the computer when the letter they want appears on the screen.

State the name of an input device and describe how it could be used by a user with very limited mobility in their hands and arms to send a signal to the computer.

How it would be used:

Rather than displaying the whole alphabet, once the first letter has been entered, the program only shows letters that could be possible according to words in its dictionary. All possible words are stored in a tree data structure.

The program is tested on a sample dictionary of four words, represented as a tree in Fig. 3:

Annotate Fig. 3 to show how the word BELTS would be removed from the tree.

Annotate Fig. 3 to show how the words BEACH and BONE would be added to the tree.

The developer decides she wants to make the software program open source.

Explain the benefits to the users of the software being open source.

A program stores entered data in a binary search tree.

The current contents of the tree are shown:

Complete the diagram to show the contents of the tree after the following data is added:

England, Scotland, Wales, Australia

Show the order of the nodes visited in a breadth first traversal on the following tree.

A pseudocode algorithm is written to search the tree to determine if the data item “Sweden” is in the tree.

The function currentNode.left()returns the node positioned to the left of currentNode

Complete the algorithm.

The algorithm needs to be used in different scenarios, with a range of different trees.

Identify two preconditions needed of a tree for this algorithm to work.

A software development team is writing a word game.

The team is using Rapid Application Development.

Players are given 10 random letters and asked to find the largest word they can make from those letters. Each letter can only be used once. The length of the word determines the number of points awarded. e.g. a word with 6 letters would mean 6 points are awarded.

The function validateAnswer takes in the randomLetters as an array of letters and the player’s as a string. It then checks if the word the player has entered only contains letters from the 10 random letters with each letter being used only once. (At this stage the program doesn’t check if the answer provided is an actual word.) It then returns a score, out of 10, for a valid word or 0 for an invalid word.

Example

If the random letters are

OPXCMURETN

The word COMPUTER returns 8

Whereas

The word POST returns 0 (there is no S in the random letters).

And

The word RETURN returns 0 (there is only one R in the random letters).

Complete the function validateAnswer

function validateAnswer(answer, randomLetters[])

endFunction

Code is to be added to check if the word is an actual English word. All English words are stored in a binary search tree.

Give one advantage of storing the words in a binary search tree over an array.

The software team use a prebuilt library to create the Graphical User Interface.

Give two advantages to the software team of using a library.

* The program is compiled. Explain the process of compilation including how code from the library becomes part of the finished program, justifying why each stage is necessary.

Identify the data structure shown in Fig. 4.1.

The programmer is considering using a depth-first (post-order) traversal, or a breadth-first traversal to find the path between node A and node X.

Explain the difference between a depth-first (post-order) and breadth-first traversal.

Show how a depth-first (post-order) traversal would find the path between node A and node X for the structure shown in Fig. 4.1.

Explain how you used backtracking in your answer to part (b)(ii).