Sequence, selection and iteration

Data in a computer program needs to be sorted.

Describe the steps a bubble sort will take to sort items into ascending order.

Darcie and Felix have both written a program that will perform a bubble sort to put these numbers into ascending order.

Darcie’s version will complete six passes. However, Felix’s version will only need to complete two passes.

Explain how Felix may have made his version more efficient than Darcie’s version.

A second type of sorting algorithm is an insertion sort.

Describe how an insertion sort can be used to put the following data into ascending order.

A third type of sorting algorithm is a quick sort.

The following quick sort algorithm is made up of two functions called partition() and quickSort(). The algorithm will sort an integer array into ascending numerical order.

Identify which of the two functions is recursive and give all of the line numbers where recursive calls are made.

Recursive function name........

Recursive call line numbers........

Identify the type of iteration used in the function partition().

Describe the role of the function partition() in the quick sort algorithm.

The algorithm needs to be changed to sort the integer array into descending numerical order.

Identify the line number that needs to be changed and write the amended line of code.

Amended line of code........

The quick sort is an example of a divide-and-conquer algorithm.

Describe what divide-and-conquer means.

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.

A student has written this pseudocode algorithm:

The program uses variables.

Describe what is meant by a variable.

Give the identifiers of all the variables used in this program.

The student has used a do loop on line 02.

Describe the difference between a do loop and a while loop.

Rewrite lines 05 to 07 to use a while loop instead of a for loop.

You should write your answer using either program code or pseudocode.

A game is being written that makes use of object-oriented programming. A prototype for one part of the game is being designed that includes a character, a road and a prize to collect.

The road will have 50 spaces that a character can move along. Each space on the road will store a null value or a prize object for the user to collect. Each space is numbered sequentially from the first space (position 0) to the last space (position 49) and will not change during the game. As the player travels down the road, the position the player is on the road will be output.

The road is designed to be a 1-dimensional array with the identifier road.

Explain why an array is a suitable data structure to represent the road.

The characters and prizes are designed as separate classes. 10 of the spaces on the road will contain an instance of the class Prize. The other spaces will be empty.

The class design for Prize is here.

new() is the constructor method. The name, type and value are passed to the constructor as parameters which then assigns these to the attributes.

The method getName() returns the data in the attribute name.

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

A global 1-dimensional array, allPrizes, stores 10 objects of type Prize.

The prize in index 3 has the name "Box", the type is "money" and the value is 25.

Write pseudocode or program code to create a new object for this prize and store it in index 3 of allPrizes.

The game starts with 10 prizes. Each prize is allocated to one space on the road.

An algorithm needs designing that will generate a random space on the road for each prize. Each road space can only store one prize.

Describe the decisions that will need to be made in this algorithm and how these will affect the program flow.

The class design for Character is here.

The four get methods return the associated attribute.

The number of moves is passed to changePosition() as a parameter. The method adds this value to the character’s position on the road.

The type and value of an object are passed to updateValues() as parameters. If the object is money the value is added to the character’s money. If the type is experience the value is added to experience. If the type is neither money or experience no changes are made.

new() is the constructor method. The name of the character is passed into the constructor as a parameter. The constructor then initialises both the experience and road position of the character to 0 and initialises the amount of money to 5.

Write the constructor method for Character using either pseudocode or program code. You do not need to declare the class, the attributes or any other methods.

The type and value of a prize are passed as parameters to the method updateValues. If the type is money the value is added to the character’s money. If the type is experience then the value is added to the experience. If the type is neither money or experience no changes are made.

For example, for the Character player1:

player1.updateValues("money",10) updates player1’s money by 10

player1.updateValues("experience",5) updates player1’s experience by 5

player1.updateValues("foo",9) has no effect on player1.

Write pseudocode or program code for the method updateValues().

This incomplete pseudocode algorithm:

• creates a new character with the name Jamal

• loops until the character reaches the end of the road

• generates a random number of spaces to move between 1 and 4 (including 1 and 4)

• moves the character and checks if the new space has a prize

• updates the character attributes if there is a prize

• outputs the character’s new attribute values.

Complete the pseudocode algorithm.

The procedure displayRoad() outputs the contents of each space in the road. The number of each space is output with either:

• the word "empty" if there is no prize

• the name of the prize if there is a prize.

The algorithm contains errors.

Give the line number of four different errors and write the corrected line for each error.

Error 1

Error 2

Error 3

Error 4

* A programmer is going to create a prototype for one small part of the game. Both road and allPrizes will be needed throughout the whole prototype. The programmer is considering making these global arrays as she thinks it will reduce the development time. Another programmer has suggested that doing this may create some problems when the rest of the game is created at a later stage.

Compare the use of global and local variables in this program.

You should include the following in your answer:

• the use of local and global variables

• alternative methods to using global variables

• the appropriateness of each to this program design.

A programmer has designed a program that includes a reusable program component.

The reusable program component is a function called isInteger(). This will take a string as an argument and then check that each digit is between 0 and 9. For example if 103 is input, it will check that the digits 1, 0 and 3 are each between 0 and 9.

The asc() function returns the ASCII value of each digit. For example asc("1") returns 49.

The ASCII value for 0 is 48. The ASCII value for 9 is 57.

Identify one identifier used in the function isInteger().

Give the line number where the branching (selection) construct starts in the function isInteger().

Give the line number where the iteration construct starts in the function isInteger()

Describe the purpose of the following lines in the function isInteger().

Line 03........

Line 04........

Line 09........

Give two reasons why reusable program components are used in programs.

