All questions of Programming & Data Structures for Computer Science Engineering (CSE) Exam

Main Applications of Tree Data Structure:

1. Manipulate Hierarchical Data:
Trees are used to represent hierarchical data, such as file systems or organization charts, where each node represents a folder, file, or employee.

2. Make Information Easy to Search:
Tree traversal algorithms can be used to search for specific data within a tree structure, making it an efficient way to store and retrieve information.

3. Manipulate Sorted Lists of Data:
Binary search trees can be used to manipulate and search sorted lists of data, providing a faster search time than traditional linear searches.

4. Router Algorithms:
Trees are used in computer networking to represent routing algorithms that determine the path of data packets through a network.

5. Multi-Stage Decision Making:
Trees can be used to represent multi-stage decision-making processes, such as in a chess game, where each node represents a possible move and the branches represent subsequent moves.

6. Workflow for Compositing Digital Images:
Trees are used in visual effects to represent the workflow for compositing digital images, where each node represents a stage in the process and the branches represent the steps taken to achieve the final image.

Therefore, the correct answer is D, as all of these applications use tree data structures.

Explanation:



The maximum number of nodes on level i of a binary tree is given by the formula: 2^(i-1)

Proof:



Let's consider the levels of the binary tree from top to bottom. The root node is at level 1, its children are at level 2, their children are at level 3, and so on.

At level 1, there is only one node which is the root node. Therefore, the maximum number of nodes on level 1 is 2^(1-1) = 1.

At level 2, there can be at most two nodes because each node at level 1 can have at most two children. Therefore, the maximum number of nodes on level 2 is 2^(2-1) = 2.

At level 3, each node at level 2 can have at most two children. Therefore, the maximum number of nodes on level 3 is 2^(3-1) = 4.

Similarly, at level i, each node at level i-1 can have at most two children. Therefore, the maximum number of nodes on level i is 2^(i-1).

Hence, the correct answer is option 'A' which is 2^(i-1).

**Answer:**

The given Java code will throw an `ArrayIndexOutOfBoundsException` when executed.

**Explanation:**

In Java, arrays are zero-indexed, which means the first element of an array is accessed using the index 0, the second element with index 1, and so on.

In the given code, an array `arr` of size 5 is declared and initialized with the values `{1, 2, 3, 4, 5}`. However, when attempting to access `arr[5]`, we are trying to access the element at index 5, which is outside the valid range of the array.

The valid indices for this array are 0, 1, 2, 3, and 4. Since index 5 does not exist in the array, an `ArrayIndexOutOfBoundsException` is thrown at runtime.

The correct way to access the last element of the array would be to use `arr[arr.length - 1]`. This expression would evaluate to `arr[4]`, which is the value 5 in this case.

Therefore, the output of the given code will be:

```
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
at array.main(array.java:7)
```

So, the correct answer is option **c) ArrayIndexOutOfBoundsException**.

What all is true about stack data structure? ( more than one option is correct)
last in first out ,
maximum 2 queues are required to implement a stack
does not have a fixed size
Correct is ABD is right ans

 Answer is not “(b) front node”, as we can not get rear from front in O(1), but if p is rear we can implement both enQueue and deQueue in O(1) because from rear we can get front in O(1). Below are sample functions. Note that these functions are just sample are not working. Code to handle base cases is missing.

For a right skewed binary tree, number of nodes will be 2^n – 1. For example, in below binary tree, node ‘A’ will be stored at index 1, ‘B’ at index 3, ‘C’ at index 7 and ‘D’ at index 15.

Since X has both children, Y must be leftmost node in right child of X.

Explanation:

To understand why the value returned by the function corresponds to the number of leaf nodes in the tree, let's analyze the pseudocode step by step.

The function DoSomething() takes a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation.

Step 1: Initialize a variable "value" to 0.

Step 2: Check if the tree pointer is not NULL. If it is NULL, it means that the tree is empty and there are no nodes. In this case, the function returns 0.

Step 3: If the tree pointer is not NULL, check if the leftMostChild pointer of the current node is NULL. If it is NULL, it means that the current node is a leaf node (a node with no children). In this case, set the value to 1.

Step 4: If the leftMostChild pointer is not NULL, recursively call the DoSomething() function with the leftMostChild pointer as the argument. This will traverse the subtree rooted at the leftMostChild pointer and count the number of leaf nodes in that subtree.

Step 5: After the recursive call, the value variable will hold the number of leaf nodes in the subtree rooted at the leftMostChild pointer.

Step 6: Call the DoSomething() function with the rightSibling pointer as the argument. This will traverse the remaining siblings of the current node and count the number of leaf nodes in each subtree rooted at the siblings.

Step 7: Finally, return the value variable.

Conclusion:

From the above analysis, we can conclude that the value returned by the DoSomething() function corresponds to the number of leaf nodes in the tree. This is because at each recursive call, the function checks whether the current node is a leaf node or not. If it is a leaf node, the value is set to 1. If it is not a leaf node, the function recursively counts the number of leaf nodes in the subtrees rooted at its children. By traversing the entire tree using the leftMostChild-rightSibling representation and counting the number of leaf nodes at each step, the function eventually returns the total number of leaf nodes in the tree.

Explanation:

In a complete binary tree, the number of nodes is always a power of 2. Let us consider a complete binary tree with 7 nodes numbered from 1 to 7 in level order traversal. The tree looks like:

```
1
/ \
2 3
/ \ / \
4 5 6 7
```

Let us now traverse the tree in inorder, preorder and postorder and observe the values of LASTIN, LASTPRE and LASTPOST.

