ComSci fin > 1.4.2. Data Structures > Flashcards

1.4.2. Data Structures Flashcards

(61 cards)

Study These Flashcards
1
Q

What is an array?

A

an ordered, finite set of elements of the same 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

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

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 defenition of a list?

A

a data structure, consisting of a number of items, where the items can occur more than once, mutable, dynamic, non-continguous

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

What are 2 differences between arrays and lists?

A
  1. lists can store data non-coniguously whereas arrays store data in order
  2. lists can store multiple data types
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, tuple is immutable wheras array is mutable

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 store an ordered set of items, in non-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

a data field, and an address field called a 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 data structure consisting of a set of nodes connected by edges

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 where 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 where 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 where the edges have a cost to traverse

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

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

A
  1. adjacency matrix 2. adjacency list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is an advantage of using an adjacency matrix?

A

easy to add new nodes
quicker look up time

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

What is an advantage of using an adjacency list compared to an adjecency matrix?

A

space efficient for large sparse networks

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

What is a stack?

A

a LIFO data structure, where items can only be removed and added to the top of the stack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Give 2 examples of where stacks may be used.
1. back buttons on a web page 2. undo buttons
26
What is a queue?
a FIFO data structure, where items are added to the end of the queue and removed from the front of the queue
27
What is a tree?
a data structure which has a root node, and child nodes connected with branches
28
What is a node?
any item in a tree
29
What is an edge?
the connection between two nodes
30
What is the root node?
the node which does not have any incoming edges, at the top of the tree
31
What is a child?
any node which has an incoming edge
32
What is a parent?
any node which has outcoming edges
33
What is a subtree?
a section of a tree which contains a parent and all of the children of the parent
34
What is a leaf?
a node which has no children
35
What is a binary tree?
a type of tree where each node can have a maximum of two children
36
What is a binary tree used for?
to search for values quickly
37
What is a hash table?
A hash table is an array which is coupled with a hash function. The hash function takes in data (a key) and releases an output (the hash). The role of the hash function is to map the key to an index in the hash table.
38
What is a collision? (hashing)
where two inputs result in the same hashed value
39
What 2 properties does a good hashing algorithm have?
1. must have a low chance of collision 2. must be fast
40
What is a pre-order traversal?
a traversal algorithm where you traverse the root node, followed by the left subtree then the right subtree
41
What is in-order traversal?
a traversal algorithm where you traverse the left subtree, the root node, then the right subtree
42
What is post-order traversal?
a traversal algorithm where you traverse the left subtree, the right subtree then the root node
43
What does the operation isEmpty() do? (lists)
checks if the list is empty
44
What does the operation append(value) do? (lists)
adds the given value to the end of a list
45
What does the operation remove(value) do? (lists)
it finds the first instance of the given value and removes it from the list
46
What does the operation search(value) do? (lists)
searches for the given value in a list
47
What does the operation length() do? (lists)
returns the length of the list
48
What does the operation index(value) do? (lists)
returns the index of a given value in the list
49
What does the operation insert(position, value) do? (lists)
adds the given value to the given position in the list
50
What does the operation pop() do? (lists)
returns and removes the last value in a list
51
What does pop(position) do? (lists)
returns and removes the value at the given position in the list
52
What does the operation isEmpty() do? (stacks)
checks if a stack is empty
53
What does the operation push(value) do? (stacks)
adds the given value to the top of a stack
54
What does the operation peek() do? (stacks)
returns the value at the top of a stack
55
What does the operation pop() do? (stacks)
returns and removes the value at the top of the stack
56
What does the operation size() do? (stacks)
returns the size of the stack
57
What does the operation isFull() do? (stacks)
checks to see if the stack is full
58
What does the operation enQueue(value) do? (queue)
adds the given value to the end of a queue
59
What does the operation deQueue() do? (queue)
returns and removes the item at the front of a queue
60
What does the operation isEmpty() do? (queue)
checks if a queue is empty
61
What does the operation isFull() do? (queue)
checks if a queue is full
ComSci fin
flashcards
Decks in class (25)
# Cards
Brainscape helps you reach your goals faster, through stronger study habits.
© 2026 Bold Learning Solutions. Terms and Conditions