2.3.1 - Algorithms

Question 1

Stack data structure: concept and application

Answer 1

LIFO
Web address stacks
Stack memory (Call stack)

Question 2

Queue data structure: concept and application

Answer 2

FIFO
Printing queues
Multi-level feedback queues

Question 3

Binary tree data structure: concept and application

Answer 3

Root at the top - branches as links - leaves as last nodes
Folder structures (Hierarchical data)
Manipulating sorted lists

Question 4

Linked lists: concept and application

Answer 4

dynamic data structure
non-contiguous memory allocation
each node holds a pointer to the next

Symbol table creation
linked allocation of files

Question 5

Name and explain all traversal algorithms

Answer 5

Pre-order/depth-first = data, left, right
in-order = left, data, right
post-order = left, right, data
breadth first = visit each neighbour using queue

Question 6

Two rules of Big o notation

Answer 6

1. Remove all terms except the one with the largest factor or exponent
2. Remove any constants

Question 7

Explain O(1) notation

Answer 7

Constant complexity

Executes the same amount of time regardless of inputs

Question 8

Explain O(log n)

Answer 8

Logarithmic
Halves the data in each path
Opposite to exponential

Question 9

Explain O(n) notation

Answer 9

Linear complexity

Performance declines as data set grows

Question 10

Explain O(n^2) notation

Answer 10

Polynomial complexity
Performance is proportional to the square of the size of the data set
(Nested iterations)

Question 11

Explain O(2^N) notation

Answer 11

Exponential complexity
Doubles with each addition to the data set
Opposite to logarithmic