GATE 2004

Question 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
Question 1 Explanation: 
Structured programming: Which is aimed at improving the clarity, quality and development time of a computer programming by making extensive use of the structured control flow constructs of selection and repetition of block structures and subroutines in contrast to using simple tests and jumps such as goto statements.
Question 2

Consider the following C function.

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

In order to exchange the values of two variables x and y.

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
Question 2 Explanation: 
Option A:
Here parameters passed by value in C then there is no change in the values.
Option B:
Here values are not swap.
Here parameters are passed by address in C.
Option C:
It is false. Return value is not valid for exchanging the variables.
Option D:
It is correct.
We cannot use swap(x,y) because parameters are passed by value.
Only exchanging the values (or) variables are passing their address and then modify the content with the help of dereferencing operator(*).
Question 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 < top2) 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)
top1 = top2 – 1
Question 3 Explanation: 
Since the stacks are growing from opposite ends, so initially top1=1 and top2=Max_size. Now to make the efficient use of space we should allow one stack to use the maximum possible space as long as other stack doesn't need it. So any of the stack can grow towards each other until there is space available in the array. Hence, the condition must be top1 = top2 - 1.
Question 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)?

Question 4 Explanation: 

Height of the binary search tree = 3
Question 5

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

Question 5 Explanation: 
Stack is the best data structure to validate the arithmetic expression.
While evaluating when left parentheses occur then it push in to the stack, when right parentheses occur pop from the stack.
While at the end there is empty in the stack.
Question 6

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

preorder traversal
in-order traversal
depth first search
breadth first search
Question 6 Explanation: 
Breadth first search:
It is an algorithm for traversing (or) searching tree (or) graph data structures. It starts at the root and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.
Question 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?

    i) 9679, 1989, 4199 hash to the same value
    ii) 1471, 6171 hash to the same value
    iii) All elements hash to the same value
    iv) Each element hashes to a different value
i only
ii only
i and ii only
iii or iv
Question 7 Explanation: 
Given Input = (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199)
Hash function = x mod 10
Hash values = (2, 4, 1, 9, 9, 1, 3, 9)
9679, 1989, 4199 have same hash values
1471, 6171 have same hash values.
Question 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.

    (i) P → Q R
    (ii) P → Q s R
    (iii) P → ε
    (iv) P → Q t R r
(i) only
(i) and (iii) only
(ii) and (iii) only
(iii) and (iv) only
Question 8 Explanation: 
Operator values doesn't contains nullable values and two adjacent non-terminals on RHS production.
i) On RHS it contains two adjacent non-terminals.
ii) Have nullable values.
Question 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
Question 9 Explanation: 
The link time can gives the reference to the executable file when the functions are present in the other modules.
Question 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 to evaluation of E1 and E2 is of no consequence
Question 10 Explanation: 
After evaluating E2 first and then E1, we will have E2 in the register and then we can simply do SUB operation with E2 which will be in memory. And if we do E1 first and then E2, then we must move E2 to memory and again bring back E1 to the register before doing SUB operation, which will increase load.
Question 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

Which of the above statements are true?

(ii), (iii) and (iv) only
(ii) and (iii) only
(i) and (iii) only
(i) and (ii) only
Question 11 Explanation: 
→ User level thread context switch is faster than kernel level threads. Option A is false.
→ If one user level thread perform blocking operation then entire process will be blocked. Option B is true.
→ User level threads are threads are transparent to the kernel. Because user level threads are created by users. Option D is true.
→ Kernel supported threads can be scheduled independently, that is based on OS. Option C is true.
Question 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?

Question 12 Explanation: 
There is no improvement in the I/O performance.
→ The better vendor benchmark results doesn't effects the I/O performance.
→ In FCFS (or) SSTF only one choice is to choose for IO from multiple IO's. There is always one I/O at a time.
Question 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?

ΠD(r2) - ΠC(r1)
ΠC(r1) - ΠD(r2)
Question 13 Explanation: 
C be a foreign key in R1 referring to R2.
→ Based on referral integrity C is subset of values in R2 then,
ΠC(r1) - ΠD(r2) results empty relation.
Question 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, 8
120, 8
960, 8
960, 120
Question 14 Explanation: 
Natural join is a JOIN operation that creates an implicit join cause for you based on common columns in the two tables being joined.
→ In the question only enroll Id's are same with the student table.
→ The no. of minimum and maximum tuples is same i.e., 8, 8.
Question 15

Choose the best matching between Group 1 and Group 2.

   Group-1   	  	  Group-2   
 P. Data link          1. Ensures reliable transport of data
                          over a physical point-to-point link
 Q. Network layer      2. Encoder/decodes data for physical
 R. Transport layer    3. Allows end-to-end communication
                          between two processes
                       4. Routes data from one network
                          node to the next
P - 1, Q - 4, R - 3
P - 2, Q - 4, R - 1
P - 2, Q - 3, R - 1
P - 1, Q - 3, R - 2
Question 15 Explanation: 
Data Link Layer :: Second layer of the OSI Model, Responsible for Hop to Hop connection or point to point connection.
Transport Layer :: Fourth layer of the OSI Model, Responsible for Service point addressing/Socket to socket connection or end to end connection with full reliability.
Network Layer :: Third layer of the OSI Model, Responsible for Host to Host.
Question 16

Which of the following is NOT true with respect to a transparent bridge and a router?

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
Question 16 Explanation: 
A bridge use MAC addresses (DLL layer) and router uses IP addresses (network layer).
Question 17

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

x' + y'
x + y
x + y'
x' + y
Question 17 Explanation: 
x'y' + xy + x'y
= x'y' + x'y + xy
= x'(y'+y)+xy
= x'⋅1+xy
= x'+xy
= (x'+x)(x'+y)
= 1⋅(x'+y)
= x'+y
Question 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
Question 18 Explanation: 

Truth table for the SR latch by cross coupling two NAND gates is

So, Answer is Option (D).
Question 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
Question 19 Explanation: 
(73)x = (54)y
7x+3 = 5y+4
7x-5y = 1
Only option (D) satisfies above equation.
Question 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)