Midterm

Question 1

A _________ binary tree is a binary tree where every interior node has exactly 2 children.

Answer 1

Full binary tree

Question 2

A _________ binary tree is a binary tree where every interior node has exactly 2 children and all leaves are at the same depth except for the deepest level which has all leaves as far left as possible.

Answer 2

Complete binary tree

Question 3

A _________ binary tree is a binary tree where every interior node has exactly 2 children and all leaves are at the same depth.

Answer 3

Perfect Binary Tree

Question 4

If a perfect binary tree as height of 10, how many leaves are there?

Answer 4

2^10

Question 5

If a perfect binary tree as height of 10, how many nodes are there?

Answer 5

2^11 - 1

Question 6

If a complete binary tree has a height of 3 and 3 leaves at the deepest level, how many nodes are there?

Answer 6

2^3 - 1 + 3 … its perfect through height 2, so that is (2^3 -1). Then the bottom depth has 3 nodes, so add 3.

Question 7

What are the height constraints on trees (minimum and maximum)?

Answer 7

A tree has the smallest height when it is complete or perfect which leads to height of approximately log(n). The worst case scenario is a non-complete tree where there is one node per height which leads to height of n.

Question 8

How do you remove a node with 1 subtree?

Answer 8

Check if the removed node is its parent’s left or right. Check if removed node’s subtree is its left or right. Then make removed node’s subtree a child of removed node’s parent.

Question 9

How do you remove a leaf node?

Answer 9

Set its parent’s left or right to None.

Question 10

How do you remove a node with 2 subtrees?

Answer 10

Find inorder successor (S) and successor’s parent (PS). Set S’s left to removed node’s (N) left. If S is not N’s right, updated PS’s left to whatever S’s right was. Then update S’s right to N’s right. Lastly, update removed node’s parent (PN) to reflect its new child, S.

Question 11

What’s the difference between data structures and ADTs?

Answer 11

Data structures define how data is stored in memory. ADT is a specification that describes how we can interact with a data structure.

Question 11

What are the differences between a C array and Python list?

Answer 11

Arrays store one type of data, Arrays can only read/write a value at an index, array size must be declared at compile time, and size of array cannot be changed at run time.

Question 11

If an array memory location starts at 200 and each element required 10 bytes, how do we access the 5th element?

Answer 11

200 + (10*4) = starting memory location of 5th element (4th index)

Question 12

What is amortized analysis?

Answer 12

The method for analyzing a given operation’s complexity or how much of a resource (time/memory) it needs to execute by computing the average cost over the entire sequence.

Question 13

What is aggregate analysis?

Question 14

What is Encapsulation?

Answer 14

A mechanism thru which we hide the internal details of a data type from the user.

Question 14

What do __iter__() and __next__() do?

Answer 14

__iter__ create a reference tp the self object and establishes an index counter. __next__ tries to get the next indexed item and returns the value / iterates index counter. If index out of range, __next__ raises a StopIteration exception.

Question 15

What are the 3 main operations of a Stack ADT?

Answer 15

Push(val), Pop(), and Peek()

Question 16

Where do new values go when pushed to a LL Stack?

Answer 16

They become the new head. O(1) complexity.

Question 17

Where do values go when pushed to a DA Stack?

Answer 17

They get added to the end. Amortized O(1) complexity.

Question 18

What are the two main operations of a Queue ADT?

Answer 18

enqueue(val) and dequeue()

Question 19

How do we implement a Queue using a LL?

Answer 19

Set head and tail values. Enqueue’s go to end of LL and become tail. Dequeue pulls the head value and sets head.next to new head.

Question 20

How do we implement a Queue using a DA?

Answer 20

Track the start index and back index. Dequeue removes value at start (of line) and enqueue adds at end (of line)

Question 21

How do we resize a Queue using a DA?

Answer 21

Reindex using the value at start of line to index 0 of new DA.

Question 22

How does the increment function work to handle circular buffer of DA Queues?

Answer 22

It simply adds 1 to either start index or end index. If index is equal to capacity, make the index 0.

Question 23

In a DA Deque, explain the implementation?

Answer 23

The Deque will track front and back, starting front at index 0 and back at index = capacity - 1. When add_front occurs, we’d decrement the front index and wraparound if necessary. When add_back occurs, we’d increment back index.

Question 24

How do you implement a LL Deque?

Answer 24

Using two sentinels. Front sentinel sits on left, back sentinel sits on right. Add(front) makes frontSentinel.next = that value, etc.

Question 25

What is a MinHeap?

Answer 25

MinHeap = a complete binary tree where every node’s value is less than or equal to its children

Question 26

What data structure is a priority queue typically implemented with?

Answer 26

The heap data structure

Question 27

In a Dynamic Array, how do you calculate a node’s left child’s index?

Answer 27

(2 * i) + 1

Question 28

In a Dynamic Array, how do you calculate a node’s left child’s index?

Answer 28

(2 * i) + 2

Question 29

In a Dynamic Array, how do you calculate a node’s parent’s index?

Answer 29

(i-1) // 2

Question 30

What is the time complexity of a heapsort?

Answer 30

O(nlogn)

Question 31

What is the time complexity to build a heap from an unsorted array?

Answer 31

O(n)

Question 32

How do you find the first non-leaf node in an array?

Answer 32

(n // 2) - 1

Question 33

What are the 3 design features of a hash function?

Answer 33

Determinism (same result for same input), Uniformity (mapping is spread out), and Speed

Question 34

What is a perfect hash function?

Answer 34

One that results in zero collisions

Question 35

What is a minimally perfect hash function?

Answer 35

One that results in no collisions when table size equals exactly the number of elements.

Question 36

What operations are ideal for hash maps?

Answer 36

Insertion, contains, and removal.

Question 37

If there are 36 elements in a hash table with 8 buckets, what is the load factor?

Answer 37

4.5

Question 38

How do you calculate average complexity in a hash table?

Answer 38

O(load factor)

Question 39

What is best and worst-case complexity for hash tables?

Answer 39

Best case is O(1) such as when 6 elements in 6 unique buckets. Worst case is O(n) such as when 6 elements in 1 bucket.

Question 40

What is the average number of links traversed in a chained hash table search()?

Answer 40

If value is found, it is load factor / 2, if not found it is load factor ON AVERAGE

Question 41

What is complexity of Open Address Hashing?

Answer 41

O (1/(1-load_factor))