Algorithms for the main data structures

A program is designed to use a stack data structure.

The current contents of part of the stack and its current pointer value are shown:

pointer = 2

Show the contents of the stack and its pointer value after the data items "t" and "s" are inserted in the order given.

The stack is stored using a 0-based 1-dimensional array called theStack with 20 elements.

The function push() stores its parameter into the next space in the stack if it is not full. The function returns true if it is successfully stored and returns false if the stack is full.

Complete the function push() using pseudocode or program code.

A pointer value of-1 indicates that the stack is empty.

The function pop() returns the next element in the stack. If the stack is empty it returns "false". The function updates the pointer value when appropriate.

Write the function pop() using pseudocode or program code.

A program is designed to reverse a set of data using the stack.

The main program takes 10 characters separately as input from the user and uses the function push() to insert these into the stack.

Once all 10 characters have been inserted into the stack, the program then uses the function pop() to output all 10 characters from the stack.

Write the main program to achieve this using pseudocode or program code.

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)........

A linked list data structure is designed using object-oriented programming.

The design includes two classes called node and linkedList.

Describe the features of a linked list data structure.

The class design for node is shown here.

new() is the constructor method. The constructor method takes a parameter and assigns this to the value attribute.

The method getNextNode() returns the attribute nextNode.

Write the method getNextNode() using pseudocode or program code.

The method setValue() takes an integer as a parameter and assigns this to the attribute value

Write the method setValue() using pseudocode or program code.

The class design for linkedList is shown here.

new() is the constructor method. The constructor initialises the attribute headNode to a null value.

Write the constructor method using pseudocode or program code.

The class design for node and linkedList are shown again here for your reference.

The method getValue() will return the value of a node. The method getNextNode() will return the next node to be accessed in the linked list.

The method outputList() traverses the linked list starting at the node headNode. The method joins the data in each node and returns it.

Complete the method outputList() using pseudocode or program code.

The method insertNode() will insert a new node into the linked list.

The method accepts an integer as a parameter, creates a new node with that data and inserts it into the linked list, e.g. insertNode(8) creates a node object with the data 8 and adds it to the linked list.

The program needs to store the following data items in the linked list in the order they are given: 10 25 39

The program then needs to output all of the data in the list using the appropriate method.

Write an algorithm using pseudocode or program code to:

• create a new linkedList object with the identifier createList

• insert each of the data items into the linked list (10, 25, 39)

• output the content of the linked list.

A new method is needed to remove a node from the linked list. The method needs to take the data to remove as a parameter and then find this data in the linked list before removing the node.

Describe the steps that this method will need to follow and the decisions that need to be made in the method to remove the correct node.

The program developer made use of computational methods when designing the object-oriented programming solution. One computational method is divide-and-conquer.

Identify three other computational methods that the program developer could have used.

* This program uses classes and objects to create a linked list.

An alternative method is creating a 2-dimensional array. In this design the first index stores the data and the second element stores the index of the next data item. Array elements not currently used are also linked together to form a chain of empty values to identify where the next data item can be inserted.

Compare the two different methods of creating a linked list that have been described.

You should include the following in your answer:

• the features of both methods including the reusability of program components

• benefits and drawbacks of both methods in this program

• a conclusion evaluating the efficiency of both methods when designing a program that needs

a linked list.

State the purpose of headPointer and tailPointer in the queue shown in Fig. 4.

The queue is used to store ID numbers of jobs that a program needs to process. Some jobs will be given a priority which means they need to be processed first.

Explain why this queue is not a suitable data structure for this program.

The contents of a stack are stored in the 1-dimensional array called numbers.

topStack stores the index of the next free space in the stack.

The array is declared with space for 100 elements.

The function pop() returns the next item from the stack and updates the appropriate pointers.

Describe the steps in the function pop().

The function push() inserts its parameter called dataValue onto the stack and updates the appropriate pointers.

Complete the function push() using pseudocode or program code.

