Data Rep Flashcards
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.
What data structure does Breadth-First Search use?
Breadth-first traversal uses a queue.
On what type of graph does Breadth-First Search work?
This algorithm will work on any connected graph.
What is a key use of Breadth-First Search?
Breadth-first traversal is useful for determining the shortest path on an unweighted graph.
What is in-order traversal?
In-order traversal is a method used for binary trees.
What is the main use of in-order traversal?
It is useful for a binary search tree and outputs the contents in ascending order.
Can in-order traversal be performed on any type of tree?
No, it can only be performed on binary trees.
What is Post-Order Traversal?
Post-order traversals can be performed on any tree.
What are the uses of Post-Order Traversal?
They are useful for Infix to RPN (Reverse Polish Notation) conversions, producing a postfix expression from an expression tree, and emptying a tree.
What is the first step in a pre-order traversal of a tree?
The first step is to mark the left hand side of each leaf.
