4.2 Abstract Data Types

Question 1

What is a Data Structure?

Answer 1

A Data Structure is a common format for storing large volumes of related data in an organised and accessible format

Question 2

What is an Abstract Data type?

Answer 2

An Abstract Data Type is a conceptual model of how data is stored and the operations that can be performed upon them

Question 3

What is an Array?

Answer 3

1) An array is a list or table of data consisting of elements with the same data type that has a variable name that identifies the list or table
2) Each item in the table is called an element
3) Can be 1 or 2 Dimensional
5) 1 Dimensional array represents a vector
6) 2 Dimensional Array represents a matrix

Question 4

What is a text file?

Answer 4

1) A text file is an organised collection of records where data is stored in human-readable characters
2) Different items of data stored in a file are referred to as a field

Question 5

What is a Static Data Structure?

Answer 5

1) A static data structure is a method of storing data where the amount of data stored and memory used is fixed

Question 6

What is a Dynamic Data Structure?

Answer 6

1) A dynamic data structure is a way of storing data where the amount of data stored will vary as the program is run
2) Uses heap which is a memory that can be allocated dynamically to a dynamic data structure

Question 7

What is a Stack and how does it work?

Answer 7

1) A stack is an example of a LIFO (Last In First Out) data structure the last item of data added is the first to be removed
2) Works, in the same way, a plate of dishes but no physical movement a stack pointer tracks the top stack position

3) -Adding an item to the stack = Pushing
- Removing item from the stack = Popping
- Identifying the top of the stack = Peeking

4) E.g. Browsers (when you press the previous page button)

Question 8

What is a Queue and how does it work?

Answer 8

1) A queue is a FIFO (First In First Out) data structure where the first item of data entered is the first item of data to leave
2) E.g. in a peripheral such as a Hard Drive sending data to the CPU, if the CPU cant deal with the data straight away then it will be placed in a queue or when a document is sent to a printer

Question 9

What is a Graph and how is it represented?

Answer 9

1) A graph is an abstract data type that can be used to represent complex, non-linear relationships between objects
2) A graph consists of nodes (also called vertices) that are connected by edges (also called arcs)
3) Graphs are usually represented as diagrams with circles that represent the nodes and lines to represent the edges

Question 10

What are the three main types of queues?

Answer 10

There ate three main types of Queue (All FIFO):

1) Linear Queue: Line of Data
2) Circular Queue: Implemented as a Ring
3) Priority Queue: Where some data is left out of sequence

Question 11

What are the typical uses of graphs?

Answer 11

Graphs can be used to represent a wide range of complex data relationships including:

1) Social Networking
2) Transport Networks (tube maps etc)
3) The Internet
4) Electric Circuits

Question 12

What is a weighted graph?

Answer 12

1) A weighted graph is a graph that has data values associated with the edges
2) A weighted graph can be either direct or undirected

Question 13

What is an undirected and a directed graph?

Answer 13

1) An undirected graph is a graph where the relationship between the vertices can go in either direction E..g On a train map

2) A Directed (Diagprah) graph is a graph where the relationship between vertices is one-way E.g. in a family tree
- Arrows were used instead of lines to represent the edges

Question 14

How can an adjacency list be used to represent a graph?

Answer 14

1) An adjacency list is a data structure that stores a list of nodes with their adjacent nodes

2) It can be represented in three different ways:
1) Directed Graph
2) Weighted Graph
3) Undirected Graph

Question 15

How can an adjacency matrix be used to represent a graph?

Answer 15

1) A matrix representation of a graph that stores the edges connecting all possible nodes
2) it is populated with 1’s and 0’s
3) A 1 is put in a cell where there is an edge and a 0 where there is no edge

3) There are again three variations of this graph:
1) Undirected Graph
2) Directed Graph
3) Weighted Graph

Question 16

Compare the uses of an adjacency matrix and an adjacency list?

Answer 16

1) List requires less memory as matrix stores a value for every combination of adjacencies which requires more memory
2) Matrix has faster processing time as all the combinations are already stored a List has to be parsed to find particular adjacencies

Question 17

What are an Adjacency List and Matrix more suited to and what are they called?

Answer 17

1) Adjacency List suited more to where there are fewer edges known as a sparse graph
2) Adjacency Matrix suited where their many edges are known as a dense graph

Question 18

What type of data structure is an array?

Answer 18

Static data structure

Question 19

What is a Binary file and what are its functions?

Answer 19

1) Binary File is organised collection of records where data is stored in binary

2) Functions of Binary File and File:
- Read into a file from a program
- Write data into a file from a program

Question 20

What is Stack overflow and underflow?

Answer 20

1) Stack Overflow: Stack needs more memory than is allocated

2) Stack Underflow: When there is no data to be popped

Question 21

What are the advantages and disadvantages of a static data structure? (6 Points)

