Brainscape's Knowledge GenomeTM

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


See full index

Data Structures > Data Structures 1 > Flashcards

Data Structures 1 Flashcards

1
Q

What is the goal of Hashing?

A

Do faster than O(LogN) time complexity for: lookup, insert, and remove operations. To achieve O(1)

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

What kind of Collection is Hashing?

A

value-orientated.

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

How does Hashing work?

A
  1. you have a key for the item.2. the item’s key gets churned within the hash function to form the Hash index.3. The hash index can be applied to the data array, and so, the specific data is found.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

hash Table:

A

An array that stores a collection of items.

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

Table Size(TS)

A

The Array’s Length

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

Load Factor (LF)

A

Number of items/Table size. For instance, a load factor of 1 = 100% of the items are used.

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

Key

A

Information in items that is used to determine where the item goes into the table.

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

Hash Function

A

A function that takes in the key to compute a specific Hash Index.

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

What would the Perfect Hash Function be?

A

Each Key maps to an unique Hash Index.

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

How do you delete a value within the hash table?

A

You just set Table[hash(Key)] = null

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

How do you look up a value within the hash table?

A

return Table[Hash(key)];

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

How do you insert a value within the hash table?

A

Table[Hash(key)]=data;

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

What is the worst case time complexity for: Insert, lookup, and delete, for hash functions?

A

O(1)

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

If we have UW-Madison student ID’s, and we wanted the ideal hash functions, how would we do it, and why would there be a problem

A

-> We’d simply count each one as an index-> Hash table would be huge.

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

Collisions:

A

When the Hash Function returns the same index for different keys.

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

Good Hash Function qualities:

A
  1. Must be deterministic:-> Key must ALWAYS generate the same Hash Index (excluding rehashing).2. Must achieve uniformity-> Keys should be distributed evenly across hash table.3. FAST/EASY to compute-> only use parts of the key that DISTINGUISH THE ITEMS FROM EACH OTHER4. Minimize collisions:
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Extraction:

A

Breaking keys into parts and using the parts that uniquely identify with the item. 379452 = 394121267 = 112

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

Folding:

A

Combining parts of the key using operations like + and bitwise operations such as exclusive or.Key: 123456789 123 456 789 — 1368 ( 1 is discarded)

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

Weighting:

A

Emphasizing some parts of the key over another.

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

Compressing:

A

Ensuring the hash code is a valid index for the table size.

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

The more items a table can hold, the () likely a collision will happen.

A

less

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

Load Factor

A

Approximately how it’s full… 0.7-0.8.

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

Why do we use prime numbers for table size?

A

We mod often, and prime numbers give us the most unique numbers. (2*ts+1)

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

Steps to resizing:

A
  1. Double table size to nearest prime number2. Re-hash items from old table into the new table.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Rehashing Complexity:

A

O(N)– costly. Carefully select initial TS to avoid re-hashing.

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

Collesion handeling:

A

How you handle the collisions so each element in the hittable stores only one item.

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

Idea of probing:

A

If you have a collision, search somewhere else on the table.

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

Linear Probing:

A

Step size is 1. Find the index, and keep incrementing by one until you find a free space.

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

Quadratic Probing:

A

Probe Sequence is (Hk+1)^2.Minimizes clusteringbetter at distinguishing items across table.

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

Probe Hashing:

A

-> Hash it, and if it leads to a collision, use a separate equation to determine the step size and use that step size to find a new site.

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

Collision Hashing using Buckets

A

-Each element can solre than one item.-throw collisions into a bucket.-buckets aren’t sorted.

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

Array Bucket

A

– a bucket of arrays. -Fixed in size.-size of about 3 work usually well.

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

Chained bucket:

A

+–easy to implement+– buckets can’t overfill+– buckets won’t waste time.+– buckets are dynamically sized.

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

Tree Buckets

A

+–WC = O(logN)+–no wasting space+–dynamically sized– more complicated than what’s needed. –> insert with dups= O(1)–> W/o dups = O(N)

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

HashCode Method:

A

-method of OBJECT class-Returns an int-default hash code is BAD– computed from Object’s memory address. –> must override

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

HashTable & HashMap class

A

java.utilimplements map interfaceK– type paramater for key and v– type parameter for associated valueOperations: lookup, insert, delete.Constructor lets you set init capacity and load factorhandles collisions with chained bucketshash map only allows null for keys and values

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

TreeMap underlying Structure:

A

RBT

38
Q

Treemap complexity of basic operations:

A

O(logN)

39
Q

TreeMap complexity for iterating over associated values:

A

O(N)

40
Q

HashMap underlying structure:

A

