GATE-CS-2004

Q.1

The goal of structured programming is to

have well indented programs

be able to infer the flow of control from the compiled code

be able to infer the flow of control from the program text

avoid the use of GOTO statements

Ans .

Explanation :

The main goal of structured programming is to get an understanding about the flow of control in the given program text. In structure programming various control structures such as switch-case, if-then-else, while, etc. allows a programmer to decode the flow of the program easily.

Q.2

void swap (int a, int b) { int temp; temp = a; a = b; b = temp; }

Call Swap(x,y)

call swap(&x, &y)

swap(x,y) cannot be used as it does not return any value

swap(x,y) cannot be used as the parameters are passed by value

Ans .

Explanation :

Why a, b and c are incorrect?
a) call swap (x, y) will not cause any effect on x and y as parameters are passed by value.
b) call swap (&x, &y) will no work as function swap() expects values not addresses (or pointers).
c) swap (x, y) cannot be used but reason given is not correct.

Q.3

A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl< top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is

(top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)

top1 + top2 = MAXSIZE

(top1= MAXSIZE/2) or (top2 = MAXSIZE)s

top1= top2 -1

Ans .

Explanation :

If we are to use space efficiently then size of the any stack can be more than MAXSIZE/2.
Both stacks will grow from both ends and if any of the stack top reaches near to the other top then stacks are full. So the condition will be top1 = top2 -1 (given that top1 < top2)

Q.4

The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

2^k

3^k

4^k

6^k

Ans .

Explanation :

                    10
                  /     \
                 1       15
                 \      /  \
                  3    12   16
                    \
                     5

Q.5

The best data structure to check whether an arithmetic expression has balanced parentheses is a

queue

stack

tree

list

Ans .

Explanation :

There are three types of parentheses [ ] { } (). Below is an arbit c code segment which has parentheses of all three types.

void func(int c, int a[])
{
   return  ((c +2)  + arr[(c-2)]) ;
}

Q.6

Level order traversal of a rooted tree can be done by starting from the root and performing

preorder traversal

inorder traversal

depth first search

breadth first search

Ans .

Explanation :


Level order traversal of the above tree is 1 2 3 4 5
 .

Q.7

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?
1.    9679, 1989, 4199 hash to the same value
2.    1471, 6171 hash to the same value
3.    All elements hash to the same value
4.    Each element hashes to a different value

1 only

2 only

1 & 2 only

3 or 4

Ans .

Explanation :

The hash value for 9679, 1989, 4199 is 9 and hash value for 1471, 6171 is 1.

Q.8

Which of the following grammar rules violate the requirements of an operator grammar ? P, Q, R are nonterminals, and r, s, t are terminals.
1. P → Q R 2. P → Q s R 3. P → ε 4. P → Q t R r

1 only

1 & 3 only

2 & 3 only

3 & 4 only

Ans .

Explanation :

An operator precedence parser is a bottom-up parser that interprets an operator-precedence grammar. For example, most calculators use operator precedence parsers to convert from the human-readable infix notation with order of operations format into an internally optimized computer-readable format like Reverse Polish notation (RPN).

An operator precedence grammar is a kind of context-free grammar that can be parsed with an operator-precedence parser. It has the property that no production has either an empty (ε) right-hand side or two adjacent nonterminals in its right-hand side. These properties allow the terminals of the grammar to be described by a precedence relation, and the a parser that exploits that relation is considerably simpler than more general-purpose parsers such as LALR parsers.

Q.9

Consider a program P that consists of two source modules M1 and M2 contained in two different files. If M1 contains a reference to a function defined in M2, the reference will be resolved at

Edit-time

Compile-time

Link-time

Load-time

Ans .

Explanation :

Static linking is done at link-time, dynamic linking or shared libraries are brought in only at runtime. (A) Edit-time : Function references can never be given/determined at edit-time or code-writing time. Function references are different from function names. Function names are used at edit-time and function references are determined at linker-time for static libraries or at runtime for dynamic libraries. (B) Compile-time : Compile time binding is done for functions present in the same file or module. (C) Link-time : Link time binding is done in the linker stage, where functions present in separate files or modules are referenced in the executable. (D) Load-time : Function referencing is not done at load-time

Q.10

Consider the grammar rule E → E1 - E2 for arithmetic expressions. The code generated is targeted to a CPU having a single user register. The subtraction operation requires the first operand to be in the register. If E1 and E2 do not have any common sub expression, in order to get the shortest possible code

