One vertex is distinguished from the others and is called the root
The level of a vertex in a rooted tree is ____.
the number of edges along the unique path between it and the root
The height of a rooted tree is ____.
the maximum level of any vertex of the tree
A binary tree is a rooted tree in which ____.
every parent has at most two children
A full binary tree is a rooted tree in which ____.
every parent has exactly two children
If k is a positive integer and T is a full binary tree with k internal verticies, then T has a total of __(a)___ verticies and ___(b)__ terminal verticies
a) 2k +1
b) k +1
If T is a binary tree that has t terminal verticies and height h, then t and h are related by the inequality ______.
or
When an algorithm segment contains a nested for-next loop, you can find the number of times the loob will interate by constructing a table in which each column represents ____.
one iteration of the innermost loop
In the worst case for an input array of length n, the sequential search algorith has to look through _____ elements of the array before it terminates.
n
The worst-case order of the insertion sort algorithm is _(a)__, and its average-case order is _(b)___.
a) n2
b) n2
for all integers n >= 1
OR
for any real number r except 1, and any integer n >= 0 OR
1 + r + r2+...rn =
The domain of any exponential function is _(a)_, and its range is _(b)_.
a) the set of all real numbers
b) the set of all positive real numbers
The domain of any logarithmic funcion is _(a)_, and its range is _(b)_.
a) the set of all positive real numbers
b) the set of all real numbers
if k is an integer and then
k
If b is a real number with b > 1 and if x is a sufficiently large real number, then when the quantities x, x2, logbx, andare arranged in order of increasing size, the result is ___.
logbx < x < x logb x < x2
if n is a positive integer, then 1 + 1/2 +1/3 +...+1/n has order ___.
ln x or equivantly log2x
b0 =
1
b-x =
Is the same as_____.
To solve a problem using a divide-and-conquer algorithm, you reduce it to a fixed number of smaller problems of the same kind, which can themselves be __(a)__, and so forth until _(b)__.
a) reduced to the same finite number of smaller problems of the same kind
b) easily resolved problems are obtained
To search an array using the binary search algorithm in each step, you compare a middle element of an array to __(a)__. If the middle element is less then __(b)__, you __(c)__, and if the middle element is greater then __(d)__, you __(e)__.
(a) the element uou are looking for
(b) the element you are looking for
(c) apply the binary search algorithm to the lower half of the array
(d) the element you are looking for
(e) apply the binary search algorithm to the upper half of the array
The worst case order of the binary search algorithm is ___.
log2n, where n is the length of the array
To sort an array using the merge sort algorithm, in each step until the last one you split the array into approximately two equal sections and sort each section using __(a)__. Then you __(b)__ the two sorted sections.
(a) merge sort
(b) merge
The worst case order of the merge sort algorithm is ___.
A graph consists of two finite sets: __(a)__ and __(b)__, where each edge is associated with a set consisting of __(c)__.
(a) a finite, nonempty set of verticies
(b) a finite set of edges
(c) one or two verticies called its endpoints
A loop in a graph is ____
an edge with a single endpoint
Two distinct edges in a graph are parallel if, and only if, ___.
they have the same set of endpoints
Two vertices are called adjacent if and only if __.
they are connected by an edge.
An edge is incident on ____.
each of its endpoints.
Two edges incident on the same endpoint are ___.
adjacent
A vertex on which no edges are incident is ___.
isolated
In a directed graph, each edge is associated with ___.
an ordered pair of vertices called its endpoints
a simple graph is ___.
a graph with no loops or parallel edges
A complete graph on n vertices is a ___.
simple graph with n vertices whose set of edges contains exactly one edge for each pair of verticies.
A complete bipartite graph on (m,n) vertices is a simple graph whose vertices can be partitioned into two disjoint sets V1 and V2 in such a way that (1) each of the m vertices in V1 is __(a)__ to each of the n vertices in V2, no vertex in V1is connected to ___(b)__, and no vertex in V2is connected to __(c)__.
(a) connected by an edge
(b) any other vertex V1
(c) any other vertex in V2
A graph H is a subgraph of a graph G if, and only if, (1)__(a)__, (2)__(b)__, and (3) __(c)__.
(a)every vertex in H is also a vertex in G
(b) every edge in H is also an edge in G
(c) every edge in H has the same endpoints as it has in G.
The degree of a vertex in a graph is ___.
the number of edges that are incident on the vertex, with an edge that is a loop counted twice.
The total degree of a graph is defined as ___.
the sum of the degrees of all the verticies of the graph
The handshake theorem says that the total degree of a graph is ___.
equal to twice the number of edges in the graph
in any graph the number of vertices of odd degree is ___.
an even number.
Let G be a graph and v and w be vertices in G,
A walk from v to w is ____.
a finite alternating sequence of adjacent verticies and edges of G
Let G be a graph and v and w be vertices in G,
A trail from v to w is ____.
a walk that does not contain a repeated edge
Let G be a graph and v and w be vertices in G,
a path from v to w is ____.
a trail that does not contain a repeated vertex
Let G be a graph and v and w be vertices in G,
a closed walk is ____.
a walk that starts and ends at the same vertex
Let G be a graph and v and w be vertices in G,
A circuit is ____.
a closed walk that contains at least one edge and does not contain a repeated edge
Let G be a graph and v and w be vertices in G,
a simple circuit is ____.
a circuit that does not have any repeated vertex other than the first and the last
Let G be a graph and v and w be vertices in G,
a trivial walk is ____.
a walk consisting of a single vertex and no edge
Let G be a graph and v and w be vertices in G,
vertices v and w are connected if, and only if, ____.
there is a walk from v to w
A graph is connected if, and only if, ____.
given any two verticies in the graph, there is a walk from one to the other
Removing an edge from a circuit in a graph does not ____.
disconnect the graph
An Euler circuit in a graph is ____.
a circuit that contains every vertex and every edge of the graph
A graph has an Euler circuit if, and only if, ____.
the graph is connected, and every vertex has positive, even degree
Given verticies v and w in a graph, there is a Euler path from v to w if, and only if, ____.
the graph is connected, v and w have odd degree, and all other vertices have positive even degree
A Hamiltonian circuit in a graph is ____.
a simple circuit that includes every vertex of the graph
If a graph G has a Hamiltonian circuit, then G has a sub graph H with the following properties: __(a)__, __(b)__, __(c)__, and __(d)__.
(a) H contains every vertex of G
(b) H is connected
(c) H has the same number of edges as vertices
(d) every vertex of H has degree 2
A traveling salesman problem involves finding a ____ that minimizes the total distance of traveled for a graph in which each edge is marked with a distance.
Hamiltonian circuit
In the adjacency matrix for a directed graph, the entry in the ith rowand jth colum is ____.
the number of arrows from vi(the ith vertex) to vj(the jth vertex)
In the adjacency matrix for an undirected graph, the entry in the ith row and jth column is ___.
the number of edges connecting vi(the ith vertex) and vj(the jth vertex)
An n * n square matrix is called symmetric if, and only if, for all integers iand j from 1 to n , the entry row __(a)__, and column__(b)___, equals the entry row __(c)__ and column__(d)__.
(a) i
(b) j
(c) j
(d) i
the ijth entry in the product of two matrices A and B is obtained by multiplying row __(a)__ of A by row __(b)__ of B
(a) i
(b) j
In an n * n identity matrix the entries on the main diagonal are all __(a)__ and the off-diagonal entries are all __(b)__.
(a) 1
(b) 0
if G is a graph with verticies v1, v2, ..., vm, and A is the adjacency matrix of G, then for each positive integer n and for all integers i and j with i , j = 1, 2, ...m, the ijth entry of An= ___.
the number of walks of length n from vi to vj
T/F? if f(n) is O(g(n)) then g(n) is
True
T/F? Mergesort and Quicksort have the same worst-case running time.
False
T/F? Postorder traversal visits the nodes of a binary search tree (with no duplicate keys) in decreasing order of their keys.
False
T/F? If every box of jelly-beans contains 20 to 30 beans then I only need to collect 23 boxes to be sure that three of my boxes contain teh same number of beans.
True
T/F? Skip list nodes (with maximum height 16) are most likely to have height 1 than height 2.
True
T/F? For all a, b > 1,
True
T/F? An algorithm with worst-case running time O(n) is faster then an algorithm with a best-case running time on any input.
False
T/F?
int sum(int n) { if ( n==0 ) return 0; else return n+sum(n-1); } is tail recursive.
False
Suppose, int sum(int n) { if ( n==0 ) return 0; else return n+sum(n-1); } takes to complete when n = 10,000 a reasonable prediction of its running time when n = 1,000,000 is : (a) , (b) 105, (c) , (d)
(c)
T/F? The height of a rooted tree with n nodes is at most n - 1
True
3 % 11 =
3
14 % 11 =
3
13 % 11 =
2
2 % 11 =
2
24 % 11 =
2
24 % 7 =
3
14 % 7 =
0
17 % 7 =
3
11 % 7 =
4
There are ____ different ways of arranging n distinct objects into a sequence, the permutations of those objects.
n!
A sample space of a random process or experiement is ___.
the set of all outcomes of the random process or experiement
An event in a sample space is ___.
a subset of the sample space
To compute the probability of an event using the equally likely probability formula, you take the ratio of the __(a)__ to the __(b)__.
(a) number of outcomes in the event
(b) total number of outcomes
if , the number of integers from m to n inclusive is ___.
n - m + 1
The multiplication rule syas that if an operation can be performed in k steps and for each i with , the ith step can be performed in niways (regaurdless of how previous steps were performed), then the operation as a whole can be performed in ___.
n1n2...nkways
A permutation of a set of elements is ___.
an ordering of the elements of the set in a row
The number of permutations of a set of n elements equals ___.
n!
An r-permutation of a set of n elements is ___.
an ordered selection of r of the elements of the set
the number of r-permutations of a set of n elements is denoted ___.
P(n, r)
One formula for the numner of r-permutations of a set of n elements is __(a)__ and another formula is __(b)__.
(a) n ( n - 1 ) ( n - 2 ) ... ( n - r + 1)
(b)
The addition rule says that if a finite set A equals the union of k dsitinct mutally disjoint subsets A1 , A2 , ... , Ak, then ____.
the number of elements in A equals N(A1) + N(A2) + ...+ N(An)
The difference rule says that if A is a finite set and B is a subset of A, then ___.
The number of elements in A - B is the difference between the number of elements in A and the number of elements in B , that is, N(A-B) = N(A) - N(B)
If S is a finite sample space and A is an event in S, Then the probability of Acequals ____.
1 - P(A)
The inclusion/exclusion rule for two sets says that if A and B are any finite sets, then ____.
The inclusion/exclusion rule for three sets says if A, B, and C are any finite sets, then ____.
The pigeonhole principal states that ___.
if n pigeons fly into m pigeonholes and n > m , then at least two pigeons fly into the same pigeonhole. OR a funcion form one finite set to a smaller finite set cannot be one-to-one
The generalized pigeonhole principal states that ___.
if n pigeons fly into m pigeonholes and, for some positive integer k , k < n/m, then at least one pigeonhole contains k +1 or more pigeons OR for any funcion f from a finite set X with n elements to a finite set Y with m elements and for any positive integer k , if k < n/m, then there is some such that y is the image of at least k +1 distinct elements of Y.
If X and Y are finite sets and f is a function form X to Y then f is one-to-one iff ___.
or