Data types, data structures and algorithms

Question 1

Properties of array

Answer 1

Static/size cannot be changed during processing
Element can be accessed directly
Contents stored contiguously in memory
Array contents are mutable
Holds data of a single type

Question 2

Properties of lists

Answer 2

Dynamic (size can changed)
Can hold data of different types
Ordered (textbook)

Question 3

Properties of tuples

Answer 3

Immutable / cannot be changed at runtime (other than this, same as a list: dynamic, can hold different data types, ordered)

Question 4

What is a linked list (definition only)

Answer 4

Dynamic data structure, each node consists of a data and pointer, pointer gives location of next node

Question 5

Properties of linked list

Answer 5

Dynamic/size can change during processing
Needs to be traversed until desired element is found
Contents may not be stored contiguously in memory (this has been corrected)

Question 6

What is a record (textbook)

Answer 6

A record is a structure used within a database to store data by categories under key fields

Question 7

Properties of records (3, textbook)

Answer 7

-A record is accessed through an attribute (or field).
-Unordered data structure
-Consists of different data types

Question 8

Describe how to access the 2nd item in a linked list

Answer 8

-Go to the first position indicated by the start pointer
-From the first position, read the next pointer value

Question 9

BFT vs DFT (i.e. suitability, performance etc.)

Answer 9

BFT is more efficient when data is closer to root, in general better time complexity
DFT is more efficient when data further down, memory requirement is linear, can be written recursively to aid understanding, in large trees may never return a value

Question 10

Graphs vs trees (at least 4 differences)

Answer 10

Trees have one root node // graphs do not have a root node
Trees do not allow cycles/loops // graphs do allow cycles / loops
Trees store hierarchy // graphs have no hierarchy
Trees are always undirected // graphs can be directed
Trees are always connected // graphs can be connected or disconnected

Question 11

Binary search trees (properties and advantages)

Answer 11

Each node can have a maximum of 2 child nodes
Nodes are ordered (left nodes less than the parent and right nodes greater)
The location to which a node is added depends on its order
Allows for faster searching (O(log n))
Inserting new nodes is faster
Do not need to sort the structure each time a new node is added

Question 12

What are heuristics (AO1)

Answer 12

-Heuristics are used to reduce time taken to solve a problem
-It is a general ‘rule of thumb’ or an educated guess
-It finds a solution which is ‘good enough’ / close to the best solution
-Heuristic is a weight added to a node/decision
-E.g. Description of use such as in A* algorithm as estimate of distance to destination

Question 13

How do heuristics help?

Answer 13

-Heuristics reduce the time complexity as every possibilities within a program does not need to be examined
-Avoid programs running indefinitely - in a computer game there could be too many possibilities so will terminate with a solution faster

Question 14

Uses/applications of heuristics

Answer 14

-Heuristics are more appropriate with complex time-critical tasks - some aspects of game may require faster searching/decisions
-Heuristics are more appropriate with large-scale tasks - game could be large scale and AI algorithms may need to be shortened
-Games are not life-critical, so a good answer is likely enough, a perfect answer is not necessarily required
-Used in AI when the exact steps cannot be pre-programmed and decisions need making

Question 15

Limitations/disadvantages of heuristics?

Answer 15

-Heuristics require skill to implement effectively
-Due to time-saving, they are not always accurate, the solution e.g. shortest path might not be the most efficient

Question 16

What is meant by a character set?
What is the number of values represented by n bits?

Answer 16

-Number of values represented with n bits is 2^n
-Character set means all the characters a computer can understand (1), may include control characters (1), binary code equates to symbols (1), e.g. ASCII (1)

Question 17

What is Unicode?

Answer 17

-Each character is represented by 1-4 bytes
-Supports very large number of characters
-Backward compatible with ASCII

Question 18

What is a D-type flip flop?

Answer 18

Stores a value of one bit when signal is given (specifically on the rising edge according to my fwends, attributions: Toba, Oliver, Yusra)

Question 19

Purpose of head pointer

Answer 19

To identify the first item/element

Question 20

Purpose of tail pointer

Answer 20

To identify the next free space

Question 21

Time complexity for traversing linked list

Answer 21

O(n) or linear complexity

Question 22

Time complexity of recursive algorithm?

Answer 22

O(2^n)

Question 23

Data structure for BFT

Answer 23

Queue

Question 24

Data structure for DFT

Answer 24

Stack

Question 25

Linear search time complexity

Answer 25

Best: O(1) Average: O(n) Worst: O(n)

Question 26

Linear search space complexity

Answer 26

O(1)

Question 27

Binary search time complexity

Answer 27

Best: O(1) Average: O(log n) Worst: O(log n)

Question 28

Binary search space complexity

Answer 28

O(1)

Question 29

Bubble sort time complexity

Answer 29

Best: O(n) Average: O(n^2) Worst: O(n^2)

Question 30

Bubble sort space complexity

Answer 30

O(1)

Question 31

Insertion sort time complexity

Answer 31

Best: O(n) Average: O(n^2) Worst: O(n^2)

Question 32

Insertion sort space complexity

Answer 32

O(1)

Question 33

Merge sort time complexity

Answer 33

Best: O(n log n) Average: O(n log n) Worst: O(n log n)

Question 34

Merge sort space complexity

Answer 34

O(n)

Question 35

Quick sort time complexity

Answer 35

Best: O(n log n) Average: O(n log n) Worst: O(n^2)

Question 36

Quick sort space complexity

Answer 36

O(log n)

Question 37

BFT vs DFT (algorithm itself)

Answer 37

**AO1: Knowledge and Understanding Indicative content** * Breadth first takes first value then visits all nodes connected to it. It then takes all nodes connected to those nodes. * Depth first goes to the left node, this becomes a new tree. It continues going to the left until a leaf. It then returns this, then goes right and repeats from the start. Follow left, follow right, take root.

Question 38

Explain why a quicksort is known as a divide and conquer algorithm

Answer 38

* decomposing data sets into smaller subsets * and then sorting each split subset * until each subset is sorted * and then combining the subsets to provide a solution

Question 39

State the purpose of the constructor

Answer 39

To create an instance of an object from a class