Skip to content
MarkSchemeMarkScheme
Sign up — no card

9618 · 10.4

Introduction to Abstract Data Types (ADT) — practice questions

Practice and worked examples for 9618 Introduction to Abstract Data Types (ADT). Short previews only — attempt the full question in MarkScheme against the official scheme.

Worked example 1

A music streaming service uses a playlist feature. Users can add a song to the end of the playlist, remove the currently playing song from the start, and see which song is next. Describe this playlist feature as an Abstract Data Type, specifying the data and the necessary operations.

Show solution outline

The playlist can be described as a Queue ADT.

Data: A collection of songs, where each song has a title and artist. The collection is ordered based on insertion time. [1 mark]

Operations:

  • ENQUEUE(song): Adds a new song to the rear (end) of the queue/playlist. [1 mark]
  • DEQUEUE(): Removes the song from the front of the queue/playlist (the one that has been there the longest). [1 mark]
  • PEEK() or FRONT(): Returns the song at the front of the queue without removing it. [1 mark]
  • isEmpty(): Returns TRUE if the queue/playlist contains no songs, otherwise FALSE. [1 mark]

(Note: The description correctly identifies the ADT and its operations without mentioning arrays or linked lists).

Worked example 2

A programmer has implemented a data type using a fixed-size array and a top pointer. The interface provides three procedures: Push(item), Pop(), and IsEmpty(). Identify the ADT being implemented and explain how the choice of data structure imposes a limitation.

Show solution outline

Identification: The ADT being implemented is a Stack. [1 mark] The operations Push (adding to the top) and Pop (removing from the top) are characteristic of a Last-In, First-Out (LIFO) structure, which is the definition of a stack. [1 mark]

Limitation: The implementation uses a fixed-size array, which is a static data structure. [1 mark] This imposes a limitation on the stack's capacity. If the number of items pushed onto the stack exceeds the size of the array, a stack overflow error will occur. The stack cannot grow dynamically to accommodate more data than was initially allocated. [1 mark]

Mark a 9618 question on this topicFull lessonOpen in course studio