data structures

Question 1

stack

Answer 1

data can be added or removed from one location - the TOP of the stack

LIFO (last in first out) structure

Question 2

stack operations

Answer 2

push() - add an item to the top of the stack
pop() - take an item from the top\

Question 3

limitations on stack operations

Answer 3

cant push if stack full
cant pop if stack empty

Question 4

how push() stack operation is carried out

Answer 4

push - add an item at the top pointer and then move the top pointer up by one

Question 5

how pop() stack operation is carried out

Answer 5

pop - return the value at the top pointer then move the top pointer down by one

Question 6

evaluate the stack

Answer 6

traverse or insert is not possible

big-O value of all stack operations is one

no wasted space

Question 7

when stack is used

Answer 7

• undo button
• recursive function

Question 8

queue

Answer 8

data can be added at the end/ tail of the queue

can be removed at the front/ head of the queue

FIFO ( first in first out) structure

Question 9

queue operations

Answer 9

Enqueue - add item to end of queue
Dequeue - take an item from front of queue

Question 10

how enqueue() queue operation is carried out

Answer 10

add an item at the end marker
move it forward by one

Question 11

how dequeue() queue operation is carried out

Answer 11

return value at front marker and move it forward by one

Question 12

limitations of queue operations

Answer 12

• queue moves along in available space as changes are made
• to avoid running out of space it can be made circular. if the end of the queue catches up w the front, no more items can be added

Question 13

evaluate queue

Answer 13

traverse insert not possible

big- O value of all queue operations is 1

no wasted space

Question 14

when queue is used

Answer 14

print queue

Question 15

linked list

Answer 15

made of nodes
each node contains an item of data and a pointer to the next node

Question 16

how to traverse a linked list

Answer 16

start at header
follow pointers until reach node with no pointers

Question 17

how to insert items to a linked list

Answer 17

add the item in an empty space
change pointers to include item in the list

Question 18

how to delete items from a linked list

Answer 18

change pointers so that the list skips over the deleted item

Question 19

What does the free space pointer do

Answer 19

computer remembers the location of an empty storage space
this is where new nodes can be added

after adding a new node the free space pointer is updated

Question 20

evaluate linked list

Answer 20

• wide range of operations possible. traverse, search , insert, sort, delete etc.
• most operations have O(n) - linear complexity, making the linked list slower than a stack or queue

Question 21

when to use a linked list

Answer 21

list data type in python

Question 22

tree data structure

Answer 22

made of nodes
each node holds one data value and more than one pointer

Question 23

parts of a tree data structure

Answer 23

root - start value
branches - nodes to left and right of root
leaf node- a node with no branches

Question 24

binary tree

Answer 24

made of nodes with two pointers

Question 25

binary search tree

Answer 25

a type of binary tree where data is added in a predictable way so it can be found easily

Question 26

How is data added to a binary search tree

Answer 26

Compare the value to the root value

If it is less go to the left branch

If it is larger go to the right branch

Continue to travel left or right until you find an empty location to add the value

Question 27

How can you find data in a binary search tree

Answer 27

Compare the value you are looking for to the root value

If it is less go to the left branch

If it is larger go to the right branch

Continue to travel left or right until you find the value.

If you find an empty location the value is not in the tree.

Question 28

What are the two ways of traversing a tree

Answer 28

Breadth-first traversal

Depth-first traversal

Question 29

Breadth-first traversal of a tree

Answer 29

Start at the root, output the value

Visit the branches, left then right, output each value in turn

Visit each level in turn, going from left to right across the tree

Question 30

Depth-first traversal of a tree

Answer 30

Start at the root but do not output any value until you have output the left and right nodes in that order

That means you will start at the bottom left of the tree

Visit each branch in order left then right then root

Work upwards until you return to the root node, which is the final value

Question 31

Describe the map data structure

Answer 31

A map is made of nodes with data and a variable number of pointers

The nodes are connected, but they do not make a regular pattern. There is no root node.

Question 32

Parts of a map

Answer 32

Each node may be called a vertex (plural vertices)

The connections may be called edges

Question 33

weighted map

Answer 33

a map with weight values added to the edges – these weights represent the distance (or effort or cost of moving) between nodes

Question 34

directed vs undirected graph

Answer 34

A directed graph has one-way connections, an undirected graph has two-way connections

Question 35

What is the purpose of Dijkstra’s algorithm

Answer 35

Dijkstra’s algorithm will find the shortest route between two nodes in a map – that is the route with the smallest total weight or distance

Question 36

What are the steps of Dijkstra’s algorithm

Answer 36

-start node is active node
i-dentify every node you can get to from active node
-enter the route and total distance into the table. If there’s a shorter route there do not replace it
- find the node which is the shortest distance from the start- becomes the active node
- repeat until route to end node is found

Question 37

How is A star different from Dijkstra

Answer 37

The A* algorithm is the same as Dijkstra but it uses a heuristic value

The heuristic value represents the distance from each node to the end point

Question 38

Evaluate the benefits and limitations of the A star algorithm

Answer 38

A* is an improvement on Dijkstra because it finds the same route as Dijkstra but with less working out

Question 39

How does the A* algorithm find the route

Answer 39

All the steps are the same as Dijkstra, except when the time comes to choose the next active node

Find the total value for each node by adding the route from the start node and the heuristic value

Choose the node with the lowest total value as the next active node