Advanced Higher
Computing Science
SDD Problem Solving
1. Stacks, Queues, Linked Lists
2. 2D Arrays
3. Sorting Algorithms
4. Binary Search
Stacks, Queues, Linked Lists
1. The names of the top 10 medal winning teams from an athletics competition are held in a stack. Part of the stack is shown.
(a) The USA wins enough medals to be fourth on the table. Write down the sequence of stack operations required to produce the new table.
(b) The stack storing the medal winning teams could be implemented
using a linked list.
The diagram below represents a linked list after the first six teams
have been added to the medal table.
Team Russia is to be added to the medal table between Germany
and the USA.
Describe how team Russia would be added to the correct place in
the linked list.
2. The titles of songs in a playlist are exported to a program for processing using a queue structure. The queue has been implemented as a 1-D array.
The contents of the queue are shown.
Use pseudocode to write an algorithm to remove a played song from the top of the playlist queue.
3. A computerised version of a card game, based on various animals native to Scotland, is being developed for a website.
During game play, players can take a card from or place a card on a pile of cards.
A stack data structure will represent this pile of cards.
The stack is held in a 1-D array and the last item placed in the stack was the Golden Eagle. The 1-D array in which the stack is held is shown below:
(a) An item is added to the stack by “pushing” and removed by “popping”. Draw the final state of the stack after the following five operations:
1. Pop
2. Push Loch Ness Monster
3. Pop
4. Pop
5. Push Grouse
(b) Apart from the 1-D array, describe another item of data required to implement a stack.
(c) When a stack is implemented using a 1-D array, adding a valid item can cause an execution error. Explain why an execution error can occur in this situation.
(d) A linked list could have been used rather than a stack to represent the pile of cards.
(e) Explain why the execution error in part (c) would not occur if a linked list is used rather than a stack.
4. A 1-D array is used to implement a stack. The variable top is a stack pointer which changes as items are added to or removed from the stack. The numbers 42, 4 and 11 have been placed on the stack. The current value of top is 2.
Index / 0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 942 / 4 / 11
(a) Describe how a stack operates
(b) State the value of top when the stack shown above is empty. Explain your answer.
(c) There are two operations that can cause stack errors to occur. State both of these operations and describe the error.
(d) Show how these stack items could be represented as a linked list.
(e) Explain why one of the errors you described in part (c) would be less likely to occur in a linked list.
2D Arrays
5. The Silver Spoon Cafe has twelve set menus which include starter, main course and dessert. The menu is presented as follows:Menu Number / Starter / Main / Dessert / Price
1 / Fruit Juice / Crispy Duck / Ice Cream / 12.30
2 / Ham & Melon / Special Burger / Strawberries / 8.50
3 / Tomato Soup / Moules Marinieres / Cheesecake / 9.60
4 / Tattie Soup / Rump Steak / Cheesecake / 14.80
5 / Spicy Ribs / BBQ Chicken Melt / Cheesecake / 13.80
6 / Prawn Cocktail / Moules Marinieres / Strawberries / 9.60
7 / Chicken Strips / Rump Steak / Strawberries / 10.50
8 / Potato Skins / BBQ Chicken Melt / Ice Cream / 14.80
9 / Ham & Melon / Crispy Duck / Ice Cream / 13.80
10 / Tomato Soup / Special Burger / Ice Cream / 8.60
11 / Tattie Soup / Moules Marinieres / Ice Cream / 10.50
12 / Spicy Ribs / Moules Marinieres / Ice Cream / 10.50
(a) Declare a 2-D array to store the set menu details shown in the table above.
(b) Write an algorithm, using pseudocode or a programming language of your choice, that will ask the diner to enter a menu item, for example, “Crispy Duck” and then display each set menu in which that item appears e.g.
1 / Fruit Juice / Crispy Duck / Ice Cream / 12.30
9 / Ham & Melon / Crispy Duck / Ice Cream / 13.80
(c) It has been suggested that a record structure would be a more efficient method of storing the café’s menu.
Describe two advantages of using a record structure rather than a 2-D array to store the menu items.
6. The aim of the game “Peg Solitaire” is to remove pegs from the board by jumping one peg over another. A peg can only jump over an adjacent peg into an empty location. The peg that has been “jumped over” is then removed from the board. Only horizontal and vertical jumps are allowed. The game is over when there are no more jumps possible. You win the game by leaving only one peg in the centre of the board.
At the start of the game, all locations (except the location in the middle of the game board) contain a peg. The initial set up of the pegs on the game board is shown below.
Cameron is an app developer, who is creating a computerised version of the “Peg Solitaire” game.
He decides to represent the location of the pegs in the game board as a
2-D array called board.
(a) Explain, in detail, how a 2-D array called board could be used to represent the position of pegs in the game board.
(b) From the initial set up position, four legal moves are possible. In each case, the peg marked X in the diagrams below can be moved to the centre location.
During play, the user indicates the chosen peg and its intended destination.
The app will record these locations using four variables:
chosenX, chosenY, intendX and intendY
where the X variables hold the horizontal positions across the array, with position 0 at the left, and the Y variables hold the vertical position up and down the array, with position 0 at the top.
Write the Boolean condition that will return true if the move indicated
by the user is valid.
(c) After each move, a check is made to see how many pegs are left.
Use pseudocode, or a programming language with which you are familiar, to write down the algorithm that will count the number of pegs left on the board.
(d) At any point in a game, the user can pause the game and save the
current game board. This is implemented by saving the contents of the
2-D array to an external file called “gameboard.txt”.
Use pseudocode, or a programming language with which you are familiar, to write down the algorithm to save the current game board to the external file.
Sorting Algorithms
7. A company salesperson is given a list of six locations to be visited. The
company’s IT department has given the salesperson an app for their
smartphone to plan the journeys. The salesperson enters the locations into the app, which calculates the distance in miles to each location from the office.
Within the app, the locations and distances are stored in a 1-D array of records.
The distances are displayed, as shown below.
(a) The app has an option to sort the locations into ascending order of distance. The app uses the insertion sort algorithm to do this.
A copy takes place when any record in the array is copied into a new position in the array.
Show the order of the locations and distances after the first three copies have taken place.
(b) Explain why the quicksort algorithm would be better than the insertion
sort algorithm for sorting an array of 5000 records.
Your answer should refer to how each algorithm works and the average time required to sort the array.
(c) After sorting, the details held in the array of records are shown below.
The button marked “Reverse” becomes active once the array has been
sorted. It is intended to reverse the order so that the records are in
descending order of distance, but the salesperson notices that this
feature does not work.
line
1 SET lower TO lowest index
2 SET upper TO highest index
3 FOR counter = lower TO upper DO
4 SET temp TO distance [counter]
5 distance [counter] = distance [upper-counter]
6 distance [upper-counter] = temp
7 END FOR
The above shows the code behind the “Reverse” button.
Applying an appropriate de-bugging technique, provide a detailed description of the error in the code and explain how to correct it.
Show your working.
8. A game includes a high score table with the names and scores of the top five players stored in two 1-D arrays.
After a number of games, the 1-D array that holds the scores is shown below:
Senga plays the game and scores 48. Her score of 48 and her name now replace the lowest score and name that were in position 0. The 1-D array for the scores is now:
A bubble sort is used to sort the scores. After the first pass, the list will be sorted:
(a) State the two exchanges that took place in this pass.
(b) Explain why the bubble sort will make another pass through the list, even though it is sorted.
(c) The updated high score table is displayed as shown.
Identify the error in the table and explain one possible cause of this error.
9. Over the first term of a course, a student submits six assignments. The percentage scores for each assignment are shown below.
80 89 96 88 79 75
The scores are to be sorted into descending order.
The selection sort using two lists algorithm is to be used. The initial state of two 1-D arrays is shown below.
This algorithm uses a dummy value.
(a) Explain the purpose of the dummy value.
(b) The dummy value used is –1. State two reasons for this choice.
(c) Copy and complete the following tables to show the state of the lists after two values have been moved to their correct position.
An alternative sort algorithm is the bubble sort.
(d) Explain how a bubble sort algorithm operates.
(e) Compare the bubble sort to the selection sort using two lists in terms of its use of memory and the number of comparisons.
Binary Search
10. The following list of numbers is to be held in a 1-D array as shown below.
A binary search for the number 42 will be performed.
(a) Using pseudocode or a language with which you are familiar, write a binary search algorithm to find the value 42.
(b) Use the values of lower, middle and upper to explain how the algorithm would perform when searching for the value 42.
(c) This algorithm will not function correctly if the list is in descending order. This can be corrected by changing one line of the algorithm. Identify the line to be changed and state the change required.