## Help authour, Buy PDF Ebook
>>>**Click Here**<<<

## Data Structure Questions and Answers-Rod Cutting

## Click on any option to know the CORRECT ANSWERS

Question 1 |

Given a rod of length n and the selling prices of all pieces smaller than equal to n, find the most beneficial way of cutting the rod into smaller pieces. This problem is called the rod cutting problem. Which of these methods can be used to solve the rod cutting problem?

Brute force | |

Dynamic programming | |

Recursion | |

All of the mentioned |

**NTA NET Questions answers**

Question 1 Explanation:

All the methods mentioned above can be used to solve the rod cutting problem.

Question 2 |

You are given a rod of length 5 and the prices of each length are as follows:

length price 1 2 2 5 3 6 4 9 5 9

What is the maximum value that you can get after cutting the rod and selling the pieces?

10 | |

11 | |

12 | |

13 |

**UPSC GS Questions answers**

Question 2 Explanation:

The pieces {1, 2 2} give the maximum value of 12.

Question 3 |

Consider the brute force implementation of the rod cutting problem in which all the possible cuts are found and the maximum value is calculated. What is the time complexity of this brute force implementation?

O(n ^{2}) | |

O(n ^{3}) | |

O(nlogn) | |

O(2 ^{n}) |

**Journalism Questions answers**

Question 3 Explanation:

The brute force implementation finds all the possible cuts. This takes O(2

^{n}) time.

Question 4 |

You are given a rod of length 10 and the following prices.

length price 1 2 2 5 3 6 4 9 5 9 6 17 7 17 8 18 9 20 10 22

Which of these pieces give the maximum price?

{1, 2, 7} | |

{10} | |

{2, 2, 6} | |

{1, 4, 5} |

**NTA NET Questions answers**

Question 4 Explanation:

The pieces {2, 2, 6} give the maximum value of 27.

Question 5 |

Consider the following recursive implementation of the rod cutting problem:

#include<stdio.h> #include<limits.h> int max....of....two(int a, int b) { if(a > b) return a; return b; } int rod....cut(int *prices, int len) { int max....price = INT....MIN; // INT....MIN is the min value an integer can take int i; if(len <= 0 ) return 0; for(i = 0; i < len; i++) max....price = max....of....two(.....); // subtract 1 because index starts from 0 return max....price; } int main() { int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22}, len....of....rod = 10; int ans = rod....cut(prices, len....of....rod); printf("%d", ans); return 0; }

Complete the above code.

max....price, prices[i] + rod....cut(prices, len - i - 1) | |

max....price, prices[i - 1]. | |

max....price, rod....cut(prices, len - i - 1) | |

max....price, prices[i - 1] + rod....cut(prices, len - i - 1) |

**NTA NET Questions answers**

Question 5 Explanation:

max....price, prices[i] + rod....cut(prices, len - i - 1) completes the above code.

There are 5 questions to complete.