Data Structures Flashcards Preview

Paper 1 - Computer Science > Data Structures > Flashcards

Flashcards in Data Structures Deck (21)
Loading 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