B2.2 Data structures questions for IB Computer Science

211 questions on Data structures, written by Augment in the style of IB exam papers. Six of them are below in full, to answer on paper.

  • IB Computer Science
  • Part of B2 Programming
  • SL and HL

Questions by paper and level

SL and HL questions are for students at either level. HL only questions cover what only HL students study.

PaperSL and HLHL onlyAll
Paper 217635211

Counted on

Questions to try

Written by Augment in the style of IB exams, not past papers. Answer them on paper, then check each one against its markscheme with a free account.

Question 1 · CS-00933Paper 2 · 5 marks

A college print room sends every print job to a single printer. Jobs wait in a queue and the printer always takes the job at the front. The queue starts empty, and then these operations happen in order:

enqueue(J1), enqueue(J2), enqueue(J3), dequeue(), enqueue(J4), dequeue(), enqueue(J5)

  1. (a)

    State the job that the printer will print next.

    1 mark

  2. (b)

    State the contents of the queue after the operations, from front to rear.

    2 marks

  3. (c)

    Outline one reason why a queue is a suitable structure for the print jobs.

    2 marks

The markschemeCheck this one with a free account
Question 2 · CS-00934Paper 2 · 6 marks

A drawing app records each action a user takes on a stack so that it can be undone. Pressing Undo pops the most recent action from the stack and reverses it. The stack starts empty.

A user carries out these actions in order:

  1. draws a circle

  2. fills it blue

  3. adds a text box

  4. presses Undo

  5. draws a line

  6. presses Undo

  7. presses Undo

  1. (a)

    State the action at the top of the stack after step 3.

    1 mark

  2. (b)

    State the contents of the stack after step 7, and which actions are still shown in the drawing.

    2 marks

  3. (c)

    Explain why a stack, rather than a queue, is used to store the actions for undo.

    3 marks

The markschemeCheck this one with a free account
Question 3 · CS-00935Paper 2 · 14 marks

A railway depot keeps the carriages of a train in a queue on the main track. A short dead-end siding behaves like a stack: a carriage can only enter or leave the siding at one end. The depot can dequeue a carriage from the front of the main track, push it into the siding, pop the carriage nearest the siding entrance, and enqueue a carriage at the rear of the main track.

The main track currently holds five carriages:

Front

Rear

C1

C2

C3

C4

C5

  1. (a)

    State the operation that removes C1 from the main track.

    1 mark

  2. (b)

    Describe, in steps, how the depot can use the siding to reverse the order of all the carriages on the main track. Your steps must work for any number of carriages.

    4 marks

  3. (c)

    State the contents of the siding when all five carriages are in it, and the order of the main track at the end of your steps in part (b).

    2 marks

  4. (d)

    The depot now needs to reverse only the first three carriages and leave the rest in their original order behind them. Starting again from the queue C1, C2, C3, C4, C5, the required result is C3, C2, C1, C4, C5 (front to rear).

    Describe, in steps, how this can be done using only the queue and stack operations. Your steps should work for any number of carriages n and any number k to be reversed, where k ≤ n.

    5 marks

  5. (e)

    Outline how the number of operations needed in part (d) grows as the number of carriages increases.

    2 marks

The markschemeCheck this one with a free account
Question 4 · CS-00936Paper 2 · 15 marks

A spreadsheet app checks that the brackets in a formula are balanced before it calculates the result. It ignores every character except the brackets (, ), [, ], { and }, and uses a stack. Every opening bracket is pushed. When a closing bracket is read, the bracket on top of the stack is popped and must be the matching opening bracket.

The brackets from one formula are:

{ [ ( ) ] ( ) }

  1. (a)

    Trace the check for this formula. Copy and complete the table, showing the stack contents (bottom to top) after each bracket is processed.

    Bracket read

    Stack after (bottom → top)

    {

    [

    (

    )

    ]

    (

    )

    }

    4 marks

  2. (b)

    Another formula has the brackets ( [ ) ]. Identify the bracket at which the check fails, and explain why.

    2 marks

  3. (c)

    A programmer suggests a simpler check that only counts the opening and closing brackets of each type and accepts the formula if the counts are equal. Explain, using the formula in part (b), why this check is not enough.

    2 marks

  4. (d)

    State the result of the stack check for each of the following, and give the reason:

    • (i) ( ( )

    • (ii) ( ) )

    2 marks

  5. (e)

    Describe, in steps, the complete bracket-checking algorithm, so that it gives the correct result for every formula, including those in part (d).

    5 marks

The markschemeCheck this one with a free account
Question 5 · CS-00937Paper 2 · 12 marks

A restaurant kitchen keeps two queues of orders: dine for customers at tables and deliv for delivery orders. To keep table customers happy, the chef uses this rule: take two orders from dine, then one order from deliv, and repeat. Whenever the queue the rule asks for is empty, the chef takes from the other queue instead.

Queue

Front → rear

dine

D1, D2, D3, D4, D5

deliv

V1, V2, V3

  1. (a)

    State the operation the chef uses to see which delivery order is next without removing it.

    1 mark

  2. (b)

    State the order in which the chef cooks all eight orders.

    3 marks

  3. (c)

    Describe, in steps, the chef's rule as an algorithm that works for any number of orders in each queue and stops when both queues are empty.

    5 marks

  4. (d)

    State the order in which the orders are cooked if dine is empty and deliv holds V7, V8, V9.

    1 mark

  5. (e)

    On Friday evenings dine almost never empties. Explain one problem this rule causes for delivery customers.

    2 marks

The markschemeCheck this one with a free account
Question 6 · CS-00938Paper 2 · 13 marks

A web browser uses two stacks, back and forward, and a variable current holding the page being shown. The rules are:

  • Visit a new page: push current onto back, empty forward, set current to the new page.

  • Back: push current onto forward, then pop back into current.

  • Forward: push current onto back, then pop forward into current.

At the start current is Home and both stacks are empty.

  1. (a)

    Outline why a stack is suitable for the back history.

    2 marks

  2. (b)

    Copy and complete the trace table for these actions. Show stacks from bottom to top.

    Action

    current

    back

    forward

    (start)

    Home

    (empty)

    (empty)

    Visit News

    Visit Sport

    Visit Weather

    Back

    Back

    Visit Shop

    Back

    Forward

    5 marks

  3. (c)

    Explain why forward is emptied when a new page is visited.

    2 marks

  4. (d)

    Describe what the browser must do when the user presses Back and back is empty.

    2 marks

  5. (e)

    The browser should keep only the 50 most recent pages in back. Outline why this is awkward to do using only the stack operations.

    2 marks

The markschemeCheck this one with a free account

Practice all 211 in Augment

Free with an account. Every question has its markscheme, and Augment keeps the ones you got wrong so you can come back to them.

Start freeLog in

The notes on B2.2 Data structures

More questions in Programming

  1. B2.1Programming fundamentals
  2. B2.2Data structuresThis page
  3. B2.3Programming constructs
  4. B2.4Programming algorithms
  5. B2.5File processing

Check your answers in Augment

A free account opens all 211 questions on Data structures with their markschemes, and keeps a record of what you have marked.

Start free