4. Data types, data structures and algorithms

Question 1

What is Polymorphism?

Question 2

What is Binary?

Answer 2

Binary is the representation of data using 0’s and 1’s. If a number is being represented this is called Base-2.

Question 3

What is Hexadecimal?

Answer 3

Hexadecimal is the representation of numbers using Base-16. Hexadecimal is commonly used as a compact representation of large numbers. For example Hexadecimal is used to represent colours, and memory addresses.

Question 4

What is the difference between a Signed and Unsigned number?

Answer 4

A Signed number can store both positive and negative values, an Unsigned number can only store positive values.

Question 5

Define the following data units: bit, byte, Kilobyte (Kb), Kibibyte (Kib), Megabyte (Mb), Mebibyte (Mib), Gigabyte (Gb), Gibibyte (Gib), Terabyte (Tb), Tebibyte (Tib).

Answer 5

bit - a single 0 or 1
byte - 8 bits
Kilobyte (Kb) - 1000 (10^3) bytes
Kibibyte (Kib) - 1024 (2^10) bytes
Megabyte (Mb) - 1,000,000 (10^6) bytes
Mebibyte (Mib) - 1,048,576 (2^20) bytes
Gigabyte (Gb) - 1,000,000,000 (10^9) bytes
Gibibyte (Gib) - 1,073,741,824 (2^30) bytes
Terabyte (Tb) - 1,000,000,000,000 (10^12) bytes
Tebibyte (Tib) - 1,099,511,627,776 (2^40) bytes

Question 6

What is ASCII?

Answer 6

ASCII is the American Standard Code for Information Interchange. It is an encoding of American English characters using a 7-bit Binary encoding. The last bit is used as a Parity Bit. Extended-ASCII uses all 8-bits for encoding a character, doubling the number of available characters.

Question 7

What is Unicode?

Answer 7

Unicode is a character encoding which builds on ASCII by supporting non-American text by using more bits per character. There are 8-bit (UTF-8), 16-bit (UTF-16) and 32-bit (UTF-32) versions.

Question 8

What is an Array?

Answer 8

An Array is an ordered Data Structure which allows multiple values to be stored in a single Variable. Arrays are Static Data Structures, which means they are fixed in size when created. Arrays are highly efficient both in time (O(1)) and space.

Question 9

What is a Record?

Answer 9

A Record is a Data Structure which allows a programmer to store related values together as named Attributes.

Question 10

What is a Tuple?

Answer 10

A Tuple is an immutable ordered collection of values.

Question 11

What is an Abstract Data Type?

Answer 11

An Abstract Data Type describes the behaviour of a Data Structure, but not how that behaviour is implemented.

Question 12

What is the difference between a Static and Dynamic Data Structure?

Answer 12

A Static Data Structure is fixed in size or capacity when it is created, whereas a Dynamic Data Structure can increase in size to fit whatever Data is inserted.

Question 13

What kind of Data Structure is described as First In First Out (FIFO), and what behaviours does it have?

Answer 13

A Queue is First In First Out, the data is removed from a Queue in the same order as it is added.

Data can be Enqueued, inserting at the rear of the Queue.

Data can be Dequeued, removing it from the front of the Queue.

Question 14

Why is a Circular Queue preferable to a Linear Queue?

Answer 14

A Linear Queue is slow to Dequeue (O(n)) because all the data items must be shifted forwards. However, a Circular Queue uses two pointers to implement Dequeue faster (O(1)).

Question 15

How do Priority Queues differ from Normal Queues.

Answer 15

Each inserted item into a Priority Queue has an associated Priority value. Items with higher Priority will be inserted ahead of items with lower Priority. So a Priority Queue is only First In First Out for items of equal Priority.

Question 16

How is a List different from an Array?

Answer 16

An Array is a Static Data Structure, fixed in size when it is created. A List can change in size to fit the contained data. Both are ordered and indexed Data Structures. Depending upon implementation operations on a List may be slower than for an Array.

Question 17

What operations can be applied to a List?

Answer 17

Append - add an item to the end of the List.
Prepend - add an item to the front of the List.
Insert - add an item in the middle of the List.
Delete - remove an item from the List.

Question 18

What kind of Data Structure is Last In First Out (LIFO), and what behaviours does it have?

Answer 18

A Stack is Last In First Out, data is added to the top of the Stack and also removed from the top. Data will be removed in the reverse order to which it is added.

Data can be Pushed onto the top of the Stack.

Data can be Popped from the top of the Stack.

Question 19

What is a Stack Overflow? What is a Stack Underflow?

Answer 19

A Stack Overflow is when there is not enough space left in the Stack to store a new item.

A Stack Underflow is when there is no item to remove from a Stack.

Question 20

What operation are Hash Tables optimised to perform? Why are they good at this?

Answer 20

Hash Tables are quick to search (O(1)). This is because they are indexed using a Hash Function, which means you can quickly find where a value should be stored in the underlying Data Structure.

Question 21

What causes Hash Tables to lose performance?

Answer 21

Hash Tables lose performance when they are too full. This is because as the Hash Table fills up you get more Collisions between stored values. Collisions mean that a value cannot be stored directly where the Hash Function indicates, and a Linear Search will be required to determine if a value is in the Hash Table.

Question 22

Identify the main differences between a Graph and a Tree.

Answer 22

A Tree has a single root node, it is undirected, and has no labels or cycles.

A Graph may be directed, edges may have labels, and it may have cycles.

Question 23

When would you use an Adjacency List as opposed to an Adjacency Matrix to represent a Graph.

Answer 23

Adjacency Lists are better at representing Graphs which are sparse - that is they have few edges in relation to the number of possible connections.