Fundamentals of Data Structures - Notes

Question 1

Abstract data types

Answer 1

They make use of other data structures to form a new way of storing data

Question 2

Advantage of using adjancency list

Answer 2

Memory Efficient as only stores the edges that exist in the graph

Question 3

Disadvantage of adjancency list

Answer 3

Time ineffiecient as slow to query, as each item in a list must be searched sequentially until the desired edge is found

Question 4

Disadvantage of using adjancency matrix

Answer 4

Memory ineffiecient as stores every possible edge between nodes, even those that dont exist and half of the graph is repeated

Question 5

Advantage of using adjancency matrix

Answer 5

Time effiecient as allows a specific edge to be queried very quickly, as it can be looked up by its row and column

Question 6

What is a dictionary

Answer 6

A collection of key value pairs in which the values is accessed by its associated key.

Question 7

How do dynamic data strucutres work

Answer 7

Each item of data is stored in the structure alongside a reference to where the next item is stored in memory. If the number of data items exceeds the number of memory locations allocated to the strucutre, new memory locations are simply added to the structure until there is enough space for the data.

Question 8

Describe the steps of rehashing

Answer 8

A larger hash table is created
Each value in the existing table is inserted into the new table
In a position determined by a new hashing algorithm

Question 9

Explain how a value is stored in a hash table

Answer 9

Hashing algorithm applied to the key
The result is an index of where to store the value in an array
It is possible that the hashing algorithm might generate the same key for two different values which is called a collision

Question 10

Why is hashing used

Answer 10

So that searching, adding and deleting can be done efficiently