A text-based computer game allows a user to dig for treasure on an island. The island is designed as a grid with 10 rows and 20 columns to store the treasure. Each square is given an x and y coordinate. Some of the squares in the grid store the name of a treasure object. Each treasure object has a value, e.g. 100 and a level, e.g. "Bronze."

The computer game makes use of abstraction.

Describe what is meant by the term abstraction and give an example of how abstraction can be used in the treasure game.

Give three benefits of using abstraction when writing a program.

The treasure game is being programmed using an object-oriented paradigm.

A class, Treasure, is used to store the treasure objects.

The design for the Treasure class, its attributes and methods is shown here.

The constructor method takes a value as an integer, e.g. 100, and a level, e.g. "bronze", as parameters and assigns these to the attributes.

Write pseudocode or program code to declare the class Treasure.

You should define the attributes and constructor method in your answer.

You do not need to write the get methods.

The get method getLevel() will return the appropriate attribute.

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

Describe the object-oriented programming technique being used in part 9(b)(ii).

A class, Board, is used to store the 10 row (x coordinate) by 20 column (y coordinate) grid.

The design for the Board class, its attributes and methods is shown here.

The constructor initialises each space in the grid to a treasure object with value as-1 and level as an empty string.

Complete the following pseudocode for the constructor method.

A procedure, guessGrid():

• takes a Board object as a parameter

• accepts the row (x) and column (y) coordinates from the user

• outputs "No treasure" if there is no treasure found at the coordinate (level is an empty string)

• if there is treasure at that coordinate, it outputs the level and the value of the treasure in an appropriate message.

Write the procedure guessGrid() using either pseudocode or program code.

Describe two benefits of using an object-oriented paradigm rather than a procedural paradigm.

* The main program initialises a new instance of Board. The programmer is considering declaring this as a global variable or as a local variable and then passing this into the subroutines that control the game.

Compare the use of variables and parameters in this game.

You should include the following in your answer:

• what is meant by a local variable and global variable

• how local and global variables can be used in this program

• the use of passing parameters by value and by reference.

A computer program stores data in an array named words.

The data in the array needs to be searched for a value that the user inputs.

One example of a searching algorithm is a binary search.

Identify the precondition for a binary search.

A second example of a searching algorithm is a linear search.

Describe how a linear search works.

The array words is defined as a global variable and contains these values:

The pseudocode function useWords() here uses the global array words.

The number of words in the array words is passed as a parameter.

Identify two variables in the function useWords().

numberOfWords is a parameter passed by value.

Describe the difference between passing a parameter by value and by reference.

Rewrite the function useWords() to use a while loop instead of a for loop.

The function header and close have been written for you.

Write your answer using pseudocode or program code.

function useWords(numberOfWords: byVal)

endfunction

Give one benefit and one drawback of declaring the array as a global variable instead of a local variable.

Describe one feature of an Integrated Development Environment (IDE) that can be used to help write the program and one feature that can be used to help test the program.

Functions and procedures are reusable components.

Give two benefits of writing a program with reusable components.

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.

The pseudocode function binarySearch() performs a binary search on the array dataArray that is passed as a parameter. The function returns the array index of searchValue within the array, and-1 if it is not in the array.

The pseudocode binary search algorithm is incomplete.

Complete the algorithm by filling in the missing statements.

The algorithm uses a while loop.

State a different type of loop that could be used instead of the while loop in the given algorithm.

The tables below show possible Big O complexities for the worst-case space, best-case space and average time for search algorithms.

Tick the worst-case space complexity for a binary and linear search.

Tick the best-case space complexity for a binary and linear search.

Tick the average time complexity for a binary and linear search.

Identify one situation where a linear search is more appropriate than a binary search.

Juan is creating a structure diagram to design the game.

A structure diagram is one method of showing the decomposition of a problem.

Explain why decomposing a problem can help a developer design a solution.

Identify one input, one process and one output required for the game.

Juan uses the structure diagram to create a modular program with a number of subroutines. The program will use two integer 2-dimensional arrays to store the puzzles:

• puzzle(5,5) stores the solution

• answerGrid(5,5) stores the user’s current grid.

A 0 represents a white box and a 1 represents a black box.

Explain the purpose of line 03 in the function countRow.

Describe the purpose of branching and iteration in the function countRow.

The function checkWon() takes answerGrid and puzzle as parameters and compares each element in the grids. If they are identical, it returns true, otherwise returns false.

There are three logic errors in the function checkWon.

State the line number of each error and give the corrected line.

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

Error 1 correction........

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

Error 2 correction........

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

Error 3 correction........

* Juan passed the two arrays as parameters, but he did consider making them globally accessible.

Compare the use of global and local variables and data structures in this program. Include the use of parameters and program efficiency in your answer.

Juan wants to create a program that will generate new Nonograms with different grid sizes. For example a Nonogram with a 10 × 10 grid or a 5 × 20 grid.

Describe how the program could be written to automatically generate a new Nonogram.

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.

A recursive function, GCD, is given in pseudocode.

The function uses branching.

Identify the type of branching statement used in the function.

Explain the difference between branching and iteration.

Identify the two parameters in the function.

1

2.

State whether the parameters should be passed by value, or by reference. Justify your answer.

Describe the arithmetic operation of MOD. Use an example in your answer.

Trace the recursive function when it is called by the statement GCD(250, 20). Give the final value returned.

Final return value:.

The function has been rewritten using iteration instead of recursion.

State one benefit and one drawback of using iteration instead of recursion.

Benefit.

Drawback.

Complete the missing statements in this iterative version of the function.

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.