1.4- data structures

Question 1

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).

Answer 1

data structure

Question 2

____ 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 _____

Answer 2

array
index

Question 3

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.

Answer 3

binary strings

Question 4

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).

Answer 4

lexicographic

Question 5

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.

Answer 5

linked list

Question 6

each node except the last one contains a single pointer to the next element

Answer 6

singly linked list

Question 7

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.

Answer 7

node

Question 8

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.

Answer 8

header

Question 9

in which every
node, except the first and the last, contains pointers to both its successor and its
predecessor

Answer 9

doubly linked list

Question 10

stack

Answer 10

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

Question 11

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

Answer 11

queue

Question 12

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.

Answer 12

priority

Question 13

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.

Answer 13

edges
undirected edge

Question 14

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

Answer 14

directed
tail

Question 15

A graph with every pair of its vertices connected by an edge

Answer 15

complete

Question 16

A standard notation for the complete graph with |V | vertices is|K|{V}. A graph
with relatively few possible edges missing is called _____

Answer 16

dense

Question 17

a graph with few edges relative to the number of its vertices is called _____

Answer 17

sparse

Question 18

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.

Answer 18

adjacency matrix

Question 19

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.

Answer 19

adjacency lists

Question 20

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

Answer 20

weighted graph

Question 21

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.

Answer 21

weight

Question 22

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.

Answer 22

length
minus

Question 23

directed path

Answer 23

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.

Question 24

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.

Answer 24

connected

Question 25

A ______ ______ is a maximal (not expandable by including another vertex and an edge) connected subgraph of a given graph.

Answer 25

connected component

Question 26

a path of a positive length that starts and ends at
the same vertex and does not traverse the same edge more than once.

Answer 26

cycle

Question 27

A graph with no cycles

Answer 27

acyclic

Question 28

(more accurately, a free tree) is a connected acyclic graph

Answer 28

tree

Question 29

A graph that has no cycles but is not necessarily connected is called a______: each of its connected components is a tree

Answer 29

forest

Question 30

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

Answer 30

subgraph

Question 31

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

Answer 31

root

Question 32

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.

Answer 32

0

Question 33

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.

Answer 33

ancestors
proper ancestors

Question 34

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.

Answer 34

parental
proper descendants

Question 35

the length of the simple path from the root to v.

Answer 35

depth

Question 36

the length of the longest simple path from the root to a leaf.

Answer 36

heigh of tree

Question 37

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.

Answer 37

ordered tree

Question 38

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.

Answer 38

binary tree

Question 39

an unordered collection (possibly empty) of distinct items called elements of the set

Answer 39

set

Question 40

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;

Answer 40

and
finding the intersection of two sets, which comprises all the common elements in
the sets.

Question 41

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 _____ _____

Answer 41

universal set

Question 42

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.

Answer 42

bit vector

Question 43

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 _____

Answer 43

dictonary

Question 44

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 ___ ____ _____

Answer 44

set union problem

Question 45

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.

Answer 45

abstract data type (ADT)