SLR 14 Flashcards
Data Structures
What is a data structure?
A way data can be stored in programming
What is a record
A collection of related fields
What number do indexes start at?
0
What does it mean if a data structure is static?
The size of the structure size can’t change during runtime
What does it mean if a data structure is dynamic?
The structure size can change during runtime
What does it mean if a data structure is mutable?
Data inside can be changed during runtime
What are the attributes of a list?
Dynamic
Mutable
Items are ordered
Can store more than one data type
What are the attributes of an array?
Static
Mutable
Ordered
Items can change
Only one data type
What are the attributes of a tuple?
Static
Immutable
Ordered
Items can’t be changed
More than 1 data type
What is a linked list?
A data structure that provides a foundation for other structures, made up of nodes and pointers that are used to link nodes
What is a graph?
A data structure that uses nodes and pointers similarly to a linked list, but also has vertices and edges
What is a Pre-Order Traversal?
Travels a graph from the left of a node
What is an in-order traversal?
Travels a graph from the bottom of a node
What is a post-order traversal?
Travels a graph from the right side of each node
What structure does a stack follow?
LIFO
Last in, first out
What does a stack do before any changes are made?
Checks if the stack is full if it is pushed onto the stack
Checks if the stack is empty if an item is to be popped
What are the attributes of a queue?
Linear
Items can be peeked at
Uses FIFO
Has a front and back pointer
What is a queue overflow?
Adding to a full queue
What is a queue underflow?
Taking from an empty queue
What is a circular queue?
A queue which cycles back to the start to avoid affecting frame rates
What are circular queues used for?
Process scheduling
Transferring data across processors l
Performing breadth-first searches
What is a tree?
A fundamental data structure that uses nodes and pointers, while also starting with a root node and having leaf nodes which branch off them
What is a binary tree?
A data structure similar to a tree but only has nodes with 0, 1 or 2 pointers connecting to a different node
Binary searches can be performed on these easily
What is a hash table?
A function that finds an item in a list without comparing it to other items in the data set
It determines a hash value for a value to find an item
How are collisions prevented in hash tables?
Every available space is checked until an empty one if found to store an item
You can also store an item in the same space twice in a 2 dimensional hash table. This is called chaining.
