4.2 Data Structures (OCR A Level Computer Science) Flashcards
Exam code: H446
1/107
0Still learning
Know0
- FrontArrays
Define 1D array.
Was this flashcard deck helpful?
Cards in this collection (107)
Define 1D array.
A 1D array is an ordered, static set of elements that can only store one data type and is structured linearly.
What does the following code do?
for element in array: print(element)This code iterates through each element in the array and prints it out one by one.
An array can only store data type.
An array can only store one data type.
True or False?
You can change the length of a 1D array after it has been created.
False.
A 1D array is a static set of elements, so its length cannot be changed after creation.
Define 2D array.
A 2D array is a data structure that can be visualised as a table with rows and columns, allowing storage of values in two dimensions.
How do you access a specific element in a 2D array?
To access a specific element in a 2D array, you first specify the row index and then the column index in the format array[row][column].
When navigating through a 2D array, you first go the rows and then the columns to find a position.
When navigating through a 2D array, you first go down the rows and then across the columns to find a position.
True or False?
A 2D array only stores data in a single row.
False.
A 2D array stores data in both rows and columns, forming a table-like structure.
Define 3D array.
A 3D array is a data structure that can be visualised as a multi-page spreadsheet, or as multiple 2D arrays stacked together, allowing data to be accessed using three indices.
True or False?
In a 3D array, the syntax array[z, y, x] means z is the array index, y is the row index, and x is the column index.
True.
In 3D array notation, z refers to the array index (depth), y to the row index, and x to the column index.
A 3D array can be thought of as a or as multiple arrays stacked together.
A 3D array can be thought of as a multi-page spreadsheet or as multiple 2D arrays stacked together.
How do you access an element in a 3D array in Python?
You access an element in a 3D array in Python using three indices: array_3d[row][col][depth].
Define record.
A record is a row in a file that is made up of fields. Records are used in databases to store related data together.
In the context of databases, what is the difference between a record and a field?
A record is a complete row of data in a file, while a field is a single data item within a record, such as a name or ID.
In Python, to access the surname of a Person record stored in variable person_record, you write: person_record. .
In Python, to access the surname of a Person record stored in variable person_record, you write: person_record.surname.
True or False?
In Java, you can access private fields of a class directly from outside the class.
False.
In Java, private fields cannot be accessed directly from outside the class; you must use getter and setter methods.
Define list.
A list is a data structure that consists of a number of items which can occur more than once and are stored non-contiguously in memory.
What is one key difference between a list and a 1D array?
A key difference is that list values are stored non-contiguously in memory, while array values are stored contiguously.
Unlike arrays, lists can contain of more than one .
Unlike arrays, lists can contain elements of more than one data type.
True or False?
The append() method adds a new value to the end of a list.
True.
The append() method is used to add a new value to the end of a list.
Define tuple.
A tuple is an ordered set of values of any type that is immutable, meaning it cannot be changed after creation.
True or False?
Elements can be added or removed from a tuple after it has been created.
False.
A tuple is immutable, so elements cannot be added or removed once it has been created.
A tuple is initialised using brackets instead of square brackets.
A tuple is initialised using regular brackets instead of square brackets.
When should a tuple be used instead of a list or array?
A tuple should be used when you need an ordered collection of values that must not be changed after creation.
Define linked list.
A linked list is a dynamic data structure that holds an ordered sequence using nodes that each contain data and a pointer to the next node.
What does the pointer field in a node of a linked list store?
The pointer field in a node stores the address of the next item in the linked list.
Each item in a linked list is called a and contains a data field and a pointer to the .
Each item in a linked list is called a node and contains a data field and a pointer to the next item.
True or False?
Linked lists must use contiguous memory locations for their nodes.
False.
The items in a linked list do not have to be in contiguous data locations. Each node can be stored anywhere in memory.
Define linked list traversal.
Linked list traversal is the process of visiting each node in a linked list, starting from the head node, by following pointers until the end of the list is reached (when the pointer is null).
What is an advantage of using a linked list compared to an array when adding or removing data?
An advantage of using a linked list is that values can be easily added or removed by updating pointers, without the need to shift other elements as in an array.
When removing a node from a linked list, the pointer of the previous node is updated to the node being deleted, so the removed node is no longer part of the list.
When removing a node from a linked list, the pointer of the previous node is updated to bypass the node being deleted, so the removed node is no longer part of the list.
True or False?
Linked lists allow direct access to any element, just like arrays.
False.
In a linked list, elements can only be accessed sequentially, not directly as in arrays.
Define stack.
A stack is a last in, first out (LIFO) data structure where items can only be added to or removed from the top of the stack.
What real-life example can help explain how a stack works?
A stack is like a stack of plates at a buffet. You can only take a plate from the top, and to reach the bottom one, you must remove all the others first.
Stacks are often implemented using an . Where the maximum size is known in advance, stacks are preferred because they make efficient use of memory.
Stacks are often implemented using an array. Where the maximum size is known in advance, static stacks are preferred because they make efficient use of memory.
True or False?
The push() operation removes the top item from a stack.
False.
The push() operation adds a new item to the top of the stack. The pop() operation removes the top item.
Define stack overflow.
A stack overflow occurs when there is an attempt to push data onto a full stack in a static data structure.
Define stack underflow.
A stack underflow occurs when there is an attempt to pop data from an empty stack in a static data structure.
When data to a stack, the data is added to the position of the pointer. After this operation, the pointer will by 1.
When pushing data to a stack, the data is added to the position of the pointer. After this operation, the pointer will increment by 1.
True or False?
When popping data from a stack, the pointer moves to the new top of the stack.
True.
When popping data from a stack, the pointer is decremented by 1 to point to the new top of the stack.
Define queue.
A queue is an abstract data structure that holds an ordered, linear sequence of items. It is a First in First out structure.
Items are added to the of the queue and removed from the .
Items are added to the end of the queue and removed from the front.
True or False?
Attempting to dequeue from an empty queue is called queue overflow.
False.
Attempting to dequeue from an empty queue is called queue underflow, not queue overflow.
What are the three main types of queue?
The three main types of queue are linear queue, circular queue, and priority queue.
Define linear queue.
A linear queue is a data structure that consists of an array, where items are added at the rear and removed from the front.
What must be checked before enqueuing (adding) an item to a linear queue?
Before enqueuing an item, you must check that the queue is not full.
True or False?
In a linear queue, items are always removed from the rear of the queue.
False.
Items are always removed from the front of a linear queue, not the rear.
When an item is dequeued from a linear queue, the item at the is removed and the pointer is incremented by 1.
When an item is dequeued from a linear queue, the item at the front is removed and the front pointer is incremented by 1.
Define circular queue.
A circular queue is a static array with fixed capacity. It reuses empty slots at the front of the array when items are dequeued by wrapping the front and rear pointers around the array.
What happens when the rear index pointer in a circular queue reaches the last position of the array?
When the rear index pointer reaches the last position of the array, it wraps around to the start of the array as long as the queue is not full.
Before enqueuing an item in a circular queue, you must check that the queue is . If it is not, the pointer is adjusted to the next free position.
Before enqueuing an item in a circular queue, you must check that the queue is not full. If it is not, the rear pointer is adjusted to the next free position.
True or False?
After dequeuing the only item in a circular queue, both front and rear pointers are reset.
True.
If the only item in the queue is dequeued, both the rear and front pointers are reset.
Define Directed Graph.
A directed graph is a set of objects that are connected together, where the edges are directed from one vertex to another.
Define Adjacency Matrix.
An adjacency matrix is a matrix containing rows and columns which is used to represent a simple labelled graph.
What is the difference between a directed and an undirected graph?
In a directed graph, edges have a direction and can only be traversed one way, while in an undirected graph, edges can be traversed in both directions.
In an adjacency matrix for an unweighted graph, is set when an edge exists between two nodes, and is set when there is no edge.
In an adjacency matrix for an unweighted graph, 1 is set when an edge exists between two nodes, and 0 is set when there is no edge.
True or False?
In an unweighted, undirected graph, the adjacency matrix is always symmetric.
True.
The adjacency matrix for an unweighted, undirected graph is symmetric because edges can be traversed in both directions.
What value is typically used in an adjacency matrix for a weighted graph to indicate that no edge exists between two nodes?
A very large number, often the infinity symbol (∞), is used to indicate that no edge exists between two nodes in a weighted adjacency matrix.
Define Adjacency List.
An adjacency list is a collection of unordered lists used to represent a finite graph.
In a directed, unweighted graph, the adjacency matrix is , so you must know the direction of edges when accessing data.
In a directed, unweighted graph, the adjacency matrix is not symmetric, so you must know the direction of edges when accessing data.
Give two real-world applications of graphs in Computer Science.
Graphs are used in social networks, transport networks, and operating systems.
Define breadth-first search.
A breadth-first search is a graph traversal algorithm that systematically visits all neighbours of a given vertex before moving to their neighbours, typically using a queue.
Define depth-first search.
A depth-first search is a graph traversal algorithm that explores as far as possible along each branch before backtracking, typically using a stack.
What data structure does a breadth-first search use to keep track of nodes to visit?
A queue is used in breadth-first search to keep track of nodes to visit.
What data structure is typically used for a depth-first search in a graph?
A stack is used for depth-first search in a graph.
True or False?
A breadth-first search visits all nodes in one branch before moving to the next branch.
False.
Breadth-first search visits all neighbouring nodes layer by layer before moving deeper into the graph, not one branch at a time.
True or False?
In a depth-first search, nodes are pushed onto a stack as they are visited.
True.
In depth-first search, each node is pushed onto a stack as it is visited, and popped when backtracking.
In a breadth-first search, nodes are stored in a as they are visited.
In a breadth-first search, nodes are stored in a queue as they are visited.
In a depth-first search, the algorithm uses a to keep track of the nodes to visit next.
In a depth-first search, the algorithm uses a stack to keep track of the nodes to visit next.
What is one difference between a graph and a tree?
A graph can have cycles, but a tree is a hierarchical structure without cycles.
Why is it important to have clear instructions for traversing a graph when adding or removing nodes?
Because graphs can have nodes connected in many ways, clear instructions are needed to locate specific nodes for adding or removing data efficiently.
Define tree (data structure).
A tree is a connected, undirected graph with nodes and pointers. The top node is called the root.
What is the height of a tree in data structures?
The height of a tree is the number of edges from the root node to the leaf node that is furthest away from it.
A node is a node with no children.
A leaf node is a node with no children.
True or False?
A node in a tree can have multiple children but only one parent.
True.
In a tree, each node can have multiple children, but only one parent.
Define binary tree.
A binary tree is a rooted tree where every node has at most two child nodes.
Which pointers are typically stored in each node to represent a binary tree?
Each node in a binary tree typically stores a left pointer and a right pointer to its child nodes.
In post-order traversal, the nodes are visited in the order: , , .
In post-order traversal, the nodes are visited in the order: left subtree, right subtree, root node.
True or False?
In breadth-first traversal of a binary tree, nodes are visited level by level from left to right.
True.
Breadth-first traversal visits all nodes at each level from left to right before moving to the next level.
What is the first step when adding data to a binary tree?
The first step is to start with an empty tree or an existing tree.
Define binary tree insertion.
Binary tree insertion is the process of adding a new value into a binary tree by identifying the correct vacant position according to the binary search property.
If the value to be inserted is less than the current node’s value, move to the child.
If the value to be inserted is less than the current node’s value, move to the left child.
True or False?
After inserting a new value, you must check that the binary tree maintains its structure and properties.
True.
It is important to verify the binary tree’s structure and properties after insertion to ensure it remains a valid binary tree.
When removing a node with two children from a binary tree, what is typically done to maintain the tree's structure?
When removing a node with two children from a binary tree, you usually replace it with the minimum value in its right subtree (or the maximum value in its left subtree) and then remove the replacement node from its original position.
A is a node in a tree that has no children.
A leaf is a node in a tree that has no children.
Define parent in the context of tree structures.
A parent is a node in a tree that has outgoing edges to one or more children.
True or False?
To remove a leaf node from a binary tree, you must replace it with its child.
False.
A leaf node has no children, so it can be simply removed from the tree without replacement.
Define binary search tree.
A binary search tree is a rooted tree where the nodes are ordered to optimise searching. For each node, the left subtree contains values less than the node, and the right subtree contains values greater than the node.
In a binary search tree, nodes to the left of the root have values that are than the root, and nodes to the right have values that are than the root.
In a binary search tree, nodes to the left of the root have values that are lower than the root, and nodes to the right have values that are higher than the root.
What is the purpose of ordering nodes in a binary search tree?
The purpose of ordering nodes in a binary search tree is to optimise searching, making it more efficient to find, insert, or delete values.
True or False?
To insert a value into a binary search tree, you always compare it to the left child first.
False.
To insert a value, you compare it with the current node and move left if it is smaller or right if it is larger, not always to the left child first.
Define in-order successor in a Binary Search Tree.
The in-order successor in a Binary Search Tree is the smallest node in the right subtree of a given node.
What are the three cases to consider when deleting a node from a Binary Search Tree?
The three cases to consider are: 1. The node is a leaf node. 2. The node has only one child. 3. The node has two children.
If the node to be deleted in a Binary Search Tree has child, its value is copied and then the node is .
If the node to be deleted in a Binary Search Tree has one child, its value is copied and then the node is deleted.
True or False?
A node with two children in a Binary Search Tree is deleted by replacing it with its left child.
False.
A node with two children is deleted by replacing it with its in-order successor, which is the minimum node in its right subtree.
Define hash table.
A hash table is an associative array that uses a hash function to map keys to indices, enabling fast data access and retrieval.
A hash function maps a to an in the hash table.
A hash function maps a key to an index in the hash table.
What is a collision in a hash table?
A collision occurs when two different keys produce the same hash value and are mapped to the same location in the hash table.
True or False?
Linear probing resolves collisions by placing the data in the next available position in the hash table.
True.
Linear probing handles collisions by checking sequential positions in the hash table until an empty slot is found.
When are used for collision resolution, each location in the hash table points to a .
When chaining is used for collision resolution, each location in the hash table points to a linked list.
What is rehashing in the context of hash tables?
Rehashing is the process of creating a new hash table (often larger), reapplying the hash function to all existing keys, and reinserting them to improve efficiency and reduce collisions.
Define adjacency matrix.
An adjacency matrix is a matrix containing rows and columns used to represent a labelled graph, where each entry shows the presence, direction, or weight of edges between nodes.
In an undirected, unweighted graph, the adjacency matrix is because the presence of an edge is the same in both directions.
In an undirected, unweighted graph, the adjacency matrix is symmetric because the presence of an edge is the same in both directions.
What is the difference between a directed and an undirected graph?
A directed graph has edges that can only be traversed in one direction, while an undirected graph has edges that can be traversed in both directions.
Define hashing function.
A hashing function is an algorithm that converts a key into an index in a hash table, allowing efficient storage and retrieval of data.
True or False?
When removing data from a hash table, if the item is not found at the computed hash value, you must check the overflow table.
True.
If the data is not found at its hash value index, the overflow table is searched linearly for the item.
The main advantage of using a hash table is that it allows access to data by computing the index directly from the key.
The main advantage of using a hash table is that it allows direct access to data by computing the index directly from the key.
Sign up to unlock flashcards
or