Kshema Previous Years Solved Sample Placement Papers
-
A binary tree that has n leaf nodes. The number of nodes of degree 2 in this tree is:
1) n
2) n - 1
3) log2n
4) n^2
Ans: Option 2
Solution:
In a binary tree, the number of nodes of degree 2 is always \( n - 1 \), where \( n \) is the number of leaf nodes. -
Which of the following is true about the characteristics of abstract data types?
i) It exports a type. ii) It exports a set of operations.
1) False, False
2) True, True
3) True, False
4) False, True
Ans: Option 2
Solution:
Abstract Data Types (ADTs) export a type and a set of operations that can be performed on the data type. -
A machine took 200 sec to sort 200 names, using bubble sort. In 800 sec, it can approximately sort:
1) 800 names
2) 400 names
3) 750 names
4) 800 names
Ans: Option 2
Solution:
Bubble sort has a time complexity of \( O(n^2) \). For 200 names, \( 200^2 = 40000 \) operations take 200 sec. In 800 sec, the machine can perform \( 4 \times 40000 \) operations, which corresponds to \( \sqrt{4 \times 40000} = 400 \) names. -
The average search time of hashing with linear probing will be less if the load factor:
1) equals one
2) is far less than one
3) is far greater than one
4) none of these
Ans: Option 2
Solution:
A lower load factor (less than 1) reduces collisions, improving the average search time in hashing with linear probing. -
The initial configuration of the queue is a,b,c,d (a is the front end). To get the configuration d,c,b,a one needs a minimum of:
1) 3 deletions and 4 additions
2) 3 deletions and 3 additions
3) 3 additions and 2 deletions
4) 2 deletions and 3 additions
Ans: Option 2
Solution:
Delete 3 elements (a, b, c) and re-add them to the rear in reverse order (c, b, a). -
State true or false:
i) The degree of root node is always zero. ii) Nodes that are not root and not leaf are called as internal nodes.
1) False, False
2) True, True
3) False, True
4) True, False
Ans: Option 3
Solution:
The degree of the root node is not zero; it depends on its children. Internal nodes are correctly described in the second statement. -
The number of binary trees with 3 nodes which when traversed in post order gives the sequence A,B,C is:
1) 9
2) 3
3) 7
4) 5
Ans: Option 4
Solution:
Using the properties of binary trees and considering permutations, the count is 5. -
Which of the following is not an internal sort?
1) Insertion Sort
2) Merge Sort
3) Heap Sort
4) Bubble Sort
Ans: Option 2
Solution:
Merge sort is an external sort as it can handle data that doesn't fit into memory. -
Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing:
1) The shortest path from W to every vertex in the graph.
2) The shortest paths from W to only those nodes that are leaves of T.
3) The longest path in the graph.
4) The shortest path between every pair of vertices.
Ans: Option 1
Solution:
BFS traversal guarantees shortest paths from the source node W to all reachable vertices in an unweighted graph. -
The number of swapping needed to sort numbers 8,22,7,9,31,19,5,13 in ascending order using bubble sort is:
1) 12
2) 11
3) 14
4) 13
Ans: Option 4
Solution:
Bubble sort repeatedly swaps adjacent elements to place them in order. Counting the swaps, we need 13 swaps. -
The postfix expression for * + a b - c d is:
1) ab cd + - *
2) ab + cd * -
3) ab + - cd *
4) ab + cd - *
Ans: Option 4
Solution:
Converting the infix expression step-by-step results in "ab + cd - *". -
Given two sorted lists of size m and n respectively. The number of comparisons needed in the worst case by the merge sort algorithm will be:
1) min(m,n)
2) mn
3) max(m,n)
4) m+n-1
Ans: Option 4
Solution:
Merging two sorted lists in the worst case involves \( m + n - 1 \) comparisons.