Home
Explore
Exams
Search for anything
Login
Get started
Home
CS data structures
CS data structures
5.0
(1)
Rate it
Studied by 2 people
Knowt Play
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Card Sorting
1/53
There's no tags or description
Looks like no tags are added yet.
Study Analytics
All Modes
Learn
Practice Test
Matching
Spaced Repetition
Name
Mastery
Learn
Test
Matching
Spaced
No study sessions yet.
54 Terms
View all (54)
Star these 54
1
New cards
2
New cards
Selection Sort
Selects the largest or smallest element to swap with.
3
New cards
Insertion sort
Inserts the first unsorted element to the front.
4
New cards
Bubble sort
The largest or smallest element bubbles up
5
New cards
Merge sort
Splits the data set in half and merge in order with the auxillary arrays
6
New cards
Quick sort
Makes an element a pivot and sorts it based on it.
7
New cards
Radix sort
Sorts based on the element’s length and content
8
New cards
Heap sort
Maximum or minim numbers get sorted as highest priority
9
New cards
Time complexity for Selection sort
Best case: O(n^2)
Average: O(n^2)
Worst case: O(n^2)
10
New cards
Time complexity for Insertion Sort
Best case: O(n)
Average: O(n^2)
Worst case: O(n^2)
11
New cards
Time complexity for Bubble Sort
Best case: O(n)
Average: O(n^2)
Worst case: O(n^2)
12
New cards
Time complexity for Merge sort
Best case: O(nlogn)
Average: O(nlogn)
Worst case: O(nlogn)
13
New cards
Time complexity for Quick sort
Best case: O(nlogn)
Average: O(nlogn)
Worst case: O(n^2)
14
New cards
Time complexity for Radix sort
Best case: O(n \* k)
Average: O(n \* k)
Worst case: O(n^2)
15
New cards
Time complexity for Heap sort
Best case: O(nlogn)
Average: O(nlogn)
Worst case: O(nlogn)
16
New cards
Linked List
A list of pointers pointing to each other in one way.
17
New cards
Stack
A linked list that goes with “First in, Last out”
18
New cards
Queue
A linked list that goes with “First in, First out”
19
New cards
Set
Unordered collection of elements
20
New cards
Hash table
An array of elements that are inserted based on their hash codes
21
New cards
Binary Search Tree
A data structure that has two children, left ones are smaller and right ones are larger
22
New cards
Maps
Data structure that associates a key with a value
23
New cards
Red-Black Tree
A self-balancing tree that utilizes color codes to balance itself
24
New cards
Node
Building block of a tree
25
New cards
Ancestor
Nodes above the current node
26
New cards
Descendant
Nodes below the current node
27
New cards
Child
A node that is below the current node and is linked left or right
28
New cards
Interior node
Node that is not a leaf
29
New cards
Parent
The previous linked node of the current node
30
New cards
Sibling
The node that is also a child of the current node
31
New cards
Root
Node with no parent
32
New cards
Time complexity for Linked List
Add: O(1), O(n) in middle
Remove: O(1), O(n) in middle
Search: O(n)
33
New cards
Time complexity for Stack
Add: O(1)
Remove: O(1)
Search: O(n)
34
New cards
Time complexity for Queue
Add: O(1)
Remove: O(1)
Search: O(n)
35
New cards
Time complexity for Hash table
Add: O(1)+
Remove: O(1)+
Search: O(1)
Iterate: O(n)
36
New cards
Time complexity for Binary Search Tree
Add: O(logn)/O(n)
Remove: O(logn)/O(n)
Search: O(logn)/O(n)
37
New cards
Time complexity for Heap
Add: O(nlogn)
Remove: O(nlogn)
Search: O(logn)
38
New cards
How much merges would be needed for an array of n length?
N - 1 merges
39
New cards
How many more times would you need to merge if you double the array size of n length?
1 more time
40
New cards
What search to use if you are only searching once?
Linear
41
New cards
What search process to use if you are searching multiple times in an unsorted data set?
Quick sort then binary sort
42
New cards
For insertion sort for sorted lists, if the time to sort 10 items is 4 seconds, the time for 30 items is
12 seconds
43
New cards
What is the Big Oh growth rate of 5000000n + 343242342?
O(n)
44
New cards
Linear search time complexity
O(n)
45
New cards
Binary search time complexity
O(nlogn)
46
New cards
What would be the best data structure to store blocked websites?
Set
47
New cards
Time efficiency to printing out all nodes of a Red-Black tree
O(n)
48
New cards
Time efficiency to printing out all nodes of a Red-Black tree
O(
49
New cards
Adding/removing from a stack/queue array time efficiency
O(1)+
50
New cards
Unordered sets/maps are more efficient than ordered ones
True
51
New cards
What does a good hash function do?
Reduce collisions and makes finding easy
52
New cards
Inorder traversal
Left, center, right
53
New cards
Pre-order traversal
Center, left, right
54
New cards
Post-order traversal
left, right, center
Explore top notes
Adolescent Development: The Self
Updated 924d ago
Note
Preview
Epithelial Tissue
Updated 1027d ago
Note
Preview
Earth Surface Processes
Updated 180d ago
Note
Preview
25. In các số chẵn chia hết cho 3 bé hơn 100
Updated 176d ago
Note
Preview
Chapter 40: Drug Dependence and Drug Abuse
Updated 859d ago
Note
Preview
Honors Biology Midterm Cram Sheet!!
Updated 241d ago
Note
Preview
Chapter 5: Political Violence
Updated 863d ago
Note
Preview
Unit 5: Hereditary
Updated 852d ago
Note
Preview
Explore top flashcards
Cancer Chemotherapy
Updated 587d ago
Flashcards (53)
Preview
GCSE Future Plans
Updated 972d ago
Flashcards (48)
Preview
单元三
Updated 458d ago
Flashcards (37)
Preview
Microbiology Exam 1 Module 2
Updated 671d ago
Flashcards (68)
Preview
Spanish IPA Capítulo 2
Updated 887d ago
Flashcards (103)
Preview
Structure and Functions in living organisms
Updated 432d ago
Flashcards (166)
Preview
Crime and Criminal Justice
Updated 655d ago
Flashcards (30)
Preview
NUR 221- Men's Health
Updated 889d ago
Flashcards (30)
Preview