1.5 Abstract data types Flashcards
What is an abstract data type (ADT)?
A data type described by predefined user operations without indicating how each operation is implemented.
Can an ADT be implemented using different underlying data structures?
Yes.
What is an example of a common ADT for holding ordered data?
List.
What operations does a list ADT commonly support?
- Append a data item
- Remove a data item
- Search for a data item
- Print the list.
What are the two common data structures used to implement a list ADT?
- Arrays
- Linked lists.
True or False: A programmer must know the underlying implementation of the list ADT to use it.
False.
What is the result of appending 11, 4, and 7 to an empty list in order?
11, 4, 7.
What happens when the item 2 is removed from the list containing 2, 20, 30?
20, 30.
What type of ADT is a stack?
An ADT in which items are only inserted on or removed from the top.
What is a deque?
An ADT where items can be inserted and removed at both the front and back.
What is a bag ADT?
An ADT for storing items where order does not matter and duplicates are allowed.
What is the underlying data structure for a priority queue?
Heap.
Fill in the blank: A __________ is an ADT that associates keys with values.
Dictionary (Map).
How does a priority queue order its items?
Based on items’ priority.
What is the characteristic of a set ADT regarding items?
Items are not ordered and duplicates are not allowed.
What is the result of the Print operation on a list ADT containing 55, 88, and 66?
55, 88, 66.
True or False: Different underlying data structures require different algorithms for the same list ADT operation.
True.
What is the length of the agesList after appending three items?
3.
