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 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

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 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  
3  
4  
6 
Height of the binary search tree = 3
Question 5 
The best data structure to check whether an arithmetic expression has balanced parentheses is a
queue  
stack  
tree  
list 
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  
inorder traversal  
depth first search  
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 
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 
i) On RHS it contains two adjacent nonterminals.
ii) Have nullable values.
Question 9 
Consider a program P that consists of two source modules M_{1} and M_{2} contained in two different files. If M_{1} contains a reference to a function defined in M_{2}, the reference will be resolved at
Edit time  
Compile time  
Link time  
Load time 
Question 10 
Consider the grammar rule E → E_{1}  E_{2} 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 E_{1} and E_{2} do not have any common sub expression, in order to get the shortest possible code
E_{1} should be evaluated first
 
E_{2} should be evaluated first  
Evaluation of E_{1} and E_{2} should necessarily be interleaved  
Order to evaluation of E_{1} and E_{2} is of no consequence

Question 11 
Consider the following statements with respect to userlevel threads and kernel supported threads
 (i) context switch is faster with kernelsupported threads
(ii) for userlevel 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 
→ 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?
50%  
40%  
25%  
0% 
→ 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 R_{1}(A,B,C) and R_{2}(D,E) be two relation schema, where the primary keys are shown underlined, and let C be a foreign key in R_{1} referring to R_{2}. Suppose there is no violation of the above referential integrity constraint in the corresponding relation instances r_{1} and r_{2}. Which one of the following relational algebra expressions would necessarily produce an empty relation?
Π_{D}(r_{2})  Π_{C}(r_{1})  
Π_{C}(r_{1})  Π_{D}(r_{2})  
Π_{D}(r_{1}⨝_{C≠D}r_{2})  
Π_{C}(r_{1}⨝_{C=D}r_{2}) 
→ Based on referral integrity C is subset of values in R_{2} then,
Π_{C}(r_{1})  Π_{D}(r_{2}) 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 
→ 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.
Group1 Group2 P. Data link 1. Ensures reliable transport of data over a physical pointtopoint link Q. Network layer 2. Encoder/decodes data for physical transmission R. Transport layer 3. Allows endtoend 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 
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 17 
The Boolean function x'y' + xy + x'y is equivalent to
x' + y'  
x + y  
x + y'  
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 crosscoupling 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 
Truth table for the SR latch by cross coupling two NAND gates is
So, Answer is Option (D).
Question 19 
If 73_{x} (in basex number system) is equal to 54_{y} (in basey number system), the possible values of x and y are
8, 16  
10, 12  
9, 13  
8, 11 
7x+3 = 5y+4
7x5y = 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)  
(i) and (ii)  
(ii) and (iii)  
(i), (ii) and (iv)

A fixed address in memory which indicates a location by specifying a distance from another location. In this displacement type addressing is preferred.
So, option A is false.
Based Addressing:
This scheme is used by computers to control access to memory. In this pointers are replaced by protected objects which can be executed by kernel (or) some other privileged process authors.
So, this is suitable for program relocation at runtime.
Relative Addressing:
The offset of the relative addressing is to allow reference to code both before and after the instruction.
This is also suitable.
Indirect Addressing:
Which leads to extra memory location which can be not suitable at run time.
This is not suitable.
→ Only Based Addressing and Relative Addressing are suitable.
Question 21 
he 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 
→ An ISA permits multiple implementations that may vary in performance, physical size and monetary cost.
Question 22 
How many 8bit 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 
So bit rate is 9600 bps.
To send one char we need to send (1 + 8 + 2 +1) = 12
So total char send = 9600 / 12 = 800
Question 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))) 
'∧' → predicts statements are always true, no matter the value of x.
'→' → predicts there is no need of left predicate to be true always, but whenever it becomes true, then right predicate must be true.
Option D:
There exists a some boys who are taller than of all girls y.
Question 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, ... }}

Answer is option B.
{(x, y)y ≥ x and x, y ∈ {0, 1, 2, ... }}
Question 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  
3/4 
Then total number of possibilities = 2^{4} = 16
No. of possibilities getting 2 heads and 2 tails is
HHTT, HTHT, TTHH, THTH, THHT, HTTH = 6
Probability of getting 2 heads and 2 tails is
= No. of possibilities/Total no. of possibilities = 6/16 = 3/8
Question 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 2^{x})
power (2,n)  
power (2,n^{2})  
power (2, (n^{2} + n)/2)
 
power (2, (n^{2}  n)/2)

