Linked Lists & Sorting Algorithms

Question 1

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

Answer 1

O(1)

Question 2

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

Answer 2

O(1)

Question 3

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

Answer 3

O(1)

Question 4

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

Answer 4

O(n)

Question 5

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

Answer 5

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

Question 6

What is the basic idea of bubble sort?

Answer 6

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.

Question 7

What is sorting ‘stability’?

Answer 7

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.

Question 8

What is the complexity of bubble sort?

Answer 8

Worst case complexity - O(n^2)

Question 9

What is the basic idea of selection sort?

Answer 9

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.

Question 10

What is the complexity of selection sort?

Answer 10

O(n^2)

Question 11

What is the basic idea of insertion sort?

Answer 11

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

Question 12

What is the complexity of insertion sort?

Answer 12

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

Question 13

What is the complexity of bubble sort on linked lists?

Answer 13

Also O(n^2)

Question 14

What is the complexity of selection sort on linked lists?

Answer 14

Also O(n^2)

Question 15

What is a preorder traversal regarding linked trees?

Answer 15

A node is visited before its descendants

Question 16

What is a postorder traversal in linked trees?

Answer 16

A node is visited after its descendants

Question 17

What is a proper binary tree?

Answer 17

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

Question 18

What is an arithmetic expression tree?

Answer 18

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

Question 19

What is a decision tree?

Answer 19

A linked tree which has connections associated with a decision process

Question 20

What is an inorder traversal with a linked tree?

Answer 20

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

Question 21

How is a linked tree actually stored?

Answer 21

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

Question 22

How is a node stored in a linked tree?

Answer 22

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

Question 23

What is an ADT?

Answer 23

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

Question 24

What are CDTs?

Answer 24

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

Question 25

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

Answer 25

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

Question 26

What are the properties of a perfect binary tree?

Answer 26

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

Question 27

What is the time complexity of binary trees?

Answer 27

O(height)

Question 28

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

Answer 28

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

Question 29

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

Answer 29

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)

Question 30

What is the height of a merge-sort tree?

Answer 30

It is O(log n)

Question 31

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

Answer 31

O(n)

Question 32

What is the total running time of merge sort?

Answer 32

O(n log n)

Question 33

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

Answer 33

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

Question 34

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

Answer 34

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

Question 35

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

Answer 35

O(n)

Question 36

How does partitioning array 'in-place' work?

Answer 36

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.

Question 37

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

Answer 37

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