1.

a:
b: T
c: F : an interface can be implemented in infinitely many ways
d: F : a tree is an heirarchiel data structure
e: F : it can be declared but not initialized
f: F : reindexing an entire array takes more steps than generating one node of a LL
g: F : that is not possible
*h: F : a binary seach tree has a better time cost for search than a sorted array
i: T
j: T : an avl tree is a BST with the balance property, so an AVL rotation maintains the BST quality
k: T
l: T : if it is theta then it must also be O and omega
m: F : this is a reference to the factory pattern
n: F : what?
o: T
p: T
q: F : abstract syntax trees are not limited to two children as a BST is
r: T : heaps are typically implemented using arrays
s: T
t: T
u: F : by n = 10 this is clearly false
v: F : adt = abstract data type
w: F : a leaf is a node without children
*x: T

2.

a: iterator
b: queue
c:
d: doubly linked
e: seperate chaining
f: shallow
g: precondition
h: constant
i: 3
j: inorder

3.

a: D
b: E
c: C
d: C
	attempt to buld:

	Y or <Start>X
	Z<Str>ZX or WZ
	Z<Start>XZ or ZYZX

e: A
f: B

	   X: 1
      --         0

	cannot be a heap, heaps are "complete" binary trees

g: B

	root = 0
	right child of root = 2(0) + 2 = 2
	left child of 2 = 2(2) + 1 = 5
H: D
I: D
J: D


4.


inserting 3:

	3

inserting 2:

	2

      3

inserting 1:

	1
      3   2

inserting 4

	1
      3   2
    4

inorder traversal: 4 3 1 2

5.

a. 4
b. 4
c. 3
d. 2
e. 3
f. 4
g. 7
i. 4
j. 4

6.

selection sort: find biggest element, place into new array O(n^2)
insertion sort: take index 0, find place in sorted array O(n^2)
heap sort: ?????? O(nlog_2_n)
merge sort: make n partitions, put stuff together log_2_n
quicksort: dependent on pivot


a. D
b. C
c.