2. Fundamentals of Data Structures Flashcards
What is an Array?
An Array is an ordered Data Structure which allows multiple values to be stored in a single Variable. Arrays are Static Data Structures, which means they are fixed in size when created. Arrays are highly efficient both in time (O(1)) and space.
What is a Record?
A Record is a Data Structure which allows a programmer to store related values together as named Attributes.
What is the difference between a Text File and a Binary File?
A Text File is encoded using either ASCII or Unicode. For example an integer would be encoded as the character values of each digit, rather than the Binary representation of the number itself. A Binary File will use the native Data Type representation to store information in a file. Binary Files are typically smaller than Text Files, but are difficult for a human to read.
What is an Abstract Data Type?
An Abstract Data Type describes the behaviour of a Data Structure, but not how that behaviour is implemented.
What is the difference between a Static and Dynamic Data Structure?
A Static Data Structure is fixed in size or capacity when it is created, whereas a Dynamic Data Structure can increase in size to fit whatever Data is inserted.
What kind of Data Structure is described as First In First Out (FIFO), and what behaviours does it have?
A Queue is First In First Out, the data is removed from a Queue in the same order as it is added.
Data can be Enqueued, inserting at the rear of the Queue.
Data can be Dequeued, removing it from the front of the Queue.
Why is a Circular Queue preferable to a Linear Queue?
A Linear Queue is slow to Dequeue (O(n)) because all the data items must be shifted forwards. However, a Circular Queue uses two pointers to implement Dequeue faster (O(1)).
How do Priority Queues differ from Normal Queues.
Each inserted item into a Priority Queue has an associated Priority value. Items with higher Priority will be inserted ahead of items with lower Priority. So a Priority Queue is only First In First Out for items of equal Priority.
How is a List different from an Array?
An Array is a Static Data Structure, fixed in size when it is created. A List can change in size to fit the contained data. Both are ordered and indexed Data Structures. Depending upon implementation operations on a List may be slower than for an Array.
What operations can be applied to a List?
Append - add an item to the end of the List.
Prepend - add an item to the front of the List.
Insert - add an item in the middle of the List.
Delete - remove an item from the List.
What kind of Data Structure is Last In First Out (LIFO), and what behaviours does it have?
A Stack is Last In First Out, data is added to the top of the Stack and also removed from the top. Data will be removed in the reverse order to which it is added.
Data can be Pushed onto the top of the Stack.
Data can be Popped from the top of the Stack.
What is a Stack Overflow? What is a Stack Underflow?
A Stack Overflow is when there is not enough space left in the Stack to store a new item.
A Stack Underflow is when there is no item to remove from a Stack.
What operation are Hash Tables optimised to perform? Why are they good at this?
Hash Tables are quick to search (O(1)). This is because they are indexed using a Hash Function, which means you can quickly find where a value should be stored in the underlying Data Structure.
What causes Hash Tables to lose performance?
Hash Tables lose performance when they are too full. This is because as the Hash Table fills up you get more Collisions between stored values. Collisions mean that a value cannot be stored directly where the Hash Function indicates, and a Linear Search will be required to determine if a value is in the Hash Table.
Identify the main differences between a Graph and a Tree.
A Tree has a single root node, it is undirected, and has no labels or cycles.
A Graph may be directed, edges may have labels, and it may have cycles.
