Brainscape's Knowledge GenomeTM

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


See full index

Big O Analysis > Data Structures > Flashcards

Data Structures Flashcards

1
Q

What is the time complexity of SEARCH for an ARRAY?

A

O(n) - okay

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

What is the time complexity of INSERTION for an ARRAY?

A

O(n) - okay

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

What is the time complexity of DELETION for an ARRAY?

A

O(n) - okay

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

What is the worst space complexity of an array?

A

O(n) - okay

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

What is the time complexity of ACCESS of a STACK?

A

O(n) - okay

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

What is the time complexity of SEARCH of a STACK?

A

O(n) - okay

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

What is the time complexity of INSERTION of a STACK?

A

O(1) - great

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

What is the average time complexity of DELETION of a STACK?

A

O(1) - great

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

What is the worst space complexity of a STACK?

A

O(n) - okay

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

What is the time complexity of ACCESS of a LINKED LIST?

A

O(n) - okay

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

What is the time complexity of SEARCH of a LINKED LIST?

A

O(n) - okay

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

What is the time complexity of INSERTION of a LINKED LIST?

A

O(1) - great

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

What is the time complexity of DELETION of a LINKED LIST?

A

O(1) - great

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

What is the worst space complexity of a LINKED LIST?

A

O(n) - okay

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

What is the average time complexity of access, search, insertion, and deletion of a SKIP LIST?

A

O(log(n)) - good

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

What is the worst time complexity of access, search, insertion, and deletion of a SKIP LIST?

A

O(n) - okay

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

What is the worst space complexity of a SKIP LIST?

A

O(n log(n)) - bad!

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

What is the time complexity of ACCESS of a HASH TABLE?

A

Not applicable (why?)

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

What is the average time complexity of SEARCH, INSERTION, and DELETION of a HASH TABLE?

A

O(1) - great!

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

What is the worst time complexity of SEARCH, INSERTION, and DELETION of a HASH TABLE?

A

O(n) - okay

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

What is the worst space complexity of a HASH TABLE?

A

O(n) - okay

22
Q

What is the average time complexity of access, search, insertion, and deletion of a BINARY SEARCH TREE?

A

O(log(n)) - good

23
Q

What is the worst time complexity of access, search, insertion, and deletion of a BINARY SEARCH TREE?

A

O(n) - okay

24
Q

What is the worst space complexity of a BINARY SEARH TREE?

A

O(n) - okay

25
Q

What is the average time complexity of ACCESS for a CARTESIAN TREE or a SPLAY TREE?

A

Not applicable (why?)

26
Q

What is the average time complexity of search, insertion and deletion for a CARTESIAN TREE?

A

O(log(n)) - good

27
Q

What is the worst time complexity of search, insertion and deletion for a CARTESIAN TREE?

A

O(n) - okay

28
Q

What is the worst space complexity of a CARTESIAN TREE?

A

O(n) - okay

29
Q

What is the time complexity of access, search, insertion and deletion for a B-TREE?

A

O(log(n)) - good

30
Q

What is the time complexity of access, search, insertion and deletion for a RED-BLACK TREE?

A

O(log(n)) - good

31
Q

What is the time complexity of search, insertion and deletion for a SPLAY TREE?

A

O(log(n)) - good

32
Q

What is the time complexity of access, search, insertion and deletion for a AVL TREE?

A

O(log(n)) - good

33
Q

What is the worst space complexity of a B-TREE?

A

O(n) - okay

34
Q

What is the worst space complexity of a RED-BLACK TREE?

A

O(n)- okay

35
Q

What is the worst space complexity of a SPLAY TREE?

A

O(n) - okay

36
Q

What is the worst space complexity of a AVL TREE?

A

O(n) - okay

37
Q

What is an array?

A

A simple data structure consisting of a collection of elements, identified by at least one array index or key.

[3,5,6,8,2]

38
Q

What is a stack?

A

An abstracted data type which is an ordered collection of elements with two operations, push (adds) and pop(removes last added).

39
Q

What data structures can be used to implement a STACK?

A

Arrays or linked lists.

40
Q

What is a linked list?

A

A data structure consisting of a group of nodes which represent a sequence. Each node consists of data and reference to the next node.

41
Q

What are advantages of linked lists?

A
  1. Dynamic data structure that allocates memory when needed
  2. Insertion and deletion are easy to implement and FAST!
  3. Can create stacks and queues easily.
  4. Reduce access time and can expand in real time without memory overhead.
42
Q

What is a doubly linked list?

A

A linked list where each node contains a reference to the next and previous nodes, allowing forward and backward traversal.

43
Q

What is XOR-linking?

A

It uses bitwise XOR operation to compress the next and previous node address information into a single address field.

44
Q

What are some disadvantages of linked lists?

A
  1. Uses more memory because of pointers needing to store next node info.
  2. Nodes need to be read in order from beginning.
  3. Nodes stored incontiguously (entries are not stored next to each other in memory), which increases time of access.
  4. Reverse traversal of singly-linked lists is cumbersome, and double linked lists take up a lot of space.
45
Q

What is a skip list?

A

A data structure that allows fast search within an ordered sequence of elements. Can be implemented with parallel linked lists.

46
Q

What is a hash table?

A

A data structure that maps keys to values (dictionary, associative array). It uses a hash function that takes a value and assigns an index to it. Usually implemented with arrays.

47
Q

What is a binary search tree?

A

A family of data structures that stores items (numbers, names, etc) in memory in sorted order so look up can use binary search.

48
Q

What is a Cartesian tree?

A

A binary tree derived from a sequence of numbers. It can be constructed in linear time using a stack-based algorithm for finding all nearest smaller values in sequence.

49
Q

What is a red-black tree?

A

A binary search tree which color-codes each node as red or black, which allows for self balancing (height balanced. Enforces property that path from root to farthest leaf is no more than twice as long as path from root to nearest leaf.

50
Q

What is a splay tree?

A

A self-adjusting binary search tree with the property that recently accessed elements are quick to access again, by reorganizing the accessed element to the root.

51
Q

What is an AVL tree?

A

Adelson-Velsky and Landis tree.
Self balancing binary search tree that ensures the heights of two child subtrees of any node differ by at most one. Tree rotations rotate child and node to balance height and distribute children evenly.

52
Q

What is the time complexity of ACCESS for an ARRAY?

A

O(1) - great

Big O Analysis (2 decks)

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