Algorithms Interview Question Part 7

63. In a proper binary tree with n nodes, the number of internal nodes is:
a). n/2
b). (n+1)/2
c). (n-1)/2
d). (n+1)/2 –1
Ans:c




True false quest


64. n2 = O(n3)
True ( Transitive property )
65. n3 = O(n2)
False
66.3n = o(n)
False [Remember, little-o means "less than" not "less than or equal."]
67.n/3 = O(n)
True
68`.n! = O (n log n)
False [But if it were big-Omega, it would be true!]
69.3n = (2n)
False [Because exponentials differ by more than just a constant factor]
70.n2 + 3n + sin n = (n2)
True
71.2n = (2n+4)
True
72.loga n = (logb n), for a and b constant, a!=b
True
73.na = (nb), for a and b constant, a!=b
False
74.It is possible to do a general purpose comparison sort on n items using O(n) comparisons.
False
75.In the worst case, access to the maximum element of a heap takes (ln n) time.
False [it's just constant time]
76.Merge sort is asymptotically faster than bubble sort in the best case.
False [bubble sort is linear in the best case!]
77.Radix sort is a stable sort.
True

78.Invoking the sort on an already sorted array is an example of a situation
Where bubble sort is faster than Quick sort.

True [ bubble sort is O(n) while Quick sort is O(n2).]






Fill in the blanks


79. ---------------- is the least number of nodes possible in an almost complete binary tree
of height h

Ans: 2^h [ This is the case where there is one lone leaf hanging off the left side of the tree.This is just one more than the number of nodes in a complete binary tree of height h-1. ]

80. Which of the following should an algorithm consist of
i. Zero or more Inputs
ii. One or more Outputs
iii. Infiniteness
iv. Definitiveness or Preciseness
a.i,ii,iii b.i,ii,iv c.ii,iii,iv d.i,iii,iv
Ans:b
An algorithm should have the following:
• Zero or more Inputs
• One or more Outputs
• Finiteness or computability
• Definitiveness or Preciseness

81. An algorithm that invokes (makes reference to) itself repeatedly until a certain condition matches, which is a method common to functional programming is called
a. recursive algorithm
b. iterative algorithm
c. random
d. deterministic
Ans:a
82. Algorithms which use repetitive constructs like loops and possibly with data structures like stack to solve the problems are called
a. recursive algorithm
b. iterative algorithm
c. random
d. deterministic
Ans:b
Recursion vs. Iteration: A recursive algorithm is one that invokes (makes reference to) itself repeatedly until a certain condition matches, which is a method common to functional programming. Iterative algorithms use repetitive constructs like loops and possibly with data structures like stack to solve the problems. Some problems are naturally suited for one implementation to other. For example, towers of hanoi is well understood in recursive implementation. Every recursive version has an equivalent (but possibly more complex) iterative version