Search Previous Year Questions

Concept:

Binary search tree: A BST is a tree in which all the nodes follow the two properties.

1. The left sub tree of a node has a key less than or equal to its parent node’s key.

2. The right sub tree of a node has a key greater than its parent’s key.

Complete binary tree: A complete binary tree is a binary tree in which every level except possibly the last level is completely filled and all nodes are as left as possible.

Explanation:

In this tree, it is clearly showing that node J and K are siblings.

Also, given tree is satisfying the property of a complete binary tree.

But it is not following the property of binary search tree. So, option 3) it is a binary search tree is incorrect here.

Concept:

Blocking factor: Number of records that can be stored in one block. It is calculated by dividing the block size by the length of each record.

Calculation:

Block size = 1024 bytes

Number of records = 30000

Record length or size = 100 bytes

File records are of fixed size and unspanned.

So, blocking factor = 1024/ 100 = ⌊10.24⌋ = 10

To find number of blocks needed:

10 records require = 1 block

1 record requires = 1/ 10 block

30000 records require = \(\frac{1}{{10}}; \times ;30000 = 3000\) blocks

Concept: A ripple counter is an asynchronous counter where only the first flip – flop is clocked by an external clock. All subsequent flip –f lops are clocked by the output of the preceding flip – flop.

Calculation:

Given that delay of one flip- flop = 20 ns

Here, we have to find the maximum delay before the output of the counter has settled to the next value. This will happen when all the bits will change.

As, it is a ripple counter, next bit cannot change until the previous is set.

So, the worst case will be when we multiply the number of flip flops with delay of one flip flop.

So, maximum delay in a 16- bit ripple counter = 20 × 16 = 320 ns

Attenuation: Attenuation is the loss of communication signal strength. It means loss of energy. When a signal travels through a medium, it loses some of its energy in overcoming the resistance of the medium.

Distortion: It means that the signal changes its form or shape. Distortion can occur in a composite signal made up of different frequencies. Signal components at the receiver have phases different from what they has at the sender. The shape of the signal is not the same.

Nquist Bit rate: Nquist bit rate is used for noiseless channels. It defines the bit rate as:

Bit rate = 2 × bandwidth × log₂L, where L is the number of signal levels.

Shannon capacity: Shannon capacity is used for noisy channels. Bit rate in this case:

Bit rate = bandwidth × log₂(1 + SNR), where SNR is signal to noise ratio.

RAID (Redundant array of inexpensive disks or drives) is a technology that is used to increase the performance and reliability of data storage. It consists of two or more drives working in parallel. There are different RAID levels, each optimized for a specific situation.

RAID 0 – Striping

RAID 1 – mirroring

RAID 5 - distributed parity

RAID 3 – parallel access

RAID 6 – Double distributed parity

RAID 10 – combining mirroring and striping

The software to perform the RAID- functionality and control the drives can either be located on a separate controller or it can simply be a driver.

Here, arr is the starting address of the array.

arr = “world” will give the error     // L- value required error.

Because, it doesn’t allow you to do the assignment since arr is an array not a free pointer.

This statement is to assign the pointer value of world to arr but cannot change the arr since nothing is pointing to the array. This can work if arr is a char* .

Double ended queue:

it is queue data structure in which deletion and insertion can be possible from either end. We can insert at both front and rear end and can delete from both the ends.

Priority queue:

A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority.

Stack:

Stack is a data structure which follows a particular order in which the operations are performed. The order stack follows is LIFO (Last in first out).

Queue:

Queue is a data structure which follows the order FIFO (First in First out).

Concept:

A natural join compares two relational schemas and is structured in such a way that columns with the same name of associated tables will appear only once.

Rules for natural join:

1. The tables have one or more pairs of identically named columns.

2. The columns must be same data type

Explanation:

The degree of a relation is the number of attributes in the table or the number of columns.

Here given two relational schemas R (A, B, C, D) and S (C, D, E, F).

Given expression is:

In this first we take the attribute A, B, C and apply the condition and then select the tuples, but number of attributes will remain same as A, B, C.

Similarly, for relational schema S according to the relational expression we will consider only attribute C, D, E.

So, when we do the natural join of these two results, we will find total 5 attributes in the final table.

So, degree of resultant relation = 5

Initially low = 0, high = n-1

n = 1000, So, high = 999

x = 501

1)while (0 <= 999) ---------------true

m = (0 + 999)/2 = 499

if(501 > a[m]), i.e. if (501 > a[499] )i.e. if (501 > 500) ----------true      [1^st comparison]

low = 499 + 1 = 500

2. while(500 < = 999) -----------------true

m = (500 + 999)/2 = 749

if(501 > 749 ) --------------false   [2^nd comparison]

elseif(501 < 749) ---------true         [3^rd comparison]

high = 749 – 1 = 748

3. while (500 <= 748) ----------------true

m = (500 + 748)/ 2 = 624

if (501 > 624) ------------false     [4^th comparison]

elseif(501 < 624) -------------true    [5^th comparison]

high = 624 -1 = 623

4. while (500 < = 623) ---------------true

m = (500 + 623)/2 = 581

if(501 > 581) -------------false     [6^th comparison]

elseif( 501 < 581)--------------true   [7^th comparison]

high = 581 - 1 = 580

5. while (500 < = 580) ---------true

m = (500 + 580)/ 2 = 540

if ( 501 > 540)---------false       [8^th comparison]

else if (501 < 540) --------------true   [9^th comparsion]

high = 539

6. while (500<= 539) -----------true

m = (500 + 539)/2 = 519

if (501 > 519) ---------------false    [10^th comparison]

elseif (501 < 519) ----------------true   [11^th comparison]

high = 519 - 1 = 518

7. while (500 < = 518) --------------true

m = (500 + 518)/ 2 = 509

if( 501 > 509 ) ---------------false    [12^th comparison]

elseif( 501 < 509) --------------true    [13^th comparison]

high = 509 – 1 = 508

8. while(500 <= 508) -----------true

m = (500 + 508)/2 = 504

if(501 > 504)------------false     [14^th comparison]

elseif(501 < 504 ) ----------true    [15^th comparison]

high = 503

9. while (500 <= 503) ---------------true

m = (500 + 503)/2 = 501

if(501 > 501) ----------false                [16^th comparison]

elseif( 501 < 501 )----------false              [17^th comparison]

else part will be executed and it will return m i.e. location where the required element is present.

So, total 17 comparisons are required in this case.

Concept:

Level is the number of nodes on path from root to the node.

Explanation:

If T is a binary tree with number of levels as L, then number of leaf nodes in the binary tree is at most 2^L-1.

Consider, tree has only one level, then number of nodes = 2^1-1 = 2⁰ = 1

It means tree will have only one node i.e. root

If tree has two levels, then maximum nodes possible at that level = 2^2-1 = 2

i.e. maximum 2 leafs are possible and 3 total nodes are possible with 2 levels.

Similarly, if we take 3 levels, number of nodes that level = 2^3-1 = 4

i.e. maximum leaf nodes possible = 4 and total nodes = 7

So, if we take level as L, total leaf nodes possible are atmost 2^L-1.