Midterm Study From Quizes

Question 1

Arrange the following expressions from the slowest to fastest growth rate.

Answer 1

Question 2

Answer 2

Question 3

Answer 3

Question 4

Answer 4

Question 5

Answer 5

Question 6

Answer 6

Question 7

Answer 7

Question 8

Answer 8

Question 9

Answer 9

Question 10

Answer 10

Question 11

Answer 11

false

Question 12

Answer 12

Question 13

Answer 13

Question 14

Answer 14

O(n). When resizing, a new array must be created, and each existing element in the old array is then individually copied into the new array.

Question 15

When do we need to increase the capacity of the underlying data storage array (i.e. data) in order to make space for the new element.

Answer 15

When the array is full, the current size equals the capacity. We must then call resize() to increase the array capacity

Question 16

Answer 16

[0, 3, 6, 9, 12, 15]

Question 17

The order in which elements are placed into the Bag ADT is important

Answer 17

False, Conceptually, we use the Bag ADT when the insertion order is irrelevant for the problem we’re working on.

Question 18

Which of the following provides better speed for a dynamic array?

Answer 18

Question 19

Suppose the size of the dynamic array is n, and we want to insert an element into the array. What is the maximum number of elements we have to move.

Answer 19

n,

Question 20

Answer 20

Question 21

Answer 21

Question 22

What will happen if we attempt to remove a value from an empty queue

Answer 22

It will raise an exception when the operation is attempted on an empty queue

Question 23

Answer 23

Question 24

Answer 24

Question 25

Why is it difficult to implement a deque using the same dynamic array implementation that was used for the dynamic array-based stack?

Answer 25

While a stack only has values added to and removed from one end of the array, a deque may have values added to or removed from both the front or the back of the array. The problem is that removing or adding a value located at index 0 (unless it is the only value in the deque) is very difficult. For adding, you must shift all other values up one index in the array, and, for removing, you must shift all other values back one index in the array. Otherwise, it would leave a “hole” in your array. Either operation would have O(n) algorithmic execution time, which is not ideal.

Question 26

Answer 26

Question 27

We know that a circular buffer or circular queue is simply an array viewed as a circle instead of a line, where we allow the values to wrap around back to the beginning of the array. When we resize our queue’s underlying physical array, what strategy do we follow?

Answer 27

The value at the start index in the old array gets copied to physical index 0 in the new array.

Question 28

Answer 28

Question 29

Answer 29

Question 30

How many calls to pop() are needed to determine the size of a stack? Answer in terms of n, where n is the number of elements in the stack.

Answer 30

n

Question 31

Answer 31

Question 32

Why do we need both front and back sentinels when implementing a deque on top of a linked list?

Answer 32

Question 33

A _____ binary tree is a binary tree in which every interior node has exactly two children.

Answer 33

Full

Question 34

Fill in the following blanks:
If we know a perfect binary tree has height h, then we know:
- it has _____ leaves.
- it has _____ total nodes.

Answer 34

2^h
2^(h+1)-1

Question 35

If we know that a perfect binary tree has n nodes, then we know its height is approximately _______.

Answer 35

O(log(n))

Question 36

Add the following numbers in the order given to a binary search tree: 45, 67, 22, 100, 75, 13, 11, 64, 30

Answer 36

Question 37

What is the height of the tree from the previous question? What is the height of the subtree rooted at the node holding the value 22? What is the depth of the node holding the value 22?

Answer 37

3, 2, 1

Question 38

Add the following numbers in the order given to a binary search tree: 3, 14, 15, 20, 25, 30, 33, 62, 200

Answer 38

Question 39

Is the following tree balanced? Why or why not? What is the execution time required for searching for a value in this tree?

Answer 39

No, it is not balanced because it has all of the child nodes on the right side of the root node and no nodes on the left side. Balanced trees should be able to maintain O(logn) for all operations, however, this tree would yield an execution time of O(n) when searching for a value.

Question 40

Add a new value, 145, to this tree:

Answer 40

Question 41

Remove the value 67 from this tree. What value did you replace it with and why?

Answer 41

Question 42

For the following binary search tree, list the nodes as they are visited in a pre-order, in-order, and post-order traversal.

Answer 42

Question 43

Why is the time required to find a key in a binary search tree O(n) in the worst case?

Answer 43

The worst case occurs when the longest path in the tree is followed in search of the target and the longest path is based on the height of the tree. Binary trees come in many shapes and sizes and their heights can vary. We read that a tree of size n can have a minimum height of roughly logn when the tree is complete and a maximum height of n when there is one node per level. If we have no knowledge about the shape of the tree and its height, wwe have to assume the worst and in this case that would be a tree of height n. Thus, the ime required to find a key in a binary search tree is O(n) in the worst case.