[Custom] Data Structures (old)

Question 1

Describe arrays.

Answer 1

• An ordered, finite set of elements of a single data type

* Always zero-indexed unless stated otherwise

Question 2

What are 1D arrays considered to be?

Answer 2

Linear arrays

Question 3

2D ARRAYS
How can they be visualized?
How do you search across them?

Answer 3

• 2D arrays can be visualized as a table or spreadsheet

* When searching through them, go down the rows then across the columns to find a given position.

Question 4

3D ARRAYS
How can they be visualized?
How do you search across them?

Answer 4

• 3D arrays can be visualized as a multi-page spreadsheet, or as multiple 2D arrays
• The three dimensions are used [z,y,x]. Z is the array number, y is the row number, x is the column number

Question 5

Describe records.
How are they used?
How can its attributes be identified?

Answer 5

• A row in a file that is made up of fields. They are used in databases.
• The fields can be identified by recordName.fieldName

Question 6

Describe lists.
In what way are the elements accessed?
How are the values stored?
What kind of elements can lists contain?

Answer 6

• A list is a data structure consisting of a number of ordered items where the items can occur more than once.
• Elements can be accessed in the same way as a 1D array.
• List values are stored non-contiguously (not next to each other in memory, unlike arrays)
• Lists can contain elements of more than one data type, unlike arrays.

Question 7

Describe tuples.
What is different about tuples?
What brackets are used to initialize them?
In what way are the elements accessed?

Answer 7

• An ordered set of values of any data type.
• Tuples are immutable, meaning they cannot be changed during runtime. Elements cannot be added or removed.
• Tuples are initialized using regular brackets instead of squares.
• Values within can be accessed in a way similar to arrays, with the exception of changing the value.

Question 8

Describe static and dynamic data structures

Answer 8

Static
• Structure size cannot change at runtime

Dynamic
• Structure size can change at runtime

Question 9

Describe mutable and immutable

Answer 9

Immutable
• Structure/data cannot be changed at runtime
Mutable
• Structure/data can be changed at runtime

Question 10

Describe stacks.

Answer 10

• A stack is a Last in First out (LIFO) data structure.
• Items can only be added or removed from the top.
• Can be implemented as static or dynamic
• Static is preferred (easier to implement, more efficient memory use)
• Top pointer

Question 11

Describe queues.

Answer 11

• A queue is a First in First out (FIFO) data structure

* Items are added to the end and removed from the front

Question 12

Describe LINEAR queues.
How are items added and removed?
What is an issue with linear queues?

Answer 12

• A data structure consisting of an array
• Items added onto the next available space in the queue, starting from the front.
• Items removed from the front of the queue
• Front Pointer (where items are removed) and Back Pointer (where items are added)
• Enqueue –> Add to a queue
• Dequeue –> Remove from a queue

• As the queue removes items, there are addresses in the array which cannot be used again, making linear queues an ineffective implementation of a queue.

Question 13

Describe CIRCULAR queues.

Answer 13

• Similar to linear (also FIFO)
• Once the queue’s rear pointer is equal to the max size of the queue, it can loop back to the front of the array and store values here, provided it is empty.
• Harder to implement, but uses space in an array more effectively.