CSE 7350/5350
Review Quiz
(Updated Jan
2005)
Spring 2005
(Sample Questions)
Discrete Mathematics/Data Structures
David W. Matula
Part A( 60 Minutes) CLOSED
BOOK
A1(2 points
each) Give one or two
sentence descriptions of each of the following terms from discrete mathematics
and /or data structures in the space provided.
1.Stack_________________________________________________________________
_______________________________________________________________________
_______________________________________________________________________
2. One-to-one
mapping_____________________________________________________
________________________________________________________________________
_______________________________________________________________________
3,. Binary search tree
______________________________________________________
________________________________________________________________________
________________________________________________________________________
4. Transitive relation
______________________________________________________
________________________________________________________________________
________________________________________________________________________
5. Hash table
_____________________________________________________________
________________________________________________________________________
_______________________________________________________________________
6. Asymptotic notation
____________________________________________________
_______________________________________________________________________
_______________________________________________________________________
7. Monotonic function
____________________________________________________
_______________________________________________________________________
_______________________________________________________________________
A2. (2 points
each): For each of the
description below give the notation that corresponds as shown in the example.
|
0.
(Example) The product 1 x 2 x 3 x 4 ..........x n |
n! ____________ |
|
1. The
sum of y1+y2+y3+ .....+
yn |
_____________ |
|
2. The
cartesian product of sets A and B |
_____________ |
|
3. The
least integer greater than or equal to x |
_____________ |
|
4. x is
an element of set X |
_____________ |
|
5. Set
A union set B |
_____________ |
|
6.
Power set of set A |
_____________ |
|
7. p
implies q |
_____________ |
A3 (16
points): Fill in the
time and space complexity for each of the following sorting methods as shown for
bubble sort.
For space complexity indicate
either that the solution is "in place" or indicate how much space is needed
(e.g. 2n + O(1)).
|
|
Sorting
Time WORST
CASE |
Complexity
BEST
CASE |
[#
comparison] AVERAGE
CASE |
SORTING
SPACE COMPLEXITY |
|
Bubble
sort |
O(n2) |
O(n) |
O(n2) |
In -place |
|
Insertion
sort |
|
|
|
|
|
Tree
sort |
|
|
|
|
|
Binary
search tree with inorder traversal sort |
|
|
|
|
|
Heap
Sort |
|
|
|
|
A4. (12
points) Give the
following traversals for the following binary tree.
PRE-ORDER
___________________________________________
IN-ORDER
___________________________________________
POST-ORDER
___________________________________________
A5.(12
points) For the
graph G represented by the following adjacency lists of
vertices:
a:
® b, f,
g
b:
® a, c, d,
f
c:
® b, d,
e
d:
® b, c, e, f,
g
e:
® c, d,
g
f:
® a, b, d,
g
g:
® a, d, e,
f
(i)
[3 points]
give the adjacency matrix for G,
(ii)
[3 points]
draw the graph G (as a planar graph if possible).
(iii)
[6 points] For the following graph
diagrams write down the answers to each question in the space provided.
|
Property |
|
|
|
Graph
of
Problem
B8 | ||
|
#
vertices |
6 |
9 |
7 |
| ||
|
# of edges |
8 |
7 |
|
| ||
|
# of
components |
1 |
|
|
| ||
|
Maximum
degree |
5 |
|
|
| ||
|
Minimum
degree |
1 |
|
|
| ||
|
Size of
largest clique |
3
(vertices) |
|
|
| ||
|
Size of
longest path |
5
(edges) |
|
|
| ||
|
Size of
largest cycle |
5
(edges) |
|
|
| ||
|
Size of
largest independent set |
3
(vertices) |
|
|
|
