Brainscape's Knowledge GenomeTM

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


See full index

Algorithms & Data Structures > Sample Final > Flashcards

Sample Final Flashcards

1
Q

Open hashing allows overflow into lists.

A

True.

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

A hash function is better if it produces few collisions.

A

True.

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

Hash functions cannot produce the same location for different keys.

A

False.

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

A hash function is better if each possible index is equally likely to occur given random keys.

A

True.

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

A process known as folding bits can reduce the impact of structure (a lack of randomness) on individual bits.

A

True.

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

Pseudo-Random probing generates random numbers during probing to avoid collisions.

A

False.

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

Using the modulo operator (%) with even numbers is a way to spread out locations independently of array size.

A

False.

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

Hashing grows more efficient as the load factor increases, encouraging small hash arrays.

A

False.

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

Using buckets with a size that is a prime number reduces probing collisions in open hashing.

A

False.

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

Closed hashing implies perfect hashing, as there is no place for duplicate keys.

A

False.

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

A hash function is used to convert a key into a location, or index.

A

True.

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

Hashing can be used to provide fast access to data in large datasets.

A

True.

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

Quadratic probing avoids clustering in many cases, but generally, not all hash table slots can be accessed during probing.

A

True.

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

Perfect hashes ensure that there can be no collisions.

A

True.

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

Open hashing allows overflow into lists, removing the need for probing.

A

False.

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

Secondary clustering happens when different keys hash to the same spot and have the same probing sequence; this cannot be fixed by conventional probing.

A

True.

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

Closed hashing stores values that hash to the same space into buckets, then performs probing when those buckets are full.

A

True.

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

Probing functions generally ignore the key.

A

True.

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

Probing functions are not hashing functions.

A

True.

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

A hash function is better if it is cheap.

A

True.

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

Hashing the key twice is called double hashing and it limits the need to perform probing.

A

False.

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

Hash functions can produce different locations for the same key.

A

False.

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

Finding an element in a heap takes theta(n) operations.

A

True.

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

A heap in an array will in general always be full.

A

False.

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

The height of a heap in an array is known if we know how many elements are in it.

A

True.

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

A heap is a tree-based data structure.

A

True.

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

Building a heap from an array can be done in theta(n) operations.

A

True.

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

Finding an element in a heap takes theta(log n) operations.

A

False.

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

A heap can only be implemented using a linked list.

A

False.

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

The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.

A

True.

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

If you add one child to any node that has only one child, and two children to every leaf node, you have added n + 1 nodes.

A

True.

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

Preorder is a traversal of a binary tree where the left child is processed before the parent node, and the right child is processed last.

A

False.

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

If you add one child to any node that has only one child, and two children to every leaf node, you have added n nodes.

A

False.

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

Binary trees must be traversed depth-first.

A

False.

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

Postorder is a traversal of a binary tree where children are processed before the parent node is processed.

A

True.

36
Q

Preorder is a traversal of a binary tree where children are processed after the parent node is processed.

A

True.

37
Q

Heap sort is always faster than merge sort for sorting arrays of integers.

A

False.

38
Q

Heapsort has a space complexity of theta(n).

A

False.

39
Q

Bottom up heapsort has a better asymptotic complexity than top down heapsort.

A

False.

40
Q

Heap sort can be implemented in-place, meaning that it does not require extra memory allocation for its operation.

A

True.

41
Q

Heapsort is faster than quicksort when finding the first 10 values of a large input.

A

True.

42
Q

Heap sort has a worst case time complexity of theta(n log n), the same as its average case complexity.

A

True.

43
Q

Prim’s algorithm guarantees a minimum cost.

A

True.

44
Q

MSTs are free trees with |V| - 1 edges.

A

True.

45
Q

Kruskal’s performs quickly because processing the heap of edges is theta(E log E), but the operational cost c is lower than that used in Prim’s algorithm.

A

False.

46
Q

MSTs can have cycles if the weights on the edges are not distinct.

A

False.

47
Q

