Data Structures Flashcards
What is a data structure?
A way of organising data in a computer so it can be accessed / modified
List the data structures you need to know for the exam
Stack, Queue, Graph, Hash Table, Dictionary
What is an array?
An array is an indexed set of related elements, it allows you to store a finite number of items of the same data type under a common name.
What are the limitations of arrays?
They must store the same data type
They are a static data structure
What is a static data structure?
Where the data structure cannot change in size once it’s been declared
When is a record data structure used?
Is used when you want to group together a collection of related fields under a single name
What is an advantage of records?
They can contain different data types
What are the 3 steps to creating a record?
Define the record, what fields will be in the record
Declare a variable or an array to use
Assign and retrieve data from the variable record
What are lists and tuples and what type of brackets do they use?
They are pythons versions of arrays, lists use square brackets, tuples use round brackets
What are tuples?
Tuples are immutable - they can’t be changed once created
What are lists?
Lists are mutable - they can be edited after creation
Explain the circumstances in which it would be more
appropriate to use an adjacency list instead of an adjacency matrix.
- When graph is sparse
- When edges rarely changed;
- When presence/absence of specific edges does not need to be tested frequently
State one reason why the graph shown in Figure 1 is not a tree.
It contains a cycle / cycles
The graph in Figure 1 is a weighted graph. Explain what is meant by a weighted graph.
A graph where each edge has a weight/value associated with it
What are files composed of?
A file is made up of records which are composed of a number of fields.
What index do arrays/lists start from?
They start from 0
Explain two differences between static and dynamic data structures
- Static data structures can waste storage space, where as dynamic data structures only take up the storage required for the actual data
- Static data structures have a fixed size whereas dynamic data structures can change size
Why is the static implementation less efficient at inserting new items into the list than the dynamic implementation
- It’s not possible to insert items into the middle of the list, so all the items that come after that item must be moved down.
- This is time consuming than the dynamic implementation
How is dynamic data structure implementation achieved
By adjusting pointers when a new item is inserted
How could a static data structure be implemented?
As an ordered list using fixed size array
How could a dynamic data structure be implemented?
As a linked list using dynamic memory allocation
