4.2 Abstract Data Types Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

What is a Data Structure?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is an Abstract Data type?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is an Array?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a text file?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a Static Data Structure?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a Dynamic Data Structure?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is a Stack and how does it work?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a Queue and how does it work?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a Graph and how is it represented?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are the three main types of queues?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are the typical uses of graphs?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a weighted graph?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is an undirected and a directed graph?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A

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

18
Q

What type of data structure is an array?

A

Static data structure

19
Q

What is a Binary file and what are its functions?

A

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

20
Q

What is Stack overflow and underflow?

A

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

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

21
Q

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

A

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

22
Q

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

A

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

23
Q

What is a Tree?

A

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

24
Q

What is a rooted Tree?

A

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

25
Q

What is a Binary Tree?

A

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

26
Q

What are the uses of a rooted Tree?

A

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

27
Q

What is a Hash table and what are its uses?

A

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

28
Q

What is a Hashing algorithm?

A

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

29
Q

What is a collision?

A

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

30
Q

How does chaining fix collisions?

A

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

31
Q

How does Rehashing fix collisions?

A

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

32
Q

What is a dictionary?

A

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

33
Q

What are the applications of Dictionaries?

A

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

34
Q

What is a Vector?

A

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

35
Q

How can a Vectors represent a data structure?

A

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

36
Q

What is Dot product of two vectors?

A

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

37
Q

What is the Application of dot product?

A

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

38
Q

How do you calculate the angle between vectors?

A

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)

39
Q

How do you use convex combinations in two vectors?

What is the expression?

A

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

40
Q

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

A

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)

41
Q

How do you do Vector multiplication?

A

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)