Data Structures I

Question 1

What is the purpose of a data structure in C++?

Answer 1

To store data in useful ways, often beyond the built-in mechanisms (like arrays).

Question 2

What does the acronym ADT stand for, and what is it?

Answer 2

Abstract Data Type

Abstract data types, commonly abbreviated ADTs, are a way of classifying data structures based on how they are used and the behaviors they provide. They do not specify how the data structure must be implemented or laid out in memory, but simply provide a minimal expected interface and set of behaviors.

For example, a stack is an abstract data type that specifies a linear data structure with LIFO (last in, first out) behavior. Stacks are commonly implemented using arrays or linked lists, but a needlessly complicated implementation using a binary search tree is still a valid implementation. To be clear, it is incorrect to say that stacks are arrays or vice versa. An array can be used as a stack. Likewise, a stack can be implemented using an array.

Question 3

Name 6 types of ADTs.

Answer 3

1. sequence
2. set
3. stack
4. queue
5. vector
6. linked list

Question 4

What are the main advantages and disadvantages of arrays?

Answer 4

1. Random access: elements of the array can be accessed directly by their index.
2. Inserting data at the end of an array is very fast
3. Searching linearly through an array is inefficient
4. Inserting data at the beginning (or anywhere in the middle) of an array is inefficient because existing data has to be shifted to create a new space for the data to be inserted.

Question 5

What is a sequence?

Answer 5

A container that stores a sequence of data in a specific order, possibly with duplicates. An array is a specific example of a sequence.

Not all sequences are arrays!

Question 6

What is a set?

Answer 6

A collection of data that does not have any duplicates and order may or may not matter (like a venn diagram.) Something is either in the set or it isn’t in the set, and that’s it.