AQA, latest A-level COMPUTER SCIENCE 2022

Materials For this paper you must have: • a computer • a printer • appropriate software • the Electronic Answer Document • an electronic version and a hard copy of the Skeleton Program • an electronic version and ...

Materials For this paper you must have: • a computer • a printer • appropriate software • the Electronic Answer Document • an electronic version and a hard copy of the Skeleton Program • an electronic version and a hard copy of the Preliminary Material • an electronic version of the Data Files game1.txt and locks.txt You must not use a calculator. Instructions • Type the information required on the front of your Electronic Answer Document. • Before the start of the examination make sure your Centre Number, Candidate Name and Candidate Number are shown clearly in the footer of every page (also at the top of the front cover) of your Electronic Answer Document. • Enter your answers into the Electronic Answer Document. • Answer all questions. • Save your work at regular intervals. Information • The marks for questions are shown in brackets. • The maximum mark for this paper is 100. • No extra time is allowed for printing and collating. • The question paper is divided into four sections. Advice You are advised to allocate time to each section as follows: Section A – 40 minutes; Section B – 20 minutes; Section C – 20 minutes; Section D – 70 minutes. At the end of the examination Tie together all your printed Electronic Answer Document pages and hand them to the Invigilator. Warning It may not be possible to issue a result for this paper if your details are not on every page of your Electronic Answer Document. A-level COMPUTER SCIENCE Paper 1 2 IB/G/Jun22/7517/1 Section A You are advised to spend no longer than 40 minutes on this section. Type your answers to Section A in your Electronic Answer Document. You must save this document at regular intervals. 0 1 Big-O notation is used to express the time complexity of an algorithm. Table 1 contains a list of algorithms. State the Big-O time complexity of each of these algorithms. The first row has been completed for you. Table 1 Algorithm Time complexity Binary tree search O(log n) Bubble sort Linear search Merge sort Copy the contents of the unshaded cells in Table 1 into the table in your Electronic Answer Document. [3 marks] 3 IB/G/Jun22/7517/1 Turn over ► 0 2 A queue data structure can be implemented as a static data structure using an array. 0 2 . 1 Describe the method that would need to be followed to attempt to remove an item from a circular queue implemented as a static data structure using an array. Your method should deal appropriately with any issues which could arise. [4 marks] 0 2 . 2 Describe three differences between dynamic and static data structures. [3 marks] Figure 1 shows data that has been stored in a stack implemented using an array S. Figure 1 [7] [6] [5] [4] [3] [2] Jib Top = 2 [1] Skye [0] Harry 0 2 . 3 What value will be returned by applying the peek operation to S? [1 mark] 0 2 . 4 What value will be returned by applying the pop operation to S? [1 mark] 0 2 . 5 Explain how a single stack can be used to reverse the order of the items in a queue. [2 marks] Turn over for the next question 4 IB/G/Jun22/7517/1 Which one of these six statements is correct? Statement 1: All of the statements below are correct. Statement 2: None of the statements below are correct. Statement 3: All of the statements above are correct. Statement 4: Exactly one of the statements above is correct. Statement 5: None of the statements above are correct. Statement 6: None of the statements above are correct. 0 3 Figure 2 shows a logic puzzle. Figure 2 0 3 . 1 Explain why Statement 1 is not correct. [1 mark] 0 3 . 2 Which one of the six statements in Figure 2 is correct? [1 mark] 0 3 . 3 For two statements other than Statement 1 and your answer to Question 03.2, explain why those statements are not correct. [2 marks] 5 IB/G/Jun22/7517/1 Turn over ► 0 4 . 1 For each of the statements in Table 2, complete each row to indicate if the statement is true or false for Dijkstra’s algorithm. Table 2 True or False? Calculates the shortest path between a node and other nodes in a graph. Can be used to prove that the Halting Problem cannot be solved. Can be used with both directed and undirected graphs. Can be used with both weighted and unweighted graphs. Copy the contents of the unshaded cells in Table 2 into the table in your Electronic Answer Document. [2 marks] Figure 3 shows a subroutine represented using pseudo-code. The subroutine makes use of an array Visited and an array ConnectedNodes that stores a graph represented as an adjacency list. Figure 3 FUNCTION G(V, P) Visited[V]  True FOR EACH N IN ConnectedNodes[V] IF Visited[N] = False THEN IF G(N, V) = True THEN RETURN True ENDIF ELSE IF N ≠ P THEN RETURN True ENDIF ENDFOR RETURN False ENDFUNCTION 0 4 . 2 The subroutine G uses recursion. Explain what is meant by a recursive subroutine. [1 mark] Question 4 continues on the next page 6 IB/G/Jun22/7517/1 Figure 3 (repeated) FUNCTION G(V, P) Visited[V]  True FOR EACH N IN ConnectedNodes[V] IF Visited[N] = False THEN IF G(N, V) = True THEN RETURN True ENDIF ELSE IF N ≠ P THEN RETURN True ENDIF ENDFOR RETURN False ENDFUNCTION Figure 4 shows a subroutine represented using pseudo-code. The subroutine makes use of the array Visited. Figure 4 FUNCTION F() FOR Count  0 TO LENGTH(Visited) - 1 IF Visited[Count] = False THEN RETURN False ENDIF ENDFOR RETURN True ENDFUNCTION Figure 5 shows a subroutine represented using pseudo-code. The subroutine makes use of the subroutine G shown in Figure 3, the subroutine F shown in Figure 4 and the array Visited. Figure 5 FUNCTION E() Set all elements of Visited to False IF G(0, -1) = True THEN RETURN False ELSE RETURN F() ENDIF ENDFUNCTION 7 IB/G/Jun22/7517/1 Turn over ► Figure 6 shows a graph consisting of three nodes, the contents of the array ConnectedNodes when it is used to represent this graph, and the contents of the array Visited after the subroutine call G(0, -1). Figure 6 0 4 . 3 Complete the unshaded cells in Table 3 to show the result of the subroutine call F() when it is applied using the graph shown in Figure 6. Table 3 Count Value returned Copy the contents of the unshaded cells in Table 3 into the table in your Electronic Answer Document. [2 marks] Question 4 continues on the next page 8 IB/G/Jun22/7517/1 Figure 7 shows a graph consisting of four nodes and the contents of the array ConnectedNodes when it is used to represent this graph. Figure 7 0 4 . 4 Complete the unshaded cells in Table 4 to show how the graph in Figure 7 would be represented as an adjacency matrix. Table 4 0 1 2 3 0 1 2 3 Copy the contents of the unshaded cells in Table 4 into the table in your Electronic Answer Document. [1 mark] Figure 3 (repeated) FUNCTION G(V, P) Visited[V]  True FOR EACH N IN ConnectedNodes[V] IF Visited[N] = False THEN IF G(N, V) = True THEN RETURN True ENDIF ELSE IF N ≠ P THEN RETURN True ENDIF ENDFOR RETURN False ENDFUNCTION 9 IB/G/Jun22/7517/1 Turn over ► 0 4 . 5 Complete the unshaded cells in Table 5 to show the result of the subroutine call G(0, -1) on the graph shown in Figure 7. Some parts of the table, including the initial values in the Visited array, have been completed for you. Table 5 Visited Subroutine call V P [0] [1] [2] [3] N False False False False G(0, -1) Final value returned: Copy the contents of the unshaded cells in Table 5 into the table in your Electronic Answer Document. [6 marks] 0 4 . 6 What is the purpose of the subroutine G? [1 mark] 0 4 . 7 State the type of graph traversal used in subroutine G. [1 mark] 0 4 . 8 If the graph represented by ConnectedNodes is undirected, what can you determine about the graph when a value of True is returned by subroutine E? [1 mark] Turn over for the next section 10 IB/G/Jun22/7517/1 Section B You are advised to spend no more than 20 minutes on this section. Enter your answers to Section B in your Electronic Answer Document. You must save this document at regular intervals. The question in this section asks you to write program code starting from a new program/project/file. You are advised to save your program at regular intervals. 0 5 Write a program that asks the user to enter a string. It should then change the order of the vowels in the string and display the result. If there are n vowels in the string, the 1st vowel in the string should swap with the nth vowel in the string, the 2nd vowel in the string should swap with the (n-1)th vowel in the string, and so on. The letters a, e, i, o and u are the only vowels. You may assume the string that the user enters will only contain lowercase letters. Examples If the user enters the string horse then the program should display the string herso. If the user enters the string goose then the program should display the string geoso. If the user enters the string pinkfairyarmadillo then the program should display the string ponkfiaryarmidalli. If the user enters the string nakedmolerat then the program should display the string nakedmolerat. If the user enters the string lynx then the program should display the string lynx. If the user enters the string pig then the program should display the string pig. 11 IB/G/Jun22/7517/1 Turn over ► Evidence that you need to provide Include the following evidence in your Electronic Answer Document. 0 5 . 1 Your PROGRAM SOURCE CODE. [12 marks] 0 5 . 2 SCREEN CAPTURE(S) showing the results of three tests of the program by entering the strings persepolis, darius and xerxes. [1 mark] Turn over for the next sectio