Brainscape's Knowledge GenomeTM

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


See full index

Data Structures > Data Structures 3 > Flashcards

Data Structures 3 Flashcards

1
Q

Array: access, search, insert, delete

A

Access: O(1)Search: O(n)Insert: O(n)Delete: O(n)

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

Array: memory

A

Memory: O(n)

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

Array: advantage, disadvantage

A

Advantage: quick insert, quick access if index is knownDisadvantage: slow search, slow delete, fixed size

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

Doubly Linked List: access, search, insert, delete

A

Access: O(n)Search: O(n)Insert: O(1)Delete: O(1)

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

Doubly Linked List: memory

A

Memory: O(3n) (LL: O 2n)

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

Doubly Linked List: advantage, disadvantage

A

Advantage: quick insert, quick deleteDisadvantage: slow search

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

Binary Tree: advantage, disadvantage

A

Advantage: quick search, delete, insertDisadvantage: complex deletion

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

of elements in a binary tree

A

2^(# of rows)

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

Heap: advantage, disadvantage

A

Advantage: quick insert, quick delete, access to largest itemDisadvantage: slow access to all other items

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

Heap Binary Tree: access, search, insert, delete,

A

Access: O(1)Search: O(n)Insert: O (lg n) Best case: sorted arrayDelete: O (lg n)

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

Heap Binary Tree: max-heapify, build-max-heap, heap-sort

A

Max-heapify: O(n)Build-max-heap: O(n)Heap-sort: O(n lgn)

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

Heap Binary Tree: memory

A

Memory: O(n)

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

Heap Binary Tree: definition

A

A binary tree with two additional constraints:Shape - complete treeHeap property - max/min heap

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

Heap Binary Tree: advantage, disadvantage

A

Advantage: fast access, quick insert and deleteDisadvantage: slow search, efficient memory if full

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

Heap-sort: definition

A

Array size doesn’t change, but heap size doesTake off bottom, reshuffle, repeatLess efficient than max-heapify because it sorts from the top instead of the bottom

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

Binary Search Tree: search, insert, delete

A

Search: O(h) / balanced, O(lg n)Insert: O(h) / balanced, O(lg n)Delete: O(h) / balanced, O(lg n)

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

Binary Search Tree: max, min, successor, predecessor

A

Max: O(h)Min: O(h)Successor: O(h)Predecessor: O(h)

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

Binary Search Tree: property

A

value[left[x]] <= value[x]value[right[x] >= value[x]

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

Binary Search Tree: memory

A

Memory: O(n)

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

Binary Search Tree: advantage, disadvantage

A

Advantage: quick search, quick insert and deleteDisadvantage: slower than hash table

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

Height of binary tree

A

number of edges on the longest downward path between the root and a leaflog(n) - complete binary tree

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

Node height

A

number of edges on the longest downward path between node and a leaf

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

Node depth

A

number of edges on the longest downward path between node and the root

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

Tries: advantage, disadvantage, memory

A

Advantage: faster search than a hash table, no collisions, no hash function needed, quick insert and deleteDisadvantage: can take up more space than a hash tableMemory: A LOT - need empty memory for every possibility

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

Tries: definition

A

Key-value storage; a kind of treeKey -not- stored in node, value stored in nodeNode variables : Boolean isNode, String value, array Edges

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

Heap Priority Queue: insert, max, extract max, increase value

A

Heap-insert: O(lg n)Heap-maximum: O(1)Heap-extract-max: O(lg n)Heap-increase-value: O(lg n)

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

Priority Queue: advantage, disadvantage

A

Advantage: cheap way to sort priorities, sometimes you want to do things firstDisadvantage: worse at inserting and searching than BST

28
Q

BST Priority Queue: insert, max, extract max, increase valye

A

BST-insert: O(h)BST-maximum: O(h)BST-extract-max: O(h)BST-increase-value: O(h)

29
Q

Red Black Tree: search, insert, delete

A

Search: O(lg n)Insert: O(lg n)Delete: O(lg n)

30
Q

Red Black Tree: max, min, successor, predecessory

A

Max: O(lg n)Min: O(lg n)Successor: O(lg n)Predecessor: O(lg n)

31
Q

Red Black Tree: memory

A

Memory: O(n)

32
Q

Red Black Tree: height

A

Height: O(lg n)

33
Q

Red Black Tree: properties

A
  1. Every node is either red or black2. The root is black3. Every leaf (NIL) is black4. If a node is red, then both its children are black5. All simple paths from node to child leaves contain the same # of black nodes
34
Q

Red Black Tree: advantage, disadvantage

A

Advantage: quick insert, delete, and searchDisadvantage: complex implementation

35
Q

Black height

A

of black nodes, including nil, on the path from given node to a leaf, not inclusive; any node with height h has black-height >= h/2

36
Q

Dictionary: definition

A

A data structure that maps keys to values.

37
Q

Direct-access table: definition

A

An element key k is stored in slot k.

38
Q

Direct-access table: memory

A

Memory: O(n)

39
Q

Direct-access table: search

A

Search: O(1)

40
Q

Direct-access table: advantage, disadvantage

A

Advantage: quick search, quick insert and deleteDisadvantage: lots of wasted memory, keys must be unique, keys should be dense

41
Q

Hash tables: memory

A

An implementation of a dictionary.Memory: O(n)

42
Q

Hash tables: search, insert, delete

A

Search: O(1-n)Insert: O(1-n)Delete: O(1-n)

43
Q

Hash collision

A

two (or more) keys hash to same slot

44
Q

Chaining

A

make each slot is the head of a linked list

45
Q

ArrayLists: insert

A

Insert: often O(1), sometimes more

46
Q

ArrayLists: advantages, disadvantages

A

Advantage: advantages of an array, plus does not run out of spaceDisadvantage: inserting can be slower than an array

47
Q

Stack: definition

A

Last in, first out.

48
Q

Stack: advantage, disadvantage

A

Advantage: quick accessDisadvantage: inefficient with an array

49
Q

Graph: definition

A

Finite set of vertices connected by edges, directed or not.

50
Q

Graph: advantage, disadvantage

A

Advantage: best models real-world situationsDisadvantage: can be slow and complex

51
Q

Adjacency list: memory

A

“Memory: O(|V|+|E|) “

52
Q

Adjacency list: add vertex/edge, delete vertex/edge

A

Add vertex: O(1)Add edge: O(1)Delete vertex: O(|E|)Delete edge: O(|E|)

53
Q

Adjacency list: query for adjacency

A

Query for adjacency: O(|V|)

54
Q

Adjacency matrix: memory

A

“Memory: O(|V|^2) “

55
Q

Adjacency matrix: add vertex/edge, delete vertex/edge

A

Add vertex: O(|V|^2)Add edge: O(1)Delete vertex: O(|V|^2)Delete edge: O(1)

56
Q

Adjacency matrix: query for adjacency

A

Query for adjacency: O(1)

57
Q

Breadth-first search

A

Visits the neighbor vertices before visiting the child verticesOften used to find the shortest path from one vertex to another.A queue is usually implemented

58
Q

Depth-first search

A

Visits the child vertices before visiting the sibling verticesA stack is usually implemented

59
Q

Java stream: definition

A

a sequence of data

60
Q

Exception handling

A

When there’s an error, the program makes an error object and passes it off to the runtime system, which looks for a method in the call stack to handle it.

61
Q

O(1)

A

O(1) = happens once

62
Q

O(lg n)

A

happens for up to the height of a balanced tree

63
Q

O(n)

A

happens for each element

64
Q

Θ-notation

A

asymptotically tight bound

65
Q

O-notation

A

asymptotic upper bound

66
Q

Ω-notation

A

asymptotic lower bound

Data Structures (14 decks)

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