Answer 21

1) Fast access of individual elements of data
2) Structure is a fixed size so they are more predictable
3) Memory addresses allocated so quicker access
4) E.g. Records and some arrays
5) Fixed relationship between different elements
6) Takes up memory even if it isn’t needed making it less efficient

Question 22

What are the advantages and disadvantages of a Dynamic data structure?
2 Advantages, 2 Disadvantages

Answer 22

Advantages:
1) More efficient as data needed varies

2) Structures vary in size so need to have a mechanism to know the size of the structure

Disadvantages
3) Slower access to each element as the memory location isn’t fixed

4) Variable relationship between elements of data as a program is run
5) E.g. Stacks, Queues and Binary Trees

Question 23

What is a Tree?

Answer 23

1) A tree is an abstract data structure that is very similar to a graph in that it has nodes and edges
2) It is a hierarchical structure with branches with a root node as all the other nodes branch away from it

Question 24

What is a rooted Tree?

Answer 24

1) A root of a tree is a start node for traversals and it is a tree with a root
2) The root is the only node with no parent and all other nodes are descendants of the roots
3) All other nodes have a parent-child relationship and are descendants of root node
3) A leaf is a node with no children
4) A Parent node is a node that comes directly before another node next to it

Question 25

What is a Binary Tree?

Answer 25

1) A binary tree is a rooted tree where each node has at most two children 2) Binary search tree which is optimised to search it is a rooted tree with ordered nodes

Question 26

What are the uses of a rooted Tree?

Answer 26

1) Can be used to store data that has an inherent hierarchical structure E.g. Operating System uses a tree for dictionaries, files and folders in its file management system

Question 27

What is a Hash table and what are its uses?

Answer 27

1) A hash table is a data structure that creates a mapping between keys and values 2) Made up of two parts - Table of data - A Key identifies the location of the data within the table

Question 28

What is a Hashing algorithm?

Answer 28

1) A hashing algorithm creates a mapping between keys and values 2) Essentially a lookup table that uses a key/value combination

Question 29

What is a collision?

Answer 29

A collision occurs when a Hashing algorithm produces the same index for two or more different keys

Question 30

How does chaining fix collisions?

Answer 30

1) Chaining is a technique for generating a unique index when there is a collision by adding the key/value to a list stored at the same index

Question 31

How does Rehashing fix collisions?

Answer 31

1) The process of running the hashing algorithm again until a unique key is created when a collision occurs 2) This is done through probing where the algorithm searches for an empty slot by looking for the next available slot to the index where there was a clash

Question 32

What is a dictionary?

Answer 32

1) A dictionary is a collection of key-value pairs in which the value is accessed via the associated key 2) An Associative array is a two-dimensional structure containing key/value pairs of data

Question 33

What are the applications of Dictionaries?

Answer 33

1) Information retrieval - Add Data - Retrieve Data - Delete Data - Update Data

Question 34

What is a Vector?

Answer 34

A data structure representing a quantitiy with both magnitude and direction, It can be represented as a list, function or geometric point

Question 35

How can a Vectors represent a data structure?

Answer 35

1) Vectors can be implemented as values that are stored in a list form

Question 36

What is Dot product of two vectors?

Answer 36

Dot product is an operation on two vectors that returns a scalar value. Hence it is sometimes also called scalar product

Question 37

What is the Application of dot product?

Answer 37

1) Dot product of two vectors is used to calculate the angle between the two vectors

Question 38

How do you calculate the angle between vectors?

Answer 38

E.g. Given a = (3,4), a = (2,6) 1) (3 x 2) + (4 x 6) = 30 2) Square root the square of the first numbers 3) Square root of 3 squared + four squared 4) Square root the square of the second numbers 5) square root 2 squared + six squared 6) Multiply the answers 7) Divide answer to 1) and answer of 6) 8) Cos -1 (the answer)

Question 39

How do you use convex combinations in two vectors? What is the expression?

Answer 39

1) Convex combinations of vectors can be used in fields of computer science such as computer games ``` 2) The expression is (a * u) + (B * v) or au + Bv - u and v are both vectors - a + B = 1 - a and B are each greater than equal to 0 ``` 3) If you plot the vectors u and v from the same starting point of origin a new vector from the same start point on the line to the connect u and v tips is made

Question 40

How do you do Vector addition with two vectors with different values

Answer 40

1) Vector Addition: Add value from the first component to the same component of the second vector 2) E.g. a = (5,13) b = (29,5) a + b = ( 5 + 29 + 13 + 5) = (34, 18)

Question 41

How do you do Vector multiplication?

Answer 41

1) Vector Multiplication: Multiply each component by the scalar of the vector 2) E.g. a = (5, 8) by 2 (10, 16) 3) E.g. b = (35, 15) by 0.5 (17.5, 7.5)