SubjectScout
ENAR
Sign inGet matched
Get matched

Constructing linked structures and bounded queues

Start questions

AI-assisted English content review; independent teacher approval pending.

Practice scope and review

Original, AI-authored English practice with worked guidance. Selected topics only; independent teacher review is pending. This is not a complete syllabus, official past-paper collection or predicted exam score. Check your own exam-board specification: these concepts are not certified against a particular board or exam year.

151 original questions across 21 selected topic areas. No account or payment required to practise.

Cambridge International AS & A Level Computer Science (9618), examination year 2027: AI-assisted conceptual alignment to official sources, not teacher or exam-board certification. Syllabus mapping and remaining coverage.

5 questions in this topic

Exact English revisions checked in an AI-assisted academic review; independent teacher approval is still pending.

All topics

Original English exercises targeting selected 9618 2027-29 requirements. Conceptual alignment only; independent teacher approval, practical competence and complete teaching coverage are not established.

Subtopics in this topic (3)
  • Array-linked nodes
  • Binary-tree ordering
  • Circular-queue overflow and underflow

5 of 5 questions shown

Loading saved responses

Question 1A singly linked list is stored in parallel arrays Data[0:3], Next[0:3]. Head=0; Data[0]=10,Next[0]=2; Data[2]=30,Next[2]=-1; slot1 is free. Insert20 in sorted order using slot1, showing assignments in safe order. Write pseudocode to search the resulting list for30, returning its array slot or-1, without assuming consecutive occupied slots. Separately insert10,6,14,8 into an empty binary search tree and state its inorder traversal.6 indicative marks
Construct, trace and explain6 indicative marksNo calculator

A singly linked list is stored in parallel arrays Data[0:3], Next[0:3]. Head=0; Data[0]=10,Next[0]=2; Data[2]=30,Next[2]=-1; slot1 is free. Insert20 in sorted order using slot1, showing assignments in safe order. Write pseudocode to search the resulting list for30, returning its array slot or-1, without assuming consecutive occupied slots. Separately insert10,6,14,8 into an empty binary search tree and state its inorder traversal.

Show indicative guidance

Worked guidance

  1. Data[1] <- 20
Next[1] <- Next[0]
Next[0] <- 1
DECLARE Current : INTEGER
DECLARE Result : INTEGER
Current <- Head
Result <- -1
WHILE Current <> -1
   IF Data[Current] = 30 THEN
      Result <- Current
      Current <- -1
   ELSE
      Current <- Next[Current]
   ENDIF
ENDWHILE
OUTPUT Result
  2. Save the successor into the new node first; setting Next[0]=1 before reading its old value would lose the intended successor and could make a self-loop. The occupied slots need not be consecutive: following links finds10 at0,20 at1,30 at2 and returns2. Missing targets eventually reach sentinel-1 without accessing Data[-1].
  3. For the separate BST, the comparison path for8 is10(left),6(right), giving nodes10 with left6/right14 and6 with right8. Inorder visits left subtree, root, right subtree and yields6,8,10,14. This is selected list implementation and tree insertion reasoning, not full linked-list/tree deletion coverage.

Self-marking points

View marking points
  1. Set Data[1]=20 and Next[1]=2 before changing the existing link.
  2. Set Next[0]=1, preserving Head0 and final chain0->1->2->-1.
  3. Search begins at Head and follows Next rather than incrementing a position through memory.
  4. Check current=-1 before accessing Data; search30 visits0,1,2 and returns2.
  5. BST places6 left of10,14 right of10,8 right of6.
  6. Inorder traversal is6,8,10,14; linked-list order is10,20,30.

Examiner tip

Indicative distinct points, not an official Cambridge mark allocation. State bounds, assumptions and intermediate states; practical teacher review remains required.

Question 2Implement a circular queue with global Q[0:2], Front=0, Rear=0 (next insertion slot), Count=0. Write Enqueue(BYVAL Value:INTEGER,BYREF Ok:BOOLEAN) and Dequeue(BYREF Value:INTEGER,BYREF Ok:BOOLEAN), rejecting full/empty operations without changing queue state; Dequeue must leave Value unchanged on failure. Trace enqueue10, enqueue20, dequeue, enqueue30, enqueue40, enqueue50. Give logical queue, pointers/count and which operations fail. Use procedures rather than BYREF function parameters.6 indicative marks
Construct, trace and explain6 indicative marksNo calculator

