Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

OCR Computer Science > 1.4.2 Data Structures > Flashcards

1.4.2 Data Structures Flashcards

(70 cards)

Start Studying
1
Q

What is an array?

A

An ordered, finite set of elements of a single type

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is meant by a 1D array?

A

A linear array

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is meant by a 2D array?

A

Visualised as a table/spreadsheet

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is meant by a 3D array?

A

Visualised as a multi-page spreadsheet

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a record?

A

A row in a database
Made up of fields

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a list?

A

A finite, ordered set of elements
Items can occur more than once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

How are lists initialised?

A

With square brackets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a tuple?

A

An ordered set of values of any data type

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How are tuples initialised?

A

With regular brackets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Are static data structures mutable or immutable?

A

Immutable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Are dynamic data structures mutable or immutable?

A

Mutable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What does immutable mean?

A

Size of a structure is defined at run-time and cannot change

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What does mutable mean?

A

Size of a structure is defined at run-time and is able to change

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Which data structures are static?

A

Arrays
Stacks
Queues
Trees

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Which data structures are dynamic?

A

Lists
Linked lists
Trees
Hash tables

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is a linked list?

A

Holds an ordered sequence

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Describe how linked lists are stored.

A

Items do not have to be in contiguous data locations
Each node contains a data field & a link or pointer field

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is the data field of a node?

A

Actual data associated with list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is the pointer field of a node?

A

Address of the next item in list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is a graph?

A

Set of vertices/nodes connected by edges/arcs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is a directed graph?

A

Edges can only be traversed in one direction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is an undirected graph?

A

Edges can be traversed in both directions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is a weighted graph?

A

Each edge has a cost attached

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

How are graphs implemented?

A

Adjacency matrix or adjaceny list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Give 2 advantages of using an adjacency matrix.
Convenient to work with Easy to add nodes
26
Give an advantage of using an adjacency list.
Space efficient for large sparse networks
27
What is a stack?
A Last In First Out data structure Can be implemented as static or dynamic
28
What are stacks used for?
Reversing actions
29
What is meant by Last In First Out?
Items can only be added to/removed from the top
30
What is a queue?
First In First Out data structure
31
What are queues used for?
Printers, keyboards & simulators
32
What is meant by First In First Out?
Items are added to the end and are removed from the front
33
What is a linear queue?
Items are added into the next avaiable space, starting from the front
34
What are 3 features of a linear queue?
Items are removed from front of the queue Uses two pointers, front/back Uses space inefficiently as positions cannot be reused once data has been removed
35
What is a circular queue?
Can loop back to the front of the queue and use empty space at front
36
What is a disadvantage of a circular queue?
Harder to implement
37
What is a tree?
A connected graph with root & child nodes
38
What is a node?
Item in a tree
39
What is an edge?
Connects two nodes together Also called branch/arc
40
What is a root?
Node with no incoming nodes
41
What is a child?
Node with incoming edges
42
What is a parent?
Node with outgoing edges
43
What is a subtree?
Section of a tree including a parent and its children
44
What is a leaf?
Node with no children
45
What is a binary tree?
A type of tree where each node has a maximum of two children
46
What is a hash table?
An array coupled with a hash function
47
What is pre-order traversal?
Follows root node, left subtree, right subtree
48
What is in-order traversal?
Follows left subtree, root node, rightsubtree
49
What is post-order traversal?
Follows left subtree, right subtree, root node
50
What is the function of isEmpty( ) with a list?
Checks if the list is empty
51
What is the function of append(value) with a list?
Adds a new value to the end of the list
52
What is the function of remove(value) with a list?
Removes the value the first time it occurs in the list
53
What is the function of search(value) with a list?
Searches for a value in a list
54
What is the function of length( ) with a list?
Returns the length of a list
55
What is the function of index(value) with a list?
Returns the position of the item
56
What is the function of insert(position, value) with a list?
Inserts a value at a given position
57
What is the function of pop( ) with a list?
Returns & removes the last item in the list
58
What is the function of pop(position) with a list?
Returns & removes the item at the given position
59
What is the function of enQueue(value) with a queue?
Adds a new item to the end of the queue
60
What is the function of deQueue( ) with a queue?
Removes the item from the front of the queue
61
What is the function of isEmpty( ) with a queue?
Checks if the queue is empty
62
What is the function of isFull( ) with a queue?
Checks if the queue is full
63
Describe how a new value is added to a linked list.
Add the new value to the end of the linked list Update the "NextFree" pointer The pointer field of the value to come before the new value is updated to the position of the new value The pointer field of the new value is updated to the position of the value to come after the new value
64
Describe how a value is removed from a linked list.
Update the pointer field of the value before the word to be removed to the value stored in the pointer field of the word to be removed
65
What is the function of isEmpty( ) with a stack?
Checks if the stack is empty
66
What is the function of push(value) with a stack?
Adds a new value to the end of a list
67
What is the function of peek( ) with a stack?
Returns the top value from the stack
68
What is the function of pop( ) with a stack?
Removes & returns the top value of the stack
69
What is the function of size( ) with a stack?
Returns the size of the stack
70
What is the function of isFull( ) with a stack?
Checks if the stack if full and returns a Boolean value

OCR Computer Science (29 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions