Test: Miscellaneous Topics- 1 - Computer Science Engineering (CSE) MCQ

If, a node has K children in B-tree, then the node contains exactly K - 1 keys

T(n) = T ( n - 1) + T ( n - 1)+1
[recursive (n - 1) = T( n - 1)]
= 2T( n - 1)+1 = O(2ⁿ [using substitution method]

Number of spanning tree possible with n-node = n^n-2
Given, n = 7
Total number of spanning trees = 7⁵

Given array:

So, the order of elements after second pass of the algorithm is 8,15,20,47, 4,9,30,40,12,17

Worst case time complexity of Quick sort
= O(n²) when input is already sorted,
Worst case time complexity of Heap sort = O(n log n).
Worst case time complexity of Merge sort = O(n log n).

An articulation point (or cut vertex) is that vertex removing which (along with its edges) disconnects the graph.

Therefore number of articulation points is 3.

Post order traversal = a b - cd*+. As we know that post order traversal goes in the order of LEFT CHILD - RIGHT CHILD - PARENT  (ROOT)

Hence, Label of 4,5,2 will be a, b, - respectively
Label of 6,7,3 will be c, d, - respectively

Label of 1 will be +

The corresponding expression is - (- a - b) + e!
This is 1 if a = - b and e is either 1 or 0, since 1! = 0! = 1

All pairs shortest path is find using Floyd Warshall algorithm, which is an example of dynamic programming.

• Quick sort and merge sort are example of “divide and conquer” algorithms.
• MST or minimum weight spanning tree is a tree with a subset of edges such that it connects all vertices and summation of edge weight is minimum Prim’s algo and Kruskal’s algorithm are used for this, which are examples of greedy approach.
• By using Depth First Search (DFS) one can easily find set of connected components.

Since the tree is used for sorting hence taking INORDER TRAVERSAL (Left-Root-Right) we have 8 placed at the left child of the node labeled 10.