Data Structure Questions and Answers-Rod Cutting

 

 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?
A
Brute force
B
Dynamic programming
C
Recursion
D
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?

A
10
B
11
C
12
D
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?
A
O(n2)
B
O(n3)
C
O(nlogn)
D
O(2n)
Journalism Questions answers

Question 3 Explanation: 
The brute force implementation finds all the possible cuts. This takes O(2n) 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?

A
{1, 2, 7}
B
{10}
C
{2, 2, 6}
D
{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.

A
max....price, prices[i] + rod....cut(prices, len - i - 1)
B
max....price, prices[i - 1].
C
max....price, rod....cut(prices, len - i - 1)
D
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.

 

 Download all FREE PDF Ebook >>>CLICK HERE<<<