E1 should be evaluated first

E2 should be evaluated first

Evaluation of E1 and E2 should necessarily be interleaved

Order of evaluation of E1 and E2 is of no consequence

Ans .

Explanation :

 E -> E1 - E2 Given that E1 and E2 don't share any sub expression, most optimized usage of single user register for evaluation of this production rule would come only when E2 is evaluated before E1. This is because when we will have E1  evaluated in the register, E2 would have been already computed and stored at some memory location. Hence we could just use subtraction operation to take the user register as first operand, i.e. E1 and E2 value from its   memory location referenced using some index register or some other form according to the instruction. Hence correct answer should be (B) E2 should be evaluated first.

Q.11

Consider the following statements with respect to user-level threads and kernel supported threads
i. context switch is faster with kernel-supported threads ii. for user-level threads, a system call can block the entire process iii. Kernel supported threads can be scheduled independently iv. User level threads are transparent to the kernel Note: This questions appeared as Numerical Answer Type.

(ii), (iii) and (iv) only

(ii) and (iii) only

(i) and (iii) only

(i) and (ii) only

Ans .

Explanation :

User thread are implemented by users.	kernel threads are implemented by OS.
OS doesn’t recognized user level threads.	Kernel threads are recognized by OS.
Implementation of User threads is easy.	Implementation of Kernel thread is complicated.
Context switch time is less.	Context switch time is more.
Context switch requires no hardware support.	Hardware support is needed.
If one user level thread perform blocking operation then entire process will be blocked.	If one kernel thread perform blocking operation then another thread can continue execution.
Example : Java thread, POSIX threads.	Example : Window Solaris.

Q.12

Consider an operating system capable of loading and executing a single sequential user process at a time. The disk head scheduling algorithm used is First Come First Served (FCFS). If FCFS is replaced by Shortest Seek Time First (SSTF), claimed by the vendor to give 50% better benchmark results, what is the expected improvement in the I/O performance of user programs?

50%

40%

25%

Ans .

Explanation :

Since Operating System can execute a single sequential user process at a time, the disk is accessed in FCFS manner always. The OS never has a choice to pick an IO from multiple IOs as there is always one IO at a time
So, the solution is (D).

Q.13

Let R1 (A, B, C) and R2 (D, E) be two relation schema, where the primary keys are shown underlined, and let C be a foreign key in R1 referring to R2. Suppose there is no violation of the above referential integrity constraint in the corresponding relation instances r1 and r2. Which one of the following relational algebra expressions would necessarily produce an empty relation ?

Ans .

Explanation :

Since C is a foreign key in R1 and there is no violation of the above referential integrity constraint, the set of values in C must be a subset of values in R2.

Q.14

Consider the following relation schema pertaining to a students database:

Student (rollno, name, address)
Enroll (rollno, courseno, coursename)

where the primary keys are shown underlined. The number of tuples in the Student and Enroll tables are 120 and 8 respectively. What are the maximum and minimum number of tuples that can be present in (Student * Enroll), where '*' denotes natural join ?

8,0

120,8

960,8

960,120

Ans .

Explanation :

The result of the natural join is the set of all combinations of tuples in R and S that are equal on their common attribute names. What is the maximum possible number of tuples? The result of natural join becomes equal to the Cartesian product when there are no common attributes. The given tables have a common attribute, so the result of natural join cannot have more than the number of tuples in larger table.

Q.15

Choose the best matching between Group 1 and Group 2.

P-1, Q-4, R-3

P-2, Q-4, R-1

P-2, Q-3, R-1

P-1, Q-3, R-2

Ans .

Explanation :

Data link layer is the second layer of the OSI Model. This layer is responsible for data transfer between nodes on the network and providing a point to point local delivery framework. So, P matches with 1. Network layer is the third layer of the OSI Model. This layer is responsible for forwarding of data packets and routing through intermediate routers. So, Q matches with 4. Transport layer is the fourth layer of the OSI Model. This layer is responsible for delivering data from process to process. So, R matches with 3.   Thus, A is the correct option.   Please comment below if you find anything wrong in the above post.

Q.16

Which of the following is NOT true with respect to a transparent bridge and a router?
GATE CSE 2014
If the pre-emptive shortest remaining time first scheduling algorithm is used to schedule the processes, then the average waiting time across all processes is _______ milliseconds. Note: This questions appeared as Numerical Answer Type.

Both bridge and router selectively forward data packets

A bridge uses IP addresses while a router uses MAC addresses