A[i][j] = A[j][i]
So, we have only two choices, they are either upper triangular elements (or) lower triangular elements.
No. of such elements are
n + (n1) + (n2) + ... + 1
n(n+1)/2
We have two choices, thus we have
2^{(n(n+1)/2)} = 2^{((n2+n)/2) choices i.e., Power (2, (n2+n)/2). }
Question 27 
Let A, B, C, D be n × n matrices, each with nonzero determinant. If ABCD = 1, then B^{1} is
D^{1}C^{1}A^{1}  
CDA
 
ADC  
Does not necessarily exist 
ABCD = I
Pre multiply A^{1} on both sides
A^{1}ABCD = A^{1}⋅I
BCD = A^{1}
Pre multiply B^{1} on both sides
B^{1}BCD = B^{1}A^{1}
CD = B^{1}A^{1}
Post multiply A on both sides
CDA = B^{1}A^{1}⋅A
∴ CDA = B^{1}(I)
∴ CDA = B^{1}
Question 28 
What is the result of evaluating the following two expressions using threedigit 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 
= (2) + 7.51
= 9.51 (✔️)
113. + (111. + 7.51)
= 113. + (103.51)
= 113. + 103
= 10 (✔️)
Question 29 
The tightest lower bound on the number of comparisons, in the worst case, for comparisonbased sorting is of the order of
n  
n^{2}  
nlogn  
nlog^{2}n 
→ Tightest upper bound is (big O).
Tightest lower bound is (big Ω).
Question 30 
The problems 3SAT and 2SAT are
both in P  
both NP complete  
NPcomplete and in P respectively  
undecidable and NPcomplete respectively 
2SAT and 3SAT is a NPcomplete.
Question 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); }
The value returned by f(1) is
5  
6  
7
 
8 
The value return by f(1) = 7
Question 32 
Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = d_{1}d_{2}…d_{m}.
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 = d_{1}d_{2}…d_{mi} and rev = d_{m}d_{m1}…d_{mi+1}
 
n = d_{mi+1}…d_{m1}d_{m} or rev = d_{mi}…d_{2}d_{1}
 
n ≠ rev  
n = d_{1}d_{2}…d_{m} and rev = d_{m}…d_{2}d_{1} 
Question 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);
The output of the program is
gnirts  
string
 
gnirt  
no output is printed 
P[0] = S[71] = S[6] = \0.
In P[ ], the first character is '\0'. Then it will results a empty string. If P[0] become '\0', then it doesn't consider about next values in sequence.
Question 34 
It is desired to design an objectoriented 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
Choose the best design
(i), (iv), (vi), (viii)  
(i), (iv), (vii)  
(i), (iii), (v), (vi), (viii)  
(ii), (v), (viii) 
Question 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)
 
(iii) only
 
(iv) only 
(i) Inorder and Preorder
(ii) Inorder and Postorder
(iii) Inorder and Levelorder
→ And following are do not
(i) Post order and Preorder
(ii) Pre order and Level order
(iii) Post order and Level order
Question 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?
rear node  
front node  
not possible with a single pointer  
node next to front 
Question 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
Question 38 
abc×+def^^  
abc×+de^f^  
ab+c×de^f^  
+a×bc^^def 
Note: When low precedence operator enters into stack then pop.
Question 39 
Two matrices M_{1} and M_{2} are to be stored in arrays A and B respectively. Each array can be stored either in rowmajor or columnmajor order in contiguous memory locations. The time complexity of an algorithm to compute M_{1} × M_{2} will be
best if A is in rowmajor, and B is in column major order  
best if both are in rowmajor order  
best if both are in columnmajor order  
independent of the storage scheme 
But if the question would have asked best time complexity in which of the following implementation (not algorithm) then Option (A) is correct.
Question 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 
Let no. of elements in list 2 be n_{2}.
Union:
To union two lists, for each element in one list we will search in other list, to avoid duplicates. So, time complexity will be O(n_{1}×n_{2}).
Intersection:
To take intersection of two lists, for each element in one list we will search in other list if it is present or not. So time complexity will be O(n_{1} × n_{2}).
Membership:
In this we search if particular element is present in the list or not. So time complexity will be O(n_{1} + n_{2}).
Cardinality:
In this we find the size of set or list. So to find size of list we have to traverse each list once. So time complexity will be O(n_{1}+n_{2}).
Hence, Union and Intersection will be slowest.
Question 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 
Question 42 
What does the following algorithm approximate?(Assume m > 1, ε > 0).
x = m; y = 1; while (x  y > ε) { x = (x + y)/2; y = m/x; } print(x);
log m  
m^{2}  
m^{1/2}  
m^{1/3} 
x = (x + m/x)/2
2x = x^{2}+m/x
2x^{2} = x^{2} + m
x^{2} = m
x = √m = m^{1/2}
Question 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 value returned by the function DoSomething when a pointer to the root of a nonempty tree is passed as argument is
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 
→ So given that pointer to root of tree is passed to DoSomething ( ), it will return height of the tree. It is done when the height of single node is '0'.
Question 44 
Suppose we run Dijkstra’s single source shortestpath 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 are finalized?
P, Q, R, S, T, U  
P, Q, R, U, S, T  
P, Q, R, U, T, S  
P, Q, T, R, U, S

