 Algorithm
 Compiler Design
 Computer Fundamentals
 Computer Networks
 Computer Organization & Architecture
 DBMS
 Digital logic
 Information System
 Ms Office
 Operating System
 Programming & Data structure
 Software Engineering
 Software Testing
 System Programming
 Theory of computation
 Web technology
 Analog & Digital Circuits
 Control System
 Electronic Devices
 EMFT
 Junctions, Diodes & Tunnel
 Signals & systems
 Wireless Communication
 Engineering Mechanics
 Fluid Mechanics
 Heat Transfer
 I.C. Engines
 Power Engineering
 Strength of Materials
 Theory of Machines
 Thermodynamics
 Concrete Structure
 Construction & Structure engineering
 Costing & Valuation of Building Materials
 Errors & Adjustments
 Hydraulics
 Soil Mechanics
 Steel Structures
 Structural Analysis
 Surveying
 Traffic Engineering
 Water supply & waste water engineering
Computer Science/IT
Electronics & communications
Mechanical Engineering
Civil engineering
Electrical engineering


( 1 ) Predict the output of following C++ program
#include
using namespace std;
class Base
{
public:
virtual void show() { cout<<" In Base \n"; }
};
class Derived: public Base
{
public:
void show() { cout<<"In Derived \n"; }
};
int main(void)
{
Base *bp = new Derived;
bp>Base::show(); // Note the use of scope resolution here
return 0;
}  1) In Base
 2) In Derived
 3) Compiler Error
 4) Runtime Error

Show Answer Report Discussion in forumAnswer : 1) In Base
Solution : A base class function can be accessed with scope resolution operator even if the function is virtual.
discussion
Answer : 1) In Base



( 2 ) B+ trees are preferred to binary trees in databases because
 1) Disk capacities are greater than memory capacities
 2) Disk access is much slower than memory access
 3) Disk data transfer rates are much less than memory data transfer rates
 4) Disks are more reliable than memory

Show Answer Report Discussion in forumAnswer : 2) Disk access is much slower than memory access
Solution : Disk access is slow and B+ Tree provide search in less number of disk hits. This is primarily because unlike binary seach trees, B+ trees have very high fanout (typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree
discussion
Answer : 2) Disk access is much slower than memory access



( 3 ) What is the worst case possible height of RedBlack tree? Assume base of Log as 2 in all options
 1) 2Log(n+1)
 2) 1.44 Logn
 3) 4Logn
 4) None of these

Show Answer Report Discussion in forumAnswer : 1) 2Log(n+1)
Solution :
discussion
Answer : 1) 2Log(n+1)



( 4 ) The order of a leaf node in a tree B+ ? is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the value field is 9 bytes long and a block pointer is 6 bytes long, what is the order of the leaf node?
 1) 63
 2) 64
 3) 67
 4) 68

Show Answer Report Discussion in forumAnswer : 1) 63
Solution : Disk Block size = 1024 bytes
Data Record Pointer size, r = 7 bytes
Value size, V = 9 bytes
Disk Block ptr, P = 6 bytes
Let order of leaf be m. A leaf node in B+ tree contains at most m record pointers, at most m values, and one disk block pointer. r*m + V*m + p <= 1024 16m <= 1018 m =< 63
discussion
Answer : 1) 63



( 5 ) Which of the following is true about Red Black Trees?
 1) The path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf
 2) At least one children of every black node is red
 3) Root may be red
 4) A leaf node may be red

Show Answer Report Discussion in forumAnswer : 1) The path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf
Solution :
discussion
Answer : 1) The path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf



( 6 ) In a complete kary tree, every internal node has exactly k children or no child. The number of leaves in such a tree with n internal nodes is:
 1) nk
 2) (n  1) k+ 1
 3) n( k  1) + 1
 4) n(k  1)

Show Answer Report Discussion in forumAnswer : 3) n( k  1) + 1
Solution :
discussion
Answer : 3) n( k  1) + 1



( 7 ) A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be
 1) log_{2}n
 2) n
 3) 2n + 1
 4) 2^{n}  1

Show Answer Report Discussion in forumAnswer : 4) 2^{n}  1
Solution : For a right skewed binary tree, number of nodes will be 2^{n}  1. For example, in below binary tree, node 'A' will be stored at index 1, 'B' at index 3, 'C' at index 7 and 'D' at index 15.
A
\
\
B
\
\
C
\
\
D
discussion
Answer : 4) 2^{n}  1



( 8 ) You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?
 1) O(Logn)
 2) O(n)
 3) O(nLogn)
 4) None of these



( 9 ) Consider B+ tree in which the search key is 12 bytes long, block size is 1024 bytes, record pointer is 10 bytes long and block pointer is 8 bytes long. The maximum number of keys that can be accommodated in each nonleaf node of the tree is
 1) 49
 2) 50
 3) 51
 4) 52

Show Answer Report Discussion in forumAnswer : 2) 50
Solution : Let m be the order of B+ tree
m(8)+(m1)12 <= 1024
[Note that record pointer is not needed in nonleaf nodes]
m <= 51
Since maximum order is 51, maximum number of keys is 50.
discussion
Answer : 2) 50



( 10 ) A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{no. of leafnodes in leftsubtree of x, no. of leafnodes in rightsubtree of x} then the worstcase time complexity of the program is
 1) θ(n)
 2) θ(nLogn)
 3) θ(n2)
 4) θ(n2log n)

Show Answer Report Discussion in forumAnswer : 2) θ(nLogn)
Solution : The recurrence relation for the recursive function is
T(N) = 2 * T(N/2) + n/2
Where N is the total no. of nodes in the tree.
T(N) = 2 * (2*T(N/2) + n/2) + n/2
= 4 * T(N/2) + 3(n/2)
Solve this till T(1) i.e. till we reach the root.
T(N) = c * T(N / 2^{i}) + (2*i  1) * (n/2)
Where i = lg(N)
= lg((2n  1) / 2)
O(c * T(N / 2^{i}) + (2*i  1) * (n/2)) reduces to
O((2*i  1) * (n/2))
O((2*( lg((2n  1) / 2))  1) * (n/2)) ...sub the value of i.
O(n * ln(n))
discussion
Answer : 2) θ(nLogn)