A bridge builds up its routing table by inspecting incoming packets

A router can connect between a LAN and a WAN

Ans .

Explanation :
```
 *** 
```

Q.17

The Boolean function x'y' + xy + x'y is equivalent to

x' + y'

x + y

x + y'

x' + y

Ans .

Explanation :

x’y’+xy+xy’ =(x’y’+y(x+x’)) =x'y’+y =x'+y Ans (d)

Q.18

In an SR latch made by cross-coupling two NAND gates, if both S and R inputs are set to 0, then it will result in

Q = 0, Q' = 1

Q = 1, Q' = 0

Q = 1, Q' = 1

Indeterminate states

Ans .

Explanation :

If both R reset and S set inputs are inactivated. It means made ‘0’, both Q and Q’ tend to be ‘1’. [NAND gate characteristic is that only when both inputs are 1,the output is 0.]  The logic of the circuit (Q’ is complement of Q) not satisfied, and the final state at an instant after inputs R and S changed to ‘0’, is only a matter of chance. Logic state is said to be indeterminate state or racing state. Each state, Q =‘1’and Q =‘0’, and Q =‘0’, Q=‘1’ trying to race through so “RACE CONDITION”  occurs and output become unstable. So ans is (D) part.

Q.19

If 73x (in base-x number system) is equal to 54y (in base-y number system), the possible values of x and y are

8,16

10,12

9,13

8,11

Ans .

Explanation :

We can solve it by converting both to decimals. 3 + 7*8 = 4 + 11*5

Q.20

Which of the following addressing modes are suitable for program relocation at run time ?
(i) Absolute addressing (ii) Based addressing (iii) Relative addressing (iv) Indirect addressing

(i) and (iv)

(i) and (ii)

(ii) and (iii)

(i), (ii) and (iv)

Ans .

Explanation :

Program relocation at run time transfer complete block to some memory locations. This requires as base address and block should be relatively addressed through this base address .This require both base address and relative address. So( C)  is correct option. Absolute addressing mode and indirect addressing modes is used for one instruction at one time, not for whole block So both are not suitable for program relocation at run time.

Q.21

The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by

the instruction set architecture

page size

physical memory size

number of processes in memory

Ans .

Explanation :

There are two important tasks in virtual memory management: a page-replacement strategy and a frame-allocation strategy. Frame allocation strategy says gives the idea of minimum number of frames which should be allocated. The absolute minimum number of frames that a process must be allocated is dependent on system architecture, and corresponds to the number of pages that could be touched by a single (machine) instruction. So, it is instruction set architecture i.e. option (A) is correct answer.

Q.22

How many 8-bit characters can be transmitted per second over a 9600 baud serial communication link using asynchronous mode of transmission with one start bit, eight data bits, two stop bits, and one parity bit ?

600

800

876

1200

Ans .

Explanation :

 Background required - Physical Layer in OSI Stack In serial Communications, information is transferred in or out one bit at a time. The baud rate specifies how fast data is sent over a serial line. It’s usually expressed in units of bits-per-second (bps). Each block (usually a byte) of data transmitted is actually sent in a packet or frame of bits. Frames are created by appending synchronization and parity bits to our data.

Q.23

Identify the correct translation into logical notation of the following assertion.
"Some boys in the class are taller than all the girls"

Note : taller(x,y) is true if x is taller than y.

(∃x) (boy(x) → (∀y) (girl(y) ∧ taller(x,y)))

(∃x) (boy(x) ∧ (∀y) (girl(y) ∧ taller(x,y)))

(∃x) (boy(x) → (∀y) (girl(y) → taller(x,y)))

(∃x) (boy(x) ∧ (∀y) (girl(y) → taller(x,y)))

Ans .

Explanation :

Now many people get confused when to use ∧ and when to use →. This question tests exactly that. We use ∧ when we want to say that the both predicates in this statement are always true, no matter what the value of x is. We use → when we want to say that although there is no need for left predicate to be true always, but whenever it becomes true, right predicate must also be true. D means there exist some boys x which taller than all girls y.

Q.24

Consider the binary relation:
S = {(x, y) | y = x+1 and x, y ∈ {0, 1, 2, ...}}
The reflexive transitive closure of S is

{(x, y) | y > x and x, y ∈ {0, 1, 2, ... }}

{(x, y) | y ≥ x and x, y ∈ {0, 1, 2, ... }}

{(x, y) | y < x and x, y ∈ {0, 1, 2, ... }}