P, Q, R, U, S, T
Question 45 
Consider the grammar with the following translation rules and E as the start symbol.
E → E_{1} # T {E.value = E_{1}.value * T.value}  T {E.value = T.value} T → T_{1} & F {T.value = T_{1}.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  
40 
2 # 3 & 5 # 6 & 4
→ Here # means multiplication (*)
& means addition (+)
→ & is having more precedence because it is far from starting symbol, here # and & are left associatives.
2 # 3 & 5 # 6 & 4
⇒ (2 * (3+5)) * (6+4)
⇒ (2 * 8) * (10)
⇒ 16 * 10 = 160
Question 46 
Consider the following set of processes, with the arrival times and the CPUburst 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.75  
6.00  
6.25 
Avg. TAT = 12+3+6+1/4 = 22/4 = 5.50
Question 47 
Consider a system with a twolevel 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 nanoseconds  
1050 nanoseconds  
1215 nanoseconds  
2060 nanoseconds 
= 100ns + 2EMAT
Now lets calculate EMAT,
EMAT = TLB + miss rate × 2 × 150ns + 150ns + 1/10000 × 8ms
= 0 + 0.1 × 300ns + 150ns + 800ns
= 980ns
∴ Effective average instruction time,
= 100ns + 2 × 980ns
= 2060ns
Question 48 
Consider two processes P_{1} and P_{2} accessing the shared variables X and Y protected by two binary semaphores S_{X} and S_{Y} 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 pseudocode of P_{1} and P_{2} is as follows:
P_{1} : While true do { L_{1} : ................ L_{2} : ................ X = X + 1; Y = Y  1; V(S_{X}); V(S_{Y}); } P_{2} : While true do { L_{3} : ................ L_{4} : ................ Y = Y + 1; X = Y  1; V(S_{Y}); V(S_{X}); }
In order to avoid deadlock, the correct operators at L_{1}, L_{2}, L_{3} and L_{4} are respectively
P(S_{y}), P(S_{x}); P(S_{x}), P(S_{y})
 
P(S_{x}), P(S_{y}); P(S_{y}), P(S_{x})
 
P(S_{x}), P(S_{x}); P(S_{y}), P(S_{y})
 
P(S_{x}), P(S_{y}); P(S_{x}), P(S_{y})

P_{1} : line 1
P_{2} : line 3 (block require S_{x})
P_{1} : line 2
P_{2} : line 4 (still in block state)
P_{1} : execute CS, the push up the value of S_{x}.
P_{2} : line 3 line 4 (block require S_{y})
P_{1} : push up S_{y}
P_{2} : line 4 get S_{y} and enter into CS
P_{2} : start execution.
So option D is Answer.
Question 49 
A Unixstyle inode 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 48bit integers are used. What is the maximum possible file size?
2^{24} bytes
 
2^{32} bytes
 
2^{34} bytes  
2^{48} bytes 
= 10 + 2^{8} + (2^{8})^{2} + (2^{8})^{3}
= 2^{24} Blocks (App)
Size of each block = 2^{10}
Maximum file size = 2^{24} × 2^{10} = 2^{34}
Question 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  
4NF 
name, courseNo → grade →(I)
rollNo, courseNo → grade →(II)
name → rollNo →(III)
rollNo → name →(IV)
Candidate keys: name, courseNo (or) rollNo
Its is not BCNF, because the relation III, there is no relationship from super key.
name → rollNo
It is not BCNF, name is not super key.
It belongs to 3NF, because if X→Y, Y is prime then it is in 3NF.
Question 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: p is the rename operator).
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 students
 
