IB Questionbank

User interface language: English | Español

Date	November 2017	Marks available	4	Reference code	17N.1.HL.TZ0.13
Level	HL	Paper	1	Time zone	no time zone
Command term	Show	Question number	13	Adapted from	N/A

Question

Consider the following doubly linked list which holds the names of flowers in alphabetical order.

Consider the two stacks: FLOWERS and FRUITS.

Describe the features of a dynamic data structure.

[2]

Explain how “Primrose” could be inserted into this doubly linked list. You should draw a labelled diagram in your answer.

[6]

Show the output produced by the following algorithm.

loop while (NOT FRUITS.isEmpty()) AND (NOT FLOWERS.isEmpty())
  X = FRUITS.pop()
  Y = FLOWERS.pop()
  if X < Y then
    output X
  else
    output Y
  end if
end loop

[4]

A third stack, FLOFRU, is needed. It should contain all the data from FLOWERS and FRUITS and will store it as shown below

Describe how the FLOFRU stack could be created.

[3]

Markscheme

Award up to [2 max].
Each node contains data and also a link to other nodes;
Links between nodes are implemented by pointers (a pointer references a location in memory or holds a memory address);
List size is not fixed / predetermined;

Award up to [6 max] as follows. (There are 7 marking points)
[1] create new node;
[1] instantiation of values and pointers in new node;
[1] state where the search starts from;
[1] how to detect position for insertion;
[1] update pointers in new node;
[1] update pointers from the node at the insertion point, to the new node;
[1] update external pointers;
Remark: Some answers may just use illustrations alone, or very minimal explanations: see note below;

Create a new node (with pointer NEWNODE) with data field Primrose and two pointer fields (next and previous), to be inserted;

Perform a linear search, either from the beginning or end of the list (using pointers FIRST and LAST, on the alphabetically order list;

The location/position of insertion, is found by comparing nodes (Primrose to be inserted after Lavender, LOCATION points to Lavender) (Accept any description to that effect);

(At the end of this phase, the situation looks as in Figure 1)

Figure 1

Then, continue by setting the “next” field/pointer in the newly created node to NULL;

Set the “previous” pointer in the newly created node to the current LAST / to point to Lavender/ to point to the node detected by LOCATION;

Change/Set/Update the Lavender’s “next” pointer to point to the new node / to link with the NEWNODE pointer (delete NULL in the field and link to the existing NEWNODE pointer);

Update the LAST pointer to point to the newly created node;

Eventually the final doubly linked list looks like this (Figure 2);

Figure 2

Note: Award [4 max] for responses that return one or more drawings without any explanation at all, for evidence of these features:
[1] Evidence of creation of an initial new node for Primrose out of the list;
[1] The order of nodes Aster/Camellia/Lavender/Primrose is eventually correct;
[1] The two unidirectional links between Lavender and Primrose are (eventually) correctly displayed, from-to the appropriate fields;
[1] LAST points correctly to the appropriate field in the new node Primrose, and NULL fills the last field of the new node;

Award [1] for each one in the correct order.
Apple;
Broom;
Camellia;
Day Lily;

Note: Solution for the Spanish version (in this order):
Aster; Camelia; Lavanda; Lirio;

Award marks as follows up to [3 max].

Example answer 1
Create an empty stack (FLOFRU);
pop all elements from FRUITS and push them onto FLOFRU;
Then pop all elements from FLOWERS and push them onto FLOFRU;

Example answer 2
Create an empty stack (FLOFRU);
While FRUITS is not empty
pop an element from FRUITS and push it onto FLOFRU;
While FLOWERS is not empty
pop an element from FLOWERS and push it onto FLOFRU;

Note: Award [2 max] for generic descriptions that do not use appropriate terminology on data structures and their operations.

Examiners report

[N/A]

Syllabus sections

Topic 5: Abstract data structures » 5.1 Abstract data structures

Show 80 related questions

Hide related questions

Topic 5: Abstract data structures

Question

Markscheme

Examiners report

Syllabus sections

View options