{(x, y) | y ≤ x and x, y ∈ {0, 1, 2, ... }}

Ans .

Explanation :

Reflexive closure of a relation R on set S is the smallest reflexive relation which contains R.
If S = {(0, 1), (1, 2)} , we make it reflexive by taking its union with set {(0, 0), (1, 1), (2, 2)}. Thus, reflexive closure of S = {(0, 0), (0, 1), (1, 1), (1, 2), (2, 2)}.
Now transitive closure is defined as smallest transitive relation which contains S.
We check where does it violate property of transitivity then add appropriate pair. We have (0, 1) and (1, 2) but not (0, 2). So, S = {(0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2)} now.

Thus, option (B) matches the final set S.

Q.25

If a fair coin is tossed four times. What is the probability that two heads and two tails will result?

3/8

1/2

5/8

2/4

Ans .

Explanation :

There are total 16 possibilities, out of which following have 2 heads and 2 tails HHTT, HTHT, TTHH, THTH, HTTH, THHT So the probability of 2 heads is 6/16 which is 3/8

Q.26

The number of different n × n symmetric matrices with each element being either 0 or 1 is: (Note: power(2, x) is same as 2x)

power(2, n)

power(2, n2)

power(2, (n2 + n)/2)

power(2, (n2 - n)/2)

Ans .

Explanation :

We are considering a symmetric matrix (given in question). So, we need to look at half of elements ie. either upper or lower traingle i.e. A[i][j] = A[j][i] Hence, No. of elements = ( n^2 + n ) / 2 Since, we have only two elements : 0 & 1 No. of choices = 2 Therefore, No. of possibilities = 2 ^ (No. of elements) = 2 ^ ( ( n^2 + n ) / 2 ) = power ( 2 , ( n^2 + n ) / 2  )

Q.27

Let A, B, C, D be n × n matrices, each with non-zero determinant. If ABCD = 1, then B-1 is

D-1C-1A-1

CDA

ADC

Does not necessarily exist

Ans .

Explanation :
```
 
```

Q.28

What is the result of evaluating the following two expressions using three-digit floating point arithmetic with rounding?
(113. + -111.) + 7.51 113. + (-111. + 7.51)

9.51 and 10.0 respectively

10.0 and 9.51 respectively

9.51 and 9.51 respectively

10.0 and 10.0 respectively

Ans .

Explanation :

(113. + -111.) + 7.51
= 2 + 7.51
= 9.51


113. + (-111. + 7.51)
= 113. + (-111. + 7.51)
= 113. - 103. = 10 [103.49 is rounded to 103.0] option A is correct.

Q.29

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

nlogn

nlog2n

Ans .

Explanation :

The number of comparisons that a comparison sort algorithm requires increases in proportion to Nlog(N), where N is the number of elements to sort. This bound is asymptotically tight:

Given a list of distinct numbers (we can assume this because this is a worst-case analysis), there are N factorial permutations exactly one of which is the list in sorted order. The sort algorithm must gain enough information from the comparisons to identify the correct permutations. If the algorithm always completes after at most f(N) steps, it cannot distinguish more than 2^f(N) cases because the keys are distinct and each comparison has only two possible outcomes. Therefore,

2^f(N) >= N! or equivalently f(N) >= log(N!).
Since log(N!) is Omega(NlogN), the answer is NlogN.

Q.30

The problems 3-SAT and 2-SAT are

both in p

both NP-complete

NP-complete and in P respectively

undecidable and NP-complete respectively

Ans .

Explanation :

The Boolean satisfiability problem (SAT) is a decision problem, whose instance is a Boolean expression written using only AND, OR, NOT, variables, and parentheses. The problem is: given the expression, is there some assignment of TRUE and FALSE values to the variables that will make the entire expression true? A formula of propositional logic is said to be satisfiable if logical values can be assigned to its variables in a way that makes the formula true.

3-SAT and 2-SAT are special cases of k-satisfiability (k-SAT) or simply satisfiability (SAT), when each clause contains exactly k = 3 and k = 2 literals respectively.

2-SAT is P while 3-SAT is NP Complete.

Q.31

Consider the following C function:

int f(int n) { static int i = 1; if (n >= 5) return n; n = n+i; i++; return f(n); }

Ans .

Explanation :

Since i is static, first line of f() is executed only once.

Q.32

Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = D1D2…Dm
int n, rev; rev = 0; while (n > 0) { rev = rev*10 + n%10; n = n/10; }
The loop invariant condition at the end of the ith iteration is:

n = D1D2….Dm-i and rev = DmDm-1…Dm-i+1 ^-f

n = Dm-i+1…Dm-1Dm and rev = Dm-1….D2D1 ^-f to 2ⁱ - 2^-f

n != rev ^-i

n = D1D2….Dm and rev = DmDm-1…D2D1 ⁱ - 2^-f

Ans .

Explanation :

The loop one by adds digits to rev starting from the last digit of n. It also removes digits from n starting from left.

Q.33

Consider the following C program segment:
char p[20]; char *s = "string"; int length = strlen(s); int i; for (i = 0; i < length; i++) p[i] = s[length — i]; printf("%s",p);

gnirts

gnirt

string

no output is printed

Ans .

Explanation :

Let us consider below line inside the for loop
p[i] = s[length — i];
For i = 0, p[i] will be s[6 — 0] and s[6] is ‘\0’
So p[0] becomes ‘\0’. It doesn’t matter what comes in p[1], p[2]….. as P[0] will not change for i >0. Nothing is printed if we print a string with first character ‘\0’

Q.34

It is desired to design an object-oriented employee record system for a company. Each employee has a name, unique id and salary. Employees belong to different categories and their salary is determined by their category. The functions to get Name, getld and compute salary are required. Given the class hierarchy below, possible locations for these functions are: i. getld is implemented in the superclass ii. getld is implemented in the subclass iii. getName is an abstract function in the superclass iv. getName is implemented in the superclass v. getName is implemented in the subclass vi. getSalary is an abstract function in the superclass vii. getSalary is implemented in the superclass viii. getSalary is implemented in the subclass
GATE CSE 2014

(i), (iv), (vi), (viii)

(i), (iv), (vii)

{(ab)ⁿ(cb^m)ⁿ | n >= 1 }(i), (iii), (v), (vi), (viii)

(ii), (v), (viii)

Ans .

Explanation :

Getid() and GetName() can be there in the base class as these functions have the same implementation for all subclasses. As the question says that every employee must have salary and salary is determined by their category, getSalary() must be there as an abstract function in base class. And all subclasses should implement salary according to their category.
Only option (A) is correct.

Q.35

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely ?
(i) preorder and postorder (ii) inorder and postorder (iii) preorder and inorder (iv) level order and postorder

(i) only

(ii), (iii)

(iv) only

(iii) only

Ans .

Explanation :

Here, we consider each and every option to check whether it is true or false. 1) Preorder and postorder

Q.36

A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time? GATE CSE 2014

Rear node

Front node

not possible with a single pointer

node next to front

Ans .

Explanation :

Answer is not “(b) front node”, as we can not get rear from front in O(1), but if p is rear we can implement both enQueue and deQueue in O(1) because from rear we can get front in O(1). Below are sample functions. Note that these functions are just sample are not working. Code to handle base cases is missing.

Therefore, option A is correct.

Q.37

The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is. GATE CSE 2014

Ans .

Explanation :

A max heap is a complete binary tree in which the value of each non-leaf node is greater than or equal to the values of its children. For the given case, first insert all the values in a complete binary tree. Then, we apply shifting. What we do is we start with the bottom most non-leaf node. If it is smaller than any (or both) of the child nodes, we swap it with the largest child. Doing the same way, we continue to move upwards the tree until all the non-leaf nodes satisfy the properties of the max heap.   So, the first time we make a complete binary tree, we have

Therefore, option A is correct.

Q.38

Assume that the operators +, -, × are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, x , +, -. The postfix expression corresponding to the infix expression a + b × c - d ^ e ^ f is

abc × + def ^ ^ -

abc × + de ^ f ^ -

ab + c × d - e ^ f ^

- + a × bc ^ ^ def

Ans .

Explanation :
```
^ is right assosciative.
```

Q.39

Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute M1 × M2 will be

best if A is in row-major, and B is in column- major order

best if both are in row-major order

best if both are in column-major order

independent of the storage scheme

Ans .

Explanation :

This is a trick question. Note that the questions asks about time complexity, not time taken by the program. for time complexity, it doesn't matter how we store array elements, we always need to access same number of elements of M1 and M2 to multiply the matrices. It is always constant or O(1) time to do element access in arrays, the constants may differ for different schemes, but not the time complexity.

Q.40

Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?

union only

intersection, membership

membership, cardinality

union, intersection

Ans .

Explanation :

