4.2 Fundamentals of data structures Flashcards
(29 cards)
What is an array
an indexed set of related elements, they are finite and can only contain one data type
what is a one-dimensional and two-dimensional array useful for
1D is useful to store vectors
2D is useful to store a matrix
what are the python commands to read/write to files
open: file_object = open(“filename”, “a”)
where a is append mode, w is write mode and r is read more
read: file_object.read()
write: file_object.write(“”)
close: file_object.close()
What are static structures
they have a fixed size so they are declared in memory as a series of sequential contiguous memory locations - if a data item exceeds the number in the static structure an overflow error will occur
What are dynamic structures
they change in size to store content so they are stored in memory with references to where the next item is stored - new data items can be added but required more work for computer to set up and use
what are the uses of a queue
the breadth first search algorithm uses a queue to track which nodes have been visited
also queues are used by keyboard buffers so letters are typed in the order clicked
compare advantages and disadvantages of static and dynamic structures
Static structures are simple to implement and provides fast access to elements, but they can be inefficient as memory may be wasted if the structure is too large, or it may be unable to store all required data if too small
Dynamic structures are more flexible and efficient in terms of memory usage, but they are more complex to manage, can be slower to access due to the use of pointers and may lead to fragmentation or memory leaks if not handled correctly.
what structure is a queue
a first in first out structure so it has two pointers, one at the front and one at the rear - the rear pointer is used to identify where to place new items and the front pointer is used to identify the items to return first
why using a circular queue is more efficient than a linear queue
a circular queue is more efficient because it reuses empty spaces left by dequeued elements. In a linear queue, once the rear reaches the end, no more elements can be added even if there is space at the front. A circular queue solves this by wrapping around, making better use of memory and avoiding the need to shift elements.
what is a graph
graphs are data structures used to represent more complex relationships - they consist of nodes which are joined by edges
what are typical uses for graphs
Social networks – representing users as nodes and friendships as edges
Routing and navigation – cities or locations as nodes, roads as edges
Network topology – devices as nodes, connections as edges
what is a weighted graph
A weighted graph is a graph where each edge has a numerical value representing things like cost, distance, or time
what are nodes and edges
nodes represent individual entities whereas edges are the connections between nodes, showing relationships
what is the difference between a directed and undirected graph
In a directed graph, edges have a direction so the relationship is one-way whereas in an undirected graph, edges have no direction representing a two-way relationship.
how is an adjacency matrix used to represent graph
uses a 2d array, where each row and column corresponds to a node, if there is an edge between two nodes, the matrix cell at that row and column is set to 1 (or the weight if it’s a weighted graph) otherwise, it is 0. In a directed graph, the direction is shown by which side of the matrix the value is on.
how is an adjacency list used to represent graph
An adjacency list represents a graph by storing a list of nodes, where each node has its own list of adjacent nodes.
when to use adjacency list or adjacency matrix
Use an adjacency list when the graph is sparse (few edges) - it’s more space-efficient and faster to iterate over neighbors.
Use an adjacency matrix when the graph is dense (many edges) or when you need to check if an edge exists quickly
what is a tree
a connected, undirected graph with no cycles
what is a rooted tree
a type of tree data structure where one node is designated as the root, and all other nodes are connected by a single path from the root. It has a hierarchical structure, with parent-child relationships between nodes
what is a binary tree and a common application
a rooted tree in which each node has at most two children - common application is a binary search tree
what is a hash table
a data structure that stores key-value pairs, it uses a hash function to compute an index (hash code) in an array, where the corresponding value is stored
what are the uses of hash tables
Hash tables are used for fast data lookup, such as in dictionaries, caches, database indexing, symbol tables, and for tasks like counting frequencies or ensuring unique items in sets
what is a hashing algorithm
takes an input and outputs a hash, a hash is unique to the input and cannot be reversed
what is meant by a collision in a hash table
A collision in a hash table occurs when two different keys produce the same hash index, meaning they try to store data in the same location
