Abstract Data Types - Test me

An ADT is best described as:

• the exact code used to store data

• a high-level description of data and allowed operations

• a sorting algorithm

• a programming language

Which pair is the best example of ADT → implementation?

• HashMap → Key-value ADT

• Stack ADT → Array-based stack

• BSTNode → BST ADT

• ArrayList → Queue ADT

Why can ADTs improve maintainability?

• They automatically make programs faster

• They allow implementation changes without changing how the structure is used

• They remove the need for testing

• They prevent all errors

In a singly linked list, each node stores:

• data only

• data + index

• data + reference to next node

• data + references to prev and next nodes

In a doubly linked list, each node stores:

• next only

• prev only

• both prev and next

• neither prev nor next

A circular linked list is one where:

• the head is always null

• the last node points back to the head

• nodes are stored contiguously

• it cannot be traversed

Why is accessing the 500th element usually faster in an array than a linked list?

• arrays store duplicates

• arrays support direct indexing; linked lists require traversal

• linked lists are always sorted

• arrays are always smaller

Linked list advantage over arrays (best answer):

• direct random access

• insertion/deletion without shifting many elements

• always sorted

• uses no extra memory

Linked list disadvantage compared to arrays:

• cannot grow

• extra memory overhead for pointers/references

• cannot be traversed

• cannot store objects

Given: head -> 9 -> 12 -> 7 -> 4 -> null

After inserting 5 at the front, write the new list.

• head -> 5 -> 9 -> 4 -> 12 -> 7 -> null

• head -> 5 -> 9 -> 12 -> 7 -> 4 -> null

• head -> 5 -> 12 -> 9 -> 7 -> 4 -> null

• head -> 5 -> 4 -> 7 -> 12 -> 9 -> null