Algorithms for the Main Data Structures (OCR A Level Computer Science): Exam Questions

Lucas writes a program that makes use of a circular queue. The queue stores the data entered into the program. An array is used to represent the queue.

The program needs two pointers to access and manipulate the data in the queue.

State the purpose of the two pointers and give an appropriate identifier for each.

A program stores data in a linked list.

The current contents of the linked list are shown in Fig. 3, along with the linked list pointers.

The function findNode will search the linked list and return either the position of the node that contains the data item, or -1 if the data item is not found.

The data held in a node at location x can be accessed with linkedList[x].data. The pointer of the node at location x can be accessed with linkedList[x].pointer.

For example, using the linked list shown in Fig. 3: linkedList[2].data returns green.
linkedList[2].pointer returns 8.

Complete the function, using pseudocode or program code.

function findNode(toFind, headPointer, linkedList)

  currentNode = ………………………………

  while(currentNode != ………………………………)

   if linkedList[currentNode]. ……………………………… == toFind 

    return currentNode

  else

   currentNode = linkedList[………………………………].pointer

  endif

 endwhile

 return ………………………………

 endfunction

Sundip writes an algorithm to carry out addition and subtraction. The algorithm will use an initially empty stack with the identifier numbers and will take input from the user.

The action the algorithm takes depends on the value input by the user. These actions are listed in Fig. 2.

Fig. 2.

do

  value = input("Enter a value")

  if value == "E" then

    num = numbers.pop()

    print(num)

  elseif value == "A" or value == "S" then

    numone = numbers.pop()

    numtwo = numbers.pop()

    if value == "A" then

      numbers.push(numone + numtwo)

    elseif value == "S" then

      numbers.push(numtwo - numone)

    endif

   else

     numbers.push(value)

   endif

until value == "E"

Complete the diagram to show the state of the stack after each value is entered into the algorithm. The letters will complete an action stated in Fig. 2.

The state of the stack after the first value, 8, has been completed for you.

Complete the following table to give the output from this algorithm when the following set of inputs are entered by the user. The letters will complete an action stated in Fig. 2.

If the user enters 4 2 S A E , the algorithm will not work correctly

Explain what problem this input data will cause and why the problem occurs.

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.

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().

pubic function pop() 
  if pointerValue == ............... then 
    return .................. 
  else 
    pointerValue = pointerValue .............
    returnValue = stackArray[................] 
    return ...........................
   endif 
endfunction

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.

returnValue = true 
while returnValue == .................
    returnValue = mathsStack. .............(input("Enter Number"))
    if returnValue == .............. then 
      ....................... ("Stack full") 
    endif
endwhile

Lucas writes a program that makes use of a circular queue. The queue stores the data entered into the program. An array is used to represent the queue.

Lucas wants a procedure, enqueue(), that will add the parameter it is passed to the queue.

Describe the steps the procedure enqueue() will follow when adding new items to the queue.

A programmer would like to traverse the binary search tree shown in Fig. 2.

Fig 2

Compare the use of a breadth-first traversal and a depth-first (post-order) traversal on the binary search tree..

You should include the following in your answer:

• how each traversal works

• the order of the return values for each traversal.

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.

The stack is programmed as an object using object-oriented programming. The design for the class, its attributes and methods are shown:

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 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.

A breadth-first traversal can be performed on both a tree and a graph.

Show how a breadth-first traversal is performed on the following binary tree.