1.4- data structures Flashcards
defined as a particular scheme of organizing related data items.
The nature of the data items is dictated by the problem at hand; they can range
from elementary data types (e.g., integers or characters) to data structures (e.g., a
one-dimensional array of one-dimensional arrays is often used for implementing
matrices).
data structure
____ is a sequence of n items of the same data type that are stored contiguously in computer memory and made accessible by specifying a
value of the array’s _____
array
index
Strings composed of zeros
and ones are called ____ ____ or bit strings. Strings are indispensable for processing textual data, defining computer languages and compiling programs written
in them, and studying abstract computational models.
binary strings
Operations we usually perform on strings differ from those we typically perform on other arrays (say, arrays
of numbers). They include computing the string length, comparing two strings to
determine which one precedes the other in _____ (i.e., alphabetical) order, and concatenating two strings (forming one string from two given strings by
appending the second to the end of the first).
lexicographic
sequence of zero or more elements called nodes, each
containing two kinds of information: some data and one or more links called
pointers to other nodes of the linked list.
linked list
each node except the last one contains a single pointer to the next element
singly linked list
To access a particular_____ of a linked list, one starts with the list’s first node
and traverses the pointer chain until the particular node is reached. Thus, the time
needed to access an element of a singly linked list, unlike that of an array, depends
on where in the list the element is located.
node
start a linked list with a special node called the _____. This node may contain information about the linked list itself, such as its
current length; it may also contain, in addition to a pointer to the first element, a
pointer to the linked list’s last element.
header
in which every
node, except the first and the last, contains pointers to both its successor and its
predecessor
doubly linked list
stack
a list in which insertions and deletions can be done only at the end. This
end is called the top because a stack is usually visualized not horizontally but
vertically—akin to a stack of plates
a list from which elements are deleted from
one end of the structure, called the front (this operation is called dequeue),
and new elements are added to the other end, called the rear (this operation is
called enqueue). Consequently, a queue operates in a “first-in–first-out” (FIFO)
fashion
queue
a collection of data items from a totally ordered universe (most often, integer or real numbers). The principal operations on a priority queue are finding its largest element, deleting its largest element, and adding a new element.
Of course, a priority queue must be implemented so that the last two operations
yield another priority queue.
priority
a graph G = <V,E>
is defined by a pair of two sets: a finite nonempty set V of items called vertices
and a set E of pairs of these items called ____-. If these pairs of vertices are
unordered, i.e., a pair of vertices (u, v) is the same as the pair (v, u), we say that
the vertices u and v are adjacent to each other and that they are connected by the
_____ _____ (u, v). We call the vertices u and v endpoints of the edge (u, v)
and say that u and v are incident to this edge; we also say that the edge (u, v) is
incident to its endpoints u and v. A graph G is called undirected if every edge in
it is undirected.
edges
undirected edge
Graph:
If a pair of vertices (u, v) is not the same as the pair (v, u), we say that the
edge (u, v) is _____ from the vertex u, called the edge’s ____, to the vertex v,
called the edge’s head. We also say that the edge (u, v) leaves u and enters v. A
graph whose every edge is directed is called directed. Directed graphs are also
called digraphs
directed
tail
A graph with every pair of its vertices connected by an edge
complete
A standard notation for the complete graph with |V | vertices is|K|{V}. A graph
with relatively few possible edges missing is called _____
dense
a graph with few edges relative to the number of its vertices is called _____
sparse
The _____ _____of a graph with n vertices is an n × n boolean matrix with one row and one
column for each of the graph’s vertices, in which the element in the ith row and
the j th column is equal to 1 if there is an edge from the ith vertex to the j th vertex,
and equal to 0 if there is no such edge.
adjacency matrix
The ____ ____ of a graph or a digraph is a collection of linked lists,
one for each vertex, that contain all the vertices adjacent to the list’s vertex
(i.e., all the vertices connected to it by an edge). Usually, such lists start with a
header identifying a vertex for which the list is compiled.
adjacency lists
a graph (or digraph) with numbers assigned to its edges. These numbers are called weights or
costs. An interest in such graphs is motivated by numerous real-world applications, such as finding the shortest path between two points in a transportation or
communication network or the traveling salesman problem
weighted graph
If a weighted graph is represented by its adjacency matrix,
then its element A[i, j ] will simply contain the weight of the edge from the ith to
the j th vertex if there is such an edge and a special symbol, e.g., ∞, if there is no
such edge. Such a matrix is called the _____ matrix or cost matrix.
weight
connectivity and acyclicity. Both are based on the notion of a path. A path from vertex u to vertex v of a graph G can be defined as a
sequence of adjacent (connected by an edge) vertices that starts with u and ends
with v. If all vertices of a path are distinct, the path is said to be simple. The ____ of a path is the total number of vertices in the vertex sequence defining the path ____ 1, which is the same as the number of edges in the path.
length
minus
directed path
a sequence of vertices in which every consecutive pair of the
vertices is connected by an edge directed from the vertex listed first to the vertex
listed next.
A graph is said to be ____ if for every pair of its vertices u and v there
is a path from u to v. If we make a model of a connected graph by connecting
some balls representing the graph’s vertices with strings representing the edges,
it will be a single piece. If a graph is not connected, such a model will consist
of several connected pieces that are called connected components of the graph.
connected
A ______ ______ is a maximal (not expandable by including another vertex and an edge) connected subgraph of a given graph.
connected component
a path of a positive length that starts and ends at
the same vertex and does not traverse the same edge more than once.
cycle
A graph with no cycles
acyclic
(more accurately, a free tree) is a connected acyclic graph
tree
A graph that has no cycles but is not necessarily connected is called a______: each of its connected components is a tree
forest
A _______ of a given graph G = <V, E> is a graph G’ = <V’, E’> such that V’ subset of V and E’ subset of E
subgraph
for every two vertices in a tree, there always exists exactly one simple path from one of these
vertices to the other. This property makes it possible to select an arbitrary vertex
in a free tree and consider it as the ____ of the so-called rooted tree
root
A rooted tree
is usually depicted by placing its root on the top (level __ of the tree), the vertices
adjacent to the root below it (level 1), the vertices two edges apart from the root
still below (level 2), and so on.
0
For any vertex v in a tree T , all the vertices on the simple path from the root
to that vertex are called ____ of v.
vertices on the simple path from the root
to that vertex are called ancestors of v. The vertex itself is usually considered its
own ancestor; the set of ancestors that excludes the vertex itself is referred to as
the set of _____ ____. If (u, v) is the last edge of the simple path from the
root to vertex v (and u = v), u is said to be the parent of v and v is called a child
of u; vertices that have the same parent are said to be siblings.
ancestors
proper ancestors
A vertex with no children is called a leaf ; a vertex with at least one child is called ______. All the vertices for which a vertex v is an ancestor are said to be descendants of v; the
____ _____ exclude the vertex v itself. All the descendants of a vertex v
with all the edges connecting them form the subtree of T rooted at that vertex.
parental
proper descendants
the length of the simple path from the root to v.
depth
the length of the longest simple path from the root to a leaf.
heigh of tree
a rooted tree in which all the children of each
vertex are ordered. It is convenient to assume that in a tree’s diagram, all the
children are ordered left to right.
ordered tree
an ordered tree in which every vertex has
no more than two children and each child is designated as either a left child or a
right child of its parent; a binary tree may also be empty.
binary tree
an unordered collection (possibly empty) of distinct items called elements of the set
set
The most important set
operations are: checking membership of a given item in a given set; finding the
union of two sets, which comprises all the elements in either or both of them;
and
finding the intersection of two sets, which comprises all the common elements in
the sets.
Sets can be implemented in computer applications in two ways. The first
considers only sets that are subsets of some large set U, called the _____ _____
universal set
If set U has n elements, then any subset S of U can be represented by a bit string of size n, called a ____ _____, in which the ith element is 1 if and only if the ith element of U is included in set S.
bit vector
In computing, the operations we need to perform for a set or a multiset most
often are searching for a given item, adding a new item, and deleting an item
from the collection. A data structure that implements these three operations is
called the _____
dictonary
A number of applications in computing require a dynamic partition of some
n-element set into a collection of disjoint subsets. After being initialized as a
collection of n one-element subsets, the collection is subjected to a sequence
of intermixed union and search operations. This problem is called the ___ ____ _____
set union problem
a set of abstract objects representing data items with a collection of operations that can be performed on them. As
illustrations of this notion, reread, say, our definitions of the priority queue and
dictionary. Although abstract data types could be implemented in older procedural languages such as Pascal (see, e.g., [Aho83]), it is much more convenient to
do this in object-oriented languages such as C++ and Java, which support abstract
data types by means of classes.
abstract data type (ADT)
