Brainscape's Knowledge GenomeTM

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


See full index

AQA Computer Science Alevel > (P1) Fundamentals of Data Structures > Flashcards

(P1) Fundamentals of Data Structures Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

Describe the steps involved in adding a record to a hash table.

A
  • Try putting record in first available position, if not able to, move to another location.
  • Hash algorithm applied to key value.
  • Result is location in table where record should be stored.
  • If location is not empty then use next free location.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Describe how a single stack could be used to evaluate an RPN expression.

A
  • Push values on to stack.
  • Each time an operator is reached, pop two values and apply operator to them.
  • Push result to stack.
  • When end of the expression is reached the top item of the stack is the result.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the formula for Dot Product?

A

A . B = (Ax × Bx) + (Ay × By)

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

True or false: All regular languages can be represented using a finite state machine without outputs.

A

True.

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

True or false: The set of strings defined by a regular language can be finite or infinite in size.

A

True.

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

True or false: There are some languages that can be represented in Backus-Naur Form that are not regular languages.

A

True.

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

Discuss the advantages and disadvantages of dynamic data structures (DDS) compared to static data structures.

A

Disadvantages of DDS: Uses more memory as it uses pointers. Can take longer to add a new item to the data structure as memory needs to be allocated.
Advantages of DDS: Can grow as more data is added to the data structure. No wasted memory.

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

Describe the steps involved in adding an item to a linear queue that has been implemented as a static data structure using an array. Your answer should include a description of how any pointers are used and changed.

A

Check if queue is full. If it is not full then add one to the value of the rear pointer. Then add the new item to the position indicated by the rear pointer.

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

Describe the steps involved when adding an item to a priority queue, implemented as a static data using an array, that are not required when adding an item to a linear queue.

A

Starting with the item at the rear of the queue move each item back one place in the array. Until you reach the start of the queue or find an item with the same or higher priority than the item to add. Add the new item in the position before that item.

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

Explain the circumstances when it would be more appropriate to use an adjacency matrix instead of an adjacency list.

A

Adjacency matrix appropriate when there are many edges between vertices. When the presence/ absence of specific edges needs to be frequently tested.

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

Explain how a stack could be used in the process of evaluating an expression in Reverse Polish Notation.

A

Push operands onto stack. Each time operator reached pop two value off stack and apply operator to them. Add result to the stack.

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

Explain what is meant by a heuristic technique.

A

Heuristic approach employs a method of finding a solution that might not be the best.

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

Explain the difference between static and dynamic data structures.

A

Static data structures have storage size determinded at compile time, whereas dynamic data structure can grow/shrink at run time. Dynamic data structure usually require more memory for pointer which static data structure do not need.

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

Explain what an array is.

A

An indexed set of elements. An array must be finite, indexed and must contain only elements with the same data type.

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

When a 2d array is set out in a table format, which coordinate is listed first?

A

The x coordinate.

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

What is a file made up of?

A

Records.

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

What are records made up of?

A

Fields.

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

What is an abstract data structure?

A

Data structures that use other data structures to form a new way of storing data.

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

Give an example of an abstract data structure.

A

Queue.

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

What is a queue?

A

An abstract data structure based on an array. FIFO.

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

Give an example of when queues are used.

A

Keyboard buffers, where each key press is added to the queue and then removed when the computer has processed the key press. This ensures that the letter appears on the screen in the same order they pressed.

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

What abstract data structure does a breadth first transversal use?

A

Queue.

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

How many pointers does a linear queue have?

A

Two pointers, front and rear.

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

What are the front and rear pointer used for?

A

Front: Identify which item is at the front of the queue.
Rear: Identify where to place a new item in a queue.

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

What is the term for adding to a queue?

A

Enqueue.

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

What is C# code for adding to a queue?

A

Queue.Enqueue.(“Insert Value”)

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

What is the term for removing a value from a queue?

A

Dequeue.

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

What is the C# code for removing a value from a queue?

A

Queue.Dequeue()

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

What are the four operations that can be performed on a queue?

A

Enqueue
Dequeue
IsEmpty
IsFull

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

How can you check is a queue is empty?

A

Compare the front and rear pointer, and if they are the same the queue is empty.

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

What is a circular queue?

A

A queue in which the front and rear pointer can move over the two ends of the queue, making for a more memory efficient data structure.

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

Describe how a priority queue works.

A

Items are assigned a priority. Items with the highest priority are Dequeue before low priority items.
In the case that multiple items have the same priority, items are removed using FIFO.

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

Describe when priority queues are used.

A

Frequently used in computer systems. Processors assign time to applications according to their priority. Applications in use by the user take priority over background applications, allowing for a faster user experience.

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

What is a stack?

A

FILO abstract data structure, which is based off an array.

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

How many pointers does a stack have?

A

One pointer, called the top pointer.

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

What is term for adding an item to a stack?

A

Push.

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

What is the term for removing off a stack?

A

Pop.

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

