16 AUG 24 SRM RMP Stream-II Day-04 AN

What is/are the disadvantages of implementing tree using normal arrays?

• difficulty in knowing children nodes of a node
• difficult in finding the parent of a node
• have to know the maximum number of nodes possible before creation of trees
• difficult to implement

What must be the ideal size of array if the height of tree is ‘l’?

• 2l-1
• l-1
• l
• 2l

Level order traversal of a tree is formed with the help of

• breadth first search
• depth first search
• dijkstra’s algorithm
• prims algorithm

Identify the reason which doesn’t play a key role to use threaded binary trees?

• The storage required by stack and queue is more
• The pointers in most of nodes of a binary tree are NULL
• It is Difficult to find a successor node
• They occupy less size

Advantages of linked list representation of binary trees over arrays?

• dynamic size
• ease of insertion/deletion
• ease in randomly accessing a node
• both dynamic size and ease in insertion/deletion

Disadvantages of linked list representation of binary trees over arrays?

• Randomly accessing is not possible
• Extra memory for a pointer is needed with every element in the list
• Difficulty in deletion
• Random access is not possible and extra memory with every element

Which of the following traversing algorithm is not used to traverse in a tree?

• Post order
• Pre order
• Post order
• Randomized

Time complexity of fractional knapsack problem is ____________

• O(n log n)
• O(n)
• O(n2)
• O(nW)

Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The capacity of knapsack=20. Find the maximum value output assuming items to be divisible.

• 60
• 80
• 100
• 40

The main time taking step in fractional knapsack problem is ___________

• Breaking items into fraction
• Adding items into knapsack
• Sorting
• Looping through sorted items