1
Q
What is a 1D array?
A
- An ordered, static set of elements
- Can only store one data type
- A 1D array is a linear array
2
Q
How would you create, access and modify a 1D array?
A
array = [1, 2, 3, 4, 5]
value = array[1]
print(value) #would print “2”
array[1] = 10
print(array) #would print “2, 10, 3, 4, 5”
3
Q
What is a 2D array?
A
- A 2D array can be visualised as a table
- Arrays within an array
- When navigating the table, you first go DOWN the rows and then ACROSS the columns
4
Q
What do the indices represent in a 2D array?
A
- Left index: how many down (the row)
- Right index: how many across (the column)
5
Q
What is a 3D array?
A
- Can be visualised as a multi-page spreadsheet
- Multiple 2D arrays
- When navigating, you first go through the pages (arrays), then down the rows, then across the columns
6
Q
What do the indices represent in a 3D array?
A
- First index: which page (which 2D array)
- Second index: how many down (the row)
- Third index: how many across (the column)
7
Q
What is a record?
A
- A row in a file, and is made up of fields
- The horizontal headers at the top, which identify the columns
- They are used in databases
8
Q
What is a list?
A
- A data structure which consists of a number of items where the items can occur more than once
- Lists are similar to 1D arrays and can be accessed in the same way
9
Q
What is the difference between a list and a 1D array?
A
- List values are stored non-contiguously
- Which means that they do not have to be stored next to each other in memory
- While values in a 1D array must be stored next to each other in memory
10
Q
What does isEmpty() do (lists)?
A
- Checks if a list is empty
- E.G: list.isEmpty()
11
Q
What does append(value) do?
A
- Adds the new value onto the end of the list
12
Q
What does remove(value) do?
A
- Removes the value the first time it appears in the list
13
Q
What does insert(position, value) do?
A
- Inserts the new value at the given position
14
Q
What does pop() do (lists)?
A
- Returns and removes the last value
list = [1, 2, 3, 4, 5]
list.pop() #returns “5”
#new list = [1, 2, 3, 4]
15
Q
What is a tuple?
A
- An ordered set of values of any type
- It is immutable: this means that it cannot be changed
- Elements cannot be added, removed or changed after the tuple has been created
- Tuples are created using regular brackets instead of square brackets
16
Q
What is a linked list?
A
- A linked list is a dynamic data structure that is used to hold an ordered sequence
- The items that form the sequence do NOT have to be in contiguous data locations (do not have to be adjacent)
17
Q
What is an item in a linked list, and what does it contain?
A
- Each item in a linked list is called a node
- Each node contains a data field along with another address, which is called a pointer
- The pointer points to the data address of the next node
18
Q
How do you traverse a linked list?
A
- Check if the linked list is empty
- Start at the node the pointer is pointing to (start = 1)
- Output the item at the current node
- Follow the pointer to the next node, repeating through each node until the end of the list is reached
- When the pointer field is empty/null, it signals that the end of the linked list has been reached
19
Q
What is an advantage of using linked lists?
A
- Values can easily be added or removed by editing the pointers
20
Q
How do you remove a node from a linked list?
A
- You do not remove the node from memory, you rather bypass it during the list
- Update the previous node to point to the node after the item you want to delete
- The node is not truly removed, but rather just ignored
- This wastes memory
21
Q
What is a stack?
A
- Stacks are a last in first out (LIFO) data structure
- Items can only be added or removed from the top of the stack
- They are used to reverse actions, such as go back a page
22
Q
What is a static stack?
A
- Where the maximum size required is known in advance, static stacks are preferred
- They are easier to implement and make more efficient use of memory
23
Q
What does isEmpty() do (stacks)?
A
- Checks if the stack is empty by checking the value of the top pointer
24
Q
What does push(value) do?
A
- This adds a new value to the top of the stack
- It will need to check the stack is not full before pushing to the stack
25
What does peek() do?
- This returns the top value of the stack
26
What does pop() do (stacks)?
- This returns and removes the top value of the stack
27
What does size() do?
- Returns the size of the stack
28
What does isFull() do?
- Checks if the stack is full and returns the Boolean value
- Does this by comparing the stack size to the top pointer
29
Why do stacks use pointers?
- The pointer in a stack points to the top of the stack
- This is where the next piece of data will be added or the current piece of data can be removed
30
What happens when pushing data onto a stack?
- When pushing data onto a stack, the data is pushed to the position of the pointer
- Once pushed, the pointer will increment by 1, signifying the top of the stack
- Since the stack is a static data structure, an attempt to push an item onto a full stack is called a stack overflow
31
What is a stack overflow?
- Attempting to push data onto a full stack
32
What happens when popping data from a stack?
- When popping data from a stack, the data is popped from the position of the pointer
- Once popped, the pointer will decrement by 1 to point to the new top of the stack
- Since the stack is a static data structure, an attempt to pop an item from an empty stack is called a stack underflow
33
What is a stack underflow?
- Attempting to pop data from an empty stack
34
What is a static data structure?
- A data structure which has a fixed size and can't change at run time
35
What is a dynamic data structure?
- A data structure which can adapt and accommodate changes to the data inside so it doesn't waste as much space in memory
36
What is a queue?
- A first in first out (FIFO) data structure
- Items are added to the end of the queue and removed from the front
37
What is a queue overflow?
- Attempting to enqueue an item to a full queue
38
What is a queue underflow?
- Attempting to dequeue an item from an empty queue
39
What does enQueue(value) do?
- Adds the value onto the back of the queue
40
What does deQueue() do?
- Returns and removes the item at the front of the queue
41
What does peek() do (queue)?
- Returns the first value in the queue without removing it
42
What is a linear queue?
- A data structure that consists of an array
- Items are added to the next available space in the queue, starting from the front
- Items are then removed from the front of the queue
43
What pointers does a queue have?
- Head pointer: points to the first value
- Tail pointer: points to the last value
44
What is a circular queue?
- A circular queue is a static array that has a fixed capacity
- It would take time to move items to the start of the array to free up space at the end, so a circular queue is implemented
- It reuses empty slots at the front of the array that are caused when items are dequeued
45
What is a graph?
- A graph is a set of vertices / nodes that are connected by edges / pointers
46
What are the different categories of graphs?
- Directed graph
- Undirected graph
- Weighted graph
47
What is a directed graph?
- A set of nodes connected by edges
- The edges can only be traversed in one direction
48
What is an undirected graph?
- A set of nodes connected by edges
- The edges can be traversed in any direction
49
What is a weighted graph?
- A set of nodes connected by edges
- A weight is assigned to each edge
50
What is an adjacency matrix?
- The connection matrix
- A matrix containing rows and columns which is used to present a simple labelled graph
51
What is an adjacency list?
- A collection of unordered lists used to represent a finite graph
52
What are the two methods to traverse a graph?
- Breadth-first search
- Depth-first search
53
What is a breadth-first search?
- A graph traversal method which systematically visits all neighbours of a given vertex before moving on to their neighbours
- It then repeats this layer by layer
54
How do you do a breadth-first traversal?
- Visit all nodes going left to right at the top layer
- Once you've gotten to the end of the layer, do the same for the next layer
- Repeat until all layers have been visited
55
What data structure does a breadth-first search use?
- Makes use of a queue data structure to enqueue each node as long as it is not already in the list of visited nodes
56
What is a depth-first search?
- A graph traversal method which uses an edge-based system
57
What data structure does a depth-first search use?
- Uses a stack data structure to push each visited node onto the stack and then pop them from the stack when there are no nodes left to visit
58
How do you do a depth-first traversal?
Computer Science A-Level
flashcards
Decks in class (17)
# Cards
-
Systems Software19
-
Computational thinking14
-
Applications generation23
-
Characteristics of the CPU54
-
Data types24
-
Web technologies30
-
Object Orientated Programming21
-
Boolean logic22
-
Algorithms40
-
Types of programming languages17
-
Ethics and legislations15
-
Software development22
-
Compression, encryption and hashing18
-
Databases53
-
Problem solving and programming46
-
Networks92
-
Data structures58