What does the Peek function on a stack do?

A

Returns the value of the item at the top of the stack without removing the value.

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

What are the five functions that can be used on a stack?

A

Push
Pop
Peek
IsEmpty
IsFull

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

What is the C# code for adding a value to a stack?

A

Stack.Push(“Insert Value”)

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

What error is produced when you try to add a value to an already full stack?

A

Stack Overflow

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

When is does a Stack Underflow error occur?

A

Caused by attempting to pop a value off on already empty stack.

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

What is a graph?

A

An abstract data structure used to represent complex relationships.

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

What is the Internet?

A

A network of interconnected computer networks.

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

What is another term for nodes?

A

Vertices.

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

What is another term for edges?

A

Arcs.

47
Q

What is a weighted graph?

A

A graph in which edges are assigned values, representing a value such as time or distance.

48
Q

What are the two ways a graph can be represented?

A

Using an adjacency matrix or adjacency list.

49
Q

What is an adjacency matrix?

A

A tabular representation of a graph. Each node in the graph is assigned a row and a column in the table.

50
Q

What is a feature of adjacency matrixes showing an unweighted graph?

A

Display diagonal symmetry. Have a diagonal line of zeros where the row and column represent the same node.

51
Q

What value is used in an adjacency matrix for a weighted graph, for when there is a non-existent edge?

A

Infinite sign.

52
Q

Give two disadvantages of an adjacency matrix.

A

Stores every possible edge between nodes, even those that don’t exist, so almost half of the matrix is repeated data.
Slow to query, as each item in a list must be searched sequentially until the desired edge is found.

53
Q

Give an advantage of adjacency matrixes.

A

Well suited to dense graphs, where there are a large number of edges.

54
Q

Give three advantages of adjacency lists.

A

Only records existing connecting in a graph.
Allows a specific edge to be queried very quickly, as it can be looked up by its row and column.
Well suited to sparse graphs.

55
Q

What is a tree?

A

A connected, undirected graph with no cycles.

56
Q

Describe the attributes of a rooted tree.

A

Has root node, from which the other nodes stem from.
Nodes which have their own nodes are called parent nodes.
Nodes with a parent are called child nodes.
A child node with no children are called leaf nodes.

57
Q

What is a binary tree?

A

A rooted tree, in which each parent node has no more than two child nodes.

58
Q

Give an example of the type of information that could be stored in a rooted tree.

A

Family tree or a file system.

59
Q

What is a hash table?

A

A way of storing data that allows data to be retrieved with a time complexity of O(1).

60
Q

What is the function of a hash algorithm?

A

Takes an input and returns a hash.
A hash is unique to its input and cannot be reversed to retrieve the input value

61
Q

Give an example of hashes being used.

A

Passwords are hashed before being stored so that your password cannot be retrieved even if the hash is exposed.

62
Q

Describe a hash table.

A

Hash table stores key-value pairs.
The key is sent to a hash function that performs arithmetic operations on it.
The resulting hash is the index of the key-value pair in the hash table.

63
Q

Describe the process of looking up an element to a hash table.

A

Key is hashed.
Once hash is calculated, the position in the table corresponding to that hash is queried and the desired information is located.

64
Q

In a hash table, what is a collision?

A

Different inputs producing the same hash. Could result in data being overwritten.

65
Q

How can collisions in a hash table be avoided?

A

Rehashing, which is finding an available position according to an agreed procedure.

66
Q

What is a dictionary?

A

A collection of key-values pairs in which the value is accessed by its associated key.

67
Q

Give an example of an application of dictionaries.

A

Dictionary-based compression.

68
Q

If a vector is viewed as a function, what way could it be represented?

A

Using an dictionary.

69
Q

If a vector is viewed as a lost, what is a way that it could be represented?

A

Using a one dimensional array.

70
Q

When vectors are added together, what process occurs?

A

Translation.

71
Q

What is the convex combination of two vectors?

A

Two vectors a and b, then a convex combination would be ax + by where x and y are both non-zero numbers less than one that add to one.

72
Q

What does convex combination achieve?

A

Creates a line that is in the position of a ratio of x to y apart from vector a and vector b.

73
Q

Describe static data structures.

A

Fixed in size.
Most frequently declared in memory as a series of sequential, contiguous memory locations.
If the number of data items to be stored in a static structure exceeds the number of memory locations allocated to the structure, an overflow error will occur.

74
Q

Describe dynamic data structures.

A

Change in size to store their content.
Number of memory locations are not fixed, therefore the computer cannot allocate them contiguous memory locations.
Each item of data is stored alongside a reference to where the next item is stored in memory.

75
Q

What is the heap in dynamic data structures?

A

The heap consists of a pool of memory which can be allocated to variables usring execution of the program.
The heap makes dynamic variables possible because these are the variables which can change size during execution.
The heap allows more efficient use of memory when dealing with data of an unknown and changing size.

76
Q

Explain why a queue is a suitable data structure to represent a deck of cards in a game.

