Brainscape's Knowledge GenomeTM

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


See full index

OCR COMPSCI OFFICIAL > 1.4.2 - Data Structures > Flashcards

1.4.2 - Data Structures Flashcards

1
Q

What is an array?

A

An ordered, finite set of elements.

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

What does zero-indexed mean?

A

The first element in the list is always considered to be at position zero.

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

What is a 1D array?

A

A linear array, always taken to be zero indexed.

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

How can a 2d array be visualised?

A

A table or spreadsheet.

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

How do you search through a 2d array?

A

Go down the rows and then across the columns.

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

How can a 3d array be visualised?

A

As a multi-page spreadsheet, made of multiple 2d arrays.

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

What is a record?

A

This is a row in a file made up of fields (which can be different types)

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

What is a list?

A

It is a data structure made up of a number of ordered items where each item can occur more than once.

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

Compare lists and arrays?

A

List values are stored non-contiguously, so they don’t have to be stored next to each other in memory. Additionally, they can contain elements 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 ordered set of values of any type. It is immutable, meaning it can’t be changed after created.

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

What is a linked list?

A

A dynamic data structure which holds an ordered sequence. The items do not have to be contiguous.

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

What is a linked list made up of?

A

A data field containing the value of the actual data.
A pointer field containing the address of the next item in the list.
Pointers containing the index of the first item in the list, and the next available space.

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

What are some negatives of linked lists?

A

Nodes are not truly removed from the list, only ignored. This wastes memory.
Storing pointers means more memory is required.
Items are stored in a sequence, so can only be traversed, not directly accessed.

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

What is a graph?

A

A set of vertices/nodes connected by edges/arcs.

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

What are the 3 types of graph?

A

Directed graph: edges traversed in only one direction. Undirected graph: edges traversed in both directions. Weighted graph: A cost attached to each edge.

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

Why are adjacency matrixes good?

A

Convenient to work with because of quicker access times, and easy to add nodes.

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

Why are adjacency lists good?

A

More space efficient for large, sparse networks.

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

What is a stack, and how is it implemented?

A

It is a LIFO data structure - items can only be added to or removed from it.
It is implemented using a pointer pointing to the top of the stack, where the next data will be inserted.

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

Where are stacks used?

A

To reverse an action, such as an undo button.

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

When are static stacks preferred?

A

When the maximum size required is known in advance, as they are easier to implement and make more efficient use of memory.

21
Q

What does stack.isEmpty() do?

A

Checks if a stack is empty by checking the value of the top pointer.

22
Q

What does stack.push(value) do?

A

Adds value to the top of the stack. Must first ensure the stack is not full.

23
Q

What does stack.peek() do?

A

Returns top value from the stack, after checking the stack is not empty by looking at top pointer.

24
Q

What does stack.pop() do?

A

Removes and returns the top value of the stack. First checks the stack is not empty by looking at value of top pointer.

25
Q

What does stack.size() do?

A

Returns the size of the stack.

26
Q

What does stack.isFull() do?

A

Checks if the stack is full and returns a Boolean value. Works by comparing stack size to the top pointer.

27
Q

What is a queue, and how is it implemented?

A

It is a FIFO data structure, where items are added to the end and removed from the front. Implemented using two pointers.

28
Q

When are queues commonly used?

A

Printers, keyboards and simulators

29
Q

What is a linear queue?

A

An array data structure. Items are added into the next available space starting from the front, and removed from the front.

30
Q

What is the issue with a linear queue?

A

As the queue removes items, there are addresses which cannot be used again, making it an ineffective implementation.

31
Q

What is a circular queue?

A

A queue where when the rear pointer is equal to the max size, it loops back to the front and stores values there (assuming it is empty).
Harder to implement but uses space more effectively.

32
Q

What does enQueue(value) do?

A

Adds a new item to the end of a queue, incrementing the back pointer.

33
Q

What does deQueue() do?

A

Removes an item from the front of a queue, incrementing the front pointer.

34
Q

What does queue.isEmpty() do?

A

Checks if the queue is empty by comparing the front and back pointer.

35
Q

What does queue.isFull() do?

A

Checks if the queue is full by comparing the back pointer and queue size.

36
Q

What is a tree?

A

A tree is a connected from of a graph, made of a root node connected to other nodes using branches.

37
Q

What is a leaf?

A

A node with no children.

38
Q

What is a binary tree?

A

A type of tree where every node has a maximum of two children.
Commonly represented storing each node with a left and right pointer in a 2d array.

39
Q

Where are binary trees commonly used?

A

To represent information for binary searches, as info is easy to search through.

40
Q

What is pre-order traversal?

A

In order you pass their left, starting from left hand side of root.
Used in languages where operation comes before values, e.g +ab

41
Q

What is in-order traversal?

A

In order you pass their base, starting from first node from left with less than two children. Traverses nodes sequentially.

42
Q

What is post order traversal?

A

In order you pass their right side.

43
Q

What is a hash table?

A

An array coupled with a hash function.

44
Q

What does a hash function do?

A

Takes in data and releases an output, to uniquely map a key to an index.

45
Q

What is a collision?

A

When two inputs result in the same hashed value - a good hashing algorithm should have a low probability of this!

45
Q

What is a collision?

A

When two inputs result in the same hashed value - a good hashing algorithm should have a low probability of this!

46
Q

What happens if a collision occurs?

A

The item is placed in the next available location - called collision resolution.

47
Q

What are hash tables normally used for?

A

Indexing, as they provide fast access to data because of the unique, one-to-one relationship with the stored address.

OCR COMPSCI OFFICIAL (29 decks)

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