Question 126 marks
Question
A program reads data from a text file and stores it in a queue. The linear queue Queue is stored as a 1D array of up to 50 elements. The queue has the following pointers: • HeadPointer – this stores the index of the first element in the queue, initialised to –1 • TailPointer – this stores the index of the last element in the queue, initialised to –1 (a) Queue is a global array of 50 integers with all elements initialised to –1 in the main program. The two pointers are declared as global variables and initialised to –1 Write program code to declare and initialise Queue, HeadPointer and TailPointer Save your program as Question1_J25. Copy and paste the program code into part 1(a) in the evidence document. [3] (b) The function Enqueue(): • takes an integer parameter to store in the next position in the queue • returns FALSE if the queue is full and the parameter cannot be stored in the queue • returns TRUE if the parameter is stored in the queue • updates the pointers where appropriate. Write program code for Enqueue() Save your program. Copy and paste the program code into part 1(b) in the evidence document. [6] (c) The function Dequeue(): • returns the next item in the queue, if the queue is not empty • returns –1 if the queue is empty • updates the pointers where appropriate. Write program code for Dequeue() Save your program. Copy and paste the program code into part 1(c) in the evidence document. [5] (d) The text file QueueData.txt stores positive integers. Each integer is on a new line in the file. The procedure CreateQueue(): • opens the file QueueData.txt • reads in each line from the text file and uses Enqueue() to insert each line into the queue • outputs "Queue full" if any item cannot be inserted into the queue • uses exception handling when opening and reading from the text file. The procedure needs to work for a file that contains an unknown number of lines. Write program code for CreateQueue() Save your program. Copy and paste the program code into part 1(d) in the evidence document. [6] (e) (i) The main program needs extending to call CreateQueue(). The main program then adds together all of the integers stored in the queue, using Dequeue() to access each integer. The total is then output. Write program code to extend the main program. Save your program. Copy and paste the program code into part 1(e)(i) in the evidence document. [5] (ii) Test your program. Take a screenshot of the output(s). Save your program. Copy and paste the screenshot into part 1(e)(ii) in the evidence document. [1]
Mark scheme
1(a) 1 mark each 3 • (Global) Queue array with 50 integer elements … • … all initialised to –1 • (Global) HeadPointer and TailPointer initialised with –1 Example program code: Python Queue = [] #integer 50 elements HeadPointer = -1 TailPointer = -1 #main HeadPointer = -1 TailPointer = -1 for x in range(50): Queue.append(-1) VB.NET Dim Queue(49) As Integer Dim HeadPointer As Integer Dim TailPointer As Integer Sub Main(args As String()) HeadPointer = -1 TailPointer = -1 For x = 0 To 49 Queue(x) = -1 Next End Sub Java public static Integer[] Queue = new Integer[50]; public static Integer HeadPointer; public static Integer TailPointer; public static void main(String args[]){ HeadPointer = -1; TailPointer = -1; for(Integer x = 0; x < 50; x++){ Queue[x] = -1; } } 1(b) 1 mark each 6 • Function Enqueue() header (and end) taking one (integer) parameter • Checking if Queue is full … • …returning FALSE if full and TRUE if not full • (Otherwise) storing data item at TailPointer + 1 (check incrementing) • Incrementing TailPointer • Checking if this is the first element and incrementing/storing 0 in HeadPointer Example program code: Python def Enqueue(Data): global Queue global TailPointer global HeadPointer if TailPointer < 49: TailPointer = TailPointer + 1 Queue[TailPointer] = Data if HeadPointer == -1: HeadPointer = 0 return True else: return False VB.NET Function Enqueue(DataValue As Integer) If TailPointer < 49 Then TailPointer = TailPointer + 1 Queue(TailPointer) = DataValue If HeadPointer = -1 Then HeadPointer = 0 End If Return True Else Return False End If End Function Java public static Boolean Enqueue(Integer DataValue){ if (TailPointer < 49){ TailPointer++; Queue[TailPointer] = DataValue; if(HeadPointer == -1){ HeadPointer = 0; } return true; }else{ return false; } } 1(c) 1 mark each 5 • Function Dequeue() header (and close) and returning appropriate value in all cases. • Checking if queue is empty … • … and returning –1 if empty • Accessing and returning element at Queue[HeadPointer] (before HeadPointer is incremented) • Incrementing HeadPointer Example program code: Python def Dequeue(): global Queue global HeadPointer if HeadPointer > -1 and HeadPointer <= TailPointer: ReturnValue = Queue[HeadPointer] HeadPointer = HeadPointer + 1 return ReturnValue else: return -1 VB.NET Function Dequeue() Dim ReturnValue As Integer If HeadPointer > -1 And HeadPointer <= TailPointer Then ReturnValue = Queue(HeadPointer) HeadPointer = HeadPointer + 1 Return ReturnValue Else Return -1 End If End Function Java public static Integer Dequeue(){ if (HeadPointer > -1 && HeadPointer <= TailPointer){ Integer ReturnValue = Queue[HeadPointer]; HeadPointer++; return ReturnValue; }else{ return -1; } } 1(d) 1 mark each 6 • CreateQueue() header (and end) and opening the file to read and closing file in appropriate place • Looping until end of file • Reading in each/all lines (and converting to integer and removing new line) • … calling Enqueue() once with each value … • … checking return value and outputting "Queue full" if full (can output once or many times) • Exception try, catch with appropriate output. All file access within try Example program code: Python def CreateQueue(): try: File = open("QueueData.txt") for Line in File: ReturnValue = Enqueue(int(Line)) if ReturnValue == False: print("Queue full") break; File.close() except: print("Cannot open or read file") VB.NET Sub CreateQueue() Dim ReturnValue As Boolean Dim ReadData As Integer Try Dim FileReader As New System.IO.StreamReader("QueueData.txt") While Not FileReader.EndOfStream ReadData = FileReader.ReadLine() ReturnValue = Enqueue(ReadData) If ReturnValue = False Then Console.WriteLine("Queue full") End If End While FileReader.Close() Catch ex As Exception Console.WriteLine("Cannot open or read file") End Try End Sub Java public static void CreateQueue(){ Boolean ReturnValue; Integer ReadData; try{ FileReader f = new FileReader("QueueData.txt"); try{ BufferedReader Reader = new BufferedReader(f); String Line = Reader.readLine(); Line = Line.replace("\n",""); while (Line != null){ Line = Line.replace("\n",""); ReturnValue = Enqueue(Integer.parseInt(Line)); if (ReturnValue == false){ System.out.println("Queue full"); } Line = Reader.readLine(); } Reader.close(); }catch(IOException ex){ } }catch(FileNotFoundException e){ System.out.println("Cannot open or read file");} } 1(e)(i) 1 mark each 5 • Calling CreateQueue() • Calling Dequeue() and storing/using return value … • … repeatedly until return value is –1 • … adding together all return values to create a total within the loop … • … outputting the total Example program code: Python CreateQueue() Total = 0 ReturnValue = 0 while ReturnValue > -1: ReturnValue = Dequeue() if ReturnValue != -1: Total = Total + ReturnValue print("The total is", Total) VB.NET CreateQueue() Dim Total As Integer = 0 Dim ReturnValue As Integer = 0 While ReturnValue > -1 ReturnValue = Dequeue() If ReturnValue <> -1 Then Total = Total + ReturnValue End If End While Console.WriteLine("The total is " & Total) Java CreateQueue(); Integer Total = 0; Integer ReturnValue = 0; while(ReturnValue > -1){ ReturnValue = Dequeue(); if(ReturnValue != -1){ Total = Total + ReturnValue; } } System.out.println("The total is " + Total); 1(e)(ii) 1 mark for screenshot showing 3059 1