Exam 3 Review

Question 1

Recursion requires what two cases?

Answer 1

A base case and a recursive case

Question 2

Recursive method for calculating a factorial

Answer 2

int fact(int n) {
        int result;

   if(n==1)
     return 1;

   else {
        return n * fact(n-1);
 } }

Question 3

What is a heap?

Answer 3

• a balanced binary tree

- created using a binary tree

Question 4

Characteristics of a binary search tree

Answer 4

• only 2 children per node

- left subtree must be less, right subtree must be more

Question 5

Pre order

Answer 5

root, left subtree, right subtree

Question 6

In order

Answer 6

left subtree, root, right subtree

IN COMPARABLE ORDER SMALLEST TO LARGEST

Question 7

Post Order

Answer 7

left subtree, right subtree, root

Question 8

Breadth-first

Answer 8

based on level… root level, then next level on the left, same level on the right

Question 9

Difference between binary search tree and binary tree?

Answer 9

The ordering of the values… for a binary tree it doesn’t matter the order as long as each node only has two nodes at most… for a binary search tree the left node must be less than the root and the right must be greater

Question 10

When adding a value to a BST, what is the first operation? What happens next?

Answer 10

1. run find() to determine where it should be

2. add the node at that position

Question 11

Know how to write the recursive find method

Answer 11

Find an element in the tree
• Compare with root, if less traverse left, else traverse right;
repeat
• Stop when found or at a leaf

.. compexity is log n

Question 12

2 properties that heaps have?

Answer 12

• Shape Property ( all leaf nodes are either on the bottom level or the second most bottom level)
• Order property (the data value stored at a node is less than or equal to the data values stored at all of its descendants)

(root value is always the smallest value int he heap)

Question 13

What are heaps good for?

Answer 13

• finding the maximum or minimum value
• sorting values into ascending or descending order
• implementing another data structure (priority queue)

Question 14

What interface must a class implement to be storable in a heap?

Answer 14

comparable

Question 15

What must you do when you add nodes to or remove nodes from a heap?

Answer 15

add -> add to the heap then maintain the shape and heap properties (swap around values until the order properties are met)

remove -> remove and return the root then rebuild the heap to SELECT a new root that is the smallest value

Question 16

Why is it important to keep the heap balanced?

Answer 16

to maintain the properties

Question 17

What must be there before the CFG is finished?

Answer 17

start symbol
variables
terminal symbols
production symbols

Question 18

Know CFGs!

Answer 18

a

Question 19

What can the compiler tell right away by loading commands into a parse tree?

Answer 19

a

Question 20

Is it good or bad if more than one parse tree can be created from the same String? What is this called?

Answer 20

bad ! ambiguity!

Question 21

Look over slides about what will this print in slides

Answer 21

aa

Question 22

What is UML? What goes in each box?

Answer 22

top: class name
middle: variables
bottom: methods

Question 23

All classes inherit from ____?

Answer 23

Object

Question 24

To inherit from a parent class, use the ____ keyword.

Answer 24

super

Question 25

Classes that inherit from a parent object have an _____ relationship. What is the difference between this and the other king of relationship?

Answer 25

inheritance?

implementation?

Question 26

What is the substitutability principle?

Answer 26

child can do what a parent can do

Question 27

Do interfaces extend object?

Answer 27

No!

Question 28

When you implement an interface, what are you promising to do?

Answer 28

form a contract between the class and the outside world

Question 29

What does an interface allow your class to do?

Answer 29

implement various other methods

Question 30

What does the Comparable interface define?

Answer 30

a

Question 31

What method must be implemented for a comparable interface?

Answer 31

compareTo(Object other)

Question 32

How do interfaces support polymorphism?

Answer 32

Yes ! you can implement mulltiple different interfaces

Question 33

Can you write a working program using only abstract classes?

Answer 33

a

Question 34

If a class has one abstract method, can it be created?

Answer 34

nope… it has to be implemented first

Question 35

If you create a child class that extends the abstract class, can it be implemented?

Answer 35

a

Question 36

Which of these algorithms would be a better choice?

O(lg n)
O(n g n)

Answer 36

O(lg n) is much more efficient!

Question 37

What is race condition?

Answer 37

occurs if the effect of multiple threads on shared

data depends on the order in which the threads are scheduled…

Question 38

What tool is used to handle potential race conditions?

Answer 38

lock

Question 39

What is a deadlock?

Answer 39

two or more threads are blocked forever waiting for one another

Question 40

Does a single threaded application need locks?

Answer 40

no

Question 41

Why does the call unlock() go in the finally code block?

Answer 41

so that the last thing that occurs is the lock is taken off so that the next thread can run

Question 42

Review threads!!

Answer 42

a

Question 43

min heap vs max heap

Answer 43

min heap: root is smalest

max heap: root is largest