8.2 Algorithms for the Main Data Structures (OCR A Level Computer Science) Flashcards
Exam code: H446
1/56
0Still learning
Know0
- FrontStacks
Define stack in programming.
Was this flashcard deck helpful?
Cards in this collection (56)
Define stack in programming.
A stack is a data structure that follows the Last In First Out (LIFO) principle, where elements are added and removed from the top.
Which stack operation allows you to view the top element without removing it?
The peek operation allows you to view the top element of the stack without removing it.
To check if a stack is empty, you can use the operation.
To check if a stack is empty, you can use the isEmpty operation.
True or False?
The push operation removes the top element from a stack.
False.
The push operation adds an element to the top of the stack. Removing the top element is done by the pop operation.
Define Stack class in Python.
The Stack class in Python is a user-defined data structure that stores elements up to a specified capacity and provides methods to push, pop, and peek items, as well as check if the stack is empty or full.
What does the push() method do in the Python Stack class?
The push() method adds an item to the stack if there is space available; otherwise, it prints a message indicating that the stack is full.
The pop() method removes and returns the item from the stack if it is not empty.
The pop() method removes and returns the top item from the stack if it is not empty.
True or False?
The peek() method removes the top item from the stack.
False.
The peek() method returns the top item of the stack without removing it.
Define AnimalStack class.
The AnimalStack class is a Java class that uses a stack to store animal names, with methods for pushing, popping, peeking, and checking the stack’s capacity and status.
The push method adds an animal to the stack if it is not . Otherwise, it prints a message.
The push method adds an animal to the stack if it is not full. Otherwise, it prints a message.
What does the pop method do in the AnimalStack class?
The pop method removes and returns the top animal from the stack if it is not empty; otherwise, it prints a message and returns null.
True or False?
The peek method removes the top animal from the stack.
False.
The peek method only returns the top animal without removing it from the stack.
Define enqueue in the context of a linear queue.
To enqueue means to add an item to the rear of a queue. This operation first checks if the queue is full before inserting the new element.
In a linear queue, the index pointer is initialised to 0 and the index pointer is initialised to -1.
In a linear queue, the front index pointer is initialised to 0 and the rear index pointer is initialised to -1.
What does the isFull() subroutine check before an item is enqueued in a linear queue?
The isFull() subroutine checks whether the rear index pointer has reached the final position in the array, meaning the queue is full and cannot accept new items.
The operation removes the item at the of the queue and increments the pointer by 1.
The dequeue operation removes the item at the front of the queue and increments the front pointer by 1.
Define circular queue.
A circular queue is a data structure where the positions of the front and rear pointers wrap around to the start of the array when they reach the end, allowing efficient use of storage.
True or False?
In a circular queue, when the rear pointer is at the last position in the array, the next position becomes 0.
True.
This occurs because (rear + 1) MOD MAX_SIZE resets the pointer to 0 when it reaches the end of the array.
A circular queue is initialised by setting the and pointers to -1.
A circular queue is initialised by setting the front and rear pointers to -1.
How do you check if a circular queue is full before enqueuing an item?
A circular queue is full if (rear + 1) MOD MAX_SIZE == front, meaning the next position would overwrite the item at the front pointer.
Define priority queue.
A priority queue is a data structure where each item has an associated priority, and items are removed in order of descending priority, with higher priority elements being dequeued before lower priority ones.
To implement a priority queue using object-oriented programming, you should the data and methods within a class definition.
To implement a priority queue using object-oriented programming, you should encapsulate the data and methods within a class definition.
True or False?
In a priority queue, new elements with higher priority than all existing elements are inserted at the front of the queue.
True.
If a new element has a higher priority than all elements currently in the queue, it is inserted at the front so it will be dequeued first.
What does the dequeue operation do in a priority queue?
The dequeue operation removes and returns the element with the highest priority from the priority queue.
Define linked list.
A linked list is a data structure consisting of nodes, where each node contains a value and a reference to the next node in the sequence.
What fields are present in a node of a linked list when storing fruits?
Each node has two fields: fruit to store the value and next to reference the next node in the list.
To connect nodes in a linked list, set the field of each node to the .
To connect nodes in a linked list, set the next field of each node to the next node.
True or False?
To remove a node from a linked list, you must update the previous node’s next field.
True.
To remove a node, the next field of the previous node must point to the node after the one being removed.
Define Node in the context of a linked list.
A Node is an object or structure that contains data (such as a fruit value) and a reference to the next node in the linked list.
What does the next field in a linked list node represent?
The next field stores a reference or pointer to the next node in the linked list. If it is None, that node is the last in the list.
To create a basic linked list, we define a class with a data field and a field that points to the next node.
To create a basic linked list, we define a Node class with a data field and a next field that points to the next node.
True or False?
In a singly linked list, each node can have more than one next reference.
False.
In a singly linked list, each node has only one next reference, which points to the next node in the sequence.
In the algorithm to add data to a linked list, what must you do after creating the new node if the list is not empty?
If the list is not empty, you must find the last node and append the new node to the end of the list.
To add a new node to an empty linked list, set the to the new node.
To add a new node to an empty linked list, set the head to the new node.
True or False?
When adding a node to a non-empty linked list, you must always update the head pointer.
False.
When adding to a non-empty linked list, you only update the next pointer of the last node, not the head pointer.
Define linked list node removal.
Linked list node removal is the process of traversing a linked list to locate the node containing the target data and updating pointers to remove that node from the list.
What must be updated when removing the first node of a linked list?
When removing the first node of a linked list, the head pointer must be updated to point to the next node.
To remove a node from a linked list, you must update the pointer of the previous node to point to the node .
To remove a node from a linked list, you must update the next pointer of the previous node to point to the node after the one being removed.
True or False?
When removing a node from a linked list, the list must be traversed until the node containing the data is found.
True.
To remove a node, you must traverse the list until you find the target data, then update pointers to remove it.
Define TreeNode in the context of tree data structures.
A TreeNode is a structure in a tree data structure that stores a value and a collection of child nodes.
What is the purpose of the addChild function when programming a tree?
The addChild function creates a new node with a specified value and appends it to the children collection of the parent node, helping to build the tree structure.
To create the root node of a tree, you call the function with the desired .
To create the root node of a tree, you call the createTreeNode function with the desired value.
True or False?
Each node in a tree data structure can have only one child.
False.
Each node in a tree can have multiple children, allowing for branches at every node.
In the tree example, to add a grandchild node, you use on .
In the tree example, to add a grandchild node, you use addChild on root.children[0].
Define post-order traversal.
A post-order traversal is a method of traversing a tree where you visit the left subtree, then the right subtree, and finally the root node.
True or False?
In post-order traversal, the root node is visited before the left and right subtrees.
False.
In post-order traversal, the root node is visited after traversing the left and right subtrees.
In post-order traversal, nodes are visited in the following order: , , .
In post-order traversal, nodes are visited in the following order: left subtree, right subtree, root node.
What attributes does a Node object have in a binary tree used for post-order traversal?
A Node object has three attributes: node.data (the value), node.left (pointer to the left child), and node.right (pointer to the right child).
Define binary tree.
A binary tree is a type of data structure where each node has at most two children, referred to as the left child and right child.
In a binary tree, what are the left and right properties of a node used for?
The left and right properties of a node are used to store references to its two possible child nodes in the binary tree.
The add_node function takes two parameters: the of the binary tree and the to be added.
The add_node function takes two parameters: the root of the binary tree and the value to be added.
True or False?
The add_node algorithm adds a new node to the binary tree by always inserting it as the left child of the root.
False.
The add_node algorithm traverses the binary tree to find the first available position, which could be either the left or right child of any node, not always the left child of the root.
Define find_node function.
The find_node function is a function that searches for a node with a given value in the tree..
What are the three cases that must be handled when removing a node from a binary tree?
When removing a node from a binary tree, the three cases are: the node has no children (leaf), the node has one child, and the node has two children. Each case requires a different approach.
If a node has two children, to remove it from a binary tree you must find the value node in the right subtree and replace the node's data with this value.
If a node has two children, to remove it from a binary tree you must find the minimum value node in the right subtree and replace the node's data with this value.
Define find_minimum function.
The find_minimum function is a function that finds the node with the minimum value in a given subtree.
Sign up to unlock flashcards
or