Computational thinking and problem-solving Banker

1. (a) A stack is stored in a 1D array Stack[1:6]. TopPointer holds the index of the top item and is 0 when the stack is empty. The stack starts empty. These operations are carried out in order:PUSH 14, PUSH 27, PUSH 8, POP, PUSH 31, PUSH 5, POP, POPState the values removed by the POP operations, in order. [2]
2. (b) State the final value of TopPointer and the contents of Stack[1] to Stack[4] after all the operations. [3]

1. (a) A circular queue is stored in an array Queue[0:4]. FrontPointer starts at 0, RearPointer starts at −1 and NumItems at 0. When RearPointer or FrontPointer moves past 4 it wraps round to 0.These operations are carried out in order: Enqueue A, Enqueue B, Enqueue C, Dequeue, Enqueue D, Enqueue E, Dequeue, Dequeue, Enqueue F, Enqueue G.State the items removed by the Dequeue operations, and the final values of FrontPointer, RearPointer and NumItems. [4]
2. (b) Enqueue H is now carried out. State the index where H is stored and the new value of NumItems, and explain what would happen if Enqueue J were then attempted. [2]

1. (a) Describe the dictionary abstract data type. [2]
2. (b) An app for learners of Urdu stores English words with their Urdu translations. Explain why a dictionary is a suitable ADT for this, rather than a 1D array. [2]
3. (c) State two operations that a dictionary ADT provides. [2]

1. (a) Explain the difference between a stack and a queue. [2]
2. (b) For each use, state whether a stack or a queue is more suitable.(i) Holding print jobs sent to a shared printer.(ii) Storing return addresses when procedures call other procedures.(iii) The 'undo' feature in a text editor.(iv) Buffering keystrokes typed faster than a program can process them. [4]

1. (a) Give two advantages of implementing a list as a linked list rather than as an ordered array. [2]
2. (b) Give one disadvantage of a linked list compared with an array. [1]
3. (c) A linked list implemented in arrays also has a free list. Explain the purpose of the free list. [2]

1. (a) A linked list of student names uses nodes created dynamically. Write pseudocode to declare:(i) a pointer type TNodePointer that points to a TNode(ii) a record type TNode with a field Name (STRING) and a field Next (TNodePointer)(iii) a variable StartPointer of type TNodePointer. [4]
2. (b) Explain why TYPE is used in (i) and (ii) but DECLARE in (iii). [1]

A linked list of fruit names is held in two arrays, Data[0:7] and Pointer[0:7]:Index | Data | Pointer0 | "Mango" | 41 | "Apple" | 32 | (empty) | 63 | "Banana" | 04 | "Peach" | −15 | (empty) | 26 | (empty) | 77 | (empty) | −1StartPointer = 1, FreePointer = 5. The null pointer is −1.

1. (a) State the items in the linked list in the order they are visited from StartPointer. [1]
2. (b) "Cherry" is inserted into the list so that it stays in alphabetical order. State the new values of StartPointer and FreePointer, and every Data or Pointer value that changes. [4]
3. (c) "Apple" is then deleted, and its node is added to the start of the free list. State the new values of StartPointer, FreePointer and Pointer[1]. [3]

1. (a) The names Kiran, Daud, Rafay, Bano, Haris, Saima, Ehsan are inserted in this order into an empty binary search tree (alphabetical order, smaller to the left). The tree is stored in arrays Data[0:6], LeftPointer[0:6] and RightPointer[0:6], each name going into the next free index starting at 0. A null pointer is −1. Give the LeftPointer and RightPointer values for every index. [4]
2. (b) Write the order in which the nodes are visited in (i) an in-order traversal (ii) a post-order traversal. [3]

1. (a) A delivery company models five depots P, Q, R, S and T as an undirected graph. Roads join P–Q, P–R, Q–S, R–S and S–T. Write the adjacency matrix for the graph, using 1 for a road and 0 for no road, with rows and columns in the order P, Q, R, S, T. [3]
2. (b) State the number of 1s in the matrix and explain why the matrix is symmetrical. [2]
3. (c) Describe how the matrix would change if each road were given a distance in kilometres. [1]

1. (a) A circular queue of patient numbers at a clinic is stored in the global array Queue[0:19] with global variables FrontPointer, RearPointer and NumItems (initially 0, −1 and 0).Write a pseudocode procedure Enqueue(Patient : INTEGER) that adds Patient to the rear of the queue, or outputs "Queue full" if there is no space. [5]
2. (b) Explain why a circular queue makes better use of the array than a linear queue. [2]

