Brainscape's Knowledge GenomeTM

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


See full index

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
Q

Binary search - number of comparisons

A

Ceiling(Lg(n+1))

Round up

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

Bubble sort - number of comparisons

A

1/2(n^2 - n)

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

Optimized bubble sort

A

Terminating the bubble sort during a pass if no swaps are made

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

Selection sort

A

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

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

Selection sort - number of comparisons

A

1/2(n^2 - n)

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

Insertion sort

A

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
Q

Insertion sort - number of comparisons

A

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
Q

Data

A

Term given to pieces of information that can be represented, stored, or manipulated using a computer

33
Q

Data structure

A

Way of organizing data in a computer so that it can be used efficiently

34
Q

Array backward - deletion

A

O(n)

35
Q

Ordered array - deletion

A

O(n)

36
Q

Ordered array - search

A

O(n) or O(lg(n))

37
Q

Array - Average

A 
Access O(1)
Search O(n)
Insertion O(n)
Deletion O(n)
38
Q

Array - Worst

A 
Access O(1)
Search O(n)
Insertion O(n)
Deletion O(n)
39
Q

Array - space complexity

A

O(n) worst

40
Q

Stack - average

A 
Access O(n)
Search O(n)
Insertion O(1) —> push
Deletion O(1) —> pop
41
Q

Stack - worst

A 
Access O(n)
Search O(n)
Insertion O(1)
Deletion O(1)
42
Q

Stack - space complexity

A

O(n) worst

43
Q

Queue - average

A 
Access O(n)
Search O(n)
Insertion O(1)
Deletion O(1)
44
Q

Queue - worst

A 
Access O(n)
Search O(n)
Insertion O(1)
Deletion O(1)
45
Q

Queue - space complexity

A

O(n) worst

46
Q

Simply-linked list - average

A 
Access O(n)
Search O(n)
Insertion O(1)
Deletion O(1)
47
Q

Simply-linked list - worst

A 
Access O(n)
Search O(n)
Insertion O(1)
Deletion O(1)
48
Q

Simply-linked list - space complexity

A

O(n) worst

49
Q

Doubly-linked list - average

A 
Access O(n)
Search O(n)
Insertion O(1)
Deletion O(1)
50
Q

Doubly-linked list - worst

A 
Access O(n)
Search O(n)
Insertion O(1)
Deletion O(1)
51
Q

Doubly-linked list - space complexity

A

O(n) worst

52
Q

Quicksort - time complexity

A 
Best O(nlog(n))
Average O(nlog(n))
Worst (nlog(n))
53
Q

Quicksort - space complexity

A

worst O(log(n))

54
Q

Bubble sort - time complexity

A 
Best O(n)
Average O(n^2)
Worst O(n^2)
55
Q

Bubble sort - space complexity

A

Worst O(1)

56
Q

Insertion sort - time complexity

A 
Best O(n)
Average O(n^2)
Worst O(n^2)
57
Q

Insertion sort - space complexity

A

Worst O(1)

58
Q

Selection sort - time complexity

A 
Best O(n^2)
Average O(n^2)
Worst O(n^2)
59
Q

Selection sort - space complexity

A

Worst O(1)

60
Q

Big-O complexity Chart (worst to best)

A 
O(n!)
O(2^n)
O(n^2)
O(nlogn)
O(n)
O(log n), O(1)
61
Q

Sorted array - average

A 
Search O(log n)
Insert O(n)
Delete O(n)
62
Q

Sorted array - worst

A 
Search O(log n)
Insert O(n)
Delete O(n)
63
Q

Data types

A 
Boolean
Int 
Float
Double
Char
Long
64
Q

Complex data types

A

Composite aggregate types

65
Q

Data type

A

Type + operations

All the possible values of the type and all the things you can do to the type

66
Q

Abstract data type

A

ADT

Values
What things can be done

Implementation details + ADT —> Data Structure

67
Q

Priority Queue

A

High - add front
Low - add back

Enqueue O(n) —> involves search
Dequeue O(n)
68
Q

Infix

A

In middle of operands

69
Q

Postfix

A

After operands (how computer works)

No parenthesis

70
Q

Postfix algorithm

A 
If operand
    Push on stack
Else
    Pop last two
    Evaluate
    Push result onto stack
71
Q

Big-O

A

Used to describe how bad an algorithm is (worst case)

How does algorithm respond with increasing data size

72
Q

Linked list unsorted

A 
Insertion O(1)
Search O(n)
Delete O(n)
Traversing O(n)
73
Q

Linked list ordered

A 
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.
© 2024 Bold Learning Solutions. Terms and Conditions