Implement a circular queue with global Q[0:2], Front=0, Rear=0 (next insertion slot), Count=0. Write Enqueue(BYVAL Value:INTEGER,BYREF Ok:BOOLEAN) and Dequeue(BYREF Value:INTEGER,BYREF Ok:BOOLEAN), rejecting full/empty operations without changing queue state; Dequeue must leave Value unchanged on failure. Trace enqueue10, enqueue20, dequeue, enqueue30, enqueue40, enqueue50. Give logical queue, pointers/count and which operations fail. Use procedures rather than BYREF function parameters.

Show indicative guidance

Worked guidance

  1. PROCEDURE Enqueue(BYVAL Value : INTEGER, BYREF Ok : BOOLEAN)
   Ok <- FALSE
   IF Count < 3 THEN
      Q[Rear] <- Value
      Rear <- (Rear + 1) MOD 3
      Count <- Count + 1
      Ok <- TRUE
   ENDIF
ENDPROCEDURE
PROCEDURE Dequeue(BYREF Value : INTEGER, BYREF Ok : BOOLEAN)
   Ok <- FALSE
   IF Count > 0 THEN
      Value <- Q[Front]
      Front <- (Front + 1) MOD 3
      Count <- Count - 1
      Ok <- TRUE
   ENDIF
ENDPROCEDURE
  2. State after enqueue10 is(F0,R1,C1); after20,(F0,R2,C2); dequeue returns10 and gives(F1,R2,C1). Enqueue30 wraps Rear to0 with Count2; enqueue40 wraps it to1 with Count3. Logical FIFO order is20 at1,30 at2,40 at0. Enqueue50 reportsFALSE and changes nothing.
  3. Dequeue three more times returns20,30,40 and reaches(F1,R1,C0). A further dequeue sets OkFALSE without reading Q or changing Value. Initialising OkFALSE on every call prevents a stale TRUE result from an earlier success. The guide permits BYREF procedure parameters but says functions should not receive BYREF parameters.

Self-marking points

View marking points
  1. Enqueue checks Count<3 before writing; otherwise sets Ok=FALSE without state mutation.
  2. Successful enqueue writes at Rear, advances(Rear+1) MOD3 and increments Count.
  3. Dequeue checks Count>0 before reading; failure leaves Value and queue state unchanged.
  4. Successful dequeue reads at Front, advances(Front+1) MOD3 and decrements Count.
  5. The first dequeue returns10; final logical queue is20,30,40 with Front1,Rear1,Count3.
  6. Enqueue50 fails; equal Front/Rear alone cannot distinguish full from empty, so Count matters.

Examiner tip

Indicative distinct points, not an official Cambridge mark allocation. State bounds, assumptions and intermediate states; practical teacher review remains required.

Question 3A stack S[1:2] has Top=0; Push rejects if Top=2, otherwise increments Top then stores. Pop rejects if Top=0, otherwise returns S[Top] then decrements Top. Failed operations leave state unchanged. Trace Push(4),Push(7),Push(9),Pop(),Pop(),Pop(); give outcomes and final Top. Write safe Pop pseudocode with BYREF Value unchanged on failure.4 indicative marks
Analyse4 indicative marksNo calculator

A stack S[1:2] has Top=0; Push rejects if Top=2, otherwise increments Top then stores. Pop rejects if Top=0, otherwise returns S[Top] then decrements Top. Failed operations leave state unchanged. Trace Push(4),Push(7),Push(9),Pop(),Pop(),Pop(); give outcomes and final Top. Write safe Pop pseudocode with BYREF Value unchanged on failure.

Cambridge 2027: Direct conceptual match

Simulated capacity2 push success/success/failure and LIFO7/4/empty; separately checked failed-pop sentinel unchanged.

AI-assisted placement. Independent teacher approval pending.

Show indicative guidance

Worked guidance

  1. The successful pushes fill slots1 and2 with4 and7. The capacity check rejects9, retaining both entries.
  2. PROCEDURE Pop(BYREF Value : INTEGER, BYREF Ok : BOOLEAN)
   Ok <- FALSE
   IF Top > 0 THEN
      Value <- S[Top]
      Top <- Top - 1
      Ok <- TRUE
   ENDIF
ENDPROCEDURE
  3. The returns are7 then4, leaving Top0. A further call reports failure and does not read index0 or overwrite the caller's Value; stale array cells beyond Top are not logical stack members.

Self-marking points

View marking points
  1. First two pushes succeed and Push9 fails.
  2. Pops return7 then4; final pop fails; Top=0.
  3. Checks empty before reading or decrementing.
  4. Failure sets Ok FALSE without changing Value or Top.