names of girl students with more marks than all the boy students 
Question 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?
24  
25  
26  
27 
Child pointer = 6 bytes
key size = 14 bytes
Block size = 512 bytes
⇒ 512 = (n1)14 + n(6)
512 = 20n  14
n = 512+14/20 = 526/20 = 26.3
∴ n = 26
Question 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 
This results the employees who having the salary more than the average salary.
Sex = M
Selects the Male employees whose salary is more than the average salary in the company.
Question 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 
The probability that A wins the second backoff race = 5/8 = 0.625
More explanation in the video.
Question 55 
The routing table of a router is shown below:
Destination Sub net mask Interface 128.75.43.0 255.255.255.0 Eth0 128.75.43.0 255.255.255.128 Eth1 192.12.17.5 255.255.255.255 Eth3 Default Eth2
On which interfaces will the router forward packets addressed to destinations 128.75.43.16 and 192.12.17.10 respectively?
Eth1 and Eth2  
Eth0 and Eth2  
Eth0 and Eth3  
Eth1 and Eth3 
If results of ANDing subnet masks and IP address are same then subnet mask with higher number of 1s is preferred.
IP address 128.75.43.16 is AND with 255.255.255.0 results 128.75.43.0 Net ID which is similar to destination of this mask, but ANDing 128.75.43.16 with 255.255.255.128 also results same destination. So, here, mask with higher number of one is considered and router will forward packet to Eth1.
ANDing 192.12.17.10 with three subnet mask in table does not result in destination Net ID so router will forward this packet to default network via Eth2.
Question 56 
Consider three IP networks A, B and C. Host H_{A} in network A sends messages each containing 180 bytes of application data to a host H_{C} in network C. The TCP layer prefixes a 20 byte header to the message. This passes through an intermediate network B. The maximum packet size, including 20 byte IP header, in each network is:
A : 1000 bytes B : 100 bytes C : 1000 bytes
The network A and B are connected through a 1 Mbps link, while B and C are connected by a 512 Kbps link (bps = bits per second).
Assuming that the packets are correctly delivered, how many bytes, including headers, are delivered to the IP layer at the destination for one application message, in the best case? Consider only data packets.
200  
220  
240  
260 
Data will be divided in three packets as:
First packet: 80 bytes + 20 byte of header
Second packet: 80 bytes + 20 byte of header
Third packet: 40 bytes + 20 byte of header
Note: Defragmentation (grouping of fragments) is done only at destination.
H_{C} will receive total 260 bytes including header.
Question 57 
Consider three IP networks A, B and C. Host H_{A} in network A sends messages each containing 180 bytes of application data to a host H_{C} in network C. The TCP layer prefixes a 20 byte header to the message. This passes through an intermediate network B. The maximum packet size, including 20 byte IP header, in each network is:
A : 1000 bytes B : 100 bytes C : 1000 bytes
The network A and B are connected through a 1 Mbps link, while B and C are connected by a 512 Kbps link (bps = bits per second).
What is the rate at which application data is transferred to host H_{C}? Ignore errors, acknowledgements, and other overheads.
325.5 Kbps
 
