1.4.2 Data structures definitions/info

Question 1

What is a stack?

Answer 1

A data structure which follows a last in, first out (LIFO) structure
- holds an ordered, linear sequence of items

Question 2

what is needed to keep track of a stack?

Answer 2

a pointer which points to the top of the stack

Question 3

what is the operation to add an item to a stack?

Answer 3

push - adds an element to the top of a stack

Question 4

what is the operation to remove an item from a stack?

Answer 4

pop - removes an element from the top of the stack

Question 5

what is the peek operation?

Answer 5

returns a copy of the element on the top of the stack without removing it

Question 6

what are the steps for the push operation?

Answer 6

• check if the stack is full
• add an item by incrementing the pointer by 1 and then inserting the item into the array at the pointer

Question 7

what are the steps for the pop operation?

Answer 7

• checks if the stack is empty
• store the item at the top of the stack (at the index equal to the pointer)
• reduce the pointer by 1
• return the item

Question 8

what are the steps for the peek operation?

Answer 8

• return the item at the top of the stack (at the index equal to the pointer)

Question 9

what other functions can there be for a stack?

Answer 9

is_empty - checks if the stack is empty
is_full - checks if the stack is at maximum capacity when stored in a static structure

Question 10

what is a static data structure?

Answer 10

a data structure of fixed size

Question 11

what are the ways a stack can be implemented?

Answer 11

• using a static array
• using a dynamic linked list

Question 12

what is a queue?

Answer 12

a data structure which follows first in, first out (FIFO) structure
- holds an ordered linear sequence of items

Question 13

what is the operation to add an item to a queue?

Answer 13

enqueue - adds an element to the queue

Question 14

what is the operation to remove an item from a queue?

Answer 14

dequeue - removes an element from the front of the queue

Question 15

what is needed to keep track of a queue?

Answer 15

• a pointer at the front
• a pointer at the back/rear

Question 16

what other operations can a queue have?

Answer 16

• is_empty - checks if the queue is empty
• is_full - checks if the queue is full

Question 17

what are the steps for the enqueue operation? (for linear queues)

Answer 17

• check if the queue is full
• increment the back/rear pointer
• add the item to where the back/rear is pointing to
• check if this is the first item to be added to the queue (if the front pointer = -1) and if so, sets the front pointer to 0

Question 18

what are the steps for the dequeue operation? (for linear queues)

Answer 18

• check if the queue is empty
• store the item at the front of the queue in a variable
• increment the front pointer
• return the item

Question 19

what is a circular queue?

Answer 19

a queue which reuses the empty slots at the front of the queue when elements are dequeued

Question 20

how does a circular queue work?

Answer 20

• as items are enqueued, and the rear pointer reaches the last position, it wraps around to point at the start of the array
• as items are dequeued, the front pointer will wrap around until it passes the rear pointer

Question 21

how is the enqueue operation adjusted for circular queues?

Answer 21

• use an additional check to cycle back to the beginning if there is free space

Question 22

how is the dequeue operation adjusted for circular queues?

Answer 22

• use an additional check to cycle to the beginning of the queue

Question 23

what is a priority queue?

Answer 23

a queue where each element in the queue has a priority
when new elements are added into the queue, they are inserted ahead of those with a lower priority and behind those with equal priority.

Question 24

what is a dynamic data structure?

Answer 24

a data structure where the size can change at any time

Question 25

what is a graph?

Answer 25

an abstract data structure that can represent relationships between objects.

Question 26

what does a graph consist of?

Answer 26

nodes (hold the data) edges (represent the relationships)

Question 27

what are neighbours in a graph?

Answer 27

when two nodes are connected by an edge

Question 28

what is the degree of a node?

Answer 28

the number of other nodes that a node is connected to

Question 29

what is a loop?

Answer 29

an edge that connects a node to itself

Question 30

what is a path?

Answer 30

a sequence of nodes that are connected by edges

Question 31

what is a cycle?

Answer 31

a closed path (starts and ends at the same node with no repeats)

Question 32

what are some applications of graphs?

Answer 32

- social networking - transport networks - the internet - the world wide web

Question 33

what is an undirected graph?

Answer 33

a graph where you can traverse in either direction between nodes

Question 34

what is a directed graph?

Answer 34

a graph where the edges have a direction

Question 35

what is a weighted graph?

Answer 35

a graph that has values associated with the edges

Question 36

what is a tree?

Answer 36

a graph that: - has no cycles - must be connected

Question 37

what does a tree having no cycles mean?

Answer 37

there is only one possible path between any two nodes

Question 38

what is the root of a tree?

Answer 38

the start node for traversals rooted trees have roots

Question 39

what is a branch?

Answer 39

a path from the root to an end point

Question 40

what is a leaf?

Answer 40

an end point on a tree - a leaf node has no other nodes attached to it except 1

Question 41

what is the height of a tree?

Answer 41

equal to the number of edges that connect the root node to the leaf node furthest from it

Question 42

what is a binary tree?

Answer 42

a tree which: - has a root node - every node must have at most two child nodes

Question 43

what is a binary search tree?

Answer 43

a rooted tree where the nodes are ordered

Question 44

how does the binary search tree algorithm work?

Answer 44

- set the current node to the root node - use a while loop to check if we have reached a leaf node - if the data in the current node is greater than the search item, we go to the left - if the data in the current node is less than the search item, we go right - if the data in the current node = the search item, return true - if a leaf node is reached, return false

Question 45

what is a breadth first traversal?

Answer 45

a traversal which goes along the horizontal layers of a graph/tree

Question 46

how does a breadth first traversal work?

Answer 46

- visit the root node - visit all nodes attached to the root node - move to the first node attached to the starting node and repeat, visiting the nodes attached to this node

Question 47

what does a breadth first traversal use to store nodes?

Answer 47

a queue stores visited nodes

Question 48

what are the different types of depth first traversal?

Answer 48

pre-order in-order post-order

Question 49

how does a pre-order traversal work?

Answer 49

visit, left, right

Question 50

how does an in-order traversal work?

Answer 50

left, visit, right

Question 51

how does a post-order traversal work?

Answer 51

left, right, visit

Question 52

what is used to store previous nodes in a depth first traversal?

Answer 52

a stack

Question 53

what is a linked list?

Answer 53

a dynamic data structure which has links to sort the data

Question 54

how is an item added to an unordered linked list?

Answer 54

- insert data into the next available free node

Question 55

how is an item added to an ordered linked list?

Answer 55

- create a new node - traverse the list to find the correct position - set the pointer of the new node to the pointer of the pointer of the current node - set the pointer of the current node to the pointer of the new node

Question 56

what is the free pointer used for?

Answer 56

it is used to point to the next available free location

Question 57

what are the steps to search a linked list?

Answer 57

- set current to the head pointer - use a while loop to continue code until the end of the linked list - check if the current node = data - return true if true - increment current to the next pointer if not - return false if the while loop breaks