Inorder traversal: 4 2 5 1 6 3 7
- LASTIN = 7 (last node visited in inorder traversal)
Preorder traversal: 1 2 4 5 3 6 7
- LASTPRE = 7 (last node visited in preorder traversal)
Postorder traversal: 4 5 2 6 7 3 1
- LASTPOST = 7 (last node visited in postorder traversal)

From the above example, we can see that none of the options (a), (b) or (c) are always true.

Conclusion:

Therefore, the correct answer is option (d) None of the above.

Explanation:


To create a single max heap of size 2n from two max heaps of size n, we need to perform the following steps:

1. Merge the two heaps into a single array of size 2n.
2. Call the heapify function on the merged array to create a max heap.

Time Complexity:


1. Merging two heaps into a single array of size 2n takes O(n) time complexity.
2. Heapify function takes O(n) time complexity.

Therefore, the minimum possible time complexity to make a one max-heap of size from elements of two max heaps is O(n).

Conclusion:


Hence, option 'C' is the correct answer.

The correct answer is option 'A' - O(mn). Let's understand why.

To merge two balanced binary search trees, we need to follow a specific algorithm that ensures the resulting tree is still balanced.

Here is a step-by-step explanation of the algorithm:

1. Convert B1 and B2 to sorted arrays using an inorder traversal. This step takes O(n) and O(m) time, respectively.

2. Merge the two sorted arrays into a single sorted array using the merge algorithm from Merge Sort. This step takes O(n+m) time.

3. Construct a balanced binary search tree from the merged sorted array. This step takes O(n+m) time.

4. The final balanced binary search tree contains n+m elements.

Now, let's analyze the time complexity of the algorithm:

- Converting B1 and B2 to sorted arrays takes O(n) and O(m) time, respectively.
- Merging the two sorted arrays takes O(n+m) time.
- Constructing a balanced binary search tree from the merged sorted array also takes O(n+m) time.

Therefore, the total time complexity of the algorithm is:

O(n) + O(m) + O(n+m) + O(n+m) = O(n+m) + O(n+m) = 2O(n+m) = O(n+m)

Since n and m are the number of elements in B1 and B2 respectively, the time complexity of the algorithm can be written as O(nm).

Hence, the best known algorithm to merge two balanced binary search trees to form another balanced binary tree containing n+m elements has a time complexity of O(nm), which is equivalent to O(mn). Therefore, the correct answer is option 'A' - O(mn).

Understanding the Function F(x, y)
The function F(x, y) is defined recursively with the condition that if x equals 0, it returns 0. Otherwise, it evaluates to a product involving recursive calls to itself.
Parallel-Outermost Rule
- This rule allows us to replace all outermost occurrences of F simultaneously.
- When computing F(1, 0), we consider the outermost F(1, 0).
- The evaluation leads to F(2, F(1, 0)) * F(0, F(1, 0)).
- Here, F(0, F(1, 0)) evaluates to 0, since x is 0.
Parallel-Innermost Rule
- This rule replaces all innermost occurrences of F simultaneously.
- In the case of F(1, 0), we first evaluate the innermost F calls.
- The innermost F(0, F(1, 0)) returns 0, and we are left with F(2, 0) * 0.
- According to the multiplication rules, anything multiplied by 0 yields 0.
Final Evaluation Results
- Using the parallel-outermost rule, we find that F(1, 0) evaluates to 0.
- Using the parallel-innermost rule, we also find that the evaluation of F(1, 0) leads to 0.
- Thus, the evaluation results in both cases yield 0.
Conclusion
- Therefore, the correct answer is option 'A': 0 and 0 respectively, as both methods yield the same result of 0.

The Answer Explained:

To understand why option 'A' is the correct answer, let's break down the probability calculation step by step.

Step 1: Probability of the first record not causing a collision
When the first record is inserted into the hash space, it does not collide with any existing records. The probability of this happening is 1 (since there are no other records to collide with).

Step 2: Probability of the second record not causing a collision
When the second record is inserted, there is already one record in the hash space. The probability of the second record not causing a collision is (x-1)/x. This is because there are x-1 empty slots available out of x total slots, and the second record should not occupy the same slot as the first record.

Step 3: Probability of the third record not causing a collision
When the third record is inserted, there are already two records in the hash space. The probability of the third record not causing a collision is (x-2)/x. This is because there are x-2 empty slots available out of x total slots, and the third record should not occupy the same slot as the first two records.

Step m: Probability of the mth record not causing a collision
Following the same logic, when the mth record is inserted, there are already (m-1) records in the hash space. The probability of the mth record not causing a collision is (x-(m-1))/x. This is because there are x-(m-1) empty slots available out of x total slots, and the mth record should not occupy the same slot as the previous (m-1) records.

Step (m+1): Probability of the (m+1)th record causing a collision
Now, when the (m+1)th record is inserted, there are already m records in the hash space. The probability of the (m+1)th record causing a collision is 1 - [(x-(m-1))/x]. This is because the (m+1)th record can only cause a collision if it occupies the same slot as one of the previous m records.

Overall probability:
To calculate the overall probability that the mth record is the first record to result in a collision, we multiply the probabilities from step 1 to step (m+1) together. This can be represented as:

1 * ((x-1)/x) * ((x-2)/x) * ... * (x-(m-2))/(x * (x-(m-1))/x)

Simplifying this expression, we get:

(x-1) * (x-2) * ... * (x-(m-2)) * (m-1) / xm-1

Therefore, the correct answer is option 'A': (x-1) * (x-2) * ... * (x-(m-2)) * (m-1) / xm-1.