Examiner tip

Check capacity/emptiness before modifying pointers.

Question 4A linked list uses Head=2, Data[2]=10,Next[2]=0,Data[0]=20,Next[0]=-1; slot1 is already free. Delete the head, adding its slot to a free-list with Free=1 and Next[1]=-1. Show safe pseudocode, resulting Head/Free/Next[2], and the values visited when traversing the live list. Explain why updating Next[2] too early loses the successor.4 indicative marks
Analyse4 indicative marksNo calculator

A linked list uses Head=2, Data[2]=10,Next[2]=0,Data[0]=20,Next[0]=-1; slot1 is already free. Delete the head, adding its slot to a free-list with Free=1 and Next[1]=-1. Show safe pseudocode, resulting Head/Free/Next[2], and the values visited when traversing the live list. Explain why updating Next[2] too early loses the successor.

Cambridge 2027: Direct conceptual match

Checked disjoint live{0}/free{2,1}, safe assignment order and one-element remainder; nonempty initial state explicitly supplied.

AI-assisted placement. Independent teacher approval pending.

Show indicative guidance

Worked guidance

  1. OldHead <- Head
Head <- Next[OldHead]
Next[OldHead] <- Free
Free <- OldHead
  2. The old head is slot2 and its saved live successor is0. Recycling2 then links it to the existing free chain1, so Head=0, Free=2, Next[2]=1.
  3. Following the live list visits Data[0]=20 then-1. The recycled chain is2->1->-1; it must not be confused with live data, and overwriting Next[2] before advancing Head would substitute a free slot for the successor.

Self-marking points

View marking points
  1. Saves OldHead and advances Head to its former successor0.
  2. Links freed slot2 to former Free1 and makes Free2.
  3. Results Head0,Free2,Next[2]=1; live traversal is20 only.
  4. Recycling Next[2] before reading its live successor loses pointer0.

Examiner tip

A pointer cell can serve the live chain or free chain, not both at once.

Question 5A finite acyclic binary tree has root8, left child3, right child10; node3 has right child6, and all other children are NULL. TreePointer is a supplied pointer type to a node record whose Left and Right fields are TreePointer values. Every pointer is NULL or points to a valid node. For a non-NULL pointer Node, Node.Left and Node.Right mean the child fields of the record it points to; never access these fields through NULL. Define CountLeaves(Node) recursively: NULL contributes0, a node with no children contributes1, otherwise sum the child results. Give pseudocode, trace the root result and test an empty tree and a single-node tree.4 indicative marks
Analyse4 indicative marksNo calculator

A finite acyclic binary tree has root8, left child3, right child10; node3 has right child6, and all other children are NULL. TreePointer is a supplied pointer type to a node record whose Left and Right fields are TreePointer values. Every pointer is NULL or points to a valid node. For a non-NULL pointer Node, Node.Left and Node.Right mean the child fields of the record it points to; never access these fields through NULL. Define CountLeaves(Node) recursively: NULL contributes0, a node with no children contributes1, otherwise sum the child results. Give pseudocode, trace the root result and test an empty tree and a single-node tree.

Cambridge 2027: Direct conceptual match

Checked recursive leaf counts on empty0, singleton1, supplied four-node tree2; finite acyclic valid-pointer precondition ensures termination, with record-field access explicitly defined and guarded against NULL.

AI-assisted placement. Independent teacher approval pending.

Show indicative guidance

Worked guidance

  1. FUNCTION CountLeaves(Node : TreePointer) RETURNS INTEGER
   IF Node = NULL THEN
      RETURN 0
   ENDIF
   IF Node.Left = NULL AND Node.Right = NULL THEN
      RETURN 1
   ENDIF
   RETURN CountLeaves(Node.Left) + CountLeaves(Node.Right)
ENDFUNCTION
  2. Leaves6 and10 each contribute1. Node3 has a missing left branch contributing0 and right leaf6 contributing1; root8 therefore sums1+1=2.
  3. For NULL the result is0 without accessing fields; for a singleton the leaf test returns1. Counting every non-null node instead would return4 here and answer a different question. Node is a supplied pointer to a record with Left/Right fields.

Self-marking points

View marking points
  1. NULL base case returns0.
  2. A childless non-null node returns1.
  3. Internal node returns sum of recursive child counts.
  4. Root8 returns2; empty returns0 and singleton1.

Examiner tip

Handle NULL before dereferencing a node's fields.

All AS & A Level subjects