1.4.2) Data Structures

Question 1

what is an array?

Answer 1

An ordered, finite set of elements of a single type

Question 2

What is a record?

Answer 2

A row in a file, made up of fields (eg. 001, Anthony, anthony@gmail.com)

Question 3

what is a list?

Answer 3

A data structure consisting of a number of orders items where the items can occur more than once, can contain more than one datatype

Question 4

what is a tuple?

Answer 4

an audit set of values of any type, is immutable so cannot be changed, use regular brackets not square

Question 5

What is a linked list?

Answer 5

A dynamic data structure used to hold an aud sequence

Question 6

how does linked list work?

Answer 6

Each piece of data has an index, the data and a pointer. The pointer indicates the next item in the list. The start pointer shows the algorithm where the beginning of the list is.

Question 7

How do you append to a linked list?

Answer 7

change the other data values pointers

Question 8

What is a disadvantage of storing pointers?

Answer 8

they waste memory, items cannot be directly accessed

Question 9

What is a graph?

Answer 9

A set of vertices/nodes connected by edges/arcs.

Question 10

What are the three different types of graph?

Answer 10

Directed graph, undirected graph, weighted graph

Question 11

what is the directed graph?

Answer 11

Graph where the edges can only be traversed in One Direction

Question 12

What is an undirected graph?

Answer 12

when the edges can be traversed in both directions

Question 13

what is a weighted graph?

Answer 13

When a cost is attached to each edge

Question 14

what is an adjacency matrix?

Answer 14

A matrix storing graphs using a table (each node is given a row and column)

Question 15

what is an adjacency list?

Answer 15

A way of storing graphs where each node stores a list where it states its connections to other nodes (eg A:{B:4, C:6})

Question 16

Advantages of an adjacency matrix

Answer 16

convenient to work with due to quicker access times, easy to add nodes

Question 17

Advantage of adjacency list

Answer 17

more space efficient for large sparse networks

Question 18

What structure does a stack have?

Answer 18

Last in first out

Question 19

What are some real life examples of stacks?

Answer 19

Going back a page in the web browser, undo buttons

Question 20

what is a static vs dynamic stack?

Answer 20

Static stack – has a fixed size (preferable as more efficient)
Dynamic – has a flexible size

Question 21

what functions are available when manipulating a stack?

Answer 21

Push, peak, pop

Question 22

What does the push function do? What must be checked before use?

Answer 22

add a value to the top of the stack, stack must be checked to see if it’s full

Question 23

what does the peek function do?

Answer 23

Return the top value from the stack

Question 25

what does the pop value do?

Answer 25

Removes and returns the top value of the stack

Question 26

what structure do queues follow?

Answer 26

first in first out

Question 27

where are queues often used?

Answer 27

Printers, keyboards

Question 28

what is a linear queue?

Answer 28

a queue where items are added to the next available space starting from the front, items are removed from the front of the queue, pointers are used to indicate the front and back of queue

Question 29

what is a circular queue?

Answer 29

The same as a linear except once the pointer reaches the maximum size of the queue it loops back to the beginning provided it’s empty

Question 30

disadvantage of a circular queue

Answer 30

Harder to implement

Question 31

What are the functions for queues?

Answer 31

enQueue, deQueue

Question 32

what are trees?

Answer 32

A form of graph with a root node which connects to all other nodes using branches

Question 33

What is a node (trees)?

Answer 33

An item in the tree

Question 34

What is an edge (tree)?

Answer 34

Connect to nodes together, also known as a branch or arc

Question 35

what is a root(tree)?

Answer 35

A single node, which does not have any incoming nodes

Question 36

what is a child (tree)?

Answer 36

A node with incoming edges

Question 37

what is a parent(tree)?

Answer 37

a node with incoming edges

Question 38

What is a sub tree?

Answer 38

A subsection of a tree consisting of a parent and all the children of a parent

Question 39

What is a leaf?

Answer 39

A node with no children

Question 40

What is a binary tree?

Answer 40

A tree where each node has a maximum of two children

Question 41

What are binary trees used for?

Answer 41

To represent information for binary searches, making it easy to search through

Question 42

What are the three methods of traversing a binary tree?

Answer 42

Pre-order, in order, post order

Question 43

What is pre order traversal?

Answer 43

pre drinks, walking with head stuck to the left

Question 44

what is in order traversal?

Answer 44

like a photocopier from left to right

Question 45

what is post order traversal?

Answer 45

i’ve gotta post this! looking at something in the distance (to the left) alllll the time

Question 47

What is a hash table?