Brainscape's Knowledge GenomeTM

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


See full index

Computer Science > Fundamentals of Data Structures > Flashcards

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
Q

What does dequeue do?

A

Removes and returns the item from the front of the queue.

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

What is a linear queue?

A

A queue organised as a line of data sequentially, where if the rear pointer is at the last position the queue is full.

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

What are the disadvantages of linear queues?

A

Can only add or remove a certain number of items.
Once elements are dequeued the empty slots are wasted ( inefficient).
Underflow and overflow errors.

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

What are the advantages of linear queues?

A

Easy to implement
Predictable behaviour

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

What is a circular queue?

A

A queue implemented as a circle, where the front and rear pointers can wrap around from the end to the start.

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

What are the disadvantages of circular queues?

A

Complex implementation
Additional isEmpty and isFull logic
Harder to debug

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

What are the advantages of circular queues?

A

Efficient memory utilization, as empty spaces are reused.
Efficiently allocates memory
Consistent performance

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

How does the isFull function of a circular queue work?

A

IF (rear+1) MOD maxSize == front THEN
Queue is full.

33
Q

How are new indexes calculated for circular queues?

A

newIndex = (oldIndex + 1 ) MOD maxSize

34
Q

What is a priority queue?

A

When each item in a queue has a priority associated with it, meaning higher priority items “jump” the queue.

35
Q

What happens in a priority queue when two items have then same priority?

A

They are handled according to their position in the queue.

36
Q

What is a graph?

A

A mathematical structure that models the relationships between pairs of objects.

37
Q

What components make up graphs?

A

Objects called nodes/vertices
Connections called edges/arcs.

38
Q

What is a weighted graph?

A

A graph with a data value labelled on each edge.

39
Q

What is a undirected graph?

A

When the relationships between vertices are two-way.

40
Q

What is a directed graph?

A

When the relationships between vertices are one-way.

41
Q

What are the uses of graphs?

A

Model complex real-life problems, such as transport networks and the Internet.

42
Q

What is an adjacency list?

A

A data structure that stores a list of nodes with their adjacent nodes to represent graphs.

43
Q

What is an adjacency matrix?

A

A two-dimensional array, showing when an edge is between a pair of nodes.

44
Q

What are the advantages of adjacency lists?

A

Only stores data when there is an edge so less memory.
Good for sparsely connected graphs. (not many edges)

45
Q

What are the disadvantages of adjacency lists?

A

Has to identify all adjacencies so increased processing time.

46
Q

What are the advantages of adjacency matrixes?

A

Adjacencies identified quickly as every combination is stored.
Good for dense graphs (many edges)

47
Q

What are the disadvantages of adjacency matrixes?

A

More memory, as a value for every combination is stored.

48
Q

What is a tree

A

A rooted, undirected graph with no cycles (unique path from each node to any other node).

49
Q

What is a root?

A

A starting node, from which other nodes branch off.

50
Q

What is a parent in trees?

A

A node with further nodes below it.

51
Q

What is a child in trees?

A

A node with nodes above it in the heirarchy.

52
Q

What is a leaf in trees?

A

A node without any nodes beneath it.

53
Q

What are the uses of trees?

A

Inherent hierarchical structure
Search and sort algorithms.

54
Q

What is a binary tree?

A

A rooted, directed tree with no more than two branches off each node.

55
Q

What are the uses of binary trees?

A

Stored data input in a random order in a sorted order.

56
Q

How do binary trees store data?

A

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
Q

What is a hash table?

A

A data structure that stores key/value pairs based on an index calculated by an algorithm.

58
Q

What is a hashing algorithm?

A

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
Q

What are the uses of hash tables?

A

Databases
Generates memory addresses for cache memory.

60
Q

What are the 3 hashing algorithms?

A

index = key MOD NumberOfSlots.
index = key^2 -> middle two digits MOD NumberOfSlots.
index = add the digits of the key MOD NumberOfSlots.

61
Q

How is the hashing algorithm performed on non-numerical keys?

A

The ASCII or Unicode values of the keys is used to generate a numerical index.

62
Q

What is a collision in hash tables?

A

When a hashing algorithm produces the same index for two or more different keys.

63
Q

What is clustering in hash tables?

A

When indices are not randomly distributed.

64
Q

What is a load factor in hash tables?

A

The ratio of NumberOfKeys / NumberOfSlots, the higher the value the harder it is to produce a unique result.

65
Q

What is chaining in hash tables?

A

If a collision occurs a list is created at that slot and the key/value pairs become elements of that list.

66
Q

What is the simplest way of dealing with collisions in hash tables?

A

Put the key/value pair in the next available slot, however this could lead to clustering. To prevent this increment the “ship” value.

67
Q

What is rehashing?

A

If a collision occurs a different hashing algorithm is run on the key until a unique address is created.

68
Q

What is a dictionary?

A

An abstract data type that maps key to data.
2-dimensional structure containing key/value pairs.

69
Q

How are dictionaries implemented?

A

Requires random access, meaning you can directly access the key without iteration. (can be implemented with a hash table)

70
Q

How can vectors be implemented?

A

As values stored in a list or elements in a one-dimensional array.

71
Q

What is a function?

A

A mathematical construct that maps an input to an output.

72
Q

What components make up vectors?

A

Tail
Head
Magnitude
Direction

73
Q

What is a scaler in context of vectors?

A

The number representing the amount to scale a vector by.
Scaling changes the magnitude, not direction.

74
Q

What is the dot product of vectors?

A

Combining two vectors to find the angle between them.

75
Q

What is the formula for dot product?

A

A.B = AxBx + AyBy
cos = A.B/ |A|.|B|

76
Q

What is a convex combination?

A

Multiplying vectors to produce a resulting vector within the convex hull.

77
Q

What is the convex hull?

A

A spatial representation of the vector space between two vectors.

78
Q

What is the formula for a convex combination?

A

D = αAB + βAC
α, β > 0
α+β=1

Computer Science (10 decks)

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