Data Rep Flashcards
(33 cards)
What is a Hash Table?
A data structure where a hashing algorithm creates a mapping between keys and values.
How can data items in a Hash Table be accessed?
By recalculation, without any search.
What is the defining characteristic of a Queue?
A first-in-first-out (FIFO) data structure.
In a Queue, what happens to the first item added?
It is the first to be removed.
What is the defining characteristic of a Stack?
A last-in-first-out (LIFO) data structure.
In a Stack, what happens to the last item added?
It is the first to be removed.
What is a Static Structure?
A data structure that is allocated a fixed amount of memory space.
What is the purpose of Trees in data structures?
To form a hierarchical structure starting at a root node.
What is a Vector in data structures?
A data structure representing a quantity with both magnitude and direction.
What does the Peek/Top operation do in a Stack?
Allows the user to view the top element of the stack without modifying it.
What does the Pop operation do in a Stack?
Removes the most recently added element that was not yet removed.
What does the Push operation do in a Stack?
Adds an element to the top of the stack.
What is an Adjacency List in graph representation?
A representation that stores a list of connected nodes to each node.
What is an Adjacency Matrix?
A matrix representation of a graph that stores the edges connecting all possible nodes.
True or False: In Directed Graphs, the order of vertices paired in an edge does not matter.
False
What is an Edge/Arc in graph structures?
A connection that represents a relationship between two nodes.
What is the characteristic of Undirected Graphs?
The order of the vertices paired in an edge does not matter.
What does the term Vertex/Node refer to in a graph?
The representation of an object on a graph that is capable of being related to others.
Advantages off an adjacency matrix?
Stores every possible edge between nodes, even those that don’t exist. Almost half of the matrix is repeated data. Memory inefficient.
Allows a specific edge to be queried very quickly, as it can be looked up by its row and column.
Disadvantages of an adjacency list
Only stores the edges that exist in the graph. Memory efficient.
Slow to query, as each item in a list must be searched sequentially until the desired edge is found.
What is a tree in graph theory?
A tree is a connected, undirected graph with no cycles.
What data structure does depth-first traversal use?
Depth-first traversal uses a stack.
What is depth-first traversal commonly used for?
Depth-first traversal is used for navigating a maze.
Can a depth-first algorithm be performed on structures other than trees?
Yes, a depth-first algorithm can be performed on any connected graph.
