Flashcards
Graphs, Trees and Hash Tables
Cards in this deck (24)
- 1What is a tree?a hierarchal non-linear data structure with data related to the data above it in the tree. Loops are not permitted
- 2What do trees help overcome?a tree helps fit data that cannot fit into a linear data structure.
- 3what are some uses of trees?- manipulating hierarchal data (eg. moves in games)
- making info easy to search
- manipulation of sorted lists
- finding dupes in a list of numbers - 4what is different about a binary tree?- each node has a max of 2 sub nodes
- contains a left pointer, right pointer and data - 5what does traversal mean?'visiting'
- 6what does a tree traversal mean?using a method of visiting each node until all have been visited
- 7what are graphs?non-linear data structures which have collections of data that are connected with edges. These can be undirected or directed and loops are permitted
- 8what are the uses of graphs?- computer networks ( nodes -> computers, edges -> bandwidth)
- social networks
-webpages and links
- project management (nodes -> tasks, edges -> time)
-maps (nodes -> cities, edges -> distance) - 9what are the two ways to traverse a graph?depth-first traversal and breadth-first traversal
- 10How does breadth-first traversal work?It uses a stack.
-Visit all nodes connecting to the start node and follow the route as far as you can go.
- Backtrack and visit a second node as go as far as you can.
- Repeat until all nodes are visited. - 11How does a depth-first traversal work?Using a queue.
- visit all nodes directly connected to the start
- visit all nodes connected to those nodes
- repeat until all nodes have been visited - 12name the differences between a tree and a graph- a tree only has one path between nodes, graphs can have multiple.
- A tree has a root node, graphs do not.
- In trees, loops are not permitted.
- trees are less complex
- trees feature in, post and pre order traversals
- trees have a hierarchal model whereas graphs have a network model. - 13Why is an array having its own index useful?This means we can access any position in the array randomly
- 14Why can arrays not grow?As they are fixed and static
- 15What does 'linked lists are dynamic' mean?They can grow/shrink in size
- 16Why are linked lists dynamic?As they do not hold their data in memory
- 17Why are linked lists bad for accessing data?Because we cannot access data randomly like in an array. This can be very inefficient
- 18Why are hash tables a mix of both arrays and linked lists?They combine the benefits, meaning they are good for accessing data at random points but can grow or shrink in size.
- 19What is a hash table?A hash table is a dynamic data structure where data is stored/accessed in a random order. Data is stored in an array and a hash function is used to generate an appropriate address where the data will be stored. If the data already exists, it will overflow into a linked list.
- 20Why is a hash table easy to use?It uses a key (a piece of code that takes in data), carries out a calculation and outputs the answer as a hash value. This will point to the array address of the data that is searched for. The same key will generate the same hash value meaning it is easy to find things.
- 21What is a poor hash function?A simple hash function will generate more clashes. These will be stored in the linked lists. Therefore this will take longer to search for as linked lists are searched linearly.
- 22What is a good hash function?Duplicate hash values are inevitable but can be reduced, leading to reduced amount of linked list data and less clashes.
- 23What are some advantages of hash tables?- even if the amount of data in the hash table is increased, the amount to search will stay the same
- any position of the hash table can be accessed quickly
- can grow or shrink in size - 24What are some disadvantages of hash tables?- In order to search, you need the key to be hashed -> could take time
- as hash table grows, increased chance of collisions
- if collisions occur, linked lists used, slower to search
- if linear probing is used, can be quite slow as it searches for an empty slot
Information
- Description
- A level Computer Science Flashcards on Graphs, Trees and Hash Tables, created by Ariana Parr on 17/10/2021.
- Created by
- Ariana Parr
- Views
- 2
- Rating