Cardinality and membership are definitely not the slowest one. For cardinality, just count the number of nodes in a list. For membership, just traverse the list and look for a match

For getting intersection of L1 and L2, search for each element of L1 in L2 and print the elements we find in L2.

There can be many ways for getting union of L1 and L2. One of them is as follows
a) Print all the nodes of L1 and print only those which are not present in L2.
b) Print nodes of L2.

Q.41

Consider the following C program

    main()
    {
        int x, y, m, n;
        scanf ("%d %d", &x, &y);
        /* Assume x > 0 and y > 0  */
        m = x;
        n = y;
        while (m! = n)
        {
            if (m > n)
                m = m - n;
            else
                n = n - m;
        }
        print f ("% d", n);
    }

The Program Computes?

x ÷ y using repeated subtraction

x mod y using repeated subtraction

the greatest common divisor of x and y

the least common multiple of x and y

Ans .

Explanation :

The given program is iterative implementation of Euclid's Algorithm for GCD

Q.42

What does the following algorithm approximate?

 x = m;
    y = 1;
    while (x - y > e)
    {
        x = (x + y)/2;
        y = m/x;
    }
    print(x);

(Assume m > 1, e > 0).

log m

m^2

m^(1/2)

m^(1/3)

Ans .

Explanation :

The given code is implementation of Babylonian method for square root

Q.43

Consider the following C program segment

    struct CellNode
    {
      struct CelINode *leftchild;
      int element;
      struct CelINode *rightChild;
    }

    int Dosomething(struct CelINode *ptr)
    {
        int value = 0;
        if (ptr != NULL)
        {
          if (ptr->leftChild != NULL)
            value = 1 + DoSomething(ptr->leftChild);
          if (ptr->rightChild != NULL)
            value = max(value, 1 + DoSomething(ptr->rightChild));
        }
        return (value);
    }

The number of leaf nodes in the tree

The number of nodes in the tree

The number of internal nodes in the tree

The height of the tree

Ans .

Explanation :

DoSomething() returns max(height of left child + 1, height of right child + 1). So given that pointer to root of tree is passed to DoSomething(), it will return height of the tree. Note that this implementation follows the convention where height of a single node is 0. Lets take a sample tree and try to run the code. .

Q.44

Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances
GATE CSE 2014

P, Q, R, S, T, U

P, Q, R, U, S, T

P, Q, R, U, T, S

P, Q, T, R, U, S

Ans .

Explanation :

Q.45

Consider the grammar with the following translation rules and E as the start symbol.

E → E1 # T { E.value = E1.value * T.value }
         | T{ E.value = T.value }
T → T1 & F { T.value = T1.value + F.value }
          | F{ T.value = F.value }
F → num { F.value = num.value }

Compute E.value for the root of the parse tree for the expression: 2 # 3 & 5 # 6 & 4.

200

180

160

Ans .

Explanation :

We can calculate the value by constructing the parse tree for the expression 2 # 3 & 5 # 6 &4.

Alternatively, we can calculate by considering following precedence and associativity rules.
Precedence in a grammar is enforced by making sure that a production rule with higher precedence operator will never produce an expression with operator with lower precedence.
In the given grammar ‘&’ has higher precedence than ‘#’.

Left associativity for operator * in a grammar is enforced by making sure that for a production rule like S -> S1 * S2 in grammar, S2 should never produce an expression with *. On the other hand, to ensure right associativity, S1 should never produce an expression with *.
In the given grammar, both ‘#’ and & are left-associative.

