Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Data Structures > Midterm > Flashcards

Midterm Flashcards

1
Q

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

A

Full binary tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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.

A

Complete binary tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

Perfect Binary Tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

2^10

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

2^11 - 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How do you remove a node with 1 subtree?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How do you remove a leaf node?

A

Set its parent’s left or right to None.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How do you remove a node with 2 subtrees?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What’s the difference between data structures and ADTs?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is amortized analysis?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is aggregate analysis?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is Encapsulation?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What do __iter__() and __next__() do?

A

__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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are the 3 main operations of a Stack ADT?

A

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

16
Q

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

A

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

17
Q

Where do values go when pushed to a DA Stack?

A

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

18
Q

What are the two main operations of a Queue ADT?

A

enqueue(val) and dequeue()

19
Q

How do we implement a Queue using a LL?

A

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.

20
Q

How do we implement a Queue using a DA?

A

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

21
Q

How do we resize a Queue using a DA?

A

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

22
Q

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

A

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

23
Q

In a DA Deque, explain the implementation?

A

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.

24
Q

How do you implement a LL Deque?

A

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

25
Q

What is a MinHeap?

A

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

26
Q

What data structure is a priority queue typically implemented with?

A

The heap data structure

27
Q

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

A

(2 * i) + 1

28
Q

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

A

(2 * i) + 2

29
Q

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

A

(i-1) // 2

30
Q

What is the time complexity of a heapsort?

A

O(nlogn)

31
Q

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

A

O(n)

32
Q

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

A

(n // 2) - 1

33
Q

What are the 3 design features of a hash function?

A

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

34
Q

What is a perfect hash function?

A

One that results in zero collisions

35
Q

What is a minimally perfect hash function?

A

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

36
Q

What operations are ideal for hash maps?

A

Insertion, contains, and removal.

37
Q

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

A

4.5

38
Q

How do you calculate average complexity in a hash table?

A

O(load factor)

39
Q

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

A

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.

40
Q

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

A

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

41
Q

What is complexity of Open Address Hashing?

A

O (1/(1-load_factor))

Data Structures (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions