Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Data Structures > Midterm > Flashcards

Midterm Flashcards

1
Q

Lists - insert (appending at end)

A

Constant O(1)

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

Lists - insertAfter

A

Linear O(n)

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

Lists - search

A

Linear O(n)

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

Lists - sorting

A

O(n^2)

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

Array backward - insert

A

O(1)

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

Arrays - searching

A

O(n)

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

Array - sorting

A

O(n^2)

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

Array - once sorting, searching (ordered array)

A

O(log2(n))

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

Array - sorted all the time, insert

A

O(lg(n))

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

Stacks

A

LIFO

Push O(1)
Pop O(1)
Peep O(1)
IsEmpty O(1) —> look at head (null)
isFull O(1)

Do not support the removal of items from the middle

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

Push

A

Add element to top of stack

Change head

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

Pop

A

Get head

Remove the top item from the stack

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

Peep

A

Without removing say what’s on top

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

Queues

A

FIFO

Enqueue O(1)
Dequeue O(1)

A list in which all insertions take place at one end (back) and all deletions take place at the opposite end (front)

Does not allow the insertion or deletion of items from the middle

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

Enqueue

A

From back

Add new item to the back

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

Dequeue

A

From front

Remove an item from the front

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

Arrays

A

Used to store multiple instance of anything as long as they are all of the same kind

Order is important

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

Linked lists

A

Can grow or shrink as needed

Not necessarily stored in contiguous memory locations

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

First node in a linked list

A

Head

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

Last node in a linked list

A

Tail (link component will always be null)

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

Bubble sort

A

Processes list of items from left-to-right

Repeatedly comparing two neighboring elements (positions i and i+1)

If two neighboring elements are out of order, they are swapped

Continue to next element to the right

Repeat until the end of the list (last element now sorted)

Largest element will bubble to the right

N-1 passes

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

Sequential search

A

Linear search

Process of locating a value in a list by checking each element one at a time until either the value is located or the end of the list has been reached

Not efficient

N/2 comparisons

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

Binary search

A

Process of locating a value in an ordered list of values by repeatedly comparing the value in the middle of the list to the desired value and discarding the appropriate half

Searching terminates when either the desired value is located or the least can no longer be divided in half

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

Binary search - find middle

A

Floor(n/2) + 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Binary search - number of comparisons
Ceiling(Lg(n+1)) Round up
26
Bubble sort - number of comparisons
1/2(n^2 - n)
27
Optimized bubble sort
Terminating the bubble sort during a pass if no swaps are made
28
Selection sort
Processes a list of items from left-to-right Finding the smallest value in the unsorted portion of the list and swapping it with the first value in the unsorted portion Increases sorted portion of list and shrinks the unsorted portion by one value n-1 passes As each pass was made, fewer and fewer elements were compared
29
Selection sort - number of comparisons
1/2(n^2 - n)
30
Insertion sort
Removes the first item from the unsorted portion and marks it as the item to be inserted Works its way from the back to the front of the sorted portion, as each step comparing the item to be inserted with the current item As long as the current item is larger than the item to be inserted, the algorithm continues moving backward through the sorted portion It will either reach the beginning of the sorted portion or encounter an item that is less than or equal to the item to be inserted (inserts the item at the current insertion point) N-1 passes
31
Insertion sort - number of comparisons
N-1 —> best case (first item is in its proper place, list already sorted) 1/2(n^2 - n) —> worst case (reverse order) 1/4(n^2 - n) —> average case (one half of items will be examined) Will be faster
32
Data
Term given to pieces of information that can be represented, stored, or manipulated using a computer
33
Data structure
Way of organizing data in a computer so that it can be used efficiently
34
Array backward - deletion
O(n)
35
Ordered array - deletion
O(n)
36
Ordered array - search
O(n) or O(lg(n))
37
Array - Average
``` Access O(1) Search O(n) Insertion O(n) Deletion O(n) ```
38
Array - Worst
``` Access O(1) Search O(n) Insertion O(n) Deletion O(n) ```
39
Array - space complexity
O(n) worst
40
Stack - average
``` Access O(n) Search O(n) Insertion O(1) —> push Deletion O(1) —> pop ```
41
Stack - worst
``` Access O(n) Search O(n) Insertion O(1) Deletion O(1) ```
42
Stack - space complexity
O(n) worst
43
Queue - average
``` Access O(n) Search O(n) Insertion O(1) Deletion O(1) ```
44
Queue - worst
``` Access O(n) Search O(n) Insertion O(1) Deletion O(1) ```
45
Queue - space complexity
O(n) worst
46
Simply-linked list - average
``` Access O(n) Search O(n) Insertion O(1) Deletion O(1) ```
47
Simply-linked list - worst
``` Access O(n) Search O(n) Insertion O(1) Deletion O(1) ```
48
Simply-linked list - space complexity
O(n) worst
49
Doubly-linked list - average
``` Access O(n) Search O(n) Insertion O(1) Deletion O(1) ```
50
Doubly-linked list - worst
``` Access O(n) Search O(n) Insertion O(1) Deletion O(1) ```
51
Doubly-linked list - space complexity
O(n) worst
52
Quicksort - time complexity
``` Best O(nlog(n)) Average O(nlog(n)) Worst (nlog(n)) ```
53
Quicksort - space complexity
worst O(log(n))
54
Bubble sort - time complexity
``` Best O(n) Average O(n^2) Worst O(n^2) ```
55
Bubble sort - space complexity
Worst O(1)
56
Insertion sort - time complexity
``` Best O(n) Average O(n^2) Worst O(n^2) ```
57
Insertion sort - space complexity
Worst O(1)
58
Selection sort - time complexity
``` Best O(n^2) Average O(n^2) Worst O(n^2) ```
59
Selection sort - space complexity
Worst O(1)
60
Big-O complexity Chart (worst to best)
``` O(n!) O(2^n) O(n^2) O(nlogn) O(n) O(log n), O(1) ```
61
Sorted array - average
``` Search O(log n) Insert O(n) Delete O(n) ```
62
Sorted array - worst
``` Search O(log n) Insert O(n) Delete O(n) ```
63
Data types
``` Boolean Int Float Double Char Long ```
64
Complex data types
Composite aggregate types
65
Data type
Type + operations All the possible values of the type and all the things you can do to the type
66
Abstract data type
ADT Values What things can be done Implementation details + ADT —> Data Structure
67
Priority Queue
High - add front Low - add back ``` Enqueue O(n) —> involves search Dequeue O(n) ```
68
Infix
In middle of operands
69
Postfix
After operands (how computer works) No parenthesis
70
Postfix algorithm
``` If operand Push on stack Else Pop last two Evaluate Push result onto stack ```
71
Big-O
Used to describe how bad an algorithm is (worst case) How does algorithm respond with increasing data size
72
Linked list unsorted
``` Insertion O(1) Search O(n) Delete O(n) Traversing O(n) ```
73
Linked list ordered
``` Insertion O(n) Search O(n) Delete O(n) Traverse O(n) ```

Data Structures (1 decks)

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