1.4.2 Data structures Flashcards Preview

A Level Computer Science > 1.4.2 Data structures > Flashcards

Flashcards in 1.4.2 Data structures Deck (51)
Loading flashcards...
1

Describe a primitive data type

A data type which is assigned to a variable used to hold a single piece of data

2

Describe a composite or compound data type

A data type which is assigned to a variable used to hold multiple related pieces of data

3

Describe an abstract data type

A conceptual model that describes how data is stored and which operations can be carried out on them

4

Describe what a data structure is

The implementation of an abstract data type in a program

5

Explain what a static data structure is

A set amount of memory locations / size to store data

6

Explain what a dynamic data structure is

Can group data, while also being able to grow in size

7

What is an array data structure?

A data type that holds data that are usually related. It has a fixed size that cannot be changed during running.

8

What is a tuple data structure?

A data structure that cannot mutate, which contains multiple constants

9

Describe a list data structure

A dynamic array

10

Describe a record data structure

A data structure which allows you to make your own data type consisting of different fields

11

Describe a linked list data structure

A list data structure which stores data in the next free space, and links them together with pointers

12

What is a node, for a linked list, and what does it contain?

An individual element of the linked list

Contains the data item and the next address location

13

What are some advantages of a linked list?

  • Flexible structure - pointers can be changed to shape the ordering system
  • Can easily remove nodes, as very few pointers need to be changed

14

What are some disadvantages of a linked list?

  • Slow to check through as it must be started at the beginning and then worked through
  • Hard to update with new nodes, as all previous nodes have to be checked and pointers moved to add the new item
  • Hard to find a specific item, as every node has to be gone through to find it
  • More storage space is required since the pointers also have to be stored

15

Describe a linear queue data structure

FIFO. Pointers point to the start of the queue where items are removed, and to the end where items are added

16

Describe a circular queue data structure

Functions the same as a linear queue, except it reuses the empty spaces at the front of the queue

17

What is the advantage of a circular queue over a linear queue?

After elements are removed, the circular queue can reuse the space left behind

18

Describe a priority queue structure

Each element has a priority value alongside the data, and it is all stored in priority order. This is similar to an ordered linked list.

A new element is added according to its priority value, and the highest priority element is removed first

19

Describe a stack data structure

LIFO. The last item to be added to the stack is the first item to be removed.

20

What is the purpose of the peek() operation?

Returns the item at the top of a stack without removing it

21

What is the purpose of the push() operation?

Adds an element to the top of the stack

22

What is the purpose of the pop() operation?

Removes an element from the top of a stack

23

Describe a tree data structure

A hierarchical structure of data, stored as nodes, with parent nodes branching into children nodes.

24

Define a node in a tree data structure

A unit for data, containing: a sub-tree pointer, the node's data, and pointers to other nodes on the same level

25

Define a parent and child for a tree data structure

Parent: the predecessor node to branching nodes

Child: a node branching from a predeceasing node

26

Describe a binary search tree data structure

A dynamic data structure, which can change size during program running. It can have only 0, 1 or 2 branches from each node

27

What is an advantage of binary search trees over standard root search trees?

Binary trees take a shorter time to search for a particular item than a rooted tree

28

What are the 3 methods of traversing a binary tree?

Preorder traversal

Inorder traversal

Postorder traversal

29

What are the features of a preorder traversal?

Is a 'top down' method

Can be used to duplicate the data to create an identical binary tree

30

Describe a preorder traversal

Pointers are to the left of the node

  • Root visited first
  • Traverses left sub-tree
  • Traverses right sub-tree