cs paper 1...

Question 1

tree

Answer 1

-form of graph
-connected
-undirected
-has no cycles (no path that returns to start node without traversing an edge twice)

Question 2

rooted trees

Answer 2

-root node (at the top)
-root connects to 0/1/more child nodes
-nodes at the bottom are leaf nodes
-nodes connected via edges

Question 3

applications of rooted tree

Answer 3

-storing/ managing file and folder structures
-implementations of A* pathfinding algorithm

Question 4

Binary tree

Answer 4

• rooted tree with 2 children max.
• binary search tree = can be searched quickly and easily for an item,new items easily added and whole tree can be printed out in sequence

Question 5

applications of binary tree

Answer 5

-wireless networking/ router tables
-operating system scheduling processes
-cryptography

Question 6

operations on tree

Question 7

Hash tables

Answer 7

-immediately find an item in a list without need to compare other item
-programming laguages use it to implement a dictionary
-hashing function used to calculate position of an item in a hash table
-needs to be big enough to store all data items, but made bigger to minimise chance of collisions

Question 8

properties of a good hashing function

Answer 8

-be calculated quickly
-result in as few collisions as possible
-use as little memory as possible

Question 9

solving collisions from hashing functions

Answer 9

1. OPEN ADDRESSING = repeatedly check next available space in hash table until empty position is found and store there
   
   • to find item, hashing function delivers start position and then linear search finds items
   • disadvantage is that it prevents other items from being stored at their correct location in hash table
   • disadvantage results in clustering, several positions being filled around common collision values

Question 10

hashing algorithm trade-off

Answer 10

-efficiency of algoritm and size of hash table

Question 11

resolving collisions

Answer 11

-use a two-dimensional hash table
-possible for more than 1 item to be placed in same position
-use 2nd table for collisions, can be searched sequentially
-use a linked list, can be searched sequentially

Question 12

applications of hash tables

Question 13

operations of hash tables

Question 14

breadth first

Answer 14

-node-based method of finding shortest path through a graph
-makes use of queue data strcuture- FIFO
-one node selected at a time, visited and maked, then adjacent nodes are visited and stored in a queue