Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

OCR Computer Science > 1.4.2 Data Structures > Flashcards

1.4.2 Data Structures Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
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
Q

Give 2 advantages of using an adjacency matrix.

A

Convenient to work with
Easy to add nodes

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

Give an advantage of using an adjacency list.

A

Space efficient for large sparse networks

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

What is a stack?

A

A Last In First Out data structure
Can be implemented as static or dynamic

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

What are stacks used for?

A

Reversing actions

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

What is meant by Last In First Out?

A

Items can only be added to/removed from the top

30
Q

What is a queue?

A

First In First Out data structure

31
Q

What are queues used for?

A

Printers, keyboards & simulators

32
Q

What is meant by First In First Out?

A

Items are added to the end and are removed from the front

33
Q

What is a linear queue?

A

Items are added into the next avaiable space, starting from the front

34
Q

What are 3 features of a linear queue?

A

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
Q

What is a circular queue?

A

Can loop back to the front of the queue and use empty space at front

36
Q

What is a disadvantage of a circular queue?

A

Harder to implement

37
Q

What is a tree?

A

A connected graph with root & child nodes

38
Q

What is a node?

A

Item in a tree

39
Q

What is an edge?

A

Connects two nodes together
Also called branch/arc

40
Q

What is a root?

A

Node with no incoming nodes

41
Q

What is a child?

A

Node with incoming edges

42
Q

What is a parent?

A

Node with outgoing edges

43
Q

What is a subtree?

A

Section of a tree including a parent and its children

44
Q

What is a leaf?

A

Node with no children

45
Q

What is a binary tree?

A

A type of tree where each node has a maximum of two children

46
Q

What is a hash table?

A

An array coupled with a hash function

47
Q

What is pre-order traversal?

A

Follows root node, left subtree, right subtree

48
Q

What is in-order traversal?

A

Follows left subtree, root node, rightsubtree

49
Q

What is post-order traversal?

A

Follows left subtree, right subtree, root node

50
Q

What is the function of isEmpty( ) with a list?

A

Checks if the list is empty

51
Q

What is the function of append(value) with a list?

A

Adds a new value to the end of the list

52
Q

What is the function of remove(value) with a list?

A

Removes the value the first time it occurs in the list

53
Q

What is the function of search(value) with a list?

A

Searches for a value in a list

54
Q

What is the function of length( ) with a list?

A

Returns the length of a list

55
Q

What is the function of index(value) with a list?

A

Returns the position of the item

56
Q

What is the function of insert(position, value) with a list?

A

Inserts a value at a given position

57
Q

What is the function of pop( ) with a list?

A

Returns & removes the last item in the list

58
Q

What is the function of pop(position) with a list?

A

Returns & removes the item at the given position

59
Q

What is the function of enQueue(value) with a queue?

A

Adds a new item to the end of the queue

60
Q

What is the function of deQueue( ) with a queue?

A

Removes the item from the front of the queue

61
Q

What is the function of isEmpty( ) with a queue?

A

Checks if the queue is empty

62
Q

What is the function of isFull( ) with a queue?

A

Checks if the queue is full

63
Q

Describe how a new value is added to a linked list.

A

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
Q

Describe how a value is removed from a linked list.

A

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
Q

What is the function of isEmpty( ) with a stack?

A

Checks if the stack is empty

66
Q

What is the function of push(value) with a stack?

A

Adds a new value to the end of a list

67
Q

What is the function of peek( ) with a stack?

A

Returns the top value from the stack

68
Q

What is the function of pop( ) with a stack?

A

Removes & returns the top value of the stack

69
Q

What is the function of size( ) with a stack?

A

Returns the size of the stack

70
Q

What is the function of isFull( ) with a stack?

A

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.
© 2024 Bold Learning Solutions. Terms and Conditions