DATA STRUCTURES PRACTICE EXAM QUESTIONS
AND ANSWERS
/.(a,b)-tree - Answer-multiway tree data structure. a kind of balanced search tree. An
(a,b)-tree has all of its leaves at the same depth, and all internal nodes except for the
root have between a and b children, where a and b are integers such that 2 ≤ a ≤
(b+1)/2. The root has, if it is not a leaf, between 2 and b children.
/.2-3 heap - Answer-heap data structure. a data structure, a variation on the heap,
designed by Tadao Takaoka in 1999. The structure is similar to the Fibonacci heap, and
borrows from the 2-3 tree.
-Time costs for some common heap operations are:
1) Delete-min takes O(log(n)) amortized time.
2) Decrease-key takes constant amortized time.
3) Insertion takes constant amortized time.
/.2-3 tree - Answer-b-tree data structure. a tree data structure, where every node with
children (internal node) has either two children (2-node) and one data element or three
children (3-nodes) and two data elements. According to Knuth, "a B-tree of order 3 is a
2-3 tree." Nodes on the outside of the tree (leaf nodes) have no children and one or two
data elements.[1][2] 2−3 trees were invented by John Hopcroft in 1970
/.2-3-4 tree (also called a 2-4 tree) - Answer-b-tree data structure. a self-balancing data
structure that is commonly used to implement dictionaries.
-The numbers mean a tree where every node with children (internal node) has either
two, three, or four child nodes:
1) a 2-node has one data element, and if internal has two child nodes;
2) a 3-node has two data elements, and if internal has three child nodes;
3) a 4-node has three data elements, and if internal has four child nodes.
-2-3-4 trees are B-trees of order 4;[1] like B-trees in general, they can search, insert and
delete in O(log n) time. One property of a 2-3-4 tree is that all external nodes are at the
same depth.
-2-3-4 trees are an isometry of red-black trees, meaning that they are equivalent data
structures. In other words, for every 2-3-4 tree, there exists at least one red-black tree
with data elements in the same order. Moreover, insertion and deletion operations on 2-
3-4 trees that cause node expansions, splits and merges are equivalent to the color-
flipping and rotations in red-black trees. Introductions to red-black trees usually
introduce 2-3-4 trees first, because they are conceptually simpler. 2-3-4 trees, however,
can be difficult to implement in most programming languages because of the large
number of special cases involved in operations on the tree. Red-black trees are simpler
to implement,[2] so tend to be used instead.
,/.AA tree* - Answer-binary tree data structure. a form of balanced tree used for storing
and retrieving ordered data efficiently. AA trees are named for Arne Andersson, their
inventor.
-AA trees are a variation of the red-black tree, a form of binary search tree which
supports efficient addition and deletion of entries. Unlike red-black trees, red nodes on
an AA tree can only be added as a right subchild. In other words, no red node can be a
left sub-child. This results in the simulation of a 2-3 tree instead of a 2-3-4 tree, which
greatly simplifies the maintenance operations. The maintenance algorithms for a red-
black tree need to consider seven different shapes to properly balance the tree (see
image in wiki).
An AA tree on the other hand only needs to consider two shapes due to the strict
requirement that only right links can be red (see image in wiki).
-Balancing rotations:
-Whereas red-black trees require one bit of balancing metadata per node (the color), AA
trees require O(log(N)) bits of metadata per node, in the form of an integer "level". The
following invariants hold for AA trees:
1. The level of every leaf node is one.
2. The level of every left child is exactly one less than that of its parent.
3. The level of every right child is equal to or one less than that of its parent.
4. The level of every right grandchild is strictly less than that of its grandparent.
5. Every node of level greater than one has two children.
A link where the child's level is equal to that of its parent is called a horizontal link, and
is analogous to a red link in the red-black tree. Individual right horizontal links are
allowed, but consecutive ones are forbidden; all left horizontal links are forbidden.
These are more restrictive constraints than the analogous ones on red-black trees, with
the result that re-balancing an AA tree is procedurally mu
/.abstract data type (ADT) - Answer-a mathematical model of the data objects that make
up a data type as well as the functions that operate on these objects. a data type is
defined by its behavior (semantics), specifically in terms of possible values, possible
operations on data of this type, and the behavior of these operations. This contrasts
with data structures, which are concrete representations of data, and are the point of
view of an implementer, not a user.
Container
List
Associative array
Multimap
Set
Multiset
Stack
Queue
Double-ended queue
Priority queue
Tree
Graph
,/.Abstract syntax tree (AST, or just syntax tree) - Answer-Application-specific tree data
structure. a tree representation of the abstract syntactic structure of source code written
in a programming language. Each node of the tree denotes a construct occurring in the
source code. The syntax is "abstract" in not representing every detail appearing in the
real syntax. For instance, grouping parentheses are implicit in the tree structure, and a
syntactic construct like an if-condition-then expression may be denoted by means of a
single node with three branches.
-This distinguishes abstract syntax trees from concrete syntax trees, traditionally
designated parse trees, which are often[citation needed] built by a parser during the
source code translation and compiling process. Once built, additional information is
added to the AST by means of subsequent processing, e.g., contextual analysis.
-Abstract syntax trees are also used in program analysis and program transformation
systems.
/.Adaptive k-d tree - Answer-space partitioning or binary space partitioning data
structure. a tree for multidimensional points where successive levels may be split along
different dimensions.
/.Adjacency list - Answer-Graph data structure. a collection of unordered lists used to
represent a finite graph. Each list describes the set of neighbors of a vertex in the
graph. This is one of several commonly used representations of graphs for use in
computer programs.
|Data Structures|
For use as a data structure, the main alternative to the adjacency list is the adjacency
matrix. Because each entry in the adjacency matrix requires only one bit, it can be
represented in a very compact way, occupying only |V|^2/8 bytes of contiguous space,
where | V| is the number of vertices of the graph. Besides avoiding wasted space, this
compactness encourages locality of reference.
-However, for a sparse graph, adjacency lists require less space, because they do not
waste any space to represent edges that are not present. Using a naïve array
implementation on a 32-bit computer, an adjacency list for an undirected graph requires
about 2(32/8)| E| = 8| E| bytes of space, where | E| is the number of edges of the graph.
-Noting that an undirected simple graph can have at most | V|^2/2 edges, allowing
loops, we can let d = |E|/| V|^2 denote the density of the graph. Then, 8| E | > | V |^2/8
when | E|/| V|^2 > 1/64, that is the adjacency list representation occupies more space
than the adjacency matrix representation when d > 1/64. Thus a graph must be sparse
enough to justify an adjacency list representation.
-Besides the space trade-off, the different data structures also facilitate different
operations. Finding all vertices adjacent to a given vertex in an adjacency list is as
simple as reading the list. With an adjacency matrix, an entire row must instead be
scanned, which takes O(| V |) time. Whether there is an edge between two given
vertices can be determined at once with an adjacency matrix, while requiring time
proportional to the minimum degree of
, /.Adjacency matrix - Answer-Graph data structure. a square matrix used to represent a
finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent
or not in the graph.
-In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with
zeros on its diagonal. If the graph is undirected, the adjacency matrix is symmetric. The
relationship between a graph and the eigenvalues and eigenvectors of its adjacency
matrix is studied in spectral graph theory.
-The adjacency matrix should be distinguished from the incidence matrix (a matrix that
shows the relationship between two classes of objects) for a graph, a different matrix
representation whose elements indicate whether vertex-edge pairs are incident or not.
/.AF-heap - Answer-heap data structure. a type of priority queue for integer data, an
extension of the fusion tree using an atomic heap proposed by M. L. Fredman and D. E.
Willard.[1]
Using an AF-heap, it is possible to perform m insert or decrease-key operations and n
delete-min operations on machine-integer keys in time O(m + n log n / log log n). This
allows Dijkstra's algorithm to be performed in the same O(m + n log n / log log n) time
bound on graphs with n edges and m vertices, and leads to a linear time algorithm for
minimum spanning trees, with the assumption for both problems that the edge weights
of the input graph are machine integers in the transdichotomous model.
/.AList - Answer-b-tree data structure. No article.
/.Alternating decision tree (ADTree) - Answer-Application-specific tree data structure. a
machine learning method for classification. It generalizes decision trees and has
connections to boosting.
-An ADTree consists of an alternation of decision nodes, which specify a predicate
condition, and prediction nodes, which contain a single number. An instance is
classified by an ADTree by following all paths for which all decision nodes are true, and
summing any prediction nodes that are traversed.
-An alternating decision tree consists of decision nodes and prediction nodes. Decision
nodes specify a predicate condition. Prediction nodes contain a single number.
ADTrees always have prediction nodes as both root and leaves. An instance is
classified by an ADTree by following all paths for which all decision nodes are true and
summing any prediction nodes that are traversed. This is different from binary
classification trees such as CART (Classification and regression tree) or C4.5 in which
an instance follows only one path through the tree.
/.And-inverter graph (AIG) - Answer-Graph data structure. a directed, acyclic graph that
represents a structural implementation of the logical functionality of a circuit or network.
An AIG consists of two-input nodes representing logical conjunction, terminal nodes
labeled with variable names, and edges optionally containing markers indicating logical
negation. This representation of a logic function is rarely structurally efficient for large
circuits, but is an efficient representation for manipulation of boolean functions.
Typically, the abstract graph is represented as a data structure in software.
AND ANSWERS
/.(a,b)-tree - Answer-multiway tree data structure. a kind of balanced search tree. An
(a,b)-tree has all of its leaves at the same depth, and all internal nodes except for the
root have between a and b children, where a and b are integers such that 2 ≤ a ≤
(b+1)/2. The root has, if it is not a leaf, between 2 and b children.
/.2-3 heap - Answer-heap data structure. a data structure, a variation on the heap,
designed by Tadao Takaoka in 1999. The structure is similar to the Fibonacci heap, and
borrows from the 2-3 tree.
-Time costs for some common heap operations are:
1) Delete-min takes O(log(n)) amortized time.
2) Decrease-key takes constant amortized time.
3) Insertion takes constant amortized time.
/.2-3 tree - Answer-b-tree data structure. a tree data structure, where every node with
children (internal node) has either two children (2-node) and one data element or three
children (3-nodes) and two data elements. According to Knuth, "a B-tree of order 3 is a
2-3 tree." Nodes on the outside of the tree (leaf nodes) have no children and one or two
data elements.[1][2] 2−3 trees were invented by John Hopcroft in 1970
/.2-3-4 tree (also called a 2-4 tree) - Answer-b-tree data structure. a self-balancing data
structure that is commonly used to implement dictionaries.
-The numbers mean a tree where every node with children (internal node) has either
two, three, or four child nodes:
1) a 2-node has one data element, and if internal has two child nodes;
2) a 3-node has two data elements, and if internal has three child nodes;
3) a 4-node has three data elements, and if internal has four child nodes.
-2-3-4 trees are B-trees of order 4;[1] like B-trees in general, they can search, insert and
delete in O(log n) time. One property of a 2-3-4 tree is that all external nodes are at the
same depth.
-2-3-4 trees are an isometry of red-black trees, meaning that they are equivalent data
structures. In other words, for every 2-3-4 tree, there exists at least one red-black tree
with data elements in the same order. Moreover, insertion and deletion operations on 2-
3-4 trees that cause node expansions, splits and merges are equivalent to the color-
flipping and rotations in red-black trees. Introductions to red-black trees usually
introduce 2-3-4 trees first, because they are conceptually simpler. 2-3-4 trees, however,
can be difficult to implement in most programming languages because of the large
number of special cases involved in operations on the tree. Red-black trees are simpler
to implement,[2] so tend to be used instead.
,/.AA tree* - Answer-binary tree data structure. a form of balanced tree used for storing
and retrieving ordered data efficiently. AA trees are named for Arne Andersson, their
inventor.
-AA trees are a variation of the red-black tree, a form of binary search tree which
supports efficient addition and deletion of entries. Unlike red-black trees, red nodes on
an AA tree can only be added as a right subchild. In other words, no red node can be a
left sub-child. This results in the simulation of a 2-3 tree instead of a 2-3-4 tree, which
greatly simplifies the maintenance operations. The maintenance algorithms for a red-
black tree need to consider seven different shapes to properly balance the tree (see
image in wiki).
An AA tree on the other hand only needs to consider two shapes due to the strict
requirement that only right links can be red (see image in wiki).
-Balancing rotations:
-Whereas red-black trees require one bit of balancing metadata per node (the color), AA
trees require O(log(N)) bits of metadata per node, in the form of an integer "level". The
following invariants hold for AA trees:
1. The level of every leaf node is one.
2. The level of every left child is exactly one less than that of its parent.
3. The level of every right child is equal to or one less than that of its parent.
4. The level of every right grandchild is strictly less than that of its grandparent.
5. Every node of level greater than one has two children.
A link where the child's level is equal to that of its parent is called a horizontal link, and
is analogous to a red link in the red-black tree. Individual right horizontal links are
allowed, but consecutive ones are forbidden; all left horizontal links are forbidden.
These are more restrictive constraints than the analogous ones on red-black trees, with
the result that re-balancing an AA tree is procedurally mu
/.abstract data type (ADT) - Answer-a mathematical model of the data objects that make
up a data type as well as the functions that operate on these objects. a data type is
defined by its behavior (semantics), specifically in terms of possible values, possible
operations on data of this type, and the behavior of these operations. This contrasts
with data structures, which are concrete representations of data, and are the point of
view of an implementer, not a user.
Container
List
Associative array
Multimap
Set
Multiset
Stack
Queue
Double-ended queue
Priority queue
Tree
Graph
,/.Abstract syntax tree (AST, or just syntax tree) - Answer-Application-specific tree data
structure. a tree representation of the abstract syntactic structure of source code written
in a programming language. Each node of the tree denotes a construct occurring in the
source code. The syntax is "abstract" in not representing every detail appearing in the
real syntax. For instance, grouping parentheses are implicit in the tree structure, and a
syntactic construct like an if-condition-then expression may be denoted by means of a
single node with three branches.
-This distinguishes abstract syntax trees from concrete syntax trees, traditionally
designated parse trees, which are often[citation needed] built by a parser during the
source code translation and compiling process. Once built, additional information is
added to the AST by means of subsequent processing, e.g., contextual analysis.
-Abstract syntax trees are also used in program analysis and program transformation
systems.
/.Adaptive k-d tree - Answer-space partitioning or binary space partitioning data
structure. a tree for multidimensional points where successive levels may be split along
different dimensions.
/.Adjacency list - Answer-Graph data structure. a collection of unordered lists used to
represent a finite graph. Each list describes the set of neighbors of a vertex in the
graph. This is one of several commonly used representations of graphs for use in
computer programs.
|Data Structures|
For use as a data structure, the main alternative to the adjacency list is the adjacency
matrix. Because each entry in the adjacency matrix requires only one bit, it can be
represented in a very compact way, occupying only |V|^2/8 bytes of contiguous space,
where | V| is the number of vertices of the graph. Besides avoiding wasted space, this
compactness encourages locality of reference.
-However, for a sparse graph, adjacency lists require less space, because they do not
waste any space to represent edges that are not present. Using a naïve array
implementation on a 32-bit computer, an adjacency list for an undirected graph requires
about 2(32/8)| E| = 8| E| bytes of space, where | E| is the number of edges of the graph.
-Noting that an undirected simple graph can have at most | V|^2/2 edges, allowing
loops, we can let d = |E|/| V|^2 denote the density of the graph. Then, 8| E | > | V |^2/8
when | E|/| V|^2 > 1/64, that is the adjacency list representation occupies more space
than the adjacency matrix representation when d > 1/64. Thus a graph must be sparse
enough to justify an adjacency list representation.
-Besides the space trade-off, the different data structures also facilitate different
operations. Finding all vertices adjacent to a given vertex in an adjacency list is as
simple as reading the list. With an adjacency matrix, an entire row must instead be
scanned, which takes O(| V |) time. Whether there is an edge between two given
vertices can be determined at once with an adjacency matrix, while requiring time
proportional to the minimum degree of
, /.Adjacency matrix - Answer-Graph data structure. a square matrix used to represent a
finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent
or not in the graph.
-In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with
zeros on its diagonal. If the graph is undirected, the adjacency matrix is symmetric. The
relationship between a graph and the eigenvalues and eigenvectors of its adjacency
matrix is studied in spectral graph theory.
-The adjacency matrix should be distinguished from the incidence matrix (a matrix that
shows the relationship between two classes of objects) for a graph, a different matrix
representation whose elements indicate whether vertex-edge pairs are incident or not.
/.AF-heap - Answer-heap data structure. a type of priority queue for integer data, an
extension of the fusion tree using an atomic heap proposed by M. L. Fredman and D. E.
Willard.[1]
Using an AF-heap, it is possible to perform m insert or decrease-key operations and n
delete-min operations on machine-integer keys in time O(m + n log n / log log n). This
allows Dijkstra's algorithm to be performed in the same O(m + n log n / log log n) time
bound on graphs with n edges and m vertices, and leads to a linear time algorithm for
minimum spanning trees, with the assumption for both problems that the edge weights
of the input graph are machine integers in the transdichotomous model.
/.AList - Answer-b-tree data structure. No article.
/.Alternating decision tree (ADTree) - Answer-Application-specific tree data structure. a
machine learning method for classification. It generalizes decision trees and has
connections to boosting.
-An ADTree consists of an alternation of decision nodes, which specify a predicate
condition, and prediction nodes, which contain a single number. An instance is
classified by an ADTree by following all paths for which all decision nodes are true, and
summing any prediction nodes that are traversed.
-An alternating decision tree consists of decision nodes and prediction nodes. Decision
nodes specify a predicate condition. Prediction nodes contain a single number.
ADTrees always have prediction nodes as both root and leaves. An instance is
classified by an ADTree by following all paths for which all decision nodes are true and
summing any prediction nodes that are traversed. This is different from binary
classification trees such as CART (Classification and regression tree) or C4.5 in which
an instance follows only one path through the tree.
/.And-inverter graph (AIG) - Answer-Graph data structure. a directed, acyclic graph that
represents a structural implementation of the logical functionality of a circuit or network.
An AIG consists of two-input nodes representing logical conjunction, terminal nodes
labeled with variable names, and edges optionally containing markers indicating logical
negation. This representation of a logic function is rarely structurally efficient for large
circuits, but is an efficient representation for manipulation of boolean functions.
Typically, the abstract graph is represented as a data structure in software.
