IB Questionbank

User interface language: English | Español

Date	November 2019	Marks available	6	Reference code	19N.2.HL.TZ0.17
Level	HL	Paper	2	Time zone	no time zone
Command term	Construct	Question number	17	Adapted from	N/A

Question

The array line in POSline is now replaced by a singly linked list of CartNode objects. The class CartNode has been defined as follows.

public class CartNode
{
   private Cart myCart;
   private CartNode next;
   
   public CartNode(Cart aCart)
   {
      this.myCart = aCart;
      this.next = null;
   }
   public Cart getCart(){ return this.myCart; }
   public CartNode getNext(){ return this.next; }
   public void setNext(CartNode nextNode)
   {
      this.next = nextNode;
   }
}

The class POSlist has been implemented with the standard list methods addLast and removeFirst that act on list.

A method leaveList(int n) is required in the class POSlist, similar to the method leaveLine(int n) that was added to the class POSline.

Define the term object reference.

[2]

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.

[4]

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

[2]

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

[2]

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.

[6]

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

[4]

Markscheme

Award [2 max].
A pointer to a memory location;
where the object is stored;

Award [4 max].
Award [1] for declaring a result variable (or similar)
Award [1] for correct use of .getCart()
Award [1] for reassigning the head of the list
Award [1] for returning the correct result (either the Cart or null)

public Cart removeFirst()
{
    Cart result = null;

    if (head != null)
    {
       result = head.getCart();
       head = head.getNext();

    }
    return result;
}

Award [2 max].
Award [1] for a three nodes in order.
Award [1] root pointer (with or without identifier) and null pointer.

Award [2 max].
The abstract data structure queue is a FIFO structure / only allows addition at the end and removal from the front;
this is not sufficient because customers can change lines at any time;

Has no fixed length;
Which could lead to unmanageable/very long queues;

Note: do not award marks for responses that focus on dynamic vs static, since queues can be implemented either way.

Award [6 max].
Award [1] for declaring all variables used (including loop variable i);
Award [1] for initialising variable(s) for list traversal;
Award [1] for dealing separately with the case where n equals 1;
Award [1] for attempted looping through the linked list until the correct position;
Award [1] for correct loop using curr = curr.getNext(); (or similar)
Award [1] for correctly rearranging references to unhook the nth node;
Award [1] for returning the correct result;

Example answer using two CartNode variables:

public Cart leaveList(int n){
   Cart result = null;        // explicit default result
   CartNode prev = null;
   CartNode curr = head;

   if (n==1){
      result = removeFirst();
   }
   else{
      int i=1;
      while (i<n){           // no need to check for null
         prev = curr;
         curr = curr.getNext();
         i++;
      }
      result = curr.getCart();
      prev.setNext(curr.getNext());
   }
   return result;
}

Example answer using one CartNode variable:

public Cart leaveList(int n){
   Cart result = null;
   CartNode curr = head;

   if (n==1){
      result = removeFirst();
   }
   else{
      int i=1;
      while (i<n-1){           // no need to check for null
         curr = curr.getNext();
         i++;
      }                        // curr points to node (n-1)
      result = curr.getNext.getCart();
      curr.setNext(curr.getNext().getNext());
   }
   return result;
}

Award [2 max] for including any of the following elements on the discussion

Indentation / Use of white space
Annotations
Meaningful identifiers
Capitalization conventions

Award [2 max] for including any of the following reasons in the discussion
Helps understanding / reading;
For easer maintenance / extension;
For better team-work / collaboration / development;
To help with de-bugging;

Mark as [2] and [2].

Examiners report

This was a straight-forward definition.

Required candidates to show their understanding of the use of pointers for moving through a linked list. Many were unprepared for this, although it is an established part of the course, and incorrectly attempted to make use of the Linked List library class along with associated methods.

Many missed out the use of both head and null pointers in sketching the linked list.

This was well-answered.

This was a question that demanded specific examples which were not always given.

Syllabus sections

Option D: Object-oriented programming » D.4 Advanced program development

Show 33 related questions

19N.2.HL.TZ0.17c:

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

Hide related questions

Option D: Object-oriented programming

Question

Markscheme

Examiners report

Syllabus sections

View options