Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Tests  >  Test: Dynamic Programming, P & NP Concepts- 1 - Computer Science Engineering (CSE) MCQ

Test: Dynamic Programming, P & NP Concepts- 1 - Computer Science Engineering (CSE) MCQ


Test Description

10 Questions MCQ Test - Test: Dynamic Programming, P & NP Concepts- 1

Test: Dynamic Programming, P & NP Concepts- 1 for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Test: Dynamic Programming, P & NP Concepts- 1 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Dynamic Programming, P & NP Concepts- 1 MCQs are made for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Dynamic Programming, P & NP Concepts- 1 below.
Solutions of Test: Dynamic Programming, P & NP Concepts- 1 questions in English are available as part of our course for Computer Science Engineering (CSE) & Test: Dynamic Programming, P & NP Concepts- 1 solutions in Hindi for Computer Science Engineering (CSE) course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Dynamic Programming, P & NP Concepts- 1 | 10 questions in 30 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
Test: Dynamic Programming, P & NP Concepts- 1 - Question 1

A binary search tree is generated by inserting in order the following integers: 50, 15, 62, 5, 20, 58, 91,3, 8, 37,60, 24. The number of nodes in the left subtree and right subtree of the root respectively is

Detailed Solution for Test: Dynamic Programming, P & NP Concepts- 1 - Question 1

The binary search tree is as follows:

The number of nodes in the left subtree and right subtree of the root respectively is (7, 4).

Test: Dynamic Programming, P & NP Concepts- 1 - Question 2

Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?

Detailed Solution for Test: Dynamic Programming, P & NP Concepts- 1 - Question 2

Bellman-Ford algorithm is used to find all pairs shortest distances in a graph and it is dynamic programming technique.

1 Crore+ students have signed up on EduRev. Have you? Download the App
Test: Dynamic Programming, P & NP Concepts- 1 - Question 3

A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?

Detailed Solution for Test: Dynamic Programming, P & NP Concepts- 1 - Question 3

A B-tree is similar to 2-3 tree. Consider a B-tree of order 4.

A B-tree of order m contains n records and if each contains b records on the average then the tree has about [ n / b ] leaves, if we split k nodes along the path from leaves then

in given problem n = 10, b = 3, m = 4

so,

Test: Dynamic Programming, P & NP Concepts- 1 - Question 4

A problem in NP is NP-complete if

Detailed Solution for Test: Dynamic Programming, P & NP Concepts- 1 - Question 4

3-SAT being an NPC problem, reducing NP problem to 3-SAT would mean that NP problem is NPC

Test: Dynamic Programming, P & NP Concepts- 1 - Question 5

For problems X and Y, Y is NP-complete and X reduces to Y in polynomial time. Which of the following is TRUE?

Detailed Solution for Test: Dynamic Programming, P & NP Concepts- 1 - Question 5

X is reducible to NPC.
Hence X is also NPC

Test: Dynamic Programming, P & NP Concepts- 1 - Question 6

Let π be a problem that belongs to the class NP. Then which one of the following is TRUE?

Detailed Solution for Test: Dynamic Programming, P & NP Concepts- 1 - Question 6

it is given that πA ∈ NP
∴ If πA is NP-hard, and since it is given that πA ∈ NP , this means that πA is NP-complete
∴ choice (c) is correct.
Notice that choice (a) is incorrect since as P ∈ NP, some NP problems are actually P and hence polynomial time algorithm can exist for these.
Choice (b) is incorrect since, If πA can be solved deterministicaily in polynomial time, it does not generate that P=NP, unless of-course it is additionally known that πA is NP-complete.
Choice (d) is incorrect since,
All problems belonging to P or NP have to be decidable.

Test: Dynamic Programming, P & NP Concepts- 1 - Question 7

The maximum number of edges in a n-nodes undirected graph without self loops is

Detailed Solution for Test: Dynamic Programming, P & NP Concepts- 1 - Question 7

The maximum number of edges in a n-node undirected graph without self loop i.e., complete graph.
n-node each having degree  such each  edge so total number of edges = 

Test: Dynamic Programming, P & NP Concepts- 1 - Question 8

The average number of key comparisons required for a successful search for sequential search on n items is

Detailed Solution for Test: Dynamic Programming, P & NP Concepts- 1 - Question 8

Number of comparison in worst case = n

Number of comparison in best case = 1 So, average number of comparison

Test: Dynamic Programming, P & NP Concepts- 1 - Question 9

A complete binary tree with n non-leaf nodes contains

Detailed Solution for Test: Dynamic Programming, P & NP Concepts- 1 - Question 9

In complete binary tree.
Number of internal nodes = No. of leaf node - 1
So total number of nodes = Internal nodes + Leaf node

Test: Dynamic Programming, P & NP Concepts- 1 - Question 10

Algorithm design technique used in quicksort algorithm is

Detailed Solution for Test: Dynamic Programming, P & NP Concepts- 1 - Question 10

Quick sort algorithm is based on divide an conquer approach.
Since we conquer the array by dividing it one the basis of pivot elements till the sorted array is obtained

Information about Test: Dynamic Programming, P & NP Concepts- 1 Page
In this test you can find the Exam questions for Test: Dynamic Programming, P & NP Concepts- 1 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Dynamic Programming, P & NP Concepts- 1, EduRev gives you an ample number of Online tests for practice

Top Courses for Computer Science Engineering (CSE)

Download as PDF

Top Courses for Computer Science Engineering (CSE)