Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Computer Science > 2 - Fundamentals of Data Structures > Flashcards

2 - Fundamentals of Data Structures Flashcards

1
Q

What is a data structure?

A

Any method used to stored data in an organised and accessible format.

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

What is an abstract data type?

A

A conceptual model of how data can be stored and the operations that can be carried out on it.

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

What is a list/array?

A

A set of related data items stored under one identifier.

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

What are static data structures?

A

When the size and amount of memory put aside for it doesn’t change.

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

What are dynamic data structures?

A

When the size and amount of memory used to store it can vary as the program runs.

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

What are the advantages of static data structures?

A

Fast access, as memory locations are fixed
Easy to implement and use

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

What are the advantages of dynamic data structures?

A

Can optimize storage as size can change
Adaptable.

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

What are the disadvantages of static data structures?

A

Will take up memory even if it doesn’t need to. (Inefficient)
Limited adaptability.

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

What are the disadvantages of dynamic data structures?

A

More complex to implement
Slower access, as memory locations aren’t fixed.

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

How do dynamic data structures work?

A

It uses a heap, which is a pool of unused memory. It can take more memory off the heap if needed and put blocks of unused memory back onto the heap.

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

What is a stack?

A

A Last In First Out structure, meaning the last item to be added is the first to be removed.

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

What is pushing in terms of a stack?

A

Adding a new item of data to the stack.

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

What is popping in terms of a stack?

A

Taking an item off the top of the stack.

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

What is peeking in terms of a stack?

A

Used to identify the item at the top of the stack.

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

What is a stack overflow error?

A

If an item is added and the stack has run out of memory.

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

What is a stack underflow error?

A

If the stack is empty and you try to pop an item.

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

What is a stack frame?

A

Uses stacks to stored information about a running program. (Removes its from the stack when it completes).

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

What does a stack frame contain?

A

Function arguments (parameters/data)
Return address
Saved frame pointer

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

What is a call stack?

A

A stack that keeps track of all active stack fames in a program.

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

When are stack frames used?

A

If an interrupt occurs the program details are stored in a stack frame until the interrupt has been dealt with and then the program can carry on from where it left off.

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

What is recursion?

A

The process of a subroutine calling itself.

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

What is a queue?

A

A first-in-first-out structure.

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

What are uses of queues?

A

Sending data to the CPU
Print queues.

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

What does enqueue do?

A

