Graphs, trees, hash tables(1.4.2 b)

Question 1

What are the three parts of trees?

Answer 1

root nodes
nodes
edges/pointers

Question 2

How many ways in a tree to get from root to subnodes?

Answer 2

one way

Question 3

Tree diagram

Answer 3

Question 4

How many children do binary trees have?

Answer 4

only two

Question 5

Binary tree

Answer 5

all other regular trees apply
every node having two children we terminate the tree at a leaf node

Question 6

Binary tree

Answer 6

Question 7

Uses of binary trees

Answer 7

searching algorithms
sorting algorithms
compression algorithms

Question 8

What are the two parts of graphs?

Answer 8

nodes
edges/pointers

Question 9

Graphs

Answer 9

edges can be weighted, be directed, create cycles
doesn’t have a root node
when using graphs we must define where to start traversing from

Question 10

How does a traversal differ from a search?

Answer 10

returns all values in the tree

Question 11

What does a search return?

Answer 11

only value searching for or not found

Question 12

Breath first traversal

Answer 12

goes from root node and goes down line by line
will print out on order starting at root node and reading nodes from left to right top to bottom

Question 13

Breath first traversal diagram

Answer 13

Question 14

Depth first traversal

Answer 14

start at root node and go left to next node until leaf node then goes back up to next unexplored node

Question 15

Depth first pre order search

Answer 15

reads nodes as first hits its

Question 16

Depth first pre order search diagram

Answer 16

Question 17

Depth first in order search

Answer 17

returns node after all left tree explored

Question 18

Depth first in order search diagram

Answer 18

Question 19

Depth first post order search

Answer 19

return node after all children have been explored
always ends with root

Question 20

Depth first post order search diagram

Answer 20

Question 21

What is hash?

Answer 21

refers to a hashing algorithm an irreversible process

Question 22

Hashing

Answer 22

irreversible
used for hashtables and cryptography
maps arbitary data to a fixed size output
similar inputs provide a very different output

Question 23

What is collision in hashing?

Answer 23

sometimes different inputs can result in the same output

Question 24

How hashtables work

Answer 24

each key value is hashed by going in a hashing algorithm
the result of the hash algorithm turns into the list index of the relevant value

Question 25

Hashtable diagram

Answer 25

Question 26

Why do we use hashtables

Answer 26

no need to search through the array (as arrays get bigger searching takes a lot longer) however we trade time for memory usage (unused space)

Question 27

Hashtable collisions

Answer 27

biggest difficulty dealing with hashtables

Question 28

Linear probing

Answer 28

put the data in the next available space when we are searching for a value that has collided we search down the table until we find the value we're looking for

Question 29

Chaining

Answer 29

each item in the hashtable is part of a linked list we traverse the linked list until we find what we're looking for

Question 30

Overflow table

Answer 30

if we detect a collision we search an overflow table place/find the item in the first available space of the overflow table

Question 31

Choice of hash algorithm

Answer 31

poor hashing algorithm = lots of collision if have lots of collisions we must spend precious time searching for the actual value good hash algorithms take more computation time (and usually have many more possible outputs meaning hashtable is bigger)

Question 32

What are linked lists made up of?

Answer 32

nodes each node has two parts data and pointers pointers identify the next node in the list

Question 33

What is contiguous data?

Answer 33

data stored together in memory

Question 34

Linked lists stored

Answer 34

not stored in contiguously more efficient as it means that items from the list can be stored wherever they fit rather than waiting for a contiguous block of memory to become available

Question 35

Linked list example

Answer 35

location | 1 | 2 | 3 | 4 | 5 node | (a, 1) | (b, 4) | (e, null) | (c, 4) | (d, 2)

Question 36

Doubly linked list

Answer 36

pointers for both next and previous items in the list

Question 37

Circular linked list

Answer 37

last item points to the first item

Question 38

Circular doubly linked list

Answer 38

last item points next to the first item and the first item points previous to the last item

Question 39

Adding to linked list

Answer 39

check that there is enough room in memory to create a new item if not return a error message create a new node containing the data to be added in the next available space traverse the list from the start pointers until the point where the item is to be inserted adjust the pointers so that the previous node points to the new node and the new node points to the next node

Question 40

Removing from a linked list

Answer 40

check the lost is not empty if it is return an error message traverse the linked list until the node to be deleted is found if the required node is not found return an error message adjust the pointer of the previous node to be the new node and the pointer of the deleted node to be null set the first free space pointer to the item to be deleted this indicates that it can be overwritten

Question 41

What is a stack?

Answer 41

a form of linked list that is only accessible at one end at the top

Question 42

Stack

Answer 42

each element in the stack has next pointer to the element below it needs a top pointer (point to the item at the top or the first free space before that item) FILO/LIFO (first in last out/last in first out)

Question 43

What is pushing - stack?

Answer 43

adding to the top of the stack

Question 44

What is popping - stack?

Answer 44

removing items from the top of the stack

Question 45

What is a queue?

Answer 45

a form of linked list that is only accessible of tow locations front and back

Question 46

Queue

Answer 46

each item has a next pointer pointing to the item after it/behind it needs two pointers a front pointer which points to the first node/element and a back pointer which points to ither the last node or the next free space

Question 47

What is enqueue - queue?

Answer 47

can only add items to the back

Question 48

What is dequeue - queue?

Answer 48

can only remove items from the front