Brainscape's Knowledge GenomeTM

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


See full index

ADE > Linked Lists & Sorting Algorithms > Flashcards

Linked Lists & Sorting Algorithms Flashcards

1
Q

What is the complexity for inserting at the head in a singly linked list?

A

O(1)

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

What is the complexity for removing at the head in a singly linked list?

A

O(1)

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

What is the complexity for inserting at the tail in a singly linked list?

A

O(1)

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

What is the complexity for removing at the tail in a singly linked list?

A

O(n)

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

What changes between a singly linked list and a double linked list?

A

The complexity for deletion at the tail is now reduced to O(1)

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

What is the basic idea of bubble sort?

A

Cycle through the array over and over again until no swaps are made. You take two elements next to each other, and you compare them. If the swap triggers, you then perform it and move on, otherwise you move on regardless. This repeats until no swaps are made in a single loop.

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

What is sorting ‘stability’?

A

A sort is stable if it preserves the original order of duplicate elements i.e. 3, 2, 2’, 1 would be sorted into 1, 2, 2’, 3. If it preserved the order of two and two prime, then it is stable, otherwise it is unstable.

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

What is the complexity of bubble sort?

A

Worst case complexity - O(n^2)

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

What is the basic idea of selection sort?

A

Similar to bubble sort, but on each scan, you remember what element has to be swapped and then move it at the end of the scan/loop directly to the spot.

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

What is the complexity of selection sort?

A

O(n^2)

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

What is the basic idea of insertion sort?

A

Keep the front of the list sorted, and then as you move through the back, we insert elements from there into the correct place at the front

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

What is the complexity of insertion sort?

A

In worst case, also O(n^2), but in best case, O(n)

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

What is the complexity of bubble sort on linked lists?

A

Also O(n^2)

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

What is the complexity of selection sort on linked lists?

A

Also O(n^2)

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

What is a preorder traversal regarding linked trees?

A

A node is visited before its descendants

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

What is a postorder traversal in linked trees?

A

A node is visited after its descendants

17
Q

What is a proper binary tree?

A

Each internal node has either two children or no children
The children of a node are an ordered pair

18
Q

What is an arithmetic expression tree?

A

Binary tree associated with an arithmetic expression:
internal nodes - binary operators
external nodes - operands

19
Q

What is a decision tree?

A

A linked tree which has connections associated with a decision process

20
Q

What is an inorder traversal with a linked tree?

A

A node is visited after its left subtree and before its right subtree
In simple terms, goes from left to right

21
Q

How is a linked tree actually stored?

A

For each node, it will have a segment for the node data, a segment which refers to the previous node, and possibly a third segment which leads to the next node/s if it has any

22
Q

How is a node stored in a linked tree?

A

A node stores its data, its parent node, and if it is applicable, both its left and right child nodes

23
Q

What is an ADT?

A

Abstract Data Type - specifies the data stored, the operations on the data, and the error conditions associated with operations

24
Q

What are CDTs?

A

Concrete Data Types - specifies the actual data structure that will be used
The choice of CDT will affect the runtime and space usage

25
Q

How are nodes stored in an array-based representation of binary trees?

A

The root node takes arr[1]
Then, if it is a left child - rank(node) is 2 x rank(parent node)
If it is a right child - rank (node) is 2 x rank (parent node) + 1

26
Q

What are the properties of a perfect binary tree?

A

It is said to be ‘proper’ i.e. full, if every internal node has exactly two children
It is perfect if it is proper and all leaves are at the same depth, hence all depths are full

27
Q

What is the time complexity of binary trees?

A

O(height)

28
Q

What is the height and size of the tree calculated as?

A

Height of the tree is logarithmic in the size of the tree
Size of the tree is exponential in the height of the tree

29
Q

What is the height of an arbitrary binary tree of size n?

A

If tree is perfect, then it has Big-Theta(log(n))
If tree is imperfect, then it is Big-Omega(log(n))
Hence, for a general binary tree on n nodes, the height is Big-Omega(log(n)) and Big-Oh(n)

30
Q

What is the height of a merge-sort tree?

A

It is O(log n)

31
Q

What is the overall amount of work done at all the nodes at depth i?

A

O(n)

32
Q

What is the total running time of merge sort?

A

O(n log n)

33
Q

What is quick sort (three-way split) and how does it work?

A

A randomised sorting algorithm based on the divide-and-conquer paradigm.
Picks a random element (x), also called the pivot, and partitions the main array into:
L - elements less than x
E - elements equal to x
G - elements greater than x
Then, sorts L and G, and finally joins all three

34
Q

What is different between quick sort (2-way split) and quick sort (three-way split)?

A

Instead of less than, equal and greater than, 2-way split combines equal and greater than into one subarray. Aside from that, it works in exactly the same way

35
Q

When splitting the array apart for quick sort, what is the run complexity?

A

O(n)

36
Q

How does partitioning array ‘in-place’ work?

A

Select a random pivot, and then, using two indices, do a two-way split. Then, each element keeps ‘moving towards the middle’. The left indice only stops when they find an element greater than or equal to the pivot, whereas the right indice does the opposite and stops only when the element found is smaller than the pivot.

37
Q

What is the worst-case and best-case running time for quick sort?

A

O(n^2) - worst case
O(n log n) - best case

ADE (8 decks)

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