Write an algorithm, using pseudocode or program code, to call the function push() with the value 15 and output a message saying "Added" if the value was successfully inserted onto the stack or "Not Added" if the stack is full.

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 program stores data in a linked list.

The current contents of the linked list are shown in Fig. 3, along with the linked list pointers.

State the purpose of headPointer and freeListPointer in the linked list shown in Fig. 3.

State the meaning of the pointers with the value NULL in the linked list shown in Fig. 3.

A procedure outputs the data in the linked list shown in Fig. 3 from the first item in the list, to the last item.

Give the output from the procedure.

A new item needs to be added to the linked list.

Describe how a new item is added to a linked list.

The function findNode will search the linked list and return either the position of the node that contains the data item, or-1 if the data item is not found.

The data held in a node at location x can be accessed with linkedList[x].data. The pointer of the node at location x can be accessed with linkedList[x].pointer.

Complete the function, using pseudocode or program code.

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 computer uses a stack data structure, implemented using an array, to store numbers entered by the user.

The array is zero based and has 100 locations.

State the purpose of pointerValue.

The stack is programmed as an object using object-oriented programming. The design for the class, its attributes and methods are shown:

The method pop() returns the next value in the stack, or –1 if the stack is empty.

Complete the pseudocode method pop().

The method push() accepts an integer as a parameter and adds it to the top of the stack unless the stack is already full.

If the push is successful the method returns true.

If the push is unsuccessful due to the stack being full the method returns false.

Write the method push() using either pseudocode or program code.

The main program initialises a new object of type stack with the identifier mathsStack

Write pseudocode or program code to declare the object.

The main program needs to:

• take numbers as input from the user

• push them onto the stack mathsStack until the stack is full

• output an appropriate message if the stack is full.

Complete the pseudocode algorithm to meet these requirements.

The main program also needs to:

• remove one item from the stack at a time and add this to a total

• output the total every time an item is removed

• stop removing items when either the stack is empty, or 20 items have been removed.

Write pseudocode or program code to meet these requirements.

The program is amended to include the use of several queue data structures.

Describe how an array can be used to implement a queue data structure.

* Discuss the use of object-oriented programming and procedural programming to create and manipulate the queue data structures.

You should include the following in your answer:

• the features of object-oriented programming

• the features of procedural programming

• the benefits of using object-oriented instead of procedural programming when creating several queue structures.

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.

Lucas writes a program that makes use of a circular queue. The queue stores the data entered into the program. An array is used to represent the queue.

The program needs two pointers to access and manipulate the data in the queue.

State the purpose of the two pointers and give an appropriate identifier for each.

Pointer 1 purpose........

Pointer 1 identifier........

Pointer 2 purpose........

Pointer 2 identifier........

Lucas wants a procedure, enqueue(), that will add the parameter it is passed to the queue.

Describe the steps the procedure enqueue() will follow when adding new items to the queue.

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 printer buffer is a storage area that holds the data, known as jobs, that are to be printed by a printer.

A simulation of the printer buffer uses a queue data structure to store jobs that are waiting to be printed. The queue is not circular.

The printer buffer is represented as a zero-indexed 1D array with the identifier buffer.

Fig. 2 shows the current contents of the queue buffer and its pointers.

State the purpose of the pointers queueHead and queueTail.

The array, buffer and pointer values are declared with global scope.

The function dequeue returns null if the array is empty, and the contents of the next element if not empty. The queue is not circular.

Write an algorithm, using pseudocode or program code, for the function dequeue()

The function enqueue returns-1 if there is no space at the end of the queue to add data, and returns 1 if the parameter was added to buffer. The array buffer contains a maximum of 100 elements.

Write an algorithm, using pseudocode or program code, for the function enqueue()

In the main program of the simulation the user is asked whether they want to add an item to the queue or remove an item.

If they choose to add an item they have to input the job name, and the function enqueue is called.

If they choose to remove an item, the function dequeue is called and the job name is output.

Appropriate messages are output if either action cannot be run because the queue is either empty or full.

