DP Computer Science Questionbank

Outline one reason why a linked list may be more suitable than a binary tree in this particular situation.

Construct the code needed to instantiate an object guests of the LinkedList class.

Define the term object reference.

Construct the code for the method penultimate() that returns the second to last element in the linked list guests. You may assume that guests is locally accessible.

Using the data provided in the diagram, trace the call recursive(0,'F'), clearly showing the levels of recursion.

Outline one reason why the use of a recursive method may be inappropriate for linked lists.

Due to unforeseen circumstances, schools may cancel their participation in an event at the last minute. Therefore, a method is needed to remove all the visiting students of one school from the linked list guests.

Construct the method removeSchool that takes the name of a school as parameter and removes all students of that school from the list guests.

Construct the method changePrice().

The method palindrome() is called by boolean t = palindrome(word);
where word is a String variable.

Without writing code, describe the recursive method palindrome() that returns whether or not a word is a palindrome.

Outline one benefit that the use of either of these choices will have over the original array structures.

Explain how a binary tree structure would allow a more efficient search for the Item object.

Sketch the resulting linked list when an airplane with ID RO225, STA 12:05 and delay 0 is added to this list.

In case of bad weather it is possible that one of the runways has to be closed and the two linked lists (runway1 and runway2) need to be merged using a method mergeLists() into one new linked list runway.

Construct the method public LinkedList<Arrival> mergeLists() that merges the two sorted linked lists in to one sorted linked list result which needs to be returned. You may assume that runway1 and runway2 are accessible to the method and do not need to be passed. The original two lists are allowed to become null as a result of the merging. 

In answering this question, you may use the following methods from the JETS LinkedList class, in addition to any method provided or developed in this exam paper.

addFirst(<object>)   // adds the object at the head of the list
addLast(<object>)    // adds the object at the tail of the list
getFirst()           // returns the head object in the list
getLast()            // returns the tail object in the list
removeFirst()        // removes and returns the head object
removeLast()         // removes and returns the tail object
size()               // returns the number of objects in the list
isEmpty()            // returns true if the list is empty

Trace the call process(runway1,0) given the diagram of runway1 as drawn above. Copy and complete the following table.

Evaluate the use of dynamic linked lists to static arrays when managing arriving airplanes.

Outline an advantage of using a library.

Define the term object reference.

Using object references, construct the method public Cart removeFirst() that removes the first CartNode object from list. The method must return the Cart object in that node or null if list is empty.

Sketch the linked list list after running the following code fragment where cart1, cart2, cart3, cart4 and cart5 have been instantiated as objects of the class Cart.

POSlist queueList = new POSlist()
queueList.addLast(cart2);
queueList.addLast(cart1);
queueList.addLast(cart4);
queueList.removeFirst();
queueList.addLast(cart5);
queueList.addLast(cart3);
queueList.removeFirst();

Outline one feature of the abstract data structure queue that makes it unsuitable to implement customers waiting in line.

Using object references, construct the method public Cart leaveList(int n) that removes the nth CartNode object from list. The method must return the Cart object in that node.

You may assume that the nth CartNode object exists in the list.
You may use any method declared or developed.

Explain the importance of using coding style and naming conventions when programming.

Outline why searching for the registration plate in a binary tree would be faster than looking for it in the two-dimensional array.

Identify the steps that would be involved in taking the data from this two-dimensional array and creating a binary search tree.

A stack can be implemented using an array or a singly linked list.

Compare the use of these two data structures for creating a stack.

Construct the staffRemoveCar method.

Copy and complete the following table to show the output when the method is called by: recursionEx(3);

Construct the method goldMails() that will return an ArrayList containing the email addresses of all current “Gold” members. You should make use of any previously defined methods.

Identify two essential features of a recursive algorithm.

Explain what would happen if the method was called by recursionEx(-3).

Identify three features which should be included in either program code or UML diagrams to help programmers understand and modify programs in the future.