HashTable with chained buckets

41
Q

HashMap complexity of basic operations:

A

O(1)

42
Q

Complexity for iterating over associated values:

A

O(T.S + N) –> worst case.

43
Q

data structure

A

a particular scheme organizing related data items.

44
Q

linked list

A

A sequence of zero or more nodes containing some data and pointers to other nodes of the list.

45
Q

list

A

a collection of data items arranged in a certain linear order

46
Q

stack

A

LIFO list in which insertions/deletions are only done at one end.

47
Q

queue

A

FIFO list in which elements are added from one end of the structure and deleted from the other end.

48
Q

priority queue

A

collection of data items from a totally ordered universe

49
Q

graph (formal)

A

G = (V,E). V: finite, nonempty set of vertices. E: set of pairs of V, called edges.

50
Q

If a graph’s edges are unordered [ (u,v) == (v,u)], then the vertices u and v are

A

adjacent

51
Q

If a graph’s edges are unordered [ (u,v) == (v,u)], then the vertices u and v are connected by

A

an undirected edge (u,v).

52
Q

The vertices u and v of the undirected edge(u,v) are the _ of the edge

A

endpoints

53
Q

The vertices u and v of the undirected edge(u,v) are _ to the edge

A

incident

54
Q

A graph is undirected if

A

every edge in it is undirected.

55
Q

If a graph’s edges are ordered [ (u,v) != (v,u)], then the edge (u,v) is _ from _ to _

A

directed from u to v

56
Q

digraph

A

A graph whose every edge is directed

57
Q

for the directed edge (u,v), u is the _ and v is the _

A

u is the tail, v is the head.

58
Q

complete graph

A

a graph with every pair of its vertices connected by an edge

59
Q

dense graph

A

A graph with very few possible edges missing

60
Q

sparse graph

A

A graph with few edges relative to the number of vertices

61
Q

weighted graph

A

A graph with numbers assigned to its edges.

62
Q

weight/cost matrix

A

Adjacency matrix of a weighted graph.

63
Q

A path from vertex u to vertex v

A

a sequence of adjacent vertices that starts with u and ends with v

64
Q

simple path

A

A path in which all vertices are distinct

65
Q

length of a path

A

The total number of vertices in the vertex sequence defining the path - 1.

66
Q

directed path

A

A sequence of vertices (v1,v2,v3,…) such that v1->v2, v2->v3,v3->… for a directed graph.

67
Q

connected graph

A

A graph such that for all vertices u and v, there exists a path from u to v.

68
Q

cycle

A

A path of positive length that starts and ends at the same vertex and does not traverse the same edge more than once.

69
Q

acyclic graph

A

A graph with no cycles.

70
Q

tree

A

A connected, acyclic graph

71
Q

forest

A

A graph that has no cycles, but not necessarily connected

72
Q

The number of edges in a tree

A

One less than the number of vertices

73
Q

Q: For every vertices u, v in a tree, there exists:

A

A: Exactly one simple path from u to v.

74
Q

tree root

A

top level vertex

75
Q

Ancestors of a vertex v in a tree

A

All vertices on the simple path from the root to v

76
Q

Proper ancestors of a vertex v in a tree

A

All vertices on the simple path from the root to v, but excluding v itself.

77
Q

if (u,v) is the last edge of the simple path from the root to vertex v, u is the _ of v

A

parent

78
Q

if (u,v) is the last edge of the simple path from the root to vertex v, v is the _ of u

A

child

79
Q

siblings

A

Vertices of a tree that have the same parent.

80
Q

leaf

A

A vertex with no children

81
Q

parental

A

A vertex with at least one child

82
Q

descendants of v

A

All vertices for which v is an ancestor in a tree

83
Q

subtree of T rooted at v

A

All descendants of a vertex v

84
Q

proper descendants

A

All vertices for which v is an ancestor in a tree, excluding v itself.

85
Q

depth of a vertex v

A

The length of the simple path from the root to v

86
Q

height of a tree

A

the length of the longest simple path from the root to a leaf

87
Q

ordered tree

A

A rooted tree in which all children of each vertex are ordered. (Usually left to right)

88
Q

binary tree

A

An ordered tree in which every vertex has no more than two children, with each child designated as a left or right child. Potentially empty.

89
Q

binary search tree

A

A binary tree with the property that for all parent nodes, the left subtree contains only values less than the parent, and the right subtree contains only values greater than the parent.

90
Q

first child-next sibling representation

A

Representation used for ordered trees with a potentially varying amount of children per parent node.

91
Q

set

A

An unordered collection (possibly empty) of distinct items called elements of the set.

Data Structures (14 decks)

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