Brainscape's Knowledge GenomeTM

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


See full index

Computer Science A-Level > Section 7: Data Structures > Flashcards

Section 7: Data Structures Flashcards

1
Q

Chapter 40:

What is Hashing?

A

Convert a string or document into a specific form using and algorithm that would completely scramble the result if one character is changed.

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

Chapter 40:

What is the difference between Hashing and Encryption?

A

Encryption is designed to be reversible, and used in transmission.
Hashing is designed to not be reversible, and used in signature checking.

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

Chapter 40:

What is a Hash Table?

A

A collection of values where the location of a value is its hash.

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

Chapter 40:

When using a Hash Table, What happens when an item is inserted, but its hash value is already taken?

A

It is rehashed.
Depending on the implementation, it may:

Place it in the next space to the right.

or

Store both values at the hash location using an array or equivelant.

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

Chapter 40:

How can we search a Hash Table for a value?

A

Hash the value you are searching for,
Look at that index,
{
If the cell has the value you are looking for, the value is present.
If the cell is empty, the value is not present.
} If the cell has a different value, look to the right and check again.

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

Chapter 40:

What is Rehashing?

A

In a hash table, if the hash of a value is taken, Rehashing is how to find the new location.

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

Chapter 40:

Why are Hash Tables useful?

A

They allow for efficient searching.

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

Chapter 40:

What common Data Type is implemented using a Hash Table?

A

Dictionaries.

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

Chapter 40:

What is a Dictionary?

A

An unordered collection of data where the values are referenced with a keyword instead of a location index.

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

Chapter 37:

What is an Abstract Data Type?

A

A logical description of how data is viewed.

The behaviour is defined by the type, but the implementation can be different.

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

Chapter 37:

What are four examples of Abstract Data Types?

A

Queues, Stacks, Trees, Graphs.

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

Chapter 37:

What kind of Abstract Data Type is a Queue?

A

FIFO.
First in first out.
New elements can only be added to the end of a Queue.
Elements can only be taken from the front of the Queue.

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

Chapter 37:

What is the difference between a Static Data Type and a Dynamic Data Type?

A

Dynamic Data Types have the ability to grow and shrink.

Static Data Types have a fixed size which must be stated on declaration.

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

Chapter 37:

What is a circular Queue?

A

When an arbitrary limit on a Queue has been reached, the last element can point back to the front of the queue, to reuse empty space at the front.

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

Chapter 37:

What is a Priority Queue?

A

A Queue where certain values may be placed further forward, and “jump the queue” or “cut in”.

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

Chapter 38:

What is a List?

A

An ordered collection of data values.
Data Types can be different for different indexes.
Data values can be repeated.

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

Chapter 38:

What is the difference between an Array and a List?

A

Arrays are static, meaning they must be declared with a size and cannot grow or shrink.
Arrays are declared with a data type that must be true for all of the values.

Lists are dynamic, meaning they can grow and shrink in size.
Lists can store different data types in different locations.

Both are ordered.

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

Chapter 38:

How do you insert an item into a list?

A

From the end of the list, back to the insertion index, copy List[x] to List[x+1].
This will push all of the values at the index and after forward one.
Then set the value of the index to the insertion value.

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

Chapter 38:

How do you delete an item from a list?

A

From the insertion index to the end of the list, copy List[x+1] to List[x].
This will push every value after the index back one.
Then set the value of the last index to Null.

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

Chapter 38:

What are Linked Lists?

A

Values are bound to pointers for other locations.

This means you can add new items to the end, change the pointers, and have it effectively be in the middle.

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

Chapter 39:

What kind of Abstract Data Type is a Stack?

A

LIFO.
Last in first out.
New elements can only be added to the top of a Stack.
Elements can only be taken from the top of the Stack.

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

Chapter 39:

What are some applications of Stacks?

A

Back (e.g. last web page), Undo, Reverse Polish Notation Calculations.

23
Q

Chapter 39:

What is Overflow and Underflow in a Stack?

A

Overflow is where you try to push a value to a full stack.
The stack can be full if it is implemented using an Array(when the size is met) or if all memory is used.

Underflow is where you try to pop a value from an empty stack.

24
Q

Chapter 39:

What is a Stack Composed of?

A

Stack Frames.

25
Q

Chapter 41:

What is a Graph?

A

A set of Nodes/Vertices connected by Edges/Arcs.

Edges may be one-way or two-way.

If all Edges are one-way, the graph is said to be a directed graph.

26
Q

Chapter 41:

What is a Weighted Graph?

A

Graph Arcs can have a value attached to them, for example, to show distance or cost.

27
Q

Chapter 41:

What is an Adjacency Matrix?

A

A Table (Matrix) showing the Arc connections between Nodes in a Graph.

