Data Structures Flashcards Preview

Paper 1 - Computer Science > Data Structures > Flashcards

Flashcards in Data Structures Deck (21)
Loading flashcards...
1

What is a data structure?

A way of organising data in a computer so it can be accessed / modified

2

List the data structures you need to know for the exam

Stack, Queue, Graph, Hash Table, Dictionary

3

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.

4

What are the limitations of arrays?

They must store the same data type
They are a static data structure

5

What is a static data structure?

Where the data structure cannot change in size once it's been declared

6

When is a record data structure used?

Is used when you want to group together a collection of related fields under a single name

7

What is an advantage of records?

They can contain different data types

8

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

9

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

10

What are tuples?

Tuples are immutable - they can't be changed once created

11

What are lists?

Lists are mutable - they can be edited after creation

12

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

13

State one reason why the graph shown in Figure 1 is not a tree.

It contains a cycle / cycles

14

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

15

What are files composed of?

A file is made up of records which are composed of a number of fields.

16

What index do arrays/lists start from?

They start from 0

17

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

18

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

19

How is dynamic data structure implementation achieved

By adjusting pointers when a new item is inserted

20

How could a static data structure be implemented?

As an ordered list using fixed size array

21

How could a dynamic data structure be implemented?

As a linked list using dynamic memory allocation