Data Structures Flashcards

You may prefer our related Brainscape-certified 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 type of array is a linear array?

A

A one-dimensional array.

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

How can you visualise a two-dimensional array?

A

As a spreadsheet or table.

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

How can you visualise a three-dimensional array?

A

A three dimensional array can be 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 also known as?

A

A row in a file.

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

What is a record made up of?

A

A record is made up of fields.

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

How can you select a field from a record using pseudocode?

A

recordName.fieldName.

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

What is the definition of a list?

A

A data structure consisting of a number of items in which the items can occur more than once.

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

What are the main differences between arrays and lists?

A
  • Lists can store data non-contiguously whereas arrays store data in order. - Lists can store data of more than one data type.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a tuple?

A

An immutable ordered set of values of any type.

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

What is the difference between a tuple and an array?

A

Tuples are initialised using regular brackets instead of square brackets.

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

What is a linked list?

A

A dynamic data structure used to hold an ordered set of items which are not stored in contiguous locations.

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

What is the name given to the items in a linked list?

A

Nodes.

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

What does each item in a linked list contain?

A

It contains a data field and another address field called a link pointer.

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

What is a data field in a linked list?

A

A field that stores the actual data.

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

What is a pointer field in a linked list?

A

A field that contains the address of the next item in the list.

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

What is a graph?

A

A graph is a data structure consisting of a set of vertices (nodes) connected by edges (arcs).

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

What is a directed graph?

A

A graph in which the edges can only be traversed in one direction.

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

What is an undirected graph?

A

A graph in which the edges can be traversed in both directions.

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

What is a weighted graph?

A

A graph in which the arcs (edges) have a cost to traverse.

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

Give two ways of representing graphs so that they can be understood by computers.

A

Adjacency Matrix Adjacency List.

22
Q

What are the advantages of using an adjacency matrix?

A
  • Convenient to work with - Easy to add new nodes.
23
Q

What are the advantages of using an adjacency list?

A

Space efficient for large sparse networks.

24
Q

What is a stack?

A

A LIFO (last in first out) data structure where items can only be removed from and added to the top of the list.

25
Q

Give an example of where stacks may be used.

A
  • Back button in a web page -Undo buttons
26
Q

What is a queue?

A

A FIFO (first in first out) data structure where items are added to the end of the queue and removed from the front of the queue.

27
Q

What is a tree?

A

A data structure which has a root node and child nodes connected with branches.

28
Q

What is a node?

A

A node is any item in a tree.

29
Q

What is an edge?

A

An edge is the connection between two nodes.

30
Q

What is the root node?

A

The node which doesn’t have any incoming nodes at the top of the tree.

31
Q

What is a child?

A

Any node which has an incoming edge.

32
Q

What is a parent?

A

Any node which has outgoing edges.

33
Q

What is a subtree?

A

A section of the tree which consists of a parent and all the children of that parent.

34
Q

What is a leaf?

A

A leaf is a node which has no children.

35
Q

What is a binary tree?

A

A type of tree in which each node has a maximum of two children.

36
Q

What is the purpose of a binary tree?

A

A binary tree is used to search for values quickly.

37
Q

What is a hash table?

A

A hash table is an array which is coupled with a hash function.

38
Q

What is a collision?

A

A collision is where two inputs result in the same hashed value.

39
Q

What properties does a good hashing algorithm have?

A

A good hashing algorithm must have a low chance of collision and must be fast.

40
Q

What is pre-order traversal?

A

Traversal algorithm in which you traverse the root node followed by the left subtree then the right subtree.

41
Q

What is in-order traversal?

A

Traversal algorithm in which you traverse the left subtree the root node then the right subtree.

42
Q

What is post-order traversal?

A

Traversal algorithm in which you traverse the left subtree the right subtree followed by the root node.

43
Q

What does the operation isEmpty do?

A

Checks if the list is empty.

44
Q

What does the operation append(value) do?

A

It adds the given value to the end of the list.

45
Q

What does the operation remove(value) do?

A

It finds the first instance of the given value and removes it.

46
Q

What does the operation search(value) do?

A

Searches for the given value in a list.

47
Q

What does the operation length do?

A

Returns the length of the list.

48
Q

What does the operation index(value) do?

A

Returns the index of a value in the list.

49
Q

What does the operation insert(position value) do?

A

Adds the value to the position in the list.

50
Q

What does the operation pop do?

A

Removes the item from the top of the stack.