354.5 Kbps  
409.6 Kbps  
512.0 Kbps 
Application data is transferred at rate of (180/260) x 512 Kbps = 354.46 Kbps
Question 58 
A circuit outputs a digit in the form of 4 bits. 0 is represented by 0000, 1 by 0001, ..., 9 by 1001. A combinational circuit is to be designed which takes these 4 bits as input and outputs 1 if the digit ≥ 5, and 0 otherwise. If only AND, OR and NOT gates may be used, what is the minimum number of gates required?
2  
3  
4  
5 
= A + BD + BC
= A + B (D + C)
So minimum two OR gates and 1 AND gate is required. Hence, in total minimum 3 gates is required.
Question 59 
Which are the essential prime implicants of the following Boolean function?
f(a,b,c) = a^{ȼ}c + ac^{ȼ} + b^{ȼ}c
a^{ȼ}c and ac^{ȼ}  
a^{ȼ}c and b^{ȼ}c  
a^{ȼ}c only  
ac^{ȼ} and bc^{ȼ} 
There are two EPI,
A'C and AC'.
Question 60 
Consider a multiplexer with X and Y as data inputs and Z as control input. Z = 0 selects input X, and Z = 1 selects input Y. What are the connections required to realize the 2variable Boolean function f = T + R, without using any additional hardware?
R to X, 1 to Y, T to Z  
T to X, R to Y, T to Z  
T to X, R to Y, 0 to Z  
R to X, 0 to Y, T to Z 
f = z'x + zy
Put z=T, x=R, y=1 in f
f = T'R + T = (T+T') (R+T) = T+R
Hence, correct option is (A).
Question 61 
Consider the partial implementation of a 2bit counter using T flipflops following the sequence 02310, as shown below
To complete the circuit, the input X should be
Q_{2}^{c}  
Q_{2} + Q_{1}  
(Q_{1} + Q_{2})^{c}  
Q_{1} ⊕ Q_{2} 
0  2  3  1  0
or
00  10  11  01  00
From the given sequence, we have state table as,
Now we have present state and next state, so we should use excitation table of T flipflop,
From state table,
T_{2} = Q_{2}⊙Q_{1} and T_{1} = Q_{2}⊕Q_{1}
X = T_{1} = Q_{2}⊕Q_{1}
Question 62 
A 4bit carry lookahead adder, which adds two 4bit numbers, is designed using AND, OR, NOT, NAND, NOR gates only. Assuming that all the inputs are available in both complemented and uncomplemented forms and the delay of each gate is one time unit, what is the overall propagation delay of the adder? Assume that the carry network has been implemented using twolevel ANDOR logic.
4 time units  
6 time units  
10 time units  
12 time units 
1) (2 time units) In 2 time units we can compute G_{i} and P_{i} in parallel, 2 time units for P_{i} since its an XOR operation and 1 time unit for G_{i} since its an AND operation.
2) (2 time units) Once G_{i} and P_{i} are available, we can calculate the carries, C_{i}, in 2 time units.
Level1 we can compute all the conjunctions (AND).
Example: P_{3}G_{2}, P_{3}P_{2}G_{1}, P_{3}P_{2}P_{1}G_{0} and P_{3}P_{2}P_{1}P_{0}C_{0} which are required for C_{4}.
Level2 we get the carries by computing the disjunction (OR).
3) (2 time units) Finally, we compute the sum in 2 time units, as its a XOR operation.
Hence, the total is 2+2+2 = 6 time units.
Question 63 
Consider the following program segment for a hypothetical CPU having three user registers R1, R2 and R3.
Instruction Operation Instruction Size(in words) MOV R1,5000; ;R1 ← Memory[5000] 2 MOV R2(R1); ;R2 ← Memory[(R1)] 1 ADD R2,R3; ;R2 ← R2 + R3 1 MOV 6000,R2; ;Memory[6000] ← R2 2 HALT ;Machine halts 1
Consider that the memory is byte addressable with size 32 bits, and the program has been loaded starting from memory location 1000 (decimal). If an interrupt occurs while the CPU has been halted after executing the HALT instruction, the return address (in decimal) saved in the stack will be
1007  
1020  
1024  
1028 
→ Interrupt occurs after executing halt instruction
So, number of instructions = 2+1+1+2+1 = 7
→ Each instruction with 4 bytes, then total instruction size = 7 * 4 = 28
→ Memory start location = 1000
→ Instruction saved location = 1000 + 28 = 1028
1028 is the starting address of next instruction.
Question 64 
Consider the following program segment for a hypothetical CPU having three user registers R1, R2 and R3.
Instruction Operation Instruction Size(in words) MOV R1,5000; ;R1 ← Memory[5000] 2 MOV R2(R1); ;R2 ← Memory[(R1)] 1 ADD R2,R3; ;R2 ← R2 + R3 1 MOV 6000,R2; ;Memory[6000] ← R2 2 HALT ;Machine halts 1
Let the clock cycles required for various operations be as follows:
Register to/ from memory transfer : 3 clock cycles ADD with both operands in register : 1 clock cycle Instruction fetch and decode : 2 clock cycles per word
The total number of clock cycles required to execute the program is
29  
24  
23  
20 
Question 65 
Consider a small twoway setassociative cache memory, consisting of four blocks. For choosing the block to be replaced, use the least recently used (LRU) scheme. The number of cache misses for the following sequence of block addresses is 8, 12, 0, 12, 8
2  
3  
4  
5 
The given sequence is 8, 12, 0, 12, 8.
So in total 4 misses is there.
Question 66 
Let A = 1111 1010 and B = 0000 1010 be two 8bit 2's complement numbers. Their product in 2's complement is
1100 0100
 
1001 1100
 
1010 0101
 
