1.4.2 Data structures Flashcards
Describe a primitive data type
A data type which is assigned to a variable used to hold a single piece of data
Describe a composite or compound data type
A data type which is assigned to a variable used to hold multiple related pieces of data
Describe an abstract data type
A conceptual model that describes how data is stored and which operations can be carried out on them
Describe what a data structure is
The implementation of an abstract data type in a program
Explain what a static data structure is
A set amount of memory locations / size to store data
Explain what a dynamic data structure is
Can group data, while also being able to grow in size
What is an array data structure?
A data type that holds data that are usually related. It has a fixed size that cannot be changed during running.
What is a tuple data structure?
A data structure that cannot mutate, which contains multiple constants
Describe a list data structure
A dynamic array
Describe a record data structure
A data structure which allows you to make your own data type consisting of different fields
Describe a linked list data structure
A list data structure which stores data in the next free space, and links them together with pointers
What is a node, for a linked list, and what does it contain?
An individual element of the linked list
Contains the data item and the next address location
What are some advantages of a linked list?
- Flexible structure - pointers can be changed to shape the ordering system
- Can easily remove nodes, as very few pointers need to be changed
What are some disadvantages of a linked list?
- Slow to check through as it must be started at the beginning and then worked through
- Hard to update with new nodes, as all previous nodes have to be checked and pointers moved to add the new item
- Hard to find a specific item, as every node has to be gone through to find it
- More storage space is required since the pointers also have to be stored
Describe a linear queue data structure
FIFO. Pointers point to the start of the queue where items are removed, and to the end where items are added
Describe a circular queue data structure
Functions the same as a linear queue, except it reuses the empty spaces at the front of the queue
What is the advantage of a circular queue over a linear queue?
After elements are removed, the circular queue can reuse the space left behind
Describe a priority queue structure
Each element has a priority value alongside the data, and it is all stored in priority order. This is similar to an ordered linked list.
A new element is added according to its priority value, and the highest priority element is removed first
Describe a stack data structure
LIFO. The last item to be added to the stack is the first item to be removed.
What is the purpose of the peek() operation?
Returns the item at the top of a stack without removing it
What is the purpose of the push() operation?
Adds an element to the top of the stack
What is the purpose of the pop() operation?
Removes an element from the top of a stack
Describe a tree data structure
A hierarchical structure of data, stored as nodes, with parent nodes branching into children nodes.
Define a node in a tree data structure
A unit for data, containing: a sub-tree pointer, the node’s data, and pointers to other nodes on the same level
Define a parent and child for a tree data structure
Parent: the predecessor node to branching nodes
Child: a node branching from a predeceasing node
Describe a binary search tree data structure
A dynamic data structure, which can change size during program running. It can have only 0, 1 or 2 branches from each node
What is an advantage of binary search trees over standard root search trees?
Binary trees take a shorter time to search for a particular item than a rooted tree
What are the 3 methods of traversing a binary tree?
Preorder traversal
Inorder traversal
Postorder traversal
What are the features of a preorder traversal?
Is a ‘top down’ method
Can be used to duplicate the data to create an identical binary tree
Describe a preorder traversal
Pointers are to the left of the node
- Root visited first
- Traverses left sub-tree
- Traverses right sub-tree
What are the features of an inorder traversal?
Outputs the data in ascending order
Describe an inorder traversal
Pointers below the nodes
- Traverses the left sub-tree
- Visits the root
- Traverses the right sub-tree
What are the features of a postorder traversal?
A ‘bottom up’ method
Used if data needs to be deleted from the tree
Describe a postorder traversal
Pointers to the right of the node
- Traverses left sub-tree
- Traverses right sub-tree
- Visits the root
What is a hash table?
An array structure with an associated hash function
What is the process of hashing?
When the data being stored (the key) is inserted into the hashing function and a hash value is output
The hash value relates to a specific location in the hash table
What are two applications of hashing?
Speeding up data retrieval
Checking validity of data
How would you search for a particular record in a hash table?
The record would be inserted into the hashing function, and then the output is the location in which you need to search
How is hashing used to check the validity of data?
If data is sent to a new location, the hash value is sent too
Once the data arrives, the hash function is carried out again, and if the new and old hash values don’t match, then the data is invalid
What is the advantage of a hash table when locating a record in a file?
Using the hash function means there will be only one location outputted that needs to be searched
What are 3 features of a good hash algorithm?
- Generates a uniform spread of unique indexes to avoid collisions
- Produces hash values quickly, thus being fast
- Is complex, thus reducing the chance of collisions, with unique hash values
What is a collision in the context of hashing?
A collision occurs when the hash function produces the same hash value for different keys, thus giving the same memory location in the hash table to both keys
What are two methods of dealing with collisions in the context of hashing?
Open addressing (closed hashing): inserts a colliding key into the next available memory location, known as rehashing
Closed addressing (open hashing): apply a linked list to a memory location where a collision occurs. This is an overflow list, which holds all subsequent keys which collide with the data already stored in this location
What are some uses of hashing?
Searching a database: can quickly find data in a database
Sending files: used to validate the data sent
Storing passwords safely: hashes the user’s password before storing it
Describe the structure of a graph
A graph is composed of multiple vertices, each connected to others by edges
Describe the difference between a directed and undirected graph
Directed graph: the edges have a direction, the way of travel
Undirected graph: no specific direction on an edge
Describe the difference between a weighted and unweighted graph
Weighted: has weights/costs marked on each edge
Unweighted: has no additional edge values
How can an adjacency matrix be used to store a graph?
How can a list be used to store a graph?
How can a dictionary be used to store a graph?
How can ordered pairs be used to store a graph?