A

Queue is a first in, first out data structure and the card game follows the same structure.

77
Q

What is abstraction?

A

The process of removing irrelevant data so that only the data required to solve the problem is stored and processed.

78
Q

Explain the circumstances when it would be better to use a adjacency list than an adjacency matrix.

A

When there are few edges between vertices. When the presence/ absense of specific edges does not need to be frequently tested.

79
Q

What is an intractable problem?

A

Problem that cannot be solved within an acceptable time frame.

80
Q

Discuss the advantages of using a hash function.

A

Don’t have to check every value as hash function can directly calculate location

81
Q

Explain what happens when a hash function computes the same value for two different pieces of data and how to deal with it.

A

Record for each value would be stored in the same location in the array. Store record in the next available position in the array.

82
Q

What is the effect of a hash collision and how might it be dealt with?

A

The hash function could compare the same value so need to verify the value stored is the one being looked up.

83
Q

Give one requirement for a binary search that isn’t a requirement for a linear search.

A

Binary search needs an ordered list, but linear search works on an unordered list.

84
Q

What is the time complexity for an Insertion Algorithm?

A

O(n^2)

85
Q

What are the rules when adding values to a binary tree?

A

Less than = left
Greater than = right

86
Q

What is a nested IF statement?

A

IF statement within an IF statement.

87
Q

What does a value of 0 in a pointer represent?

A

Null pointer.

88
Q

Describe the method to remove an item from a circular queue.

A
  • Check if queue is empty.
  • Compare the value of the front pointer with the maximum size of the array minus one.
  • If equal then front pointer becomes 0.
  • Otherwise, add one to the front pointer.
89
Q

Describe three differences between static and dynamic data structures.

A

Static data structures:
- Have size determined at compile time.
- Wastes memory if number of items is less than size of structure.
- Stores data in consecutive memory locations.

Dynamic Data Structures:
- Can grow/shrink at run time.
- Only takes up amount of space required for the actual data.
- Doesn’t store data in consecutive memory locations.

90
Q

Explain how a single stack can be used to reverse the order of the items in a queue.

A

Until queue is empty, repeatedly remove the front item from the queue and push onto stack.
Until stack is empty, repeatedly pop items off the stack and add them to the queue.

91
Q

What is a recursive subroutine?

A

Subroutine that calls itself.

92
Q

What is meant meant by recursively defined?

A

Calls itself.

93
Q

Write an algorithm to show how a data item is added to a queue.

A

IF Stop Pointer = maxsize then
Stop Pointer: = 1
ELSE
Stop Pointer: = Stop Pointer + 1
ENDIF
queue (Stop Pointer): = data
endproc

94
Q

What information is contained in every node?

A

Data item, left pointer and right pointer.

95
Q

When writing binary trees, which values goes to the left and which values go to the right?

A

Left: smaller values.
Right: bigger values.

96
Q

Why are queues in computer systems usually implemented as circular queues?

A

In a circular queue, locations will be reused, making them a more efficient use of memory.

97
Q

What is meant by the term ‘dynamic structure’?

A

The amount of memory taken up can vary at run time.

98
Q

What is the ‘head’ of a list?

A

The first value.

99
Q

What is the ‘tail’ of a list?

A

Every value except the first value.

100
Q

Explain why it is faster to access data stored in a one-dimensional array rather than a list.

A

Elements in a list can only be accessed sequentially. Elements in an array can be accessed directly.

101
Q

Describe two examples of the use of a binary tree.

A

Allows fast searching of data.
Outputs ordered data.

102
Q

Give a disadvantage of using linked lists.

A

Space used up by pointers.

103
Q

In what circumstances would it be more appropriate to use an array?

A

When amount of data is predictable.

104
Q

In what circumstances would it be more appropriate to use a linked list?

A

When size of stack is unknown.

105
Q

What is the purpose of tail pointers?

A

Shows position of the last item in a queue.
Next item to be added is at position: Rear Pointer + 1.

106
Q

When can a queue become unstable?

A

If space is not re-useable so queue becomes full.

107
Q

What is the role of a stack when a recursively-defined procedure is executed?

A

Store parameters.
Stores return addresses.
Stores local variables.

108
Q

What can a circular queue do that other queues cannot?

A

Wrap Around

109
Q

What properties must a graph have for it to be a tree?

A

No cycles.
Connected.
Undirected.

110
Q

Describe the process of how data stored in a binary tree can be stored in three 1D arrays.

A

One array stores data items.
One array for left pointer.
One array for right pointer.

111
Q

Describe the process of how data stored in a binary tree can be stored in an array of records.

A

Record created to store data item and pointers.
One pointer to left child.
One pointer to right child.

112
Q

Why are static implementations less efficient at inserting new items into the list than dynamic implementations?

A

Not possible to simply insert item into middle of list. Must move all items that should come after the new process down in the array.

113
Q
A

AQA Computer Science Alevel (9 decks)

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