Adds an item to the rear of a queue.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
What does dequeue do?
Removes and returns the item from the front of the queue.
26
What is a linear queue?
A queue organised as a line of data sequentially, where if the rear pointer is at the last position the queue is full.
27
What are the disadvantages of linear queues?
Can only add or remove a certain number of items. Once elements are dequeued the empty slots are wasted ( inefficient). Underflow and overflow errors.
28
What are the advantages of linear queues?
Easy to implement Predictable behaviour
29
What is a circular queue?
A queue implemented as a circle, where the front and rear pointers can wrap around from the end to the start.
30
What are the disadvantages of circular queues?
Complex implementation Additional isEmpty and isFull logic Harder to debug
31
What are the advantages of circular queues?
Efficient memory utilization, as empty spaces are reused. Efficiently allocates memory Consistent performance
32
How does the isFull function of a circular queue work?
IF (rear+1) MOD maxSize == front THEN Queue is full.
33
How are new indexes calculated for circular queues?
newIndex = (oldIndex + 1 ) MOD maxSize
34
What is a priority queue?
When each item in a queue has a priority associated with it, meaning higher priority items "jump" the queue.
35
What happens in a priority queue when two items have then same priority?
They are handled according to their position in the queue.
36
What is a graph?
A mathematical structure that models the relationships between pairs of objects.
37
What components make up graphs?
Objects called nodes/vertices Connections called edges/arcs.
38
What is a weighted graph?
A graph with a data value labelled on each edge.
39
What is a undirected graph?
When the relationships between vertices are two-way.
40
What is a directed graph?
When the relationships between vertices are one-way.
41
What are the uses of graphs?
Model complex real-life problems, such as transport networks and the Internet.
42
What is an adjacency list?
A data structure that stores a list of nodes with their adjacent nodes to represent graphs.
43
What is an adjacency matrix?
A two-dimensional array, showing when an edge is between a pair of nodes.
44
What are the advantages of adjacency lists?
Only stores data when there is an edge so less memory. Good for sparsely connected graphs. (not many edges)
45
What are the disadvantages of adjacency lists?
Has to identify all adjacencies so increased processing time.
46
What are the advantages of adjacency matrixes?
Adjacencies identified quickly as every combination is stored. Good for dense graphs (many edges)
47
What are the disadvantages of adjacency matrixes?
More memory, as a value for every combination is stored.
48
What is a tree
A rooted, undirected graph with no cycles (unique path from each node to any other node).
49
What is a root?
A starting node, from which other nodes branch off.
50
What is a parent in trees?
A node with further nodes below it.
51
What is a child in trees?
A node with nodes above it in the heirarchy.
52
What is a leaf in trees?
A node without any nodes beneath it.
53
What are the uses of trees?
Inherent hierarchical structure Search and sort algorithms.
54
What is a binary tree?
A rooted, directed tree with no more than two branches off each node.
55
What are the uses of binary trees?
Stored data input in a random order in a sorted order.
56
How do binary trees store data?
The first item of data it the root, if the value of the next data item is less than the node branch less, otherwise branch right.
57
What is a hash table?
A data structure that stores key/value pairs based on an index calculated by an algorithm.
58
What is a hashing algorithm?
An algorithm used on the keys to calculate the index where they should be stored, allowing for data to be retrieved in one step. (efficient).
59
What are the uses of hash tables?
Databases Generates memory addresses for cache memory.
60
What are the 3 hashing algorithms?
index = key MOD NumberOfSlots. index = key^2 -> middle two digits MOD NumberOfSlots. index = add the digits of the key MOD NumberOfSlots.
61
How is the hashing algorithm performed on non-numerical keys?
The ASCII or Unicode values of the keys is used to generate a numerical index.
62
What is a collision in hash tables?
When a hashing algorithm produces the same index for two or more different keys.
63
What is clustering in hash tables?
When indices are not randomly distributed.
64
What is a load factor in hash tables?
The ratio of NumberOfKeys / NumberOfSlots, the higher the value the harder it is to produce a unique result.
65
What is chaining in hash tables?
If a collision occurs a list is created at that slot and the key/value pairs become elements of that list.
66
What is the simplest way of dealing with collisions in hash tables?
Put the key/value pair in the next available slot, however this could lead to clustering. To prevent this increment the "ship" value.
67
What is rehashing?
If a collision occurs a different hashing algorithm is run on the key until a unique address is created.
68
What is a dictionary?
An abstract data type that maps key to data. 2-dimensional structure containing key/value pairs.
69
How are dictionaries implemented?
Requires random access, meaning you can directly access the key without iteration. (can be implemented with a hash table)
70
How can vectors be implemented?
As values stored in a list or elements in a one-dimensional array.
71
What is a function?
A mathematical construct that maps an input to an output.
72
What components make up vectors?
Tail Head Magnitude Direction
73
What is a scaler in context of vectors?
The number representing the amount to scale a vector by. Scaling changes the magnitude, not direction.
74
What is the dot product of vectors?
Combining two vectors to find the angle between them.
75
What is the formula for dot product?
A.B = AxBx + AyBy cos = A.B/ |A|.|B|
76
What is a convex combination?
Multiplying vectors to produce a resulting vector within the convex hull.
77
What is the convex hull?
A spatial representation of the vector space between two vectors.
78
What is the formula for a convex combination?
D = αAB + βAC α, β > 0 α+β=1

Computer Science (12 decks)

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