Data structures

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.

Sundip writes an algorithm to carry out addition and subtraction. The algorithm will use an initially empty stack with the identifier numbers and will take input from the user.

The action the algorithm takes depends on the value input by the user. These actions are listed in

Complete the pseudocode here to implement Sundip’s algorithm.

Complete the following table to give the output from this algorithm when the following set of inputs are entered by the user. The letters will complete an action stated in Fig. 2

If the user enters 4 2 S A E, the algorithm will not work correctly.

Explain what problem this input data will cause and why the problem occurs.

A stack is one data structure that is available for Sundip to use. She could also use a queue, list, linked list, array or tuple.

Describe one difference between a stack and a queue.

Describe one difference between an array and a list.

State how a tuple is different to a list.

Describe how the second item in a linked list would be accessed using pointer values.

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.

A programmer is writing software for a firewall. She is writing code so that it keeps a track of websites that users are permitted to visit. The software stores the websites’ addresses along with details about who can view them and when.

The following data is also stored about each website:

• Access level needed (1-4) • If it is available all the time (true) or just lunch times and out of work hours (false).

So a website which is available to users of access level 2 and above, all the time, would have the details [2, true] stored.

A website accessible to users of access level 3 and above, only outside of work hours, would have the details [3, false] stored.

State the name of a data structure that could be used to store a single site’s details.

A flaw with the current hash function is it tends to generate lots of collisions (addresses that compute to the same hash). Below is a diagram of part of the hash table. The address www.rnd.com with details [2, true] is being added to the hash table.

Explain how a hash table can be used to handle collisions, referring to the example below.

The hash function is changed so there are no longer high numbers of collisions.

During busy periods the firewall is expected to check several addresses a second. It is anticipated that roughly 10 new addresses will be added to a whitelist (list of acceptable addresses) each day.

There is a debate as to whether a hash table (with the new hash function) is the best approach, or if the whitelist would be better stored in a linked list.

*Discuss whether a hash table or linked list is better to store acceptable websites. You should compare how each structure can be searched and has data added and come to a

recommendation as to which is better for the whitelist.

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 coach company offers tours of the UK.

A linked list stores the names of cities on a coach tour in the order they are visited.

Describe what is meant by the term ‘linked list’.

The tour is amended. The new itinerary is: London, Oxford, Manchester then York. Explain how Birmingham is removed from the linked list and how York is added. You may use the diagram below to illustrate your answer.

The program stores records about its customers.

Often an individual customer’s record needs to be accessed. This is done by searching using the Customer ID. Explain why a hash table is better suited than a linked list to store the customer records, particularly as the company acquires more customers.

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.