Given a connected, undirected, weighted graph, the MST of that graph is still connected and has the minimum total cost when you measure that cost by summing all the weights on the subset of edges kept from the original graph.

A

True.

48
Q

Kruskal’s algorithm is generally more efficient than Prim’s algorithm, but cannot guarantee a minimum cost in some cases.

A

False.

49
Q

(Quicksort) When available, tail recursion eliminates stack overflow caused by pathological pivot selection.

A

True.

50
Q

A pathological case for Quicksort when always selecting the rightmost value as the pivot would be to sort already sorted data.

A

True.

51
Q

(Quicksort) Diverting to heap sort after a certain depth can prevent theta(n^2) complexity in the worst case.

A

True.

52
Q

(Quicksort) When available, tail recursion can prevent theta(n^2) complexity in the worst case.

A

False.

53
Q

With proper pivot selection, quicksort performs in theta(n) in the best case of inputs.

A

False.

54
Q

Quicksort always performs more efficiently than merge sort.

A

False.

55
Q

(Dictionary) Search keys are comparable.

A

True.

56
Q

Asymptotic complexity of Dictionary operations depends on the underlying storage mechanism.

A

True.

57
Q

Dictionaries cannot be used with multi-dimensional arrays, like points (e.g. x,y coordinates).

A

False.

58
Q

Removing a record with an unsorted array-based list as the underlying storage mechanism is of complexity theta(n).

A

True.

59
Q

All possible keys are considered when comparing two records for placement.

A

False.

60
Q

Finding a record with a sorted array-based list as the underlying storage mechanism is of complexity theta(n).

A

False.

61
Q

A max heap, where the key is the priority, is the optimal form of heap for a priority queue.

A

True.

62
Q

Adding/removing nodes and retrieving the highest priority element all have the same complexity for a heap.

A

True.

63
Q

theta(log n) is a realistic complexity to find the next item, for a well written priority queue.

A

True.

64
Q

theta(n log n) is a realistic complexity to find the next item, for a well written priority queue.

A

False.

65
Q

theta(n) is a realistic complexity to find the next item, for a well written priority queue.

A

False.

66
Q

A min heap, where the key is the priority, is the optimal form of heap for a priority queue.

A

False.

67
Q

A heap is the standard BST used in priority queues.

A

False.

68
Q

(Heap sort) Heapifying, or putting the input into its initial heap state is in the class theta(n) in all cases.

A

True.

69
Q

Starting from the end of the array where a heap is stored, it takes theta(n) operations to find the first non-leaf node.

A

False.

70
Q

Finding an element in a heap takes theta(n) operations.

A

True.

71
Q

A heap in an array will in general always be complete.

A

True.

72
Q

A heap is a linear data structure.

A

False.

73
Q

A heap is useful for finding the median element in constant time.

A

False.

74
Q

In the average case, there are 2 and 2/3 comparisons - when sorting 3 numbers.

A

True.

75
Q

Space efficiency in the average case is theta(n^2) - when sorting 3 numbers.

A

False.

76
Q

In the best case, there are only 2 comparisons - when sorting 3 numbers.

A

True.

77
Q

In the average case, there are only 2 comparisons - when sorting 3 numbers.

A

False.

78
Q

In all cases the algorithm is stable - when sorting 3 numbers.

A

False.

79
Q

In the worst case, there are only 3 comparisons - when sorting 3 numbers.

A

True.

80
Q

(Heap) Given the index of a node i, the right Child can be found using 2*(i-1).

A

False.

81
Q

(Heap) Given the index of a node i, the parent of a non-root node can be found using ((i+1)»1) - 1.

A

True.

82
Q

(Heap) Given the index of a node i, the left Child can be found using 2*(i + 1) - 1.

A

True.

83
Q

(Heap) Given the index of a node i, the right Child can be found using 2*(i + 1).

A

True.

84
Q

(Heap) Given the index of node i, the parent of a non root node can be found using (i-1)/2.

A

False.

85
Q

(Heap) Given the index of a node i, the left child can be found using 2*(i+1).

A

False.

Algorithms & Data Structures (5 decks)

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