1.
The _____________ algorithm works by repeatedly scanning through the list, comparing adjacent elements, and swapping them if they are in the wrong order.
Correct Answer
A. Bubble sort
Explanation
Bubble sort is the correct answer because it is an algorithm that repeatedly scans through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted. Bubble sort is known for its simplicity but is not efficient for large lists.
2.
The _____________ algorithm works by repeatedly scanning through the list, comparing adjacent elements, and swapping them if they are in the wrong order.
Correct Answer
A. Bubble sort
Explanation
Bubble sort is an algorithm that works by repeatedly scanning through the list, comparing adjacent elements, and swapping them if they are in the wrong order. This process is repeated until the list is sorted. In each pass, the largest element "bubbles" up to its correct position, hence the name "bubble sort".
3.
A __________ is a list of elements in which items are always inserted at one end and deleted from the other end.
Correct Answer
A. Queue
Explanation
A queue is a data structure that follows the FIFO (First-In-First-Out) principle, where elements are inserted at one end called the rear and deleted from the other end called the front. This means that the first element inserted into the queue will be the first one to be removed. Therefore, a queue is the correct answer as it fits the description of a list of elements where items are always inserted at one end and deleted from the other end.
4.
In ______________ traversal method, the root is processed before traversing the left and right subtrees.
Correct Answer
A. Preorder
Explanation
In Preorder traversal method, the root is processed before traversing the left and right subtrees. This means that the root node is visited first, followed by the traversal of the left subtree, and then the right subtree. This order of processing ensures that the root is always visited before its children, making it a pre-order traversal.
5.
Identify the degree of a node B in the given figure.
Correct Answer
A. 1
Explanation
The degree of a node in a graph refers to the number of edges connected to that node. In the given figure, node B is connected to only one edge, which is represented by the number 1. Therefore, the degree of node B is 1.
6.
Which of the following Big O Notations has constant order of growth?
Correct Answer
B. O(1)
Explanation
The Big O Notation O(1) has a constant order of growth. This means that the time complexity of the algorithm does not depend on the size of the input. It will always take the same amount of time to execute, regardless of the input size. This is because the algorithm has a fixed number of operations that it performs, and it does not increase or decrease with the input size. Therefore, O(1) represents a constant time complexity.
7.
What is the order of growth of the bubble sort algorithm?
Correct Answer
C. Quadratic
Explanation
The bubble sort algorithm has a quadratic order of growth. This means that as the size of the input increases, the time it takes to sort the elements using bubble sort increases quadratically. In other words, if the input size doubles, the time it takes to sort the elements will increase by a factor of four. This is because bubble sort compares and swaps adjacent elements multiple times until the entire list is sorted, resulting in a time complexity of O(n^2).
8.
To implement __________ search algorithm, the list should be sorted.
Correct Answer
B. Binary
Explanation
To implement the binary search algorithm, the list should be sorted. This is because the binary search algorithm works by repeatedly dividing the sorted list in half and comparing the target value with the middle element. If the list is not sorted, the algorithm will not be able to accurately determine the position of the target value, leading to incorrect results. Therefore, sorting the list is a prerequisite for successfully implementing the binary search algorithm.
9.
Consider the algorithm to insert a node at the beginning of the link list and identify the error:
1. Assign value to the data field of the new node
2. Allocate memory for the new node
3. Make the next field of the new node point to the first node in the list.
4. Make START point to the new node.
Correct Answer
C. The sequence is wrong, the correct sequence is 2->1->3->4
Explanation
The given correct answer suggests that the error in the algorithm is that the sequence of the steps is incorrect. The correct sequence should be 2->1->3->4. This means that the new node should be inserted after the second node, making it the first node in the list.
10.
Which of the following will be the postfix expression for the given infix expression: ((C+(D*E))-F)
Correct Answer
A. CDE*+F-
Explanation
The given infix expression is ((C+(D*E))-F). To convert it to postfix, we follow the rules of postfix conversion. First, we encounter C, so we push it into the stack. Then, we encounter +, so we push it into the stack. Next, we encounter D, so we push it into the stack. After that, we encounter *, which has higher precedence than +, so we push it into the stack. Then, we encounter E and push it into the stack. Now, we encounter the closing parenthesis, so we pop all the operators from the stack until we reach the opening parenthesis and add them to the postfix expression. The next operator is -, which has lower precedence than *, so we push it into the stack. Finally, we encounter F, so we push it into the stack. We have reached the end of the expression, so we pop all the remaining operators from the stack and add them to the postfix expression. The resulting postfix expression is CDE*+F-.
11.
What address would a node with an empty left child of a threaded binary tree store?
Correct Answer
D. Inorder predecessor
Explanation
In a threaded binary tree, a node with an empty left child would store the inorder predecessor. The inorder predecessor is the node that comes before the current node in the inorder traversal of the tree. Since the left child is empty, there is no node to the left of the current node, so the inorder predecessor is stored in the current node.
12.
What will be the Inorder traversal of the given tree?
Correct Answer
A. D H B E A F C I G J
Explanation
The given tree's inorder traversal is D H B E A F C I G J.
13.
Which of the following stack operations could result in stack underflow?
Correct Answer
B. Pop
Explanation
The pop operation could result in a stack underflow. This is because when we try to pop an element from an empty stack, there are no elements to remove, leading to an underflow condition.
14.
If a stack is represented in memory by using a linked list, then insertion and deletion of data will be done ___.
Correct Answer
B. At the beginning of the list
Explanation
When a stack is represented in memory using a linked list, the insertion and deletion of data will be done at the beginning of the list. This is because in a linked list, adding or removing an element at the beginning is more efficient than doing it at the end. When inserting at the beginning, we simply need to update the head pointer to point to the new element, while when deleting at the beginning, we just need to update the head pointer to skip the first element. This allows for constant time complexity for both insertion and deletion operations.
15.
If a stack is represented in memory by using an array, then what will be the stack overflow condition?
Correct Answer
C. Top=SIZE-1
Explanation
In a stack represented in memory by using an array, the stack overflow condition occurs when the top of the stack reaches the maximum size of the array minus one (Top=SIZE-1). This means that the stack is full and there is no more space to add new elements to it. If the top of the stack exceeds this value (Top=SIZE), it would result in accessing memory beyond the array's bounds, causing a stack overflow error.
16.
If a queue is represented in memory by using a linked list, then what will be the stack empty condition?
Correct Answer
D. FRONT=NULL
Explanation
In a linked list representation of a queue, the front pointer points to the first element in the queue and the rear pointer points to the last element. When the queue is empty, both the front and rear pointers should be NULL, indicating that there are no elements in the queue. Therefore, the stack empty condition in this case would be FRONT=NULL.
17.
Consider the following statement related to queue:
A. The Insertion is done at REAR and deletion at FRONT end
B. A queue is also known as LIFO list.
Correct Answer
A. Statement A is true and B is False
Explanation
The correct answer is that Statement A is true and B is False. This means that insertion is indeed done at the rear end of a queue, while deletion occurs at the front end. However, a queue is not known as a LIFO (Last In, First Out) list. Instead, a queue follows the FIFO (First In, First Out) principle, where the element that is inserted first is the one that will be deleted first.
18.
In a binary search tree, all values in the left subtree of a node are ________ than the value of the node.
Correct Answer
A. Smaller
Explanation
In a binary search tree, all values in the left subtree of a node are smaller than the value of the node. This is because binary search trees follow a specific ordering rule, where all values in the left subtree must be smaller than the parent node, and all values in the right subtree must be greater than the parent node. This allows for efficient searching and retrieval of values in the tree.
19.
What is the tree empty condition for a Threaded Binary Tree?
Correct Answer
C. The left child field of the header node is a thread pointing to itself
Explanation
The tree empty condition for a Threaded Binary Tree is when the left child field of the header node is a thread pointing to itself. This means that there are no actual left child nodes in the tree, and the left child field is being used as a thread to navigate the tree. This condition indicates that the tree does not contain any elements or nodes.
20.
Consider the algorithm of deleting a node from the beginning of a linked list and identify the error:
1. Mark the first node in the list as current
2. Make START point to the next node in sequence.
3. Release the memory for the node marked as current.
Correct Answer
A. The algorithm has no error
Explanation
The given algorithm correctly deletes a node from the beginning of a linked list. It starts by marking the first node as the current node, then it updates the start pointer to point to the next node in the sequence, and finally, it releases the memory for the node marked as current. This sequence of steps ensures that the first node is properly removed from the linked list without any errors.