1. (a) Write program code for a class Stack, implemented with an array/list of fixed size, with methods Push(Item) (returns False if full), Pop() (returns None/null if empty) and IsEmpty(). The top pointer must be a private attribute.Then write a function Balanced(Expression) that uses a Stack to return True if every bracket ( [ { in Expression is closed by the matching bracket in the correct order, and False otherwise. (Python shown; Java or VB.NET solutions are equally acceptable.) [9]
2. (b) State the value returned by Balanced for each test string: "(a+b)*[c-d]", "{x*(y+z]}", "((p+q)", "[(m/n)+{r*s}]". [2]

1. (a) A bank branch in Hyderabad issues numbered tokens to customers. Waiting tokens are stored in a circular queue of size 5 using a global array Queue, and global variables Front (0), Rear (−1) and NumItems (0).Write program code for:• a function Enqueue(Token) that adds a token and returns True, or returns False if the queue is full• a function Dequeue() that removes and returns the token at the front, or returns −1 if the queue is empty. (Python shown; Java or VB.NET solutions are equally acceptable.) [7]
2. (b) Tokens 101, 102, 103, 104 are enqueued, then Dequeue is called twice, then tokens 105, 106, 107 and 108 are each enqueued. State the values returned by the two Dequeue calls, which of the last four Enqueue calls return False, and the final values of Front and Rear. [4]

1. (a) A linked list is stored in the array List[0:9] of records of type TNode:TYPE TNode DECLARE Data : STRING DECLARE Pointer : INTEGERENDTYPEGlobal variables StartPointer and FreeListPointer hold the indices of the first node and the first free node; NullPointer is a constant −1.Write a pseudocode function DeleteNode(Item : STRING) RETURNS BOOLEAN that removes the first node whose Data is Item, adds that node to the front of the free list, and returns TRUE. It returns FALSE if Item is not in the list. [7]

1. (a) A stack of up to 10 integers is stored in the global array Stack[1:10]. The global variable TopPointer is 0 when the stack is empty.Write pseudocode for:• a function Push(Value : INTEGER) RETURNS BOOLEAN that adds Value to the stack and returns TRUE, or returns FALSE if the stack is full• a function Pop() RETURNS INTEGER that removes and returns the top value, or returns −1 if the stack is empty. [7]
2. (b) Explain why the order of the two statements that change TopPointer and access the array is different in Push and Pop. [1]

1. (a) A program keeps town names in alphabetical order using a linked list stored in two arrays of 8 elements, Data (strings) and Pointer (integers). StartPointer is initially −1 (null) and FreePointer is 0; at the start every node is in the free list, with Pointer[i] = i + 1 and Pointer[7] = −1.Write program code for:• the global arrays and pointers, initialised as described• a function Insert(Item) that takes the first free node, stores Item in it and links it into the correct alphabetical position, returning False if there is no free node and True otherwise• a procedure OutputList() that outputs the items in list order. (Python shown; Java or VB.NET solutions are equally acceptable.) [10]
2. (b) The towns Quetta, Bannu, Murree, Attock and Swat are inserted in that order. State the output of OutputList() and the final values of StartPointer and FreePointer. [3]

1. (a) A binary search tree of exam scores is stored in three global arrays of 10 elements: Data, LeftPointer and RightPointer (null = −1). RootPointer starts at −1 and NextFree at 0; nodes are used in index order.Write program code for:• a procedure AddNode(Value) that stores Value in the next free node and links it into the tree (smaller values to the left, equal or larger to the right), outputting "Tree full" if all nodes are used• a recursive procedure InOrder(Node) that outputs the values in ascending order• a function Find(Value) that returns the number of comparisons made to find Value, or the negative of the number of comparisons made if Value is not in the tree. (Python shown; Java or VB.NET solutions are equally acceptable.) [10]
2. (b) The scores 50, 30, 72, 18, 41, 66, 90, 35 are added in this order. State the output of InOrder(RootPointer), the value returned by Find(35) and the value returned by Find(70). [3]

1. (a) Describe an algorithm (in steps, not pseudocode) to search a binary search tree for a given value. [4]
2. (b) The values 10, 20, 30, 40, 50, 60, 70 are inserted in ascending order into an empty binary search tree. State the maximum number of comparisons needed to find a value, and the maximum if the same values had been inserted in the order 40, 20, 60, 10, 30, 50, 70. Explain the difference. [3]

1. (a) Describe how a linear search finds an item in a 1D array. [2]
2. (b) State the condition that must be met before a binary search can be used. [1]
3. (c) Explain why a binary search is usually faster than a linear search for a large array. [2]

1. (a) A sorted array contains 64 items. State the maximum number of comparisons needed to find an item using (i) a linear search (ii) a binary search. [2]
2. (b) The array grows to 128 items. State how the maximum number of comparisons changes for each search. [2]

1. (a) A bubble sort can be improved by using a Boolean flag. Describe how the flag improves the algorithm. [3]
2. (b) State the best-case and worst-case time complexity of the improved bubble sort, describing the data that gives each. [2]

1. (a) The array Values[1:15] contains:3, 8, 11, 17, 22, 26, 31, 38, 42, 47, 53, 59, 64, 70, 78A binary search uses Mid ← (Low + High) DIV 2, starting with Low = 1 and High = 15. State the values of Low, High and Mid at each step when searching for 59. [3]
2. (b) State the values of Mid in order when searching for 20, and the number of comparisons made before the search reports that 20 is not present. [3]

1. (a) State the Big O time complexity of each algorithm in the worst case.(i) linear search (ii) binary search (iii) bubble sort (iv) insertion sort [4]
2. (b) Explain what Big O notation describes, and state the space complexity of an insertion sort carried out in place. [2]

1. (a) An insertion sort is used to put this array into ascending order:29, 13, 41, 7, 22, 35Write the contents of the array after each pass of the outer loop (each pass inserts the next element into the sorted part). [5]
2. (b) Explain why insertion sort is efficient for an array that is already almost sorted. [1]

1. (a) Write a pseudocode function BinarySearch(SearchItem : STRING) RETURNS INTEGER that searches the global sorted array Names[1:500] and returns the index of SearchItem, or −1 if it is not found. Use an iterative (not recursive) method. [7]
2. (b) State the maximum number of comparisons with Names[Mid] your function makes for an array of 500 names. [1]

1. (a) An algorithm with time complexity O(n²) takes 2 seconds to process 1000 records on a server in Islamabad. Estimate the time to process 5000 records on the same server. [2]
2. (b) A linear search of 2000 records takes 0.4 ms in the worst case. Estimate the worst-case time for 10 000 records. [1]
3. (c) A binary search needs at most 10 comparisons for an array of 1000 items. State the maximum number of comparisons for 1 000 000 items and explain your answer. [2]

1. (a) Write program code for:• a function InsertionSort(Items) that sorts a list/array of integers into ascending order in place and returns the number of comparisons made between Items[j] and the value being inserted• a function BinarySearch(Items, Target) that returns the index of Target in the sorted list (indices start at 0), or −1 if not present. (Python shown; Java or VB.NET solutions are equally acceptable.) [9]
2. (b) The main program sorts the list 8611, 4692, 7027, 3500, 8126, 6050, 5100, 7788 and then searches for 7027 and for 6000. State the sorted list, the number of comparisons returned by InsertionSort, and the two values returned by BinarySearch. [4]

1. (a) Explain what is meant by a recursive subroutine and state the two types of case it must have. [3]
2. (b) FUNCTION Mystery(N : INTEGER) RETURNS INTEGER IF N = 0 THEN RETURN 0 ELSE RETURN (N MOD 10) + Mystery(N DIV 10) ENDIFENDFUNCTIONState the value returned by Mystery(4073), the number of times Mystery is called in total, and what the function calculates. [3]

1. (a) PROCEDURE Show(N : INTEGER) IF N > 0 THEN CALL Show(N DIV 2) OUTPUT N MOD 2 ENDIFENDPROCEDUREThe procedure outputs each value on the same line with no spaces. State the output of CALL Show(13) and explain why the digits appear in this order. [3]
2. (b) State what the procedure does, and the output of CALL Show(0). [2]

1. (a) FUNCTION Power(B : INTEGER, E : INTEGER) RETURNS INTEGER DECLARE Half : INTEGER IF E = 0 THEN RETURN 1 ENDIF IF E MOD 2 = 0 THEN Half ← Power(B, E DIV 2) RETURN Half * Half ELSE RETURN B * Power(B, E - 1) ENDIFENDFUNCTIONList the calls made when Power(3, 10) is evaluated, and state the value returned. [4]
2. (b) Explain how the stack is used when Power(3, 10) runs, and state the maximum number of stack frames for Power at any one time. [3]
3. (c) Give one reason why an iterative solution might be preferred to a recursive one. [1]

1. (a) A child can climb a staircase by taking either 1 step or 2 steps at a time. The number of different ways to climb N steps is: Ways(1) = 1, Ways(2) = 2, and Ways(N) = Ways(N − 1) + Ways(N − 2) for N > 2.Write program code for a recursive function Ways(N) and an iterative function WaysIterative(N) that give the same results. (Python shown; Java or VB.NET solutions are equally acceptable.) [6]
2. (b) State the values returned for N = 5 and N = 10. [2]
3. (c) The recursive function makes 109 calls in total to calculate Ways(10). Explain why it is very slow for large N and how the iterative version avoids this. [2]