#### 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
• Discussion in forum
Solution : A base class function can be accessed with scope resolution operator even if the function is virtual.

discussion

• ( 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
• Discussion in forum
Answer : 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 Red-Black tree? Assume base of Log as 2 in all options

• 1) 2Log(n+1)
• 2) 1.44 Logn
• 3) 4Logn
• 4) None of these
• Discussion in forum
Solution :

discussion

• ( 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
• Discussion in forum
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

• ( 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
• Discussion in forum
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
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 k-ary 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)
• Discussion in forum
Answer : 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. 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) log2n
• 2) n
• 3) 2n + 1
• 4) 2n - 1
• Discussion in forum
Answer : 4) 2n - 1
Solution : For a right skewed binary tree, number of nodes will be 2n - 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) 2n - 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
• Discussion in forum
Solution :

discussion

• ( 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 non-leaf node of the tree is

• 1) 49
• 2) 50
• 3) 51
• 4) 52
• Discussion in forum
Solution : Let m be the order of B+ tree
m(8)+(m-1)12 <= 1024
[Note that record pointer is not needed in non-leaf nodes]
m <= 51
Since maximum order is 51, maximum number of keys is 50.

discussion

• ( 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 leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then the worst-case time complexity of the program is

• 1) θ(n)
• 2) θ(nLogn)
• 3) θ(n2)
• 4) θ(n2log n)
• Discussion in forum
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 / 2i) + (2*i - 1) * (n/2)
Where i = lg(N)
= lg((2n - 1) / 2)
O(c * T(N / 2i) + (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