m2 Flashcards
How do you remove data from a singly linked list?
You can only remove the data in the middle of the list.
You can only remove the last data from the list.
You can only remove the first data from the list.
You can remove the first data, last data, or any data in the list by adjusting the pointers of the respective nodes.
You can remove the first data, last data, or any data in the list by adjusting the pointers of the respective nodes.
What are the operations used in linked list structures?
Traversing the list, inserting data, removing data, and retrieving data.
Sorting the list, merging lists, splitting the list, and reversing the list.
Adding elements to the list, updating elements in the list, and searching for elements in the list.
Finding the maximum element, finding the minimum element, and finding the length of the list.
Traversing the list, inserting data, removing data, and retrieving data.
How do you retrieve data from a singly linked list?
Sort the list and compare the data field of each node to the value being searched for.
Reverse the list and compare the data field of each node to the value being searched for.
Skip every other node and compare the data field of each node to the value being searched for.
Traverse the list and compare the data field of each node to the value being searched for.
Traverse the list and compare the data field of each node to the value being searched for.
How do you insert data into a singly linked list?
Always insert the new data in between the first and second nodes of the list.
Always insert the new data at the beginning of the list.
Always insert the new data at the end of the list.
If the list is empty, create the first node. Otherwise, find the right position to insert the new data (beginning, end, or in between nodes)`
If the list is empty, create the first node. Otherwise, find the right position to insert the new data (beginning, end, or in between nodes).
What are the disadvantages of using a circular linked list?
It requires more complex implementation of operations on linked list structures.
It has limited functionality compared to other linked list structures.
It occupies more memory than other linked list structures.
It has slower traversal compared to other linked list structures
It requires more complex implementation of operations on linked list structures.
How do you traverse a singly linked list?
Starting from the head, check if the next pointer is null. If not, move to the next node until the end of the list is reached.
Starting from a random position, check if the previous or next pointer is null. If not, move to the previous or next node depending on the condition.
Starting from the tail, check if the previous pointer is null. If not, move to the previous node until the start of the list is reached.
Starting from the middle, check if the previous or next pointer is null. If not, move to the previous or next node depending on the condition.
Starting from the head, check if the next pointer is null. If not, move to the next node until the end of the list is reached.
How do you traverse and retrieve data from a circular linked list?
Skip every other node and compare the data field of each node to the value being searched for.
Reverse the list and compare the data field of each node to the value being searched for.
Sort the list and compare the data field of each node to the value being searched for.
Perform similar operations as with a singly linked list, but ensure the termination condition for traversal considers the circular nature of the list.
Perform similar operations as with a singly linked list, but ensure the termination condition for traversal considers the circular nature of the list.
What makes a doubly linked list different from a singly linked list?
A doubly linked list has a circular structure.
A doubly linked list allows bidirectional traversal.
A doubly linked list has three fields: data, previous, and next pointer.
A doubly linked list contains a reference to both the previous and next elements in the list.
A doubly linked list contains a reference to both the previous and next elements in the list.
What is a singly linked list?
A data structure that consists of two fields: data and previous pointer.
A data structure that consists of a sequence of elements, each containing a reference to the previous element.
A data structure that consists of a sequence of elements, each containing a reference to the next element.
A data structure that contains a reference to both the previous and next elements.
A data structure that consists of a sequence of elements, each containing a reference to the next element.
What are the advantages of using a circular linked list?
It uses less memory than other linked list structures.
It provides easy manipulation of the pointers and efficient searching.
It allows for faster insertion and deletion operations compared to other linked list structures.
It guarantees constant time complexity for all operations.
It provides easy manipulation of the pointers and efficient searching.
What is the purpose of converting an infix expression to postfix notation using a stack?
To reverse the order of the operands and operators
To convert numbers from decimal to binary notation
To evaluate arithmetic expressions and handle operator precedence
To group the operands and operators in parentheses
To evaluate arithmetic expressions and handle operator precedence
What are some of the applications that can be solved using Stack data structure?
Expression Evaluation, Function Call Stack, Undo Operations, Backtracking, Memory Management
Sorting Algorithms, Binary Search, Linked Lists
Looping, Conditional Statements, File Handling
Networking, Database Management, Artificial Intelligence
Expression Evaluation, Function Call Stack, Undo Operations, Backtracking, Memory Management
Which operations can be used in the implementation of Stack data structure?
Append and Prepend
Push and Pop
Insert and Delete
Sort and Search
Push and Pop
In a Stack data structure, where are elements inserted and removed?
Middle of the stack
Random positions in the stack
Bottom of the stack
Top of the stack
Top of the stack
Which notation places the operator before the operands in an arithmetic expression?
Postfix notation
Polish notation
Infix notation
Prefix notation
Prefix notation
What is the principle behind Stack data structure?
Last-in-First-Out (LIFO)
Random
First-in-First-Out (FIFO)
Priority-based
Last-in-First-Out (LIFO)
What is the application of Stacks in memory management?
Managing activation records during program execution
Displaying graphics on computer screens
Storing data on hard disks
Accessing data from databases
Managing activation records during program execution
What is the term used for inserting elements into a stack?
Insert operation
Append operation
Push operation
Add operation
Push operation
Which data structure can be used to implement a Stack?
Arrays and Linked Lists
Queues and Graphs
Hash Tables and Trees
Sets and Matrices
Arrays and Linked Lists
What is the term used for deleting elements from a stack?
Remove operation
Extract operation
Pop operation
Delete operation
Pop operation
What is the function of the IsNull() operation in the Queue data structure?
Returns the size of the Queue
Evaluates if the queue is empty
Retrieves the element from the front of the Queue without removing it
Checks if the Queue is full or not
Evaluates if the queue is empty
Which operation is used to store elements in the Queue?
Size
Peek
Dequeue
Enqueue
Enqueue
Which operations can be used in the implementation of the Queue data structure?
Push and Pop
Enqueue and Dequeue
Sort and Search
Insert and Delete
Enqueue and Dequeue
What is the function of the Peek() operation in the Queue data structure?
Get the element from the front of the Queue without removing it
Enqueue the element into the Queue
Dequeue the element from the Queue
Returns the size of the Queue
Get the element from the front of the Queue without removing it
What is the function of the Size() operation in the Queue data structure?
Retrieves the element from the front of the Queue without removing it
Inserts the element into the Queue
Checks if the Queue is empty or not
Returns the size of the Queue
Returns the size of the Queue
What is the function of the IsFull() operation in the Queue data structure?
Checks if the Queue is full or not
Checks if the Queue is empty or not
Returns the size of the Queue
Retrieves the element from the front of the Queue without removing it
Checks if the Queue is full or not
Which operation is used to remove elements from the Queue?
Size
Enqueue
Peek
Dequeue
Dequeue
What is the principle behind the Queue data structure?
Random access
First In First Out (FIFO)
Last In First Out (LIFO)
Stack
First In First Out (FIFO)
What are some applications that can be solved using the Queue data structure?
Sorting and Searching
Job scheduling and Handling resource sharing
Hashing and String Matching
Graph Traversal and Shortest Path Finding
Job scheduling and Handling resource sharing
What are some of the variations of the Queue data structure?
Circular Queue and Priority Queue
Binary Tree and Heap
Graph and Hash Table
Stack and Linked List
Circular Queue and Priority Queue
What is a heap tree?
A binary tree with only leaf nodes
A binary tree with no nodes
A complete binary tree where the key at the root node is either the greatest (Max-Heap) or the smallest (Min-Heap) among all its children
A binary tree with only root nodes
A complete binary tree where the key at the root node is either the greatest (Max-Heap) or the smallest (Min-Heap) among all its children
What is the depth of a tree?
The highest level of the tree
The number of leaf nodes in the tree
The number of edges in the tree
The number of nodes in the tree
The highest level of the tree
What is a tree data structure?
A finite collection of data arranged in a hierarchical fashion
A linear collection of data arranged in a hierarchical fashion
A random collection of data arranged in a hierarchical fashion
An infinite collection of data arranged in a hierarchical fashion
A finite collection of data arranged in a hierarchical fashion
What is a subtree?
A tree with only leaf nodes
A tree with only root nodes
A complete tree within the main tree
A tree with no nodes
A complete tree within the main tree
What is the degree of a node?
The value of the node
The parent of the node
The level of the node
The number of child nodes
The number of child nodes
What is a leaf node?
A node with no child nodes
A node with a value of 0
A node with multiple child nodes
There is no such thing as a leaf node
A node with no child nodes
What is a binary search tree (BST)?
A binary tree with no sub-trees
A binary tree with only one node
An ordered binary tree where elements in the left sub-tree are less than the root, and elements in the right sub-tree are greater than or equal to the root
A binary tree with no order
An ordered binary tree where elements in the left sub-tree are less than the root, and elements in the right sub-tree are greater than or equal to the root
What is the root node of a tree?
There is no root node
The middle node
The topmost node
The bottommost node
The topmost node
What is a binary tree?
A tree with only one node
A tree where each node can have at most 2 children
A tree with no children
A tree with unlimited children
A tree where each node can have at most 2 children
What is an AVL tree?
A binary search tree with no balance factor
A binary search tree with infinite nodes
A binary search tree with no heights assigned
A height-balanced binary search tree where each node is associated with a balance factor that equals the height of its left sub-tree minus the height of its right sub-tree
A height-balanced binary search tree where each node is associated with a balance factor that equals the height of its left sub-tree minus the height of its right sub-tree
What is a skewed binary tree?
A binary tree in which the height is the maximum number of nodes
A binary tree in which all nodes have only one child
A binary tree in which the height is always equal to the number of nodes
A binary tree in which the height is the maximum number of branches plus 1
A binary tree in which the height is the maximum number of branches plus 1
What is a binary tree?
A tree in which the left subtree always has smaller values
A tree in which every node has exactly two children
A tree in which the right subtree always has larger values
A tree in which no node can have more than two subtrees
A tree in which no node can have more than two subtrees
What is an almost complete binary tree?
In the last level, the nodes will be as far left as possible and all other levels have maximum nodes
A binary tree in which nodes are evenly distributed across all levels
A binary tree in which the height is always equal to the number of nodes
A binary tree in which all nodes have two children
In the last level, the nodes will be as far left as possible and all other levels have maximum nodes
What does In-order traversal mean?
Traverse the right subtree first, then the root, and finally the left subtree
Traverse the root first, then the right subtree, and finally the left subtree
Traverse the left subtree first, then the root, and finally the right subtree
Traverse the root first, then the left subtree, and finally the right subtree
Traverse the left subtree first, then the root, and finally the right subtree
What does Pre-order traversal mean?
Traverse the right subtree, then left subtree, and finally root
Traverse the left subtree, then right subtree, and finally root
Traverse the right subtree, then root, and finally the left subtree
Traverse the root first, then left subtree, and finally right subtree
Traverse the root first, then left subtree, and finally right subtree
What is a strictly binary tree?
The degree of any node in the binary tree will be either 0 or 2
The degree of any node in the binary tree will be either 1 or 3
The degree of any node in the binary tree will be either 2 or 3
The degree of any node in the binary tree will be either 1 or 2
The degree of any node in the binary tree will be either 0 or 2
What is a complete binary tree?
A binary tree that contains exactly 2^d nodes at each level between level 0 and d
A binary tree in which the height is the maximum number of nodes
A binary tree in which the height is the maximum number of levels
A binary tree in which all nodes have exactly one child
A binary tree that contains exactly 2^d nodes at each level between level 0 and d
What are the characteristics of a binary tree data structure?
A node can only have a right subtree
A node can only have a left subtree
A node always has exactly two subtrees
A node can have zero, one, or two subtrees
A node can have zero, one, or two subtrees
What does Post-order traversal mean?
Traverse the root first, then the right subtree, and finally the left subtree
Traverse the right subtree first, then the left subtree, and finally the root
Traverse the root first, then the left subtree, and finally the right subtree
Traverse the left subtree first, then the right subtree, and finally the root
Traverse the left subtree first, then the right subtree, and finally the root
How do we traverse a binary tree?
Pre-order, In-order, Post-order
Only In-order traversal
Only Post-order traversal
Only Pre-order traversal
Pre-order, In-order, Post-order
What is the disadvantage of binary search?
Requires additional memory for storing and manipulating the tree structure
Not suitable for large datasets
Requires the array to be sorted and requires elements to be comparable
Slow searching process in comparison to arrays and linked lists
Requires the array to be sorted and requires elements to be comparable
How is a node searched in a binary search tree?
The search is performed by traversing the tree in breadth-first order
Starting from the root, the key value is compared with the node’s value and the search continues in the left subtree if it’s less or in the right subtree if it’s greater
Only the nodes in the lower levels of the tree are considered for search
Starting from any leaf node, the key value is compared with the node’s value and the search continues until the root is reached
Starting from the root, the key value is compared with the node’s value and the search continues in the left subtree if it’s less or in the right subtree if it’s greater
What are the characteristics of a binary search tree?
The values in the left subtree are greater than the root, and the values in the right subtree are less than the root
The values in the left subtree are less than the root, and the values in the right subtree are greater than the root
The tree has a balanced structure with equal number of nodes in each level
The tree has a height of log(n), where n is the number of nodes
The values in the left subtree are less than the root, and the values in the right subtree are greater than the root
What are the operations that can be performed on a binary search tree?
Finding the median of the elements, computing the sum of all elements
Balancing the tree, merging two trees into one
Sorting the tree in ascending order, finding the height of the tree
Inserting a node, searching for a node, deleting a node, traversing the tree
Inserting a node, searching for a node, deleting a node, traversing the tree
What are some applications of binary search trees?
Sorting elements in descending order
Performing arithmetic operations on large numbers
Building algorithms for machine learning, searching in computer graphics, searching in databases
Storing and retrieving data from cache memor
Building algorithms for machine learning, searching in computer graphics, searching in databases
What is the expected result of an in-order traversal of a binary search tree?
The nodes are visited in descending order of their values
The nodes are visited in ascending order of their values
The nodes are visited in a pre-determined order based on their level in the tree
The nodes are visited in a random order
The nodes are visited in ascending order of their values
What is a binary search tree (BST)?
A type of tree used for sorting elements in ascending order
A type of binary tree with specific ordering properties
A type of tree used for storing data in a balanced manner
A type of search algorithm that uses a binary approach
A type of binary tree with specific ordering properties
How is a new node inserted in a binary search tree?
The value is always inserted as the root node
The value is compared with the root and inserted in the left subtree if it’s less or in the right subtree if it’s greater
The value is inserted randomly in any subtree
The value replaces the current root node and becomes the new root
The value is compared with the root and inserted in the left subtree if it’s less or in the right subtree if it’s greater
How is a node deleted in a binary search tree?
The node is removed and the height of the tree is adjusted accordingly
The node is replaced with the maximum value from the right subtree
The node is replaced with the minimum value from the left subtree
The node is replaced with either the in-order predecessor or the in-order successor, depending on the case
The node is replaced with either the in-order predecessor or the in-order successor, depending on the case
What is the advantage of using a binary search tree?
Efficient storage of elements in contiguous memory locations
Efficient searching, insertion, and deletion operations
Efficient retrieval of an element at a specific index
Efficient sorting of elements in ascending order
Efficient searching, insertion, and deletion operations
Which case of imbalance in an AVL tree requires a single left rotation?
LL (Left-Left Imbalance)
RL (Right-Left Imbalance)
LR (Left-Right Imbalance)
RR (Right-Right Imbalance)
RR (Right-Right Imbalance)
Which case of imbalance in an AVL tree requires a double rotation?
LL (Left-Left Imbalance)
LR (Left-Right Imbalance)
RL (Right-Left Imbalance)
RR (Right-Right Imbalance)
LR (Left-Right Imbalance) / RL (Right-Left Imbalance)
What are the procedures to maintain a balanced BST?
Add nodes randomly to balance the tree
Perform rotations to balance the tree
Remove all nodes with balance factor greater than 1
Sort the elements in the tree in ascending order
Perform rotations to balance the tree
What is the balance factor (BF) of a node in an AVL tree?
The minimum height of the left and right subtrees
The difference between the height of the left subtree and the height of the right subtree
The sum of the heights of the left and right subtrees
The maximum height of the left and right subtrees
The difference between the height of the left subtree and the height of the right subtree
What is an AVL tree?
A tree with arbitrary balance factors
A tree with only left subtrees
A tree with no balance factor
A self-balancing binary search tree
A self-balancing binary search tree
Which case of imbalance in an AVL tree requires a single right rotation?
LR (Left-Right Imbalance)
LL (Left-Left Imbalance)
RR (Right-Right Imbalance)
RL (Right-Left Imbalance)
LL (Left-Left Imbalance)
What are the forms of a BST that are not balanced?
Perfect binary trees
Full binary trees
Complete binary trees
Left-skewed and right-skewed trees
Left-skewed and right-skewed trees
What are the characteristics of a balanced binary search tree?
The heights of the left and right subtrees are determined randomly
The heights of the left and right subtrees differ at most by 1 for every node
The heights of the left and right subtrees are always the same
The heights of the left and right subtrees can differ by any amount
The heights of the left and right subtrees differ at most by 1 for every node
What are the possible balance factors for a node in an AVL tree?
Show answer choices
−1, 0, 1, or 2
0, 1, or 2
−2, −1, 0, or 1
−1, 0, or 1
−1, 0, or 1
Which case of imbalance in an AVL tree requires a double rotation?
RR (Right-Right Imbalance)
RL (Right-Left Imbalance)
LR (Left-Right Imbalance)
LL (Left-Left Imbalance)
RL (Right-Left Imbalance) / LR (Left-Right Imbalance)
What are the characteristics of a heap tree data structure?
It is used in Prim’s algorithm.
It has a binary tree structure.
It allows elements to be accessed in constant time.
It has a heap property that states the data value of any parent node is greater than or equal to the data value of its children.
It has a heap property that states the data value of any parent node is greater than or equal to the data value of its children.
What is the heap property in a max-heap?
The tree follows a complete binary tree structure.
The data value of any parent node is greater than or equal to the data value of its children.
The data value of any parent node is less than or equal to the data value of its children.
The root of the tree contains the largest data element.
The data value of any parent node is greater than or equal to the data value of its children.
What does the empty function on the vector indicate in a heap tree implementation?
It checks if the vector is in a valid state.
It checks if the vector is full and no more elements can be added.
It checks if the heap is empty.
It checks if the heap is full and needs resizing.
It checks if the heap is empty.
What are the steps involved in inserting a new data element in a heap tree?
Append the new data to the end of the tree.
Replace the data of the last (rightmost) leaf node with the new data.
Check if the tree is empty before inserting the new data.
Insert the new data as the next node, check if it violates the heap property, and make necessary swaps if required.
Insert the new data as the next node, check if it violates the heap property, and make necessary swaps if required.
What are the operations on a heap tree?
Traversal and searching of data elements.
Modification and sorting of data elements.
Creation and manipulation of data elements.
Insertion and deletion of data elements.
Insertion and deletion of data elements.
What is the heap property in a min-heap?
The root of the tree contains the smallest data element.
The data value of any parent node is less than or equal to the data value of its children.
The data value of any parent node is greater than or equal to the data value of its children.
The tree follows a binary search tree structure.
The data value of any parent node is less than or equal to the data value of its children.
How is the root element deleted in a max-heap?
Replace the data of the root node with that of the last (rightmost) leaf node and perform heapifyDown to maintain the heap property.
Delete the last leaf node of the tree.
Swap the root element with its largest child.
Perform heapifyUp on the root node.
Replace the data of the root node with that of the last (rightmost) leaf node and perform heapifyDown to maintain the heap property.
What is an application of a heap tree?
Sorting using heap sort.
Accessing the minimum or maximum element in constant time.
Implementing priority queues.
Finding the minimum cost edge in the Prim’s algorithm.
All of the above.
All of the above.
What is the purpose of a vector in a heap tree implementation?
It maintains the heap property by comparing the value at a given index with its children nodes.
It adds a new element to the heap by pushing it to the back of the vector and calling heapifyUp.
It maintains the heap property by comparing the value at a given index with its parent node.
It stores elements and allows fast random access to any element.
It stores elements and allows fast random access to any element.
What is a heap data structure?
A type of sorting algorithm.
A linear arrangement that allows fast random access to any element.
A special type of tree structure that follows a heap property.
A data structure used to maintain the heap property.
A special type of tree structure that follows a heap property.
What are some operations that can be used in the implementation of a graph data structure?
Add vertex, add edge, remove vertex, remove edge, search for a node, and traverse the graph
Push, pop, enqueue, and dequeue
Sort, merge, and search
Insert, delete, and search
Add vertex, add edge, remove vertex, remove edge, search for a node, and traverse the graph
What are the terminologies used in a graph data structure?
Nodes and pointers
Vertices and edges
Leaves and parents
Indexes and elements
Vertices and edges
What is an undirected graph?
A graph where each node is connected with all other nodes
A graph where each vertex has an in-degree and an out-degree
A graph where the edges have no direction
A graph where the edges form an ordered pair
A graph where the edges have no direction
What is a graph data structure?
A linear data structure used to store a collection of elements.
A data structure that stores data in a hierarchical manner.
A finite collection of interlinked data represented by a set of vertices and edges.
A data structure used to implement stacks and queues.
A finite collection of interlinked data represented by a set of vertices and edges.
What is a complete graph?
A graph with two or more disconnected graphs
A graph where the edges have no direction
A graph where every node is connected with all other nodes
A graph with a cycle consisting of a single arc
A graph where every node is connected with all other nodes
What are two common graph traversal algorithms?
Selection Sort and Bubble Sort
Insertion Sort and Merge Sort
Breadth First Search (BFS) and Depth First Search (DFS)
Linear Search and Binary Search
Breadth First Search (BFS) and Depth First Search (DFS)
What are some applications that can be solved using a graph data structure?
Performing mathematical calculations
Finding shortest routes, planning computer networks, social networking, representing website structures
Storing and retrieving data
Searching and sorting data
Finding shortest routes, planning computer networks, social networking, representing website structures
How do we represent a graph in a solution?
By using an array
By using an adjacency matrix or an adjacency list
By using a hash table
By using a linked list
By using an adjacency matrix or an adjacency list
What is a path in a graph?
A sequence of nodes that are followed in order to reach some terminal node from an initial node
A cycle in the graph
A complete graph with all nodes connected
A set of adjacent vertices
A sequence of nodes that are followed in order to reach some terminal node from an initial node
What is a cycle in a graph?
A path consisting of at least three vertices that starts and ends with the same vertex
A graph where all nodes are connected with all other nodes
A set of disjoint graphs
A loop in the graph
A path consisting of at least three vertices that starts and ends with the same vertex