1101 0101 
B = 0000 1010 = 10_{10} [2's complement number]
A×B = 6×10 =  60_{10}
⇒ 60_{10} = 10111100_{2}
= 11000011_{2} (1's complement)
= 11000100_{2} (2's complement)
Question 67 
The microinstructions stored in the control memory of a processor have a width of 26 bits. Each microinstruction is divided into three fields: a microoperation field of 13 bits, a next address field (X), and a MUX select field (Y). There are 8 status bits in the inputs of the MUX.
How many bits are there in the X and Y fields, and what is the size of the control memory in number of words?
10, 3, 1024  
8, 5, 256  
5, 8, 2048  
10, 3, 512 
Micro process field width = 13 bits
MUX consists of 8 state bits, then it require 3 inputs to select input line.
No. of bits for next address field = 26  13  3= 10
For 10 bit addressing, we require 2^{10} memory size
Size (X, Y) = 10, 3
Question 68 
A hard disk with a transfer rate of 10 Mbytes/ second is constantly transferring data to memory using DMA. The processor runs at 600 MHz, and takes 300 and 900 clock cycles to initiate and complete DMA transfer respectively. If the size of the transfer is 20 Kbytes, what is the percentage of processor time consumed for the transfer operation?
5.0%  
1.0%  
0.5%  
0.1% 
For DMA initiation and completion total 1200 cycles is required. So total time will be = 1200 × 1/600 × 10^{6} = 2μs
Disk transfer rate = 10MB/s
1B = 1/10^{7} s
So, total transfer 20KB time taken will be,
20 × 10^{3} × 1/(10^{7}) s
= 2000μs
∴ Percentage of processor time consumed is,
2/2+2000 × 100 = 0.1%
Question 69 
A 4stage pipeline has the stage delays as 150, 120, 160 and 140 nanoseconds respectively. Registers that are used between the stages have a delay of 5 nanoseconds each. Assuming constant clocking rate, the total time taken to process 1000 data items on this pipeline will be
120.4 microseconds
 
160.5 microseconds  
165.5 microseconds
 
590.0 microseconds 
1st instruction × 4 × clock time + 999 instruction × 1 × clock time
1 × 4 × 165ns + 999 × 1 × 165ns
= 1654.95ns
= 165.5μs
Question 70 
The following propositional statement is (P → (Q v R)) → ((P v Q) → R)
satisfiable but not valid
 
valid  
a contradiction  
None of the above 
If P=T; Q=T; R=T
(P→(T∨T)) → ((T∨T)→R)
(P→T) → (T→R)
(T→T) → (T→T)
T→T
T(Satisfiable)
Question 71 
How many solutions does the following system of linear equations have?
x + 5y = 1 x  y = 2 x + 3y = 3
infinitely many  
two distinct solutions  
unique  
none 
rank = r(A) = r(AB) = 2
rank = total no. of variables
Hence, unique solution.
Question 72 
The following is the incomplete operation table a 4element group.
The last row of the table is
c a e b  
c b a e  
c b e a  
c e a b 
The last row is c e a b.
Question 73 
The inclusion of which of the following sets into
S = {{1,2}, {1,2,3}, {1,3,5}, (1,2,4), (1,2,3,4,5}}
is necessary and sufficient to make S a complete lattice under the partial order defined by set containment?
{1}  
{1}, {2, 3}  
{1}, {1, 3}  
{1}, {1, 3}, (1, 2, 3, 4}, {1, 2, 3, 5} 
For the set {1, 2, 3, 4, 5} there is no supremum element i.e., {1}.
Then clearly we need to add {1}, then it is to be a lattice.
Question 74 
An examination paper has 150 multiplechoice questions of one mark each, with each question having four choices. Each incorrect answer fetches 0.25 mark. Suppose 1000 students choose all their answers randomly with uniform probability. The sum total of the expected marks obtained by all these students is:
0  
2550  
7525  
9375 
Probability of selecting a wrong answer = 3/4
For correct answer +1, for wrong answer0.25;
Expected marks for each question = (1/4) × 1 + (3/4) (0.25)
= 1/4 + (3/16)
= 43/16
= 1/16
= 0.0625
Expected marks for 150 questions = 150 × 0.625 = 9.375
The sum total of expected marks obtained by 1000 students is = 1000×9.375 = 9375
Question 75 
Mala has a colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints with one of k colours, such that the colourpairs used to colour any two letters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of k that satisfies this requirement?
9  
8  
7  
6 
Each is printed twice the no. of letters = 26×2 = 52
If Mala has k colours, she can have k pairs of same colours.
She also can have ^{k}C_{2} different pairs in which each pair is having different colours.
So total no. of pairs that can be coloured = k+^{k}C_{2}
k+^{k}C_{2} ≥ 26
k+k(k1)/2 ≥ 26
k(k+1)/2 ≥ 26
k(k+1) ≥ 52
k(k+1) ≥ 7*8
k≥7
Question 76 
In an M×N matrix such that all nonzero entries are covered in a rows and b columns. Then the maximum number of nonzero entries, such that no two are on the same row or column, is
≤ a+b  
≤ max(a, b)  
≤ min(Ma, Nb)  
≤ min(a, b) 
→ Such that a row can have maximum of a elements and no row has separate element and for b also same.
→ By combining the both, it should be ≤ (a,b).
Question 77 
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same colour, is
2  
3  
4  
5 
→ a, b, c, d = 4
→ The minimum no. of colours required to colour a graph = 4 (no two adjacent vertices have same colours)
Question 78 
Two n bit binary strings, S_{1} and S_{2}, are chosen randomly with uniform probability. The probability that the Hamming distance between these strings (the number of bit positions where the two strings differ) is equal to d is
^{n}C_{d} /2^{n}
 
^{n}C_{d} / 2^{d}  
d/2^{n}  
1/2^{d} 
Total no. of cases where n positions have any binary bit = 2^{n}
The probability of 'd' bits differ = ^{n}C_{d} / 2^{n}
Question 79 
How many graphs on n labeled vertices exist which have at least (n^{2}  3n)/2 edges?
Maximum no. of vertices = n(n1)/2 = v
No. of graphs with minimum b edges is
= C(v,e) + C(v,e+1) + C(v,e+2) + ... + C(v,v)
= C((v,ve) + C(v,v(e+1)) + C(v,v(e+2)) + ... + C(v,0)
= C(a,n) + C(a,n1) + C(a,n2) + ... + C(a,0) (since ab=n)
= C(n(n1)/2,n) + C(n(n1)/2,n1) + ... + C(n(n1)/2,0)
Question 80 
A point is randomly selected with uniform probability in the XY plane within the rectangle with corners at (0,0), (1,0), (1,2) and (0,2). If p is the length of the position vector of the point, the expected value of p^{2} is
2/3  
1  
4/3  
5/3 
Above diagram shows the scenario of our question.
The length p of our position vector (x,y) is
p = √x^{2} + y^{2}
p^{2} = x^{2} + y^{2}
E(p^{2}) = E(x^{2} + y^{2}) = E(x^{2}) + E(y^{2})
Now we need to calculate the probability density function of X and Y.
Since distribution is uniform,
X goes from 0 to 1, so PDF(x) = 1/10 = 1
Y goes from 0 to 2, so PDF(y) = 1/20 = 1/2
Now we evaluate,
E(p^{2}) = E(x^{2}) + E(y^{2}) = 5/3
Question 81 
Let G_{1} = (V,E_{1}) and G_{2} = (V,E_{2}) be connected graphs on the same vertex set V with more than two vertices. If G_{1} ∩ G_{2} = (V, E_{1} ∩ E_{2}) is not a connected graph, then the graph G_{1} U G_{2} = (V, E_{1} U E_{2})
cannot have a cut vertex
 
must have a cycle  
must have a cutedge (bridge)
 
has chromatic number strictly greater than those of G_{1} and G_{2}

(A)
False, since in G_{1}∪G_{2} 'C' is a cut vertex.
(B) True, for all conditions.
(C)
False. G_{1}∪G_{2} has no bridge.
D)
False. G_{1}∪G_{2}, G_{1}, G_{2} all the three graphs have chromatic number of 2.
Question 82 
Let A[1,...,n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is θ(m). Consider the following program fragment written in a C like language:
counter = 0; for (i = 1; i < = n; i++) { if (A[i] == 1) counter++; else { f(counter); counter = 0; } }
The complexity of this program fragment is
Ω(n^{2})
 
Ω(nlogn) and O(n^{2})  
θ(n)  
o(n) 
If the string contains all one's then it takes O(n) time, because counter++ can execute n times.
If it contains half 0's and half 1's then also it takes O(n) time.
Question 83 
The time complexity of the following C function is (assume n > 0)
int recursive (int n) { if (n == 1) return (1); else return (recursive (n  1) + recursive (n  1)); }
O(n)  
O(n log n)  
O(n^{2})  
O(2^{n})

return(1)
else
return(recursive(n1) + recursive(n1))
n>0:
T(2) = T(1) + T(1) = 2T(1)
T(3) = T(2) + T(2) = 2T(2) = 2⋅2T(1) = 2^{2}T(1)
T(4) = 2^{3}⋅T(1)
⋮
T(n) = 2^{n}⋅T(1) = O(2^{n})
Question 84 
The recurrence equation
T(1) = 1 T(n) = 2T(n  1) + n, n ≥ 2
evaluates to
2^{n+1} – n – 2  
2^{n} – n  
2^{n+1} – 2n – 2  
2^{n} + n 
T(n) = 2T(n1) + n
T(2) = 2T(1) + 2 = 2 + 2 = 4
T(3) = 2T(2) + n = 2(4) + 3 = 11
T(4) = 2T(3) + 4 = 22 + 4 = 26
Let check with the options:
Option A:
n=4
2^{4+1}  4  2
32  6
26 (✔️)
Option B:
n=4
2^{n}n
2^{4}4
12(✖️)
Option C:
n=4
2^{4+1}  2(4)  8
32  10
22(✖️)
Option D:
n=4
2^{n}  n
2^{4}  4
12(✖️)
Question 85 
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 leafnodes in leftsubtree of x, no. of leafnodes in rightsubtree of x} then the worstcase time complexity of the program is
Θ (n)  
Θ (n log n)  
Θ (n^{2})  
Θ (n^{2} log n) 
⇒ g(x) = min (no. of leaf nodes of leftsubtree of x, no. of leaf nodes in the rightsubtree of x)
→ Total no. of leaves = n
Time complexity for a binary search = log n
Time complexity of the program is = O(n(log n))
Question 86 
The following finite state machine accepts all those binary strings in which the number of 1's and 0's are respectively.
divisible by 3 and 2  
odd and even  
even and odd  
divisible by 2 and 3 
For example 001 consists of even no. of zero's and odd no. of one's. It is not accepted by TM.
So, it is false.
Option C:
For example 110, contains even 1's and odd 0's but not accepted by TM.
So, it is false.
Option D:
For example 11000, where no. of 1's divisible by '2', and no. of zero's divisible by 3, but not accepted by TM.
So, it is false.
Option A:
It accepts all string where no. of 1's divisible by 3, and no. of zero's divisible by 2.
It is true.
Question 87 
The language {a^{m} b^{n} C^{m+n}  m, n ≥ 1} is
regular  
contextfree but not regular
 
context sensitive but not context free  
type0 but not context sensitive 
PUSH z_{0} into stack
PUSH K to stack of occurrence of a
PUSH L to stack of occurrence of b
POP K and L for the occurrence of c
→ After POP no elements in the stack. So, this is context free language.
Note:
Regular:
R = {a^{n}  n ≥ 1}, Example.
CFL:
R = {a^{n}b^{m}  n,m ≥ 1}, Example.
Question 88 
Consider the following grammar G:
S → bS aA b A → bA aB B → bB aS a
Let N_{a}(w) and N_{b}(w) denote the number of a's and b's in a string w respectively. The language L(G) ⊆ {a, b}^{+} generated by G is
{wN_{a}(w) > 3N_{b}(w)}
 
{wN_{b}(w) > 3N_{a}(w)}  
{wN_{a}(w) = 3k, k ∈ {0, 1, 2, ...}}
 
{wN_{b}(w) = 3k, k ∈ {0, 1, 2, ...}} 
S→baA
S→babA
S→babaB
S→babaa
n(a)=3; n(b)=2
Option A:
N_{a}(w) > 3N_{b}(w)
3 > 3(2)
3 > 6 (✖️)
Option B:
N_{b}(w) > 3N_{b}(w)
2 > 3(2)
2 > 6 (✖️)
Option D:
N_{b}(w) = 3k
2 = 3k(✖️)
S = aA
S→aA
S→abA
S→abaB
S→abaa
n(a)=3
n(a)=3
→ Answer: Option C(✔️)
Question 89 
L_{1} is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w_{1}, w_{2}, w_{3}, ... Define another language L_{2} over Σ Union {#} as {w_{i} # w_{j} : w_{i}, w_{j} ∈ L_{1}, i < j}. Here # is a new symbol. Consider the following assertions.
S_{1}: L_{1} is recursive implies L_{2} is recursive S_{2}: L_{2} is recursive implies L_{1} is recursive
Which of the following statements is true?
Both S_{1} and S_{2} are true
 
S_{1} is true but S_{2} is not necessarily true  
S_{2} is true but S_{1} is not necessarily true  
Neither is necessarily true

L_{1} = recursively enumerable language
L_{2} over Σ∪{#} as {w_{i}#w_{j}  w_{i}, w_{j} ∈ L_{1}, i < j}
S_{1} is True.
If L_{1} is recursive then L_{2} is also recursive. Because, to check w = w_{i}#w_{j} belongs to L_{2}, and we give w_{i} and w_{j} to the corresponding decider L_{1}, if both are to be accepted, then w∈L_{1} and not otherwise.
S_{2} is also True:
With the corresponding decider L_{2} we need to make decide L_{1}.
Question 90 
Choose the best matching between the programming styles in Group 1 and their characteristics in Group 2.
Group1 Group2 P. Functional 1. Commandbased, procedural Q. Logic 2. Imperative, abstract data type R. Objectoriented 3. Sideeffect free, declarative, expression evaluation S. Imperative 4. Declarative, clausal representation, theorem proving
P  2, Q  3, R  4, S  1  
P  4, Q  3, R  2, S  1  
P  3, Q  4, R  1, S  2  
P  3, Q  4, R  2, S  1 
Q) Logic is also declarative but involves theorem proving.
R) Object oriented is imperative statement based and have abstract data types.
S) Imperative programs are made giving commands and follow definite procedure.