So expression 2 # 3 & 5 # 6 &4 will become
((2 # (3 & 5)) # (6 & 4))
Let us apply translation rules, we get
((2 * (3 + 5)) * (6 + 4)) = 160.

Q.46

Consider the following set of processes, with the arrival times and the CPU-burst times given in milliseconds<

    Process   Arrival Time    Burst Time
    P1          0              5
    P2          1              3
    P3          2              3
    P4          4              1

What is the average turnaround time for these processes with the preemptive shortest remaining processing time first (SRPT) algorithm ?

5.50

5.57

6.00

6.25

Ans .

Explanation :

The following is Gantt Chart of execution
P1	P2	P4	P3	P1
1	4	5	8	12   Turn Around Time = Completion Time - Arrival Time   Avg Turn Around Time  =  (12 + 3 + 6+  1)/4 = 5.50

Q.47

Consider a system with a two-level paging scheme in which a regular memory access takes 150 nanoseconds, and servicing a page fault takes 8 milliseconds. An average instruction takes 100 nanoseconds of CPU time, and two memory accesses. The TLB hit ratio is 90%, and the page fault rate is one in every 10,000 instructions. What is the effective average instruction execution time?

645 ns

1050 ns

1215 ns

1230 ns

Ans .

Explanation :

Please note that page fault rate is given one page fault per 10,000 instructions. Since there are two memory accesses per instruction, so we need double address translation time for average instruction execution time. Also, there are 2 page table accessed if TLB miss occurred. TLB access assumed as 0. Therefore, Average Instruction execution time = Average CPU execution time + Average time for getting data(instruction operands from memory for each instruction) = Average CPU execution time + Average address translation time for each instruction + Average memory fetch time for each instruction + Average page fault time for each instruction = 100 + 2×(0.9×(0)+0.1×(2×150)) + 2×150 + 1 /10000 × 8 × 106 = 100 + 60 + 300 + 800 = 1260 ns So, none option is correct.

Q.48

Consider two processes P1 and P2 accessing the shared variables X and Y protected by two binary semaphores SX and SY respectively, both initialized to 1. P and V denote the usual semaphone operators, where P decrements the semaphore value, and V increments the semaphore value. The pseudo-code of P1 and P2 is as follows : P1 :

  While true do {
    L1 : ................
    L2 : ................
    X = X + 1;
    Y = Y - 1;
    V(SX);
    V(SY);
  }

P2:

  While true do {
     L3 : ................
     L4 : ................
     Y = Y + 1;
     X = Y - 1;
     V(SY);
     V(SX);
  }

In order to avoid deadlock, the correct operators at L1, L2, L3 and L4 are respectively

P(SY), P(SX); P(SX), P(SY)

P(SX), P(SY); P(SY), P(SX)

P(SX), P(SX); P(SY), P(SY)

P(SX), P(SY); P(SX), P(SY)

Ans .

Explanation :


  Option A: In line L1 ( p(Sy) ) i.e. process p1 wants lock on Sy that is
  held by process p2 and line L3 (p(Sx)) p2 wants lock on Sx which held by p1.
  So here circular and wait condition exist means deadlock.

  Option B : In line L1 ( p(Sx) ) i.e. process p1 wants lock on Sx that is held
  by process p2 and line L3 (p(Sy)) p2 wants lock on Sx which held by p1. So here
  circular and wait condition exist means deadlock.

  Option C: In line L1 ( p(Sx) ) i.e. process p1 wants lock on Sx and line L3 (p(Sy))
  p2 wants lock on Sx . But Sx and Sy can’t be released by its processes p1 and p2.

Q.49

A Unix-style i-node has 10 direct pointers and one single, one double and one triple indirect pointers. Disk block size is 1 Kbyte, disk block address is 32 bits, and 48-bit integers are used. What is the maximum possible file size ?

2^24 bytes

2^32 bytes

2^34 bytes

2^48 bytes

Ans .

Explanation :

Size of Disk Block = 1Kbyte

Disk Blocks address = 32bits,
but 48 bit integers are used for address
Therefore address size = 6 bytes


No of addresses per block = 1024/6  = 170.66
Therefore 170 ≈ 2^8 addresses per block can be stored

Maximum File Size = 10 Direct + 1 Single Indirect +
                    1 Double Indirect + 1 Triple Indirect
                 = 10 + 28 + 28*28 + 28*28*28
                 ≈ 224 Blocks

Since each block is of size 210

Maximum files size = 224 * 210
                   = 234

Q.50

The relation scheme Student Performance (name, courseNo, rollNo, grade) has the following functional dependencies: name, courseNo → grade rollNo, courseNo → grade name → rollNo rollNo → name
The highest normal form of this relation scheme is

2 NF

3 NF

BCNF

4 NF

Ans .

Explanation :

For easy understanding let's say attributes (name, courseNo, rollNo, grade)
be (A,B,C,D)

Then given FDs are as follows:
AB->D, CB->D, A->C, C->A

Here there are two Candidate keys, AB and CB.

Now AB->D and CB->D satisfy BCNF as LHS is superkey in both.

But, A->C and C->A, doesn't satisfy BCNF. Hence we check for 3NF for
these 2 FDs.

As C and A on RHS of both the FDs are prime attributes, they satisfy 3NF.

Hence for the whole relation the highest normal form is 3NF.

Q.51

Consider the relation Student (name, sex, marks), where the primary key is shown underlined, pertaining to students in a class that has at least one boy and one girl. What does the following relational algebra expression produce? (Note: r is the rename operator). GATE CSE 2014
The condition in join is "(sex = female ^ x = male ^ marks ≤ m)"

names of girl students with the highest marks

names of girl students with more marks than some boy student

names of girl students with marks not less than some boy students4)

names of girl students with more marks than all the boy students

Ans .

Explanation :

he above relational algebra expression has two sub expressions.
The first one takes as input the Student relation (Student) and filters
out all the tuples where sex=female(r sex=female (Student))
and then projects their names (P name r sex=female (Student)).
So we get a new relation with names of all the female students.

The second one takes as input the Student relation and performs a rename
operation on one with attributes name, sex and marks renamed as n, x, m
respectively (r n, x, m(Student)) and then followed by a self-Cartesian
 product on the Student relation. The condition (sex = female ^ m = male ^ marks ≤ m)
filters tuples with all female students from the first relation,
male students from the second relation and performs a Cartesian product where
marks of the female student is either less than or equal to a male student and
then projects their names. So we get a new relation with names of all female
students whose marks are lesser than at least one of the male student.

Q.52

The order of an internal node in a B+ tree index is the maximum number of children it can have. Suppose that a child pointer takes 6 bytes, the search field value takes 14 bytes, and the block size is 512 bytes. What is the order of the internal node?

Ans .

Explanation :

Key size = 14 bytes (given) Child pointer = 6 bytes (given)
We assume the order of B+ tree to be ‘n’.
Block size = (n - 1) * key size + n * child pointer 512 >= (n - 1) * 14 + n * 6 512 >= 14 * n – 14 + 6 * n n = (512 + 14) / 20 n = 526 / 20 n = 26.3 n = 26

Thus, option (C) is correct.

Q.53

The employee information in a company is stored in the relation

Employee (name, sex, salary, deptName)

  Consider the following SQL query
  select deptName
         from Employee
         where sex = 'M'
         group by deptName
         having avg (salary) > (select avg (salary) from Employee)

It returns the names of the department in which

the average salary is more than the average salary in the company

the average salary of male employees is more than the average salary of all male employees in the company

the average salary of male employees is more than the average salary of employees in the same department

the average salary of male employees is more than the average salary in the company

Ans .

Explanation :

In this SQL query, we have
select deptName ---------------  Select the department name
from Employee  ----------------  From the database of employees
where sex = 'M' ---------------  Where sex is male (M)
group by deptName -------------  Group by the name of the department
having avg (salary) >
(select avg (salary) from Employee)  -----  Having the average salary
                                            greater than the average salary
                                            of all employees in the organization.

Q.54

A and B are the only two stations on an Ethernet. Each has a steady queue of frames to send. Both A and B attempt to transmit a frame, collide, and A wins the first backoff race. At the end of this successful transmission by A, both A and B attempt to transmit and collide. The probability that A wins the second backoff race is:

0.5

0.625

0.75

1.0

Ans .

Explanation :

This is basically the question related to unfairness of exponential back-off algorithm called 'capture effect'. You can find more info about it here: http://intronetworks.cs.luc.edu/current/html/ethernet.html#capture-effect The solution to the above problem goes like this: At every attempt to transit a frame, both A and B chooses value of 'k' randomly. Based on the value of 'k', back-off time is calculated as a multiple of 'k'. The station or node having the smaller back-off time gets to send the frames eariler. 1st attempt: Value of 'k' would be k=0 or k=1 (0 <= k <= 2^n-1; where n=nth attempt). Since A won the first race, A must have chosen k=0 and B must have chosen k=1 (A wins here with probability 0.25). As A won, A will again choose k=0 or k=1 for its 2nd frame, but B will choose k=0,1,2 or 3 as B failed to send its first frame in the first attempt. 2nd attempt: Let kA= value of k chosen by A and kB = value of k chosen by B. We will use notation (kA,kB) to show the possible values. Now the sample space for the 2nd attempt is (kA,kB) = (0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2) or (1,3) i.e. 8 possible outcomes. For A to win, kA should be less than kB (kA < kB). Thus, our event space is (kA, kB) = (0,1),(0,2),(0,3),(1,2),(1,3) i.e. 5 possible outcomes. Thus the probability that A wins the 2nd back-off race = 5/8 = 0.625

Journey of a Thousand Miles begins with One Click!!!

UPSCFEVER - POPULAR PAGES

Join The Movement

Discussions and Comments