Data structures and algorithsm

Question 1

What is a linked list

Answer 1

A dynamic data structure where each node consists of data and a pointer. The pointer gives the location of the next node.

Question 2

What is a tree

Answer 2

A data structure that consists of nodes and sub nodes. The first node is called the root and lines that join nodes are called branches.

Question 3

What is a binary tree

Answer 3

A type of tree where each node has a maximum of two sub nodes. If a child node is less than the parent node, to goes to the left of the parent and if a child node is greater than the parent node is goes to the right of the parent.

Question 4

What is depth-first traversal?

Answer 4

Dept-first traversal is an algorithm for searching a graph/tree. It goes to the left child node when it can and if there is no left child it goes to the right child. When there are no child nodes, the algorithm backtracks to the parent node. It uses a stack.

Question 5

What is breadth-first traversal?

Answer 5

Breadth-first traversal is an alghorithm for searching a graph/tree. It visits all nodes connected directly to the start node, then visits all nodes directly connected to each of those nodes directly connected to each of those nodes and so on. it uses a queue.

Question 6

What are the advantages of depth-first traversal in comparison to breath-fiorst traversal

Answer 6

Depth-first traversal require less memory than breath-first tranversal. It is also quicker if you are looking at deep parts of the tree.

Question 7

What are the disadvantages of depth-first traversal in comparison to breadth-first traversal.

Answer 7

Depth-first isn’t guarateed to find the quickest solution and possibly many never find the solution if we don’t take precautions not to revisit previously visited state.s

Question 8

What is a Stack.

Answer 8

A data structure that operates on a first in last out basis.

Question 9

What is a queue.

Answer 9

A data structure that oerates on a first in first out basis,.

Question 10

What is a hash table?

Answer 10

A data structure that maps keys to values. It uses a hash function to generate the key.

Question 11

What is the difference between an Array and a linked list.

Answer 11

An array is static yet a linked list is dynamic

Elements in arrays can be accessed directly but has to be traversed ina linked list.

Contents of array are stored contiguously in memory nit a linked list might not be.

Question 12

What is meant by a graph structure?

Answer 12

A collection of data (nodes) and connections (edges) are made between nodes. Edges can directional, bi-directional directed or undirected.

Question 13

Define Big O notiation

Answer 13

The Big O notation describes the complexity of an algorithm, It evalutates the worst-case scenario for an algorithm and shows how time/ memory increase as data size increases.

Question 14

What is meant by logarithmic growth in terms the complexity of an algorithm

Answer 14

As the size of an array increases, the rate at which the algorithm runs increases more slowly. This is the inverse of exponential growth, the rate of increase is a logarithmic function of the size of an array.

Question 15

When might a linear search perform better than a binary search?

Answer 15

If the data set is small or if the item being search for is close to the start of the array.

Question 16

What’s the best case for binary search?

Answer 16

If the element you are search for is the first element to be compared to (the midpoint).

Question 17

What’s the best case for linear search?

Answer 17

If the element you are searching or is the first element to be compared to ( the first element in the list).

Question 18

Whats’ the best case for bubble sor?

Answer 18

O(n)

Question 19

What’s the best case for insertion sort?

Answer 19

O(n)

Question 20

What’s the best case for merge sort?

Answer 20

O(n log n)

Question 21

Whats the best case for quick sort?

Answer 21

O( n log n)

Question 22

name an algorithm that has a big O notation of O(1)

Answer 22

Hash function

Question 23

Name an algorithm that has a Big O notation of O(n)

Answer 23

e.g Linear search

Question 24

Name an algoriuthm that has a big O notation of O(n^2)

Answer 24

e.g Bubble sort.

Question 25

Name an algorithm that has a Big O notaƟon

of O(2n)

Answer 25

E.g. Fibonacci sequence

Question 26

Name an algorithm that has a Big O notaƟon

of O(log2n)

Answer 26

E.g. Binary search

Question 27

Name an algorithm that has a Big O notaƟon

of O(n log2n)

Answer 27

E.g. Merge sort

Question 28

How does the linear search algorithm work?

Answer 28

Linear search works by:
Going through each element in the list.
Comparing each element to the target value.
Returning the index of the target value once

found.

Question 29

How does the binary search algorithm work?

Answer 29

Binary search works by: Finding the midpoint of a list.
Comparing the midpoint to the target value.
Returning the midpoint if it is equal to the target
value. Creating a sub‐list from the left if the midpoint
is greater than the target value. Creating a sub‐list
from the right if the midpoint is less than the target
value. Repeating this process until the midpoint is

equal to the target value.

Question 30

How does the bubble sort algorithm work?

Answer 30

Bubble sort works by:

Looking at the first two elements of the list.
Comparing their values. Swapping them if the
second element is smaller than the first
element. Repeating this until no further
changes need to be made.

Question 31

How does the insertion sort algorithm work?

Answer 31

Intersion sort works by:

going through each element of the list.
Comparing its value to each element on the left of the element. Inserting the item in the correct position in the list.

Question 32

how does the merge sort algorithm work?

Answer 32

Merge sort works by:

splitting the list of size n into n number of lists. Comparing values in these lists merging them into temporaty lists.

Question 33

How does the qucik sort algorithm work?

Answer 33

Quick sort works by:

choosing an item as a pivot. Creating two sub-lists, one bigger than the pivot, one smaller.
Comparing each item to the pivot and sorting them accordingly.

Question 34

Name the two path finding algorithms?

Answer 34

Dijkstr’s algorithm and A* algorithm

Question 35

What are the differences between dikstra’s and the A* algorithm

Answer 35

The A* algorithm uses a heuristic value, so finds a path in a faster time. Does not consider all possible paths. Dijkstra’s uses a weightinh value and considers all paths before finding a solution, so may take longer but may find shorter route.