Write, using pseudocode or program code, an algorithm for the main program of the simulation.

The queue is changed to make it a circular queue.

Describe how the functions enqueue and dequeue will need to be changed to allow buffer to work as a circular queue.

Some print jobs can have different priorities. The higher the priority the sooner the job needs to be printed.

Describe how the program could be changed to deal with different priorities.

Barney is writing a program to store data in a linked list. He is writing the initial program for a maximum of 10 data items.

Each node in the linked list has a data value and a pointer (to the next item).

A null pointer is stored with the value –1.

Describe the purpose of freeListPointer.

State the purpose of headPointer.

Barney wants the nodes to be stored as objects using object-oriented programming. He designs the following class.

The constructor assigns the parameters to the attributes to create an object.

The class node, uses get methods and set methods.

Describe one difference between get methods and set methods.

The function findNodePath() takes the data item to find in the linked list as a parameter and follows the pointers to find the required node.

The function returns the array indexes of all the nodes it visits and joins this to a suitable message stating whether the data was found or not found and then returns this as one string.

Describe how the function findNodePath() will search for the data item and return the required message.

The procedure printLinkedList() follows the pointers to print all of the elements in the linked list.

The procedure has a number of errors.

Identify the line of each error and write the corrected line.

Error 1 line number........

Error 1 correction........

Error 2 line number........

Error 2 correction........

Error 3 line number........

Error 3 correction........

Barney will use an Integrated Development Environment (IDE) to debug his program code.

Describe three features commonly found in IDEs that Barney could use to debug his program code.

* Barney would like his linked list to be part of a base program that is saved in a library. This means that it can be reused and changed by other programs.

Discuss the benefits of using different object-oriented techniques that Barney could use to achieve this.

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 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 computer program stores data input on a stack named dataItems. The stack has two sub-programs to add and remove data items from the stack. The stack is implemented as a 1D array, dataArray.

The current contents of dataItems are shown:

The main program asks a user to push or pop an item from the stack. If the user chooses ‘push’, the data item is added to the stack. If the user chooses “pop”, the next item is removed from the stack, multiplied by 3 and output.

The main program is shown:

Before the sub-programs, push() and pop(), can add or remove items from the stack, a selection statement is used to decide if each action is possible.

Describe the decision that needs to be made in each sub-program and how this impacts the next process.

The algorithm does not work when the user enters "PUSH" or "Push". The algorithm needs to be changed in order to accept these inputs.

Identify the line number to be changed and state the change that should be made.

The stack is implemented as a 1D array, dataArray.

Describe how a 1D array can be set up and used to push and pop items as a stack.

As an array, the data in dataArray is sorted and then searched for a specific value.

The data in dataArray is sorted into ascending order using an insertion sort.

The current contents of dataArray are shown:

Show the steps of an insertion sort on the current contents of the array dataArray.

The array dataArray can now be searched using a binary search.

Describe the stages of a binary search on an array of size n.

The array has 50 items.

The function, searchItem(), performs a linear search for a data item.

Rewrite the function using a while loop.

Kamran is writing a program to manipulate the data for a set of items.

For each item, the program needs to store:

• Item name (e.g. Box)

• Cost (e.g. 22.58)

• Date of arrival (e.g. 1/5/2018)

• Transferred (e.g. true)

The items are added to a queue for processing.

The queue is defined as a class, itemQueue.

The head attribute points to the first element in the queue. The tail attribute points to the next available space in the queue. The numItems attribute states how many items are currently in the queue.

The data about the items can be stored using either a record structure, or as objects of a class.

Explain the similarities and differences between a record and a class.

Kamran chooses to use a record structure to store the data about the items.

Record structures may be declared using the following syntax:

Complete the pseudocode to declare a record called items.

New records may be created using the following syntax:

Write a programming statement to create a new item, using the identifier ‘box1’, with the item name “Box”, the cost 22.58, date of arrival 1/5/2018 and transferred true.

The array, theItems, stores the items in the queue. When the tail of the queue exceeds the last element in the array, it adds a new item to the first element if it is vacant.

For example, in the following queue, the next item to be added would be placed at index 0.

Define the term ‘queue’.

The attributes in itemQueue are all declared as private.

Explain how a private attribute improves the integrity of the data.

The constructor method creates a new instance of itemQueue and sets the head, tail and numItems attributes to 0.

Write an algorithm, using pseudocode or program code, for the constructor including the initialisation for all attributes.

The enqueue method:

takes as a parameter the item to insert in the queue

checks if the queue is full

reports an error and returns false if the queue is full

does the following if the queue is not full: o adds the item to the array at the tail position and adjusts the pointer(s) o returns true

The attribute numItems stores the number of items currently in the queue.

Write an algorithm, using pseudocode or program code, for the enqueue method.

Write a programming statement to declare an instance of itemQueue called myItems

Write a procedure, insertItems(), to ask the user to input the data for an item. The item is then added to the queue myItems. The user is continually asked to input data items until the queue is full.

When the main program ends, the items and the queue no longer exist.

Describe how Kamran could amend the program to make sure the items and queue still exist and are used the next time the program is run.

* Kamran wants to expand the program to allow it to handle up to 100,000,000 items and to allow him to search for data about items. Kamran is worried that the increase in the number of items will cause a decrease in the performance of the program. He decides to investigate the benefits of caching and concurrent processing.

Evaluate the use of caching and concurrent processing in this scenario and make a recommendation to Kamran.

A programmer is developing an ordering system for a fast food restaurant. When a member of staff inputs an order, it is added to a linked list for completion by the chefs.

Explain why a linked list is being used for the ordering system.

Order 158 has been made, and needs adding to the end of the linked list.

Add the order, 158, to the linked list as shown in Fig. 2.1. Show the contents of the linked list in the following table.

Order 159 has been made. This order has a high priority and needs to be the second order in the linked list. Add the order, 159, to the original linked list as shown in Fig. 2.1. Show the contents of the linked list in the following table.

The linked list is implemented using a 2D array, theOrders:

• Row 0 stores orderNo

• Row 1 stores next

The data now stored in theOrders is shown in Fig. 2.2.

The following algorithm is written:

Outline why nodeNo does not need to be stored in the array.

Complete the trace table for procedure x, for the data shown in Fig. 2.2.

Describe the purpose of procedure x.

A new order, 190, is to be added to theOrders. It needs to be the third element in the list. The current contents of the array are repeated here for reference:

Describe how the new order, 190, can be added to the array, so the linked list is read in the correct order, without rearranging the array elements.

The user needs to be able to search for, and find, a specific order number.

State an appropriate search algorithm that could be used, and justify your choice against an alternative Search algorithm.

Appropriate Search Algorithm........

The programmer is writing the program using an IDE.

Identify three features of an IDE that the programmer would use when writing the code and describe how the features benefit the programmer.

(f*) The programmer is considering using concurrent programming.

Discuss how concurrent programming can be applied to the food ordering system and the

benefits and limitations of doing so.

An encryption routine reads a line of text from a file, reverses the order of the characters in the string and subtracts 10 from the ASCII value of each letter, then saves the new string into the same file.

The program is split into sub-procedures. Three sub-procedures are described as follows:

• Read string from file

• Push each character of the string onto a stack

• Read and encrypt each character message

Identify one further sub-procedure that could be used in the program.

Describe two advantages of splitting the problem into sub-procedures.

A function, readMessage:

• takes the file name as a parameter

• reads and returns the line of text

Complete the pseudocode algorithm for readMessage:

A function, push, can be used to add a character to a stack. For example:

theStack.push("H")

places the character H onto the stack, theStack.

A procedure, pushToStack, takes a string as a parameter and pushes each character of the message onto the stack, messageStack.

Complete the procedure below.

Add comments to explain how your code works.

procedure pushToStack(message)

endprocedure

Describe the steps that the program would have to take in order to encrypt the characters stored in the stack, and save them in a single variable.

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).