Weighted graphs store values, non-weighted graphs store booleans.

28
Q

Chapter 41:

What is an Adjacency List?

A

A list of Arcs, with neighbouring nodes next to them.
Weighted Graphs can be represented using colon separation.

e.g.
A = {B:5, C:4}
B = {C: 3}
C = {}

[Depending of the implementation, the connections may not be referenced by both nodes]

29
Q

Chapter 41:

When would you use an Adjacency Matrix over an Adjacency List?

A

When there are a large amount of Arcs.

When you need to know if an Arc exists.

30
Q

Chapter 41:

When would you use an Adjacency List over an Adjacency Matrix?

A

When there are few Arcs, to save memory and storage space.

31
Q

Chapter 41:

When might Graphs be used?

A

To represent networks.
To represent roads between towns.
To represent states in an FSM.

32
Q

Chapter 41:

How does Google’s PageRank Algorithm work?

A

Sites are given a rank based on searches for the page, and references to the page.
Furthermore, references from high-ranking pages are more valuable.

33
Q

Chapter 41:

*Who were the inventors of the Google Search Engine?

A

Larry Page, and Sergey Brin.

34
Q

Chapter 42:

What kind of Abstract Data Type is a Tree?

A

Trees are a type of graph that have a hierarchical structure.

35
Q

Chapter 42:

What is a Root node in a Tree type?

A

A node that has no incoming edges.

36
Q

Chapter 42:

What is a Leaf node in a Tree type?

A

A node that has no outgoing edges.

37
Q

Chapter 42:

What is a Child node in a Tree type?

A

The Child node of node A is a node that node A points to.

38
Q

Chapter 42:

What is a Parent node in a Tree type?

A

The Parent node of node A is a node that points to node A.

39
Q

Chapter 42:

What is a Connected Graph?

A

A Graph where all nodes have some route to each other.

40
Q

Chapter 42:

What is a Cycle in a Graph?

A

Where there is a route from node A, back to node A, where no Edge can be traversed multiple times.

41
Q

Chapter 42:

What is a Binary Search Tree?

A

A Tree where each node can have a maximum of 2 child nodes.

42
Q

Chapter 42:

What is the Pre-Order Tree Traversal?

A

Look at Node,
Check left Child,
Check right Child.

43
Q

Chapter 42:

What is the In-Order Tree Traversal?

A

Check left Child,
Look at Node,
Check right Child.

44
Q

Chapter 42:

What is the Post-Order Tree Traversal?

A

Check left Child,
Check right Child,
Look at Node.

45
Q

Chapter 42:

How can Trees be implemented?

A

Using an array of records/arrays.
(Or just multiply records)

Every record stores its data, the index of the item to the left, and the index of the item to the right.

46
Q

Chapter 43:

What is a Geometric Vector?

A

A quantity having a direction and a magnitude.

Can be used to represent position, velocity, and acceleration. (Examples)

47
Q

Chapter 43:
How can you scale a Vector?
What is the effect?

A

Multiply every value by the same scalar.
Magnitude of the vector changes, but the direction stays the same, unless the scalar is negative, where the direction is reversed.

48
Q

Chapter 43:

How do you find the Convex Combination of two Vectors?

A

αu + βv,
where α + β = 1, α >= 0, β >= 0.
and where u and v are the vectors.

49
Q

Chapter 43:

What is the Convex Combination of two Vectors?

A

Imagine a vector OA and a vector OB, (O = origin).
OAB forms a triangle.

Vector OC is a Convex Combination of OA and OB if OC can be written in the form (αu + βv), where α + β = 1, α >= 0, β >= 0.

Vector OC is a Convex Combination of OA and OB if OC lies within area OAB.

50
Q

Chapter 43:

What is another name for Dot Product?

A

Scalar Product.

51
Q

Chapter 43:

Algebraically, what is the Dot Product of two Vectors?

A

Each component from the first vector is multiplied by the same component of the other vector.
The sum of the products is the Dot Product.

[The Dot Product is a number, not a vector]

52
Q

Chapter 43:

Geometrically, what is the Dot Product of two Vectors?

A

The amount of one vector that goes in the direction of the other.

53
Q

Chapter 43:

How do you calculate the angle between two Vectors?

A

Two vectors U and V.
Angle between = θ.

formula:
cos θ = (U dot V) / (abs(U) * abs(V))

DP = (Ux * Vx) + (Uy * Vy) [+ …]
VectLens = sqrt( (Ux^2 + Uy^2 [+ …]) + (Vx^2 + Vy^2 [+ …]) )
θ = arccos(DP / VectLens)
———————————————————————
Alternatively:
θ = arcos( DP )
Where DP is the Dot Product of the Normalised Vectors.

Computer Science A-Level (12 decks)

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