What is the minimum number of comparisons required to find the minimum and the maximum of hundred numbers?

(A) 147.1 to 148.1 (B) 145.1 to 146.1 (C) 140 to 146 (D) 140 to 148

If n is odd: 3*(n-1)/2 If n is even: 3n/2 -2

Here n = 100,

3n/2 - 2 = 3*100/2 - 2 = 148 how is it 147.1 to 148.1 ?

Page 2

Improve Article

Save Article

Like Article

Consider the following pseudo code. What is the total number of multiplications to be performed?

(A) Half of the product of the 3 consecutive integers.
(B) One-third of the product of the 3 consecutive integers.
(C) One-sixth of the product of the 3 consecutive integers.
(D) None of the above.

Answer: (C)

Explanation: The statement “D = D * 3” is executed n*(n+1)*(n-1)/6 times. Let us see how. 

For i = n, the statement is not executed at all 

So overall the statement is executed following times 
[(n-1) + (n-2) + .. 2 + 1] + [(n-2) + (n-3) + .. 2 + 1] + … + 1 + 0 

The above series can be written as 
S = [n*(n-1)/2 + (n-1)*(n-2)/2 + ….. + 1] 

The sum of above series can be obtained by trick of subtraction the series from standard Series S1 = n2 + (n-1)2 + .. 12. The sum of this standard series is n*(n+1)*(2n+1)/6 

S1 – 2S = n + (n-1) + … 1 = n*(n+1)/2 2S = n*(n+1)*(2n+1)/6 – n*(n+1)/2 

S = n*(n+1)*(n-1)/6

The above solution is relies on a trick to obtain the sum of the series, but there is a much more straightforward way of obtaining the same result :

For i = 1, the multiplication statement is executed (n-1) + (n-2) + .. 2 + 1 times.

For i = 2, the statement is executed (n-2) + (n-3) + .. 2 + 1 times 

Therefore, for each i, the number of times the statement is executed is: 

This is the sum of n natural numbers from 1 to n – i. Therefore, it can be simplified to:

Multiplying, we will get the following:

Now, this is the number of times the statement will be executed for each i. Therefore, in total, the number of times the statement will be executed is:

Ignore the half for the moment. Expanding the summation is simple. You can distribute it across the expression to get this:

Using the formulae for sum of n natural numbers and the sum of squares of n natural numbers, we get:

Simplifying further and taking n/6 as a common term will give you:

Now, take 2 as the common term and use it to cancel out the half that we ignored before. This gives you:

Finally, using a2-b2, you get the required answer:

This should make the solution clear to you now!

Quiz of this Question

Page 3

Page 4

Page 5

Improve Article

Save Article

Like Article

Let T(n) be the number of different binary search trees on n distinct elements.
Then

Answer: (B)

Explanation: The idea is to make a key root, put (k-1) keys in one subtree and remaining n-k keys in other subtree.

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −

• The left sub-tree of a node has a key less than or equal to its parent node’s key.
• The right sub-tree of a node has a key greater than to its parent node’s key.

Now construction binary search trees from n distinct number-Lets for simplicity consider n distinct numbers as first n natural numbers (starting from 1)

If n=1 We have only one possibility, therefore only 1 BST.

If n=3 We have 5 possibilities. Keeping each number first as root and then arranging the remaining 2 numbers as in case of n=2.

If n=4 We have 14 possibilities. Taking each number as root and arranging smaal numbers as left subtree and larger numbers as right subtree.

Thus we can conclude that with n distinct numbers, if we take ‘k’ as root then all the numbers smaller than k will left subtree and numbers larger than k will be right subtree where the the right subtree and left subtree will again be constructed recursively like the root.Therefore,

This solution is contributed by Parul Sharma.

Quiz of this Question

Page 6

Improve Article

Save Article

Like Article

The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is _____________

Note: The height of a tree with a single node is 0.

[This question was originally a Fill-in-the-Blanks question]
(A) 2
(B) 4
(C) 64
(D) 32

Answer: (C)

Explanation: To get height 6, we need to put either 1 or 7 at root.

So count can be written as T(n) = 2*T(n-1) with T(1) = 1

Therefore count is 26 = 64

Another Explanation:

Consider these cases,1 2 3 4 5 6 71 2 3 4 5 7 61 7 6 5 4 3 21 7 6 5 4 2 37 6 5 4 3 2 17 6 5 4 3 1 27 1 2 3 4 5 6

7 1 2 3 4 6 5

For height 6, we have 2 choices. Either we select the root as 1 or 7.Suppose we select 7.Now, we have 6 nodes and remaining height = 5.So, now we have 2 ways to select root for this sub-tree also.Now, we keep on repeating the same procedure till remaining height = 1

For this last case also, we have 2 ways.

Therefore, total number of ways = 26= 64

Quiz of this Question

Page 7

Improve Article

Save Article

Like Article

Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT be the sequence of nodes examined?
(A) {10, 75, 64, 43, 60, 57, 55}
(B) {90, 12, 68, 34, 62, 45, 55}
(C) {9, 85, 47, 68, 43, 57, 55}
(D) {79, 14, 72, 56, 16, 53, 55}

Answer: (C)

Explanation: In BST, on right child of parent should be greater than parent and left child should be smaller than the parent, but in C after 47, 68 goes on the right side because it greater then parent, now everything below this point should be greater then 47 but 43 appears that does not satisfy the BST property.

Quiz of this Question

Page 8

Page 9

Improve Article

Save Article

Like Article

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.

IV. 550, 149, 507, 395, 463, 402, 270

Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?
(A) II and III only
(B) I and III only
(C) III and IV only
(D) III only

Answer: (D)

Explanation: Key to be searched 273:

• I) 81, 537, 102, 439, 285, 376, 305 is not correct
  We cannot go to 376 from 285 as 273 is smaller than 285.
• II) 52, 97, 121, 195, 242, 381, 472 is not correct.
  We cannot go to 472 from 381 as 273 is smaller than 381.
• III) 142, 248, 520, 386, 345, 270, 307 is correct
  
  
• 550, 149, 507, 395, 463, 402, 270 is not correct.
  We cannot go to 463 from 395 in search of 273

Following representation of the binary search trees is given below.

Quiz of this Question

Page 10

Page 11

Page 12

Page 13

Page 14

Improve Article

Save Article

Like Article

A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is 5, 3, 1, 2, 4, 6, 8, 7. If the tree is traversed in post-order, the sequence obtained would be

 
(A) 8, 7, 6, 5, 4, 3, 2, 1
(B) 1, 2, 3, 4, 8, 7, 6, 5
(C) 2, 1, 4, 3, 6, 7, 8, 5
(D) 2, 1, 4, 3, 7, 8, 6, 5

Answer: (D)

Explanation: Please see this link for more details

https://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/

Quiz of this Question

Page 15

Page 16

Improve Article

Save Article

Like Article

Consider the following C-program fragment in which i, j and n are integer variables.

for (i = n, j = 0; i >0; i /= 2, j += i);

Let val(j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?
(A) val(j) =

(logn)
(B) vaI(j) =

(sqrt(n))
(C) val(j) =

(n)
(D) val(j) =

(nlogn)

(A) A
(B) B
(C) C
(D) D

Answer: (C)

Explanation: The variable j is initially 0 and value of j is sum of values of i. i is initialized as n and is reduced to half in each iteration.

j = n/2 + n/4 + n/8 + .. + 1 = Θ(n)

Note the semicolon after the for loop, so there is nothing in the body.

Same as question 1 of https://www.geeksforgeeks.org/c-language-set-6/

Quiz of this Question

Page 17

Page 18