wds

Question 1

When is adjacency matrix more appropriate to use instead of an adjacency list?

Answer 1

When there are more edges between vertices

Question 2

When is adjacency list more appropriate to use instead of an adjacency matrix?

Answer 2

When there are few edges between vertices

Question 3

What is a graph?

Answer 3

A nonlinear abstract data structure

Question 4

What are two examples of linear data structures?

Answer 4

Queue

Stack

Question 5

What are two examples of non-linear data structures?

Answer 5

Graph

Tree

Question 6

What does a graph consist of and what can they be used to represent?

Answer 6

Consist of vertices and edges

To record relationships between objects

Question 7

What properties must a graph have for it to be a tree?

Answer 7

• No cycles
• Undirected
• Connected

Question 8

Where should I place the dot and number to solve a pre-order traversal?

Answer 8

On the left and use a dotted line around the outside starting from the root

Question 9

Where should I place the dot and number to solve a In-order traversal?

Answer 9

Below - Starting with the left leaf

Question 10

Where should I place the dot and number to solve a post-order traversal?

Answer 10

On the right - Starting from the left leaf

Question 11

What can a programmer do to ‘solve’ an intractable problem?

Answer 11

An algorithm could make an educated guess based on previous data

Question 12

How can a Universal Turning machine be considered as a interpreter?

Answer 12

It reads instructions one at a time and executes the instructions

Question 13

What is representational abstraction?

Answer 13

Removing (unnecessary) details;

Question 14

What is abstraction by generalisation?

Answer 14

Grouping by common characteristics // a hierarchical / ‘kind-of’ relationship;

Question 15

Explain the circumstances when it would be more appropriate to use an adjacency
matrix instead of an adjacency list.

Answer 15

Adjacency matrix appropriate when there are many edges between vertices

When graph/matrix is not sparse;
When edges frequently changed;
When presence/absence of specific edges needs to be tested frequently;

Question 16

What is BNF (Backus-Naur Form)?

Answer 16

A formal mathematical way of defining syntax unambiguously

Question 17

Describe the relationship between regular expressions and FSMs.

Answer 17

Regular language can be defined as any language that a FSM will accept

Question 18

What is Universal Turing Machine?

Answer 18

A Turing machine that can execute the behaviour of any other Turing
machine // can compute any computable sequence

Question 19

What the difference between a local and global variable?

Answer 19

Local variables only be accessed in a subroutine of a program whereas global variables can be assessed from any part of the program

Question 20

Why is it good practice to use local variables?

Answer 20

Less chance of accidently changing the value of a variable

Question 21

Why is reverse polish notation sometimes used instead of infix notation?

Answer 21

• Simpler for a computer to evaluate

- Doesn’t need brackets

Question 22

Describe the halting problem?

Answer 22

Determining if a program will halt without running the program for an particular input

Question 23

Why is it not possible to create a Turing machine that solves the halting problem?

Answer 23

The Halting problem is non-computable and there is no algorithm that solves the Halting problem

Question 24

What components must a Turing machine have?

Answer 24

• Read-write head
• Start state
• Current state
• Finite set of states

Question 25

Why is a Turing machine more powerful than any computer?

Answer 25

Because it has an infinite amount of memory

Question 26

Why is a circular queue better than a linear queue?

Answer 26

• Linear queues can have wasted space that’s not able to be used
• To avoid all items being moved forward when an item is deleted from the queue

Question 27

What is meant by recursively-defined?

Answer 27

A procedure/ subroutine that can call itself

Question 28

What is the big O notation for Bubble Sort, Merge Sort, Binary Search and Linear Search?

Answer 28

O(log n): Binary Search - GOOD
O(n): Linear - DECENT
O(n^2) : Bubble Sort - POOR
O(nlog n): Merge Sort

Question 29

What is the big O notation for bubble sort?

Answer 29

O(n^2) : Bubble Sort - POOR

Question 30

What is the big O notation for merge sort?

Answer 30

O(nlog n): Merge Sort

Question 31

What is the big O notation for Binary Search?

Answer 31

O(log n): Binary Search - GOOD

Question 32

What is the big O notation for Linear Search?

Answer 32

O(n): Linear - DECENT

Question 33

What’s the difference between a static and dynamic data structure?

Answer 33

-Static data structures have storage size determined before program is
run
-Dynamic data structures can grow/shrink during execution

Question 34

What’s the difference between a protected attribute and a private attribute?

Answer 34

A protected attribute can be accessed (within its class and) by derived class instances /
subclasses;
A private attribute can only be accessed within its class;