Comp Exam paper 1

Question 1

What is meant by recursion?

Answer 1

A recursive route is one that is defined in terms of itself

Question 2

How do stacks work?

Answer 2

They store items and follow a last in first out (LIFO) rule. (Like taking from a stack of plates). Used to stored actions so they can be undone.

Question 3

What does pushing the stack do?

Answer 3

Used to add items to the stack. Pushes the top position of the stack up and adds the item to the stack.

Question 4

What does popping the stack do?

Answer 4

Used to remove elements from the stack. Moves the top of the counter down and removes the item.

Question 5

What function has a constant time?

Answer 5

f= O(n^0)

f=O(1)

Question 6

What function has a logarithmic time?

Answer 6

f= O(log n) : The Binary search
List is split into half with one rejected
f = O(n log n) : Merge sort

Question 7

What function has a linear time?

Answer 7

f= O(n) : Linear Search

Checks each element of the list individually

Question 8

What function has a polynomial time?

Answer 8

f= O(n^2) : Bubble sort- swaps item if one is bigger

Question 9

What function has exponential time?

Answer 9

f= O(2^n) : Fibonacci

Question 10

What function has factorial time?

Answer 10

f= O(n!) : Travelling salesman problem

Question 11

What are intractable problems?

Answer 11

Problems that can be solved by a computer, but not in a reasonable amount of time when there are large inputs. (Less than polynomial time)

Question 12

What is an heuristic approach?

Answer 12

A guessed solution can be checked in polynomial time. Problem becomes tractable.

Question 13

What is the halting problem?

Answer 13

An unsolvable problem which asks whether it is possible to create a program which takes another program as an input and determines whether it will halt or loop infinitely.

Question 14

How should you compare Algorithms?

Answer 14

Time complexity: How long it takes to complete a task with a given input
Space complexity: How much memory an algorithm needs to complete a task with a given input
Order of growth: How quickly the complexity grows with growth in input size

Question 15

What is the proof of the halting problem?

Answer 15

def(g):
           If halts(g):
                   loop_forever()
If halts(g) is true, g will call loop forever and will never halt.
If halts(g) is false, g will halt as it doesn’t call loop forever. This is a contradiction.

Question 16

How do queues work?

Answer 16

They follow a first in, first out rule (FIFO). Has a front of queue, end of queue, size of queue and max size of queue.

Question 17

What is a static data structure?

Answer 17

They have a fixed size The allocated memory cannot change at runtime. An example is a static array. Doesn’t have overflow or underflow errors

Question 18

What is a dynamic data structure?

Answer 18

It’s size can grow or shrink at runtime. Often consists of pointers. More efficient use of memory

Question 19

What are the differences between static and dynamic structures?

Answer 19

Static data structures have a fixed maximum size, whereas the size of dynamic data structures can change

Question 20

What does peeking the stack do?

Answer 20

Looks at the previous item in the stack

Question 21

What are trees and graphs?

Answer 21

A way of representing real world problems. It has vertices and edges

Question 22

What is used to models trees and graphs?

Answer 22

Arrays

Question 23

When would you use an Adjacency matrix?

Answer 23

When there are many connections (edges)

Question 24

When would you use an Adjacency list?

Answer 24

When there are few edges(connections)

Question 25

What is a weighted graph?

Answer 25

A graph with edges that are labelled with numbers (a weight)

Question 26

How would you trace a breadth-first search? ⭐️

Answer 26

Use a queue and would find the route with the great vertexes between the start and the end. Finds shortest path for an unweighted graph.

Question 27

How would you trace a depth first search?

Answer 27

Use a stack and exhaustively search each branch to its depth, then back track. Uses less more than breadth first search. Good for navigating a maze.

Question 28

What is the purpose of Dijkstra’s algorithm?

Answer 28

It finds the shortest path between a node and every other node in a weighted graph. Similar to breadth search but uses a priority queue rather than fifo.

Question 29

What are the properties of a tree?

Answer 29

It is a connected, unidirectional graph with no cycles.

Question 30

What is an array?

Answer 30

A data structure that holds similar or related data

Question 31

What is a one dimensional array?

Answer 31

A type of linear array. Good for storing a vector

Question 32

What is a two-dimensional array?

Answer 32

Can be visualised on a grid with rows or columns. Good for representing a matrix