- 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 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
-
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 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)
-
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) log2n
- 2) n
- 3) 2n + 1
- 4) 2n - 1
-
Show Answer Report Discussion in forumAnswer : 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
-
-
-
( 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
-
Show Answer Report Discussion in forumAnswer : 2) 50
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
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 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)
-
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 / 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
Answer : 2) θ(nLogn)
-