Pgtrbcomputerscience

Table of Contents
1. GATE Syllabus .. 3
2. Programming and Data Structures... 5
3. Design And Analysis Of Algorithms 57
4. Compiler Design . 69
5. Operating System 90
6. Databases ... 124
7. Software Engineering . 154
8. Computer Networks 160
9. Web technologies. 179
10. Computer Organization.. 185
11. Digital Logic . 237
2
GATE SYLLABUS
1. COMPUTER SCIENCE AND INFORMATION TECHNOLOGY CS & IT
Engineering Mathematics
Mathematical Logic: Propositional Logic; First Order Logic.
Probability: Conditional Probability; Mean, Median, Mode and Standard Deviation; Random
Variables; Distributions; uniform, normal, exponential, Poisson, Binomial.
Set Theory & Algebra: Sets; Relations; Functions; Groups; Partial Orders; Lattice; Boolean
Algebra.
Combinatorics: Permutations; Combinations; Counting; Summation; generating functions;

recurrence relations; asymptotics.
Graph Theory: Connectivity; spanning trees; Cut vertices & edges; covering; matching;
independent sets; Colouring; Planarity; Isomorphism.
Linear Algebra: Algebra of matrices, determinants, systems of linear equations, Eigen values
and Eigen vectors.
Numerical Methods: LU decomposition for systems of linear equations; numerical solutions

of non-linear algebraic equations by Secant, Bisection and Newton-Raphson Methods;
Numerical integration by trapezoidal and Simpson's rules.
Calculus: Limit, Continuity & differentiability, Mean value Theorems, Theorems of integral
calculus, evaluation of definite & improper integrals, Partial derivatives, Total derivatives,
maxima & minima.
GENERAL APTITUDE(GA):
Verbal Ability: English grammar, sentence completion, verbal analogies, word groups,
instructions, critical reasoning and verbal deduction.
Computer Science and Information Technology
Programming and Data Structures: Programming in C; Functions, Recursion, Parameter

passing, Scope, Binding; Abstract data types, Arrays, Stacks, Queues, Linked Lists, Trees,
Binary search trees, Binary heaps.
Algorithms: Analysis, Asymptotic notation, Notions of space and time complexity, Worst and
3
average case analysis; Design: Greedy approach, Dynamic programming, Divide-and-conquer;
Tree and graph traversals, Connected components, Spanning trees, Shortest paths; Hashing,
Sorting, Searching. Asymptotic analysis (best, worst, average cases) of time and space, upper
and lower bounds, Basic concepts of complexity classes P, NP, NP-hard, NP-complete.
Compiler Design: Lexical analysis, Parsing, Syntax directed translation, Runtime

environments, Intermediate and target code generation, Basics of code optimization.
Operating System: Processes, Threads, Inter-process communication, Concurrency,

Synchronization, Deadlock, CPU scheduling, Memory management and virtual memory, File
systems, I/O systems, Protection and security.
Databases: ER-model, Relational model (relational algebra, tuple calculus), Database design
(integrity constraints, normal forms), Query languages (SQL), File structures (sequential files,
indexing, B and B+ trees), Transactions and concurrency control.
Information Systems and Software Engineering: information gathering, requirement and

feasibility analysis, data flow diagrams, process specifications, input/output design, process life
cycle, planning and managing the project, design, coding, testing, implementation,
maintenance.
Computer Networks: ISO/OSI stack, LAN technologies (Ethernet, Token ring), Flow and
error control techniques, Routing algorithms, Congestion control, TCP/UDP and sockets,
IP(v4), Application layer protocols (icmp, dns, smtp, pop, ftp, http); Basic concepts of hubs,
switches, gateways, and routers. Network security basic concepts of public key and private key
cryptography, digital signature, firewalls.
Theory of Computation: Regular languages and finite automata, Context free languages and
Push-down automata, Recursively enumerable sets and Turing machines, Undecidability.
Digital Logic: Logic functions, Minimization, Design and synthesis of combinational and
sequential circuits; Number representation and computer arithmetic (fixed and floating point).
Computer Organization and Architecture: Machine instructions and addressing modes, ALU
and data-path, CPU control design, Memory interface, I/O interface (Interrupt and DMA mode),
Instruction pipelining, Cache and main memory, Secondary storage.
Web technologies: HTML, XML, basic concepts of client-server computing.
4
Programming and Data Structures
1. Which one of the following is the tightest upper bound that represents the time complexity
of inserting an object into a binary search tree of n nodes?
(A) O(1) (B) O(log n) (C) O(n) (D) O(n log n) (GATE 2013)
Answer: (C)
Explanation: For skewed binary search tree on n nodes, the tightest upper bound to insert a
node is O(n).
2. Which one of the following is the tightest upper bound that represents the number of
swaps required to sort n numbers using selection sort?
(A)O(log n) (B) O(n) (C) O(n log n) (D) O(n2) (GATE 2013)
Answer: (B)
Explanation: The maximum number of swaps that takes place in selection sort on n numbers is
n
3. Consider the following operation along with Enqueue and Dequeue operations on queues,
where k is global parameters
MultiDequeue(Q) {
m=k
while (Q is not empty) and (m >0) {
Dequeue(Q)
m=m-1
} }
What is the worst case time complexity of a sequence of n queue operations on an initially
empty queue?
(A) (n) (B) (n+k) (C) (nk) (D) (n2) (GATE 2013)
Answer: (C)
4. The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42.
Which one of the following is the postorder traversal sequence of the same tree?
(A) 10,20,15,23,25,35,42,39,30 (B) 15,10,25,23,20,42,35,39,30
(C) 15,20,10,23,25,42,35,39,30 (D) 15,10,23,25,20,35,42,39,30
5
Answer: (D)
Explanation:
Preorder : 30,20,10,15,25,23,39,35,42
Inorder :10,15,20,23,25,30,35,39,42
5. What is the return value of f p,pif the value of p is initialized to 5 before the call? Note that the first
parameter is passed by reference, whereas the second parameter is passed by value.
int f(int&x,int c)
{
c=c-1;
if (c==0) return 1;
x=x+1;
return f(x,c)*x;
}
(A) 3024 (B) 6561 (C) 55440 (D) 161051 (GATE 2013)
Answer: (B)
6
Explanation:
Common Data Questions 6 & 7:

The procedure given below is required to find and replace certain characters inside an input
character string supplied in array A. The characters to be replaced are supplied in array oldc,
while their respective replacement characters are supplied in array newc. Array A has a fixed
length of five characters, while arrays oldc and newc contain three characters each. However,
the procedure is flawed
voidfind_and_replace( char *A, char *oldc, char *newc)

{
for (inti=0;i<5;i++)
for (int j=0;j<3;j++)
if (A[i]==oldc[j])
A[i]=newc[j];
}
The procedure is tested with the following four test cases

7
(1) oldc= "abc ", newc= "dab" (2) oldc= " cde", newc= "bcd"
(3) oldc= "bca", newc= "cda" (4) oldc= "abc ", newc= "bac "
6. The tester now tests the program on all input strings of length five consisting of characters
a, b, c, d and e with duplicates allowed. If the tester carries out this testing with the four
test cases given above, how many test cases will be able to capture the flaw?
(A) Only one (B) Only two (C) Only three (D) All four (GATE 2013)
Answer: (B)
Explanation: Flaw in this given procedure is that one character of Array A can be replaced by
more than one character of newc array, which should not be so.Test case (3) and (4) identifies
this flaw as they are containing oldc and newc array characters arranged in specific manner.
Following string can reflect flaw, if tested by test case (3).
Likewise single character b in A is replaced by c and then by d. Same way test case (4) can
also catch the flaw.
7. If array A is made to hold the string abcde, which of the above four test cases will be
successful in exposing the flaw in this procedure?
(A) None (B) 2 only (C) 3 and 4 only (D) 4 only (GATE 2013)
Answer: (C)
Explanation: Now for string abcde in array A, both test case (3) and (4) will be successful in
finding the flaw, as explained in above question.
8. What will be output of the following program?
8
char inChar=A;
switch(inChar)
{
case A: print(Choice A\n);
case B:
case C: printf(Choice B);
case D:
case E:
default: printf(No Choice);
}
(A) No Choice
(B) Choice A
(C) Choice A
Choice B No Choice
(D) Program gives no output as it is erroneous (GATE 2012)
Answer: (C)
Explanation:-Since there is no break statement, the program executes all the subsequent
case statements after printing choice A.
9. Supposeacircularqueueofcapacity(n1)elementsisimplementedwithan
arrayofnelements.Assumethattheinsertionanddeletionoperationsarecarriedoutusi
ngREARandFRONTasarrayindexvariables,respectively.Initially,REAR=FRONT=0.Thecond
itionstodetectqueuefullandqueueemptyare
(A)full:(REAR+1)modn==FRONT (B)full:(REAR+1)mod n==FRONT
empty:REAR==FRONT empty:(FRONT+1)modn==REAR
(C)full:REAR==FRONT(D)full:(FRONT+1)mod n==REAR
empty:(REAR+1)modn==FRONTempty:REAR==FRONT
(GATE 2012)
Answer:(A)
Explanation:-
Thecounterexamplefortheconditionfull:REAR=FRONTis
InitiallywhentheQueueisemptyREAR=FRONT=0bywhichtheabovefullcondition
issatisfiedwhichisfalse
Thecounterexamplefortheconditionfull:(FRONT+1)modn=REARis
InitiallywhentheQueueisemptyREAR=FRONT=0andletn=3,soafterinsertingone
elementREAR=1andFRONT=0,atthispointtheconditionfullaboveissatisfied,buts
tillthereisplacefor onemoreelementinQueue,sothisconditionisalsofalse
Thecounterexamplefortheconditionempty:(REAR+1)modn=FRONTis
elementREAR=1andFRONT=0,atthispointtheconditionemptyaboveissatisfied,b
utthequeueofcapacityn-1isfullhere
9
Thecounterexamplefortheconditionempty:(FRONT+1)modn=REARis
elementREAR=1andFRONT=0,atthispointtheconditionemptyaboveissatisfied,b
utthequeueofcapacityn-1isfullhere
COMMON DATA QUESTIONS 10 & 11

Consider the following C program (2012)
int a, b, c = 0;
voidprtFun (void);
int main ()
{
staticint a = 1; /* line 1 */
prtFun();
a += 1;
prtFun();
printf ( "\n %d %d " , a, b) ;
}
voidprtFun (void)
{
staticint a = 2; /* line 2 */
int b = 1;
a += ++b;
printf (" \n %d %d " , a, b);
}
10.What output will be generated by the given code segment?
(A) 3 1 (B) 4 2 (c) 4 2 (D) 3 1
41 61 62 52
42 61 20 52
Answer (C)
Explanation:
a and b are global variable. prtFun() also has a and b as local variables. The local
variables hide the globals (See Scope rules in C). When prtFun() is called first time, the local b
becomes 2 and local a becomes 4.
When prtFun() is called second time, same instance of local static a is used and a new
instance of b is created because a is static and b is non-static. So b becomes 2 again and
a becomes 6.
main() also has its own local static variable named a that hides the global a in main. The
printf() statement in main() accesses the local a and prints its value. The same printf()
statement accesses the global b as there is no local variable named b in main. Also, the
defaut value of static and global int variables is 0. That is why the printf statement in main()
prints 0 as value of b.
10
11.What output will be generated by the given code d\segment if: (GATE 2012)
Line 1 is replaced by auto int a = 1;
Line 2 is replaced by register int a = 2;
(A) 3 1 (B) 4 2 (C) 4 2 (D) 4 2
41 61 62 42
42 61 20 20
Answer (D)
Explanation:
If we replace line 1 by auto int a = 1; and line 2 by register int a = 2;, then a
becomes non-static in prtFun(). The output of first prtFun() remains same. But, the output of
second prtFun() call is changed as a new instance of a is created in second call. So 4 2 is
printed again. Finally, the printf() in main will print 2 0. Making a a register variable wont
change anything in output.
12. What does the following fragment of C-program print? (GATE 2011)
char c[] = "GATE2011";
char *p =c;
printf("%s", p + p[3] - p[1]) ;
(A) GATE2011
(B) E2011
(C) 2011
(D) 011
Answer: (C)
Explanation:
See comments for explanation.
char c[] = "GATE2011";
// p now has the base address string "GATE2011"
char *p =c;
// p[3] is 'E' and p[1] is 'A'.

// p[3] - p[1] = ASCII value of 'E' - ASCII value of 'A' = 4
// So the expression p + p[3] - p[1] becomes p + 4 which is
// base address of string "2011"
printf("%s", p + p[3] - p[1]) ;
13. A max-heap is a heap where the value of each parent is greater than or equal to the value
of its children. Which of the following is a max-heap? (GATE 2011)
11
Answer: - (B)
Explanation: - Heap is a complete binary tree
COMMON DATA QUESTIONS 14 & 15
Consider the following recursive C function that takes two arguments (2011)
unsignedint foo(unsigned int n, unsigned int r) {
if (n > 0) return (n%r + foo (n/r, r ));
else return 0;
}
14. What is the return value of the function foo when it is called as foo(513, 2)?
(A) 9
(B) 8
(C) 5
(D) 2 (GATE 2011)
Answer: (D)
Explanation:
foo(513, 2) will return 1 + foo(256, 2). All subsequent recursive calls (including foo(256, 2)) will
return 0 + foo(n/2, 2) except the last call foo(1, 2) . The last call foo(1, 2) returns 1. So, the
value returned by foo(513, 2) is 1 + 0 + 0. + 0 + 1.
The function foo(n, 2) basically returns sum of bits (or count of set bits) in the number n.
12
15. What is the return value of the function foo when it is called as foo(345, 10) ?
(GATE 2011)
(A) 345
(B) 12
(C) 5
(D) 3
Answer: (B)
Explanation:
The call foo(345, 10) returns sum of decimal digits (because r is 10) in the number n. Sum of
digits for 345 is 3 + 4 + 5 = 12.
16. WhatisthevalueprintedbythefollowingCprogram? (GATE 2010)

#include<stdio.h>
intf(int*a,intn)
13
{
if(n<=0)return0;
elseif(*a% 2==0)return*a+ f(a+1,n-1);
elsereturn*a-f(a+1,n-1);
}
intmain()
{
inta[]={12,7,13,4,11,6};
printf("%d",f(a,6));
return0;
}
1)-9 2)5 3)15 4)19
Answer (C)
Explanation:
f() is a recursive function which adds f(a+1, n-1) to *a if *a is even. If *a is odd then f()
subtracts f(a+1, n-1) from *a. See below recursion tree for execution of f(a, 6).
.
f(add(12), 6) /*Since 12 is first element. a contains address of 12 */
|
|
12 + f(add(7), 5) /* Since 7 is the next element, a+1 contains address of 7 */
|
|
7 - f(add(13), 4)
|
|
13 - f(add(4), 3)
|
|
4 + f(add(11), 2)
|
|
11 - f(add(6), 1)
|
|
6+0
So, the final returned value is 12 + (7 (13 (4 + (11 (6 + 0))))) = 15
14
17. The following C function takes a singly-linked list as input argument. It modified the list by
moving the last element to the front of the list and returns the modified list. Some part of the
code is left blank. (GATE 2010)
typedefstruct node {
int value;
struct node *next
} Node;
Node *mode )_to_front(Node *head){
Node *p,*q;
if((head==NULL) ||(head->next==NULL))return head;
q=NULL;p=head;
while(p->next!=NULL)
{
q=p;
p=p->next;
}
----------------------------------------
return head;
}
Choose the correct alternative to replace the blank line.
1) q=NULL; p->next=head; head=p;
2) q->next=NULL; head=p; p->next=head;
3) head=p; p->next=q; q->next=NULL;
4) q->next=NULL; p->next=head; head=p;
Answer: (D)
Solution:
Here the program wants to make the last node of the list, the first node.
Here q is the second last node and p is the last node
The second last nodes next should be now NULL so
q->next=NULL.
15
p->next should below head node.
sop->next=head
Now the head node is p.
So head = p.
Hence (D) is correct option.
18. ThecyclomaticcomplexityofeachofthemodulesAandBshownbelowis10.Whatisthe
cyclomaticcomplexityofthesequentialintegrationshownontherighthandside?
(GATE 2010)
1)19 2)21 3)20 4)10

Answer: (1)
Explanation:
Cyclomatic complexity is defined as the no. of independent paths form begin to exit in a
module. If some dependent sub modules are there in the module then the individual
cyclomatic complexities are added & overall sum is reduced by 1.
Here CC(complete) = CC(A) + CC(B) 1
So 10+10-1=19
Hence (1) is correct option.
19. What does the following program print? (GATE 2010)
#include<stdio.h>
void f(int *p, int *q)
{
p = q;
*p = 2;}
inti = 0, j = 1;
int main()
{
f(&i, &j);
printf("%d %d \n", i, j);
getchar();
return 0;
}
(A) 2 2
(B) 2 1
(C) 0 1
(D) 0 2
Answer: (D)
16
Explanation:
See below f() with comments for explanation.
/* p points to i and q points to j */
void f(int *p, int *q)
{
p = q; /* p also points to j now */
*p = 2; /* Value of j is changed to 2 now */
}
20.The following program is to be tested for statement coverage : (GATE 2010)

begin
if(a==b){S1;exit}
else if(c==d){S2;}
else {S3;exit;}
S4;
end
The test cases T1, T2, T3, and T4 given below are expressed in terms of the properties satisfied
by the values of variables a_b_cand d. The exact values are not given.
T1: a,b,c and d are equal
T2: a,b,c and d are all distinct
T3: a=b and c!=d
T4: a!=b and c=d
Which of the test suites given below ensures coverage of statements S1, S2, S3 and S4?
A) T1, T2, T3
B) T2, T4
C) T3, T4
D) T1, T2, T4
Answer: (D)
Explanation:
The following test cases covers statements.
T1: all are equal
S1 executed and then so no other execution.
T2: all are distinct
Only S3 executed
T3: a=b & c!=d
Only S1 executed
T4: a!=b & c=d
Only S2,S4only
So to have all statements the option should be either T1,T2,T4or T2,T3,T4
Option (D) is T1,T2,T4
Statement for Linked Answer Questions 21 & 22 (GATE 2010)
17
A has table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear
probing. After inserting 6 values into an empty has table, the table is as shown below.
0
1
2 42
3 23
4 34
5 52
6 46
7 33
8
9
21. Which one oft he following choices gives a possible order in which the key values could
have been inserted in the table ?
(A) 46, 42, 34, 52, 23, 33 (B) 34, 42, 23, 52, 33, 46
(C) 46, 34, 42, 23, 52, 33 (D) 42, 46, 33, 23, 34, 52
Answer: (C)
Explanation:
Here for hashing Linear probing is used, i.e. it finds the hash key value through hash function
and maps the key on particular position In Hash table. In case of key has same hash address
then it will find the next address then it will find the next empty position in the Has Table.
Here we check all options:
(A) Here 42 will be inserted at the 2nd position in the array next 52, also has same hash
address 2. But it already occupied so it will search for the next free place which is 3rd position.
So here 52 is misplaced and it is not possible key values.
(B) Here 46 is misplaced so it is not possible value.
(C) This is same as given hash table.
So correct order is 46, 34, 42, 23, 52, 33
Hence (C) is correct option.
22. How many different insertion sequences of the key values using the same hash function
and linear probing will result in the hash table shown above ?
(A) 10 (B) 20 (C) 30 (D) 40
Answer: (C)
Explanation:
Here the given order of insertion is 46, 34, 42, 23, 52, 33
Here 42, 23, 34, 46 are inserted direct using hash function"
But to insert 52 we have 6 vacant places."
After insertion of 52 at any of the 6 places, we have 5 places"remaining for 33.
So total combination.
6 * 5 = 30 possible ways
18
23.Whatisthenumberofswapsrequiredtosortnelements usingselectionsort,intheworst case?
(GATE 2009)
A)(n) B)(nlogn)
C)(n2 ) D)(n2logn)
Answer: (C)
24. Consider the program below: (GATE 2009)
#include<stdio.h>
int fun(int n, int *f_p){
intt,f;
if (n<=1){
*f_p=1
return 1;
}
t=fun(n-1,f_p);
f=t+*f_p;
*f_p=t;
return f;
}
int main () {
int x=15;
printf(%d\n, fun(5,&x));
return 0;
}
The value printed is:
A) 6 B) 8 C) 14 D) 15
Answer: B
Explanation:
Here the table column I, II, & III are during the forward calls of the recursive function fun &The
part after arrow in column III is updated value during return calls & column IV & V are the
returned values.
19
In the end 8 is returned so only this will be printed
Hence (B) is correct option.
25. What is the maximum height of any AVL-tree with 7 nodes ? Assume that the height of a
tree with a single node is 0. (GATE 2009)
(A) 2 (B) 3
(C) 4 (D) 5
Answer: (B)
Explanation:
AVL tree is a partially balanced tree with the weights assigned to thenodes can be only 1,0 or
1. This weight is assigned on the basis of difference of the no. of children in the left subtree&
right subtree. If some other weight is there then we rotate the tree to balance it.
In this tree the height is 3 and it is Also AVL balanced so maximum height will be 3
Statement for Linked Answer Question 26 & 27 (GATE 2009)

Consider a binary max-heap implemented using an array
26.Which one of the follow9ng array represents a binary max-heap?
(A) {25, 12, 16, 13, 10, 8, 14}
(B) {25, 14, 13, 16, 10, 8, 12}
(C) {25, 14, 16, 13, 10, 8, 12}
(D) {25, 14, 12, 13, 10, 8, 16}
Answer: (C)
Explanation:
If the value presented at any node is greater then all its children then the tree is called the
max heap.
Here we need to draw heap for all options
20
27. What is the content of the array after two delete operations on the correct answer to the
previous question? (GATE 2009)
(A) {14, 13, 12, 10, 8} (B) {14, 12, 13, 8, 10}
(C) {14, 13, 8, 12, 10} (D) {14, 13, 12, 8, 10}
Answer: (D)
Explanation:
21
28. Which combination of the integer variables x,y, and z makes the variable a get the value 4
in the following expression? (GATE 2008)
a = (x >y)?((x>z)?x:z): ((y >z)?y:z)
(A) x= 3,y = 4,z = 2 (B) x = 6,y = 5,z = 3

(C) x= 6,y = 3,z = 5 (D) x = 5,y = 4,z = 5
Answer: (A)
Explanation:
a = (x >y)?((x>z)?x:z): ((y >z)?y:z)
Expr 1?expr 2 : expr 3 ;
Here Expr 1 is a comparison expression whose result may be true or false. If true returned the
expr 2 is selected as choice otherwise expr3.
Here we want 4 to be printed which is only in option (A) & (D) for y = 4 to be printed.
x >y should be false since y is in true part so this expr should be true.
So both the conditions are true in option (A) only so correct.
We can check.
x=3y=4z=2
a = (x >y)?((x >z)?x:z) ((y >z)?y:z)
First we can check 3 >2 ?3 : 2 thus 3 is selected
Then 4 >2 ?4 : 2 here 4 is selected
Hence a = 3 > 4?3:4 = 4
Hence (A) is correct option.
30. What is printed by the following C program? (GATE 2008)

int f(int x, int *py, int **ppz)
{
int y, z;
**ppz += 1;
z = **ppz;
22
*py += 2;
y = *py;
x += 3;
return x + y + z;
}
void main()
{
int c, *b, **a;
c = 4;
b = &c;
a = &b;
printf( "%d", f(c,b,a));
getchar();
}
(A) 18
(B) 19
(C) 21
(D) 22
Answer :(B)
Explanation:
/* Explanation for the answer */
/*below line changes value of c to 5. Note that x remains unaffected

by this change as x is a copy of c and address of x is different from c*/
**ppz += 1
/* z is changed to 5*/
z = **ppz;
/* changes c to 7, x is not changed */

*py += 2;
/* y is changed to 7*/
y = *py;
/* x is incremented by 3 */
x += 3;
/* return 7 + 7 + 5*/
return x + y + z;
23
31. Choose the correct option to fill ?1 and ?2 so that the program below prints an input string
in reverse order. Assume that the input string is terminated by a newline character.
(GATE 2008)
void reverse(void)
{
int c;
if (?1) reverse() ;
?2
}
main()
{
printf ("Enter Text ") ;
printf ("\n") ;
reverse();
printf ("\n") ;
}
(A) ?1 is (getchar() != \n)
?2 is getchar(c);
(B) ?1 is (c = getchar() ) != \n)
?2 is getchar(c);
(C) ?1 is (c != \n)
?2 is putchar(c);
(D) ?1 is ((c = getchar()) != \n)
?2 is putchar(c);
Answer: (D)
Explanation:
getchar() is used to get the input character from the user and putchar() to print the entered
character, but before printing reverse is called again and again until \n is entered. When \n
is entered the functions from the function stack run putchar() statements one by one.
Therefore, last entered character is printed first.
You can try running below program
void reverse(void); /* function prototype */
void reverse(void)
{
int c;
if (((c = getchar()) != '\n'))
reverse();
putchar(c);
}
main()
{
printf ("Enter Text ") ;
printf ("\n") ;
24
reverse();
printf ("\n") ;
getchar();
}
32. The following postfix expression with single digit operands in evaluated using a stack
823^/23*+ 51* . Note that ^ is the exponentiation operator. The top two elements of the stack
after the first* is evaluated are (GATE 2007)
(A) 6, 1 (B) 5, 7
(C) 3, 2 (D) 1, 5
Answer: (B)
Explanation:
Given postfix expression is 823^/23*+ 51*
Scanning the string from left to right we push all the digits,& we get any operator we evaluate
the operation between top 2 elements poped from stack. Then the result is pushed again into
stack.
Stack contain 5, 7
Hence (B) is correct option
33.Consider the following C-function in which a[n] and b[n] are two sorted integer arrays and
c[n+m] be another integer array. (GATE 2006)
void xyz (int a[],int b[],int c[]){
inti, j, k;
i=j=k=0;
while((i<n))&&(j<m)
if (a[i]<b[j])
c[k++]=a[i++];
25
else
c[k++]=b[j++];
}
Which of the following condition (s) hold (s) after the termination of
the while loop ?
I j<m, k=n+j-1, and a [n-1]<b[j] if i=n
II i<n, k=m+j-1, and b[m-1]<=a[i] if j=m
(A) only (I)
(B) only (II)
(C) either (I) or (II) but not both
(D) neither (I) nor (II)
Answer: (C)
Explanation:
While loop will terminate i>= n &j >= m program is to merge a &b arrays into C .
While loop terminates after merging then either (I) or (II) should hold but not both at the same
time.
(I) says j <m & (II) say j = m vice versa
34.Consider the C code to swap two integers and these five statements:
the code (GATE 2006)
void swap(int *px,int*py){
*px=*px*py;
*py=*px+*py;
*px=*py*px;
}
S1: will generate a compilation error
S2: may generate a segmentation fault at runtime depending on the arguments passed
S3: correctly implements the swap procedure for all input pointers referreing to integers
stored in memory locations accessible to the process
S4: implements the swap procedure correctly for some but not all valid input pointers
26
S5: may add or subtract integers and pointers
(A) S1 (B) S2 and S3
(C) S2 and S4 (D) S2 and S5
Answer: (C)
Explanation:
Here pointers are used without initialization also the address pointed by then may be out of
segment of program, so segmentation.
Fault may be there so. S2 correct.
Here no compiler error S1 false.
Correctly done swap procedure but not all valid import pointers so S4 also true.
S2 &S4 are correct.
Common Data Questions 35 & 36
(GATE 2006)
A 3-ary max heap os like a binary max heap, but instead of 2 children, nodes have 3
children, A 3-ary heap can be represented by an array as follows: The root is stored in the first
location, a [0], nodes in the next level, from left to right, is stored form a[1] to a[3]. The nodes
from the second level of the tree from left to right are stored from a[4]
location onward.
An item x can be inserted into a 3-ary heap containing n items by placing x in the location a [n]
and pushing it up the tree to satisfy the heap property.
35.Which one of the following is a valid sequence of elements in an array representing 2-ary
max heap ?
(A) 1, 3, 5, 6, 8, 9 (B) 9, 6, 3, 1, 8, 5
(C) 9, 3, 6, 8, 5, 1 (D) 9, 5, 6, 8, 3, 1
Answer: (D)
Explanation:
27
Here in option (A), (B) and (C), value present at node is not greater then all its children.
36.Suppose the elements 7, 2, 10, and 4 are inserted, in that order, into the valid 3-ary max
heap found in the above question, Q. 38. Which on of the following is the sequence of items in
the array representing the resultant heap ? (GATE 2006)
(A) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4
(B) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
(C) 10, 9, 4, 5, 7, 6, 8, 2, 1, 3
(D) 10, 8, 6, 9, 7, 2, 3, 4, 1, 5
Answer: (A)
Explanation:
Given heap is as follows
To add 7, 2, 10, 4 we add the node at the end of array
28
We keep if at right place in the heap tree.
Compare elements with its parent node. Since 10 > 6 and 7 >5, we interchange
Since 10 >9, we interchange and we get
n/2=10/2=5
3 is at right position
4 is at right position
37. What does the following C-statement declare? (GATE 2005)
Int (*f) (int*)
(A) A function that takes an integer pointer as argument and returns an integer
(B) A function that takes an integer pointer as argument and returns an integer pointer
(C) A pointer to a function that takes an integer pointer as argument an returns
(D) A function that takes an integer pointer as argument returns a function pointer
29
Answer: (C)
Explanation:
Given statement int (*f) (int*)
This is not the declaration of any function since the f has *(pointer symbol) before it. So f is a
pointer to a function also the argument type is int *& the return type is int.
So overall we can say that f is a pointer to a function that takes an integer pointer as argument
and returns an integer.
38.An Abstract Data type (ADT) is (GATE 2005)
(A) same as an abstract class
(B) a data type that cannot be instantiated
(C) a data type for which only the operations defined on it can be
used, but none else
(D) all of the above
Answer: (C)
Explanation:
Abstract Data type :- It is defined as a user defined data type, specified by keyword abstract
& defines the variables & functions, these operations can only use the variables of this data
type.
So option (C) which says that Abstract data type for which only operations defined on it can be
used is correct.
Eg.stack data type
Here operations defined are push & pop. So we can apply only these 2 operations on it.
39.A common property of logic programming languages and functional languages is
(A) both are procedural language (GATE 2005)
(B) both are based oncalculus
(C) both are declarative
(D) all of the above
Answer: (D)
30
Explanation:
-calculus" It provides the semantics for computation with functions so that properties of
functional computation can be studied.
Both the languages require declaration before use of any object.
Both are procedural
So option (D) is correct.
Both the languages are based on calculus, procedural & declarative
40.Which of the following are essential features of an object-oriented programming
languages? (GATE 2005)
1. Abstraction and encapsulation
2. Strictly-typedness
3. Type-safe property coupled with sub-type rule
4. Polymorphism in the presence of inheritance
(A) 1 and 2 only (B) 1 and 4 only
(C) 1, 2 and 4 only (D) 1, 3 and 4 only
Answer: (B)
Explanation:
Object oriented programming languages necessarily have features like Abstraction
Encapsulation, inheritance with polymorphism. but OOPL are also strongly-typed since there
are restrictions on how operations involving values having different data types can be
intermixed.
Eg.two integers can be divided but one integer & one string cant.
41.A program P reads in 500 integers in the range (0, 100) representing the scores of 500
students. It then prints the frequency of each score above 50. What be the best way for P to
store the frequencies? (GATE 2005)
(A) An array of 50 numbers
(B) An array of 100 numbers
(C) An array of 500 numbers
31
(D) A dynamically allocated array of 550 numbers
Answer: (A)
Explanation:
Here the no. readable are range 0 to 100 but the output of the program is interested in scores
above 50 so there are 50 values (51 to 100) in this range.
So only an array 50 integers required as we get any no. we increment the value stored at
index.
Array [x 50] by 1.
Hence (A ) is correct option.
42.Consider the following C-program (GATE 2005)
double foo (double); /* Line 1*/
int main(){
doubleda_db;
// input da
db _foo(da);
}
double foo(double a){
returna;
}
The above code complied without any error or warning. If Line 1 is deleted, the above code
will show
(A) no compile warning or error
(B) some complier-warning not leading to unitended results
(C) Some complier-warning due to type-mismatch eventually leading to unitended results
(D) Complier errors
Answer: (C)
Explanation:
Here if line 1 which is prototype declaration of the function foo, in C compilation process this
would give an compile warning , due to type-mismatch. Since then compiler wont know what
is the return type of foo.
So unintended results may occur.
43.Postorder traversal of a given binary search tree, T produces the following sequence of
keys10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29
Which one of the following sequences of keys can be the result of an inorder traversal of the
tree T? (GATE 2005)
32
(A) 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
(B) 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
(C) 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
(D) 95, 50, 60, 40, 27, 23, 22, 25, 10, 0, 15, 29
Answer: (A)
Explanation:
When we are given any no elements & even any order (preorder or post order) & we need to
calculate inorder, then inorder is simply sorted sequence of the elements.
Here 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
44.Assume that the operators +, -,# are left associative and ^ is right associative .The order of
precedence (from highest to lowest) is ^,#, +, -. The postfix expression corresponding to the
infix expression a + b#c - d ^ e ^ f is (GATE 2004)
(A) abc#+def ^^ (B) abc#+de^f^
(C) ab+c#de^f^ (D) +a#bc^^def

Answer: (A)
Explanation:
Given expression a + b)c d/e/f
parenthesizing the expression as per given rules.
= ((a + (b)c)) (d/(e/f)))
= ((a + (bc))) (d/(ef/)))
= ((abc)+) (def//))
= (abc)+def//)
So option (A) is correct
You can also solve using stack.
45.Consider the following C program (GATE 2004)

main ()
33
{ 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=mn;
else
n=nm;
}
printf(%d,n);
}
The program computers

(A) x'y, using repeated subtraction (B) x mod y using repeated subtraction
(C) the greatest common divisor of x and y (D) the least common multiple of x only
Answer: (A)
Explanation:
Here if m >n then m = m n
m <n then n = n m
Let take X = 24 Y = 9
Then m = 24 n = 9
iteration m n
1 24 9 = 15 9
2 15 9 = 6 9
3 6 96=3
4 63=3 3
Here m = n so n returned
Which is GCD (Greatest common divisor) of X &Y
46.What does the following algorithm approximate ? (Assume m>1, E> 0). (GATE 2004)
x=m;
y=1;
while (xy>E)
{ x=(x+y)/2;
y=m/x;
}
print (x);
34
(A) log m (B) m2
(C) m1/2 (D) m1/3
Answer: (C)
Explanation:
Here we take let x = 16
Loop will stop when x y = 0 or >0
Iteration X Y
1 (16+1)/2=8 16/8=2
2 (8+2)/2=5 16/5=3
3 (5+3)/2=4 16/4=4
Here X = Y
Then take X. which is 4.
(m)1/2 = 4 = (16)1/2
47.Choose the best matching between the programming styles in Group 1 and their
characteristics in Group 2. (GATE 2004)
Group-1 Group-2
P. Functional 1. Command-based, procedural
Q. Logic 2. Imperative, abstract data types
R. Object-oriented 3. Side-effect free, declarative,

expression evaluation
S. Imperative
4. Declarative, clausal
representation, theorem proving
35
(A) P-2, Q-3, R-4, S-1 (B) P-4, Q-3, R-2, S-1
(C) P-3, Q-4, R-1, S-2 (D) P-3, Q-4, R-2, S-1
Answer: (D)
Explanation:
p. Functional Programming is declarative in nature, involves expression evaluation, & side
effect free.
q Logic is also declarative but involves theorem proving.
r. Object oriented is imperative statement based & have abstract (general) data types.
s Imperative :- The programs are made giving commands & follows definite procedure &
sequence.
48)What is printed by the print statements in the program P1 assuming
call by reference parameter passing ? (2001)
Program P1( )
{
_ _ 1__
_ _ __
____1(*)_
_r___ x;
_r___ y;
}
func1(x,y,z)
{
y=y+4
z=x+y+z;
}
(A) 10, 3
(B) 31, 3
(C) 27, 7
(D) None of the above
36
SOLUTION
Since the function fun 1 doesnt return the values of x & y and x & y are not passed by
reference. So in program P1( ) would print x = 10 & y = 3. So 10, 3
49)Consider the following three functions. (2001)

[P1] int *g(void)
{
Int x=10;
return (& x);
}
[P2] int *g(void)
{
int *px;
*px=10;
return px;
}
[P3] int *g(void)
{
int *px
px=(int*)malloc (size of (int));
*px=10;
return px;
}
Which of the above three functions are likely to cause problems with
pointers ?
(A) Only P3
(B) Only P1 and P3
(C) Only P1 and P2
(D) P1, P2 and P3
SOLUTION
37
P1 : Here the function is returning address of the variable x (& x ) but the return type is pointer
to integer not address. So incorrect.
P2 : *px = 0 directly assigned a value but still px doesnt point to any memory location, so
memory initialization or allocation should be done before. So incorrect.
P3: Correction made in P2, memory pre allocated, So correct.
50)Consider the following program (2001)

Program P2
Var n:int:
procedure W (var x:int)
begin
X=X+1
Print x;
end
Procedure D
Begin
var n:int;
n=3;
W(n);
End
Begin \\begin P2
n=10;
D;
end
If the language has dynamic scooping and parameters are passed by reference, what will be
printed by the program ?
(A) 10
(B) 11
(C) 3
38
SOLUTION
n = 10 given but not passed to D. In D, n = 3 & W(n) increments by
1. So n = n + 1 = 4.
51)The results returned by function under value-result and reference parameter passing
conventions. (2002)
(A) Do not differ
(B) Differ in the presence of loops
(C) Differ in all cases
(D) May differ in the presence of exception
SOLUTION
The results returned by function under value & reference parameter passing may differ in
presence of loops.
52)Consider the following declaration of a two-dimensional array in C. (2002)

Char a[100][100]
Assuming that the main memory is byte-addressable and that array is stored starting form
memory address 0, the address of a [40] [50] is
(A) 4040 (B) 4050
(C) 5040 (D) 5050
SOLUTION
Char a[100] [100]
1 char require 1 byte
Total required 10000 bytes.
Memory format is byte addressable
A[0] a[0][50] a[0][99]
. .
. .
. .
A[50][0] a[40][50]
.
39
.
.
A[99][0] a[99][99]
100 bytes per row. I.e 40#100 = 4000
1 byte per column I. e. 50#1 = 50
Total 4050
53) Consider the following C function.(2003)

fl oat f(fl oat x, int y){
fl oat p, s; int i;
for (s=1, p=1, i=1, i<y; i++)
{
p)=x/i;
s+=p;
}
return s;
}
For large values of y, the return value of the function f best approximates
(A) xy
(B) ex
(C) In(1 + x)
(D) xx
SOLUTION
The function is rewritten as
s = _;p = _;
for _i = _;i _ y;i ++_
{ p = p)x/i;
s = s + p;
}
Here initial value of s increments every time with a factor of p)x/i
Initially s = _ _ p = _
40
1x1+x
4 x3/3! x/4 x4/4! # = 1 + x + x2/2! + x3/3! + x4/4!
Loop P S
counter (i)
1 x 1+x
2 x)x/2 : 1 = x2/2 : 1 1 + x + x2/2
3 x2/2)x/3 = x3/3 : 2 : 1 1 + x + x2/2! + x3/3!
4 x3/3! x/4 x4/4! 1 + x + x2/2! + x3/3! + x4/4!
Thus it can be checked for every value.

Here the assumption is that the value of y is very large so y " 3
So the series 1 + x + x2/2! + x3/3!................3 will have infinite terms & from our previous
knowledge we know that this 3 series is expansion of ex (exponential series) so. 1 + x + x2/2! +
x3/3!...........3 = ex
54)Assume the following C variable declaration (2003)

int)A[10], B[10][10];
Of the following expressions
(1) A[2]
(2) A[2][3]
(3) B[1]
41
(4) B[2][3]
Which will not give compile-time errors if used as left hand sides of assignment statements in a
C program ?
(A) 1, 2, and 4, only (B) 2, 3, and 4, only
(C) 2 and 4 only (D) 4 only
SOLUTION
We have int )* which is an array of 10 integer value pointer whereas B[10] [10] is an array
which stores 10#10 = 100 integers So let us try to solve it eliminating way.
" Option 3 B[1] cant be at the left side since it is 2D array so cant use single index. We need
not necessarily specify the size of first dimension for B[][3]
" Option 4 B[2][3] is assignment to the array B value so possible.
" Option 1 A [2] is also possible to assign some address os integer value
" Option 2 this is some what tricky. Here A[2][3] becomes a 2D array if integer where A [2]
means the 2nd integer in this array and A[2][3]o means 3rd integer in this row. eg. A[2] [3] = 5
means that at second row the third integer value is 5. Hence (*) Is correct option.
55)Let T(n) be the number of different binary search trees on n distinct elements. (2003) Then
T[n] T(k 1)T(x)
k1
n
=
=/
, where x is
(A) n k + 1
(B) n k
(C) n k 1
(D) n k 2
SOLUTION
42
Binary search tree has a root node & its 2 subtrees. So for every node other than the leaves, all
the elements smaller than the node are its left subtree & all the nodes which have value equal to
or greater than that node are at right subtree. Here the given expression.
T(n) T(k 1)T(X)
K
n
1
=
=/
Figure
n(B) = no. of nodes in left subtree
n(C) " no. of nodes in right subtree
T(n) = n(B) + n(C) + 1
T(n) T(X)T(k 1)
K
n
1
=
=/
Expanding forT (k 1) we get
T(n) T(X) [T(0) T(1) T(2) .....T(n 1)]
K
n
1
=:++
= 144444444424444444443
/
no. of nodes in left subtree denoted by K
Total nodes = n
So remaining node n (k 1) i.e nodes in the right subtree.
So = n k + 1
So overall we can say that the no. of different BSTs on n different
43
elements.
T(n) T(n k 1)T(k 1)
n
k
1
= +
=/
Hence ( ) is correct option.
56) A data structure is required for storing a set of integers such that each of the following
operations can be done is (logn) time, where n is the number of elements in the set. (2003)
1. Delection of the smallest element.
2. Insertion of an element if it is not already present in the set.
Which of the following data structures can be used for this purpose ?
(A) A heap can be used but not a balanced binary search tree
(B) A balanced binary search tree can be used but not a heap
(C) Both balanced binary search tree and heap can be used
(D) Neither balanced binary search tree nor heap can be used
SOLUTION
Both the tasks can be performed by both the data structures but heap is a data structure where to
perform these function every element has to be checked so O(n) complexity. But the balance
binary search tree is efficient data structure since at every decision it selects one of its subtree to
no. of elements to be checked are reduced by a factor of 1/2 every time.
n/2! = x
x = logn
57) Let S be a stack of size n $ 1. Starting with the empty stack, suppose we push the first n
natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop
operation take X seconds each , and Y seconds elapse between the end of the one such stack
operation and the start of the next operation. For m $ 1, define the stack-life of mcs the time
44
elapsed from the end or Push (m) to the start of the pop operation that removes m from S . The
average stack-life of an element of this stack is (2003)
(A) n(X + Y)
(B) 3Y + 2X
(C) n(X + Y) X
(D) Y + 2X
SOLUTION
Here each of PURSH & POP operation take X seconds & Y seconds are elapsed between two
consecutive stack operations. m is the life time of element in stack. So m X is time for push.
m X is time for pop.
m Y is time for intermediate
So total m(2X + Y)
Average stack life ( )
m
= m 2X + Y
= 2X + Y
= Y + 2X
58) Consider the C program shown below.

#include <stdio.h>
#defi ne print(x)printf(%d,x)
int x;
void Q (int z){
z+=x; print(z);
}
void p (int)y){
int x=)y+2;
Page 13
www.gatehelp.com CS Topicwise 2001-2010
Programming & Data
45
Structure
Q(x);)y=x-1;
print(x);
}
main (void){
x=5;
p(&x);
print(x);
}
The output of this program is
(A) 12 7 6 (B) 22 12 11
(C) 14 6 6 (D) 7 6 6
SOLUTION
Figure
Here X is the global variable so still 5. Figure Here this is global X whose xy has been changed
to 6 so 6 is printed 12 66
First x=5 Then by function p(&x)
X =5+2=7 Then by function Q(x)
z =z+x
=7+5=12
Here x is global variable so still it is 5. Return to function p(&x)
Y =7-1=6
print x =7
return to main
Print x =6
Here this is global x whose *y ahs been changed to 6 so 6 is printed.
59) Consider the function - defined below.(2003)
struct item {
int data;
struct item)next;
};
46
int f (struct item )p){
return ((p==NULL)||(p>next==NULL)||
((p>data<=p>next>data)&&
f(p>next)));
}
For a given linked list p, the function f return 1 if and only if
(A) the list is empty or has exactly one element
(B) the elements in the list are sorted in non-decreasing order of data value
(C) the elements in the list are sorted in non-increasing order of data value
(D) not all elements in the list have the same data value
SOLUTION
Here the return 1 any 1 of the following should be correct.
(A) P == NULL i.e the list is empty (ends)
(B) P " next = NULL i.e have one element.
(C) P " data <= p " next " data i.e the element is smaller than its next element also. This is true
for whole list. Since &&f(p "next) is also there. So overall it gives that the elements should be
in sorted order.
60) The goal of structured programming is to (2004)

(A) have well indented programs
(B) be able to infer the flow of control from the compiled code
(C) be able to infer the flow of control form the program text
(D) avoid the use of GOTO statements
SOLUTION
Structured programming :- It is way of programming using the sub structure method, i.e
splitting the programs into sub sections. Structured programming prevents confusing transfer of
control of avoiding the use of GOTO statements.
61) Consider the following C function (2004)

void swap (int a, int b)
{int temp;
47
temp =a;
a =b;
b =temp;
}
In the order to exchange the values of two variables x and y .
(A) call swap (x,y)
(B) call swap (&x,&y)
(C) swap (x,y) cannot be used as it does not return any value
(D) swap (x,y) cannot be used as the parameters are passed by value
SOLUTION
Here the function takes the arguments by value.
" Option (A) sends parameter by value but only the local variable
a & b will be exchanged but not the actual variables x & y so
incorrect.
" Option (B) is incorrect sending address of x & y .
" Option (C) swap (x,y) is usable there is no need to return.
" Option (D) is the opposite statement of option (A), it says that the values are passed by value
so wont swap so the option is correct.
62) A single array A [1........MAXSIZE] is used to implement two stacks. The two stacks grow
from opposite ends of the array. Variables top 1 and top 2 (top 1<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
(A) (top 1=MAXSIZE/2) and (top 2=MAXSIZE/.2+1)
(B) top 1+top2=MAXSIZE
(C) (top 1=MAXSIZE/2) or (top2=MAXSIZE)
(D) top 1=top 21
SOLUTION
Let take maxsize =10
1 2 3 4 5 6 7 8 9 10
48
Here the stack will be fuel if both top 1 & top 2 are at the adjacent index values i.e. their
difference is 1.
So top 1 = top 2 1
Here (D) is correct option.
63) The best data structure to check whether an arithmetic expression

has balanced parenthesis is a
(A) queue
(B) stack
(C) tree
(D) list
SOLUTION
Balanced parenthesis in an equation are such that the no. of opening and closing parenthesis and
in correct order should be there. We can check balancing using stack. When we get any opening
parenthesis then we push that in the stack & if we get a closing one then we pop the stack. After
the complete scanning of input string if
stack is found empty then the arithmetic expression is balanced.
63) 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
(A) 5 (B) 6
(C) 7
49
(D) 8
SOLUTION
Here i is an static variable, so if it is once initialized it cant be initialized again during its scope
n is incremented by 1 & f(n) is called then. The final return is when n>=5 i.e. n returned then
Step Call n i
(1) 1 1 1 condition false n < 5
(2) 1+1=2 2
(3) 2 2 2 false n < 5
(4) 2+2=4 3
(5) 3 4 3 false n < 5
(6) 4+3=7 4
(7) 4 7 4 true return n = 7
So return value is 7.
64) Consider the following program fragment for reversing the digits in a given integer to
obtain a new integer. Let ....... n d d d. = 1 2 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
(A) n = d1d2......dmi and rev = dmdm1......dmi+1
(B) n = dmi+1.....dm1dm or rev = dmi .....d2d1
(C) n =Y rev
(D) n = d1d2....dm or rev = dm......d2d1
SOLUTION
Here after every iteration one digit is reduced from n since n = n/10 so unit place is removed.
50
This unit place is then added into the previous reverse sum (rev) after multiplying rev by 10. So
1 digit is incremented every iteration.
So at the ith iteration n should have m i digits d1d2.....dmi & rev
have dmdm1..........dmi+1
i n rev
1 d1d2....dm1 dm
2 d1d2......dm2 dmdm1
So on.
65)Consider the following C program segment. (2003)

char p[20];
char)s= string;
int length=strlen(s);
for (i=0;i<length; i++)
p[i]=s[length_i];
printf(% s, p);
The output of the program is
(A) gnirts (B) string
(C) gnirt (D) no output is printed
SOLUTION
In line 8 p[i]=S[length-i];
Here p is a character pointer variable so we cant assign the value of a pointer variable into
character variable so no output is printed. The block of code shown here is actually outputs the
reversal of string given in S. Which is a char type pointer. But the mistake during the loop
execution is done. The statement is accessing the
s[length - i] & loop starts from 0 When i = 0, s[length - 0] & s[length]. So this value for string
is always P will start with null pointer. So the string p will start with null pointers and nothing
will be printed.
51
66) 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 ? (2003)
(A) rear node
(B) front node
(C) not possible with a single pointer
(D) node next to front
SOLUTION:
Here due to circular connection the rear & front are connected. Here if we point P to rear the P
"next point to front node & P " data will point to rear value while inserting at rear following
sequence of operations done.
These operation done is 0(1) time So constant complexity.
67) Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that

order into an initially empty binary search tree. The binary search
tree uses the usual ordering on natural numbers. What is the inorder
transversal sequence of the resultant tree ?(2003)
(A) 7 5 1 0 3 2 4 6 8 9
(B) 0 2 4 3 1 6 5 9 8 7
(C) 0 1 2 3 4 5 6 7 8 9
(D) 9 8 6 4 2 3 0 1 5 7
SOLUTION
We can solve it in shortcut that the first given element in 7, so we need to choose that particular
option in which 7 is at the right place i.e. all the elements on its left should be smaller than it &
all the elements on the right should be equal & greater than it. So this rule is followed in option
C only. The method to make BST for given inputs is 7, 5, 1, 8, 3, 6, 0, 9, 4, 2.
52
To make in order of a binary search tree.
(i) Start with the root node.
(ii) Scan its left subtree,
(iii) If the node in subtree has any left child then store the node in stack & repeat this step for its
left child unit no. left child of any node.
(iv) If leaf reached then print the node & pop the stack, print the poped value.
(v) Check its right subtree & repeat step (III) for it.
(vi) When stack empty then stop
53
So here inorder is 0 1 2 3 4 5 6 7 8 9. Actually a fact can be remembered that inorder traversal
of a BST leads to a sorted sequence of elements.
Hence (C) is correct option
67) Consider the following 2-3-4 tree (i.e., B-tree with a minimum degree of two in which each
data item is a letter. The usual alphabetical ordering of letters is used in constructing the
tree.(2003)
What is the result of inserting G in the below tree ?

SOLUTION
54
2-3-4 B-tree means the min degree of a node is two & it can be max 4 So maximum of 3
elements can be there in a node.
Here in this node the no. of element >3. So we need a split or rotation. Since the adjacent child
has no. of element n 2 2 # = 4 = 2 so we apply a right rotation. So here.
68) 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 (tree height is the maximum
distance of a leaf node from the root) (2003)
(A) 2
(B) 3
(C) 4
(D) 6
SOLUTION
55
Given are 10, 1, 3, 5, 15, 12, 16
The height of the leaf node (5) is high 3. Hence (B) is correct option.
56
DESIGN AND ANALYSIS OF ALGORITHMS
1.Consider a linked list of n elements. What is the time taken to insert an element after an element
pointed by some pointer?
A. O (1) B. O (n) C. O (log2 n) D .O (n log2 n)
Answer A
2.An algorithm is made up of two independent time complexities f (n) and g (n). Then the
complexities of the algorithm is in the order of
A. f(n) x g(n) B. Max ( f(n),g(n)) C. Min (f(n),g(n)) D. f(n) + g(n)
Answer B
3.Two main measures for the efficiency of an algorithm are
A. Processor and memory B. Complexity and capacity C. Time and space D. Data and space
Answer C
4.The total number of comparisons in a bubble sort is
A. 0(log n) B. 0(n log n) C. 0(n) D. None of the above
Answer B
5.Time complexities of three algorithms are given. Which should execute the slowest for large
values of N?
A. ( 1 2 ) O N B. O(N) C. O(log N) D. None of these
Answer B
6.The upper bound of computing time of m coloring decision problem is
A. O(nm) B .O(nm) C. O(nmn) D. O(nmmn)
Answer C
7.The space factor when determining the efficiency of algorithm is measured by
A. Counting the maximum memory needed by the algorithm
B. Counting the minimum memory needed by the algorithm
C. Counting the average memory needed by the algorithm
D. Counting the maximum disk space needed by the algorithm
57
Answer A
8.If the address of A[1][1] and A[2][1] are 1000 and 1010 respectively and each element occupies 2
bytes then the array has been stored in _________ order.
A. row major B. column major C. matix major D. none of these
Answer A
9.The time factor when determining the efficiency of algorithm is measured by
A. Counting microseconds
B. Counting the number of key operations
C. Counting the number of statements
D. Counting the kilobytes of algorithm
Answer B
10.The Worst case occur in linear search algorithm when
A. Item is somewhere in the middle of the array
B. Item is not in the array at all
C. Item is the last element in the array
D. Item is the last element in the array or is not there at all
Answer D
11.A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort
algorithm. The worst case running time of this computation is
A. O (n log n) B. O (n2 log n) C. O (n2 + log n) D. O (n2)
Answer A
12.Which of the following case does not exist in complexity theory
A. Best case B. Worst case C. Average case D. Null case
Answer D
13.The minimum number of multiplications and additions required to evaluate the polynomial P =
4x3+3x2-15x+45 is
A. 6 & 3 B. 4 & 2 C. 3 & 3 D. 8 & 3
Answer C
58
14.The concept of order Big O is important because
A. It can be used to decide the best algorithm that solves a given problem
B. It determines the maximum size of a problem that can be solved in a given given amount of time
C. It is the lower bound of the growth rate of algorithm
D. Both A and B
Answer A
15.The worst case running time to search for an element in a balanced binary search tree with n2n
elements is
A. T(nlogn) B. T(n2n) C. T(n) D. T(logn)
Answer C
16.Which of the following sorting algorithm is of divide-and-conquer type?
A. Bubble sort B. Insertion sort C. Quick sort D. All of above
Answer C
17.The quick sort algorithm exploit _________ design technique
A. Greedy B. Dynamic programming C. Divide and Conquer D. Backtracking
Answer C
18.The number of distinct simple graphs with up to three nodes are
A. 15 B. 10 C. 7 D. 9
Answer C
19.The number of unused pointers in a complete binary tree of depth 5 is
A. 4 B. 8 C. 16 D. 32
Answer C
20.A given connected graph G is a Euler graph , if and only if all vertices of G are of
A. Same degree B .Even degree C .Odd degree D. Different degree
Answer B
21.What is the maximum number of nodes in a B-tree of order 10 of depth 3 (root at depth 0) ?
A. 111 B.999 C. 9999 D. None of the above
59
Answer D
22.One can convert a binary tree into its mirror image by traversing it in
A. Inorder B. Preorder C. Postorder D. Any order
Answer C
23.Graphs are represented using
A. Adjacency tree B. Adjacency linked list C. Adjacency graph D. Adjacency queue
Answer B
24.The data structure required for breadth first traversal on a graph is
A. Queue B. Stack C. Array D. Tree
Answer A
25.Number of edges of a complete binary tree with 16 leaf nodes are
A. 14 B. 30 C. 32 D. 28
Answer B
26.Tree
A. Is a bipartite graph
B. With n node contains n-1 edges
C. Is a connected graph
D. All of these
Answer D
27.If every node u in G is adjacent to every other node v in G, A graph is said to be
A. Isolated B. Complete C. Finite D. Strongly Connected
Answer B
28.Consider the following pseudo-code :

If (A > B) and (C > D) then
A=A+1
B=B+1
Endif
The cyclomatic complexity of the pseudo-code is
A. 2 B. 3 C. 4 D. 5
Answer D
29.Leaves of which of the following trees are at the same level ?

60
A. Binary tree B. B-tree C. AVL-tree D. Expression tree
Answer B
30.The Inorder traversal of the tree will yield a sorted listing of elements of tree in
A. Binary tree B. Binary search tree C. Heaps D. None of the above
Answer B
31.One can make an exact replica of a Binary Search Tree by traversing it in
Answer B
32.Let A be an adjacency matrix of a graph G. The th ij entry in the matrix K A , gives
A. The number of paths of length K from vertex Vi to vertex Vj.
B. Shortest path of K edges from vertex Vi to vertex Vj.
C. Length of a Eulerian path from vertex Vi to vertex Vj.
D. Length of a Hamiltonian cycle from vertex Vi to vertex Vj.
Answer B
33. A graph in which all nodes are of equal degree is called
A. Multi graph B. Non regular graph C. Regular graph D. Complete graph
Answer C
34. The time complexity to build a heap of n elements is
A. 0(1) B. 0(lgn) C. 0(n) D. 0(nlgn)
Answer D
35. Given a binary tree whose inorder and preorder traversal are given by
Inorder : EICFBGDJHK
Preorder : BCEIFDGHJK
The post order traversal of the above binary tree is
A. IEFCGJKHDB B. IEFCJGKHDB C. IEFCGKJHDB D. IEFCGJKDBH
Answer A
36. The running time of the following sorting algorithm depends on whether the partitioning is
balanced or unbalanced
61
A. Insertion sort B. Selection sort C. Quick sort D. Merge sort
Answer C
37. In worst case Quick Sort has order
A. O (n log n) B. O (n2/2) C. O (log n) D. O (n2/4)
Answer B
38. The sorting technique where array to be sorted is partitioned again and again in such a way
that all elements less than or equal to partitioning element appear before it and those which are
greater appear after it, is called
A. Merge sort B. Quick sort C. Selection sort D. None of these
Answer B
39. The best average behaviour is shown by
A. Quick Sort B. Merge Sort C. Insertion Sort D. Heap Sort
Answer A
40. Quick sort is also known as
A. Merge sort B. Heap sort C. Bubble sort D. None of these
Answer D
41. Assuming P ? NP, which of the following is TRUE?
A. NP-complete = NP B. NP-completenP=theta C. NP-hard = NP D. P = NP-complete
Answer B
42. If there is an NP complete language L whose complement is in NP ,then complement of any

language in NP is in
A. P B. NP C. Both A and B D. None of these
Answer B
43. Both P and NP are closed under the operation of
A. Union B. Intersection C. Concatenation D. Kleene
Answer D
44. If every node u in G is adjacent to every other node v in G, A graph is said to be
A. Isolated
62
B. Complete
C. Finite
D. Strongly Connected
Answer:B
45. Which of the following sorting algorithms has the lowest worst case complexity?
A. Merge sort
B. Bubble sort
C. Quick sort
D. Selection sort
46. Randomized quicksort is an extension of quicksort where the pivot is
chosen randomly. What is the worst case complexity of sorting n
numbers using randomized quicksort?
(a) O(n) (b) O(n log n) (c) O(n2) (d) O(n!)
47. Level of any node of a tree is
A. Height of its left subtree minus height of its right subtree

B. Height of its right subtree minus height of its left subtree
C. Its distance from the root
D. None of these
48. The total number of comparisons in a bubble sort is
A. 0(log n)
B. 0(n log n)
C. 0(n)
D. None of the above
49. Time complexities of three algorithms are given. Which should execute the slowest for
large values of N?
A. ( 1 2 ) O N
B. O(N)
C. O(log N)
D. None of these
50. The quick sort algorithm exploit _________ design technique
63
A. Greedy
B. Dynamic programming
C. Divide and Conquer
D. Backtracking
51. A sort which relatively passes through a list to exchange the first element with any
element less than it and then repeats with a new first element is called
A. Insertion sort B. Selection sort

C. Heap sort Quick sort
52. The pre order and post order traversal of a Binary Tree generates the same output.
The tree can have maximum
A. Three nodes
B. Two nodes
C. One node
D. Any number of nodes
53. A search technique where we keep expanding nodes with least accumulated cost so far
is called
A. Hill climbing
B. Branch and bound
C. Best first
D. Divide and conquer
54. The spanning tree of connected graph with 10 vertices contains
A. 9 edges B. 11 edges C. 10 edges D.10 vertices
55. The post order traversal of a binary tree is DEBFCA. Find out the preorder
traversal.
A. ABFCDE
B. ADBFEC
C. ABDECF
D. ABDCEF
56. Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected graph is in
P.
(2) The problem of determining whether there exists a cycle in an undirected graph is in
NP.
64
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time
algorithm to solve A.
A. 1,2 and 3 B. 1 and 2 only C. 2 and 3 only D. 1 and 3 only
57. A binary tree can easily be converted into q 2-tree
A. by replacing each empty sub tree by a new internal node

B. by inserting an internal nodes for non-empty node
C. by inserting an external nodes for non-empty node
D. by replacing each empty sub tree by a new external node
58. Which of the following sorting procedures is the slowest?
A. Quick sort
B. Heap sort
C. Shell sort
D. Bubble sort
59. The pre-order and post order traversal of a Binary Tree generates the same output.
The tree can have maximum
A. Three nodes
B. Two nodes
C. One node
D. Any number of nodes
60.
A. A B. B C. C D. D
61. Two isomorphic graphs must have
A. Equal number of vertices

B. Same number of edges
C. Same number of vertices
D. All of the above
62. If each node in a tree has value greater than every value in its left subtree and has
value less than every in the its right subtree ,the tree is called
65
A. Complete tree B.Full binary tree
C. Binary search tree D. Threaded tree
63. A simple graph in which there exists an edge between pair of vertices is called
A. Regular graph B. Planner graph
C.Euler graph D. Complete graph
64. The best average behaviour is shown by
A. Quick sort B. Merge sort
C.Insertion sort D. Heap sort
65. Which of the following sorting algorithm is of divide-and-conquer type?
A. Bubble sort
B. Insertion sort
C. Quick sort
D. All of above
66. The recurrence relation capturing the optimal execution time of the Towers of Hanoi
problem with n discs is
A. T(n) = 2T(n - 2) + 2
B. T(n) = 2T(n - 1) + n
C. T(n) = 2T(n/2) + 1
D. T(n) = 2T(n - 1) + 1
67.
A. A B. B C. C D. D
68. The goal of hashing is to produce a search that takes
A. O(1) time
B. O(n2 ) time
C. O(log n ) time
D. O(n log n ) time
69. One can make an exact replica of a Binary Search Tree by traversing it in
66
70. When converting binary tree into extended binary tree, all the original nodes in binary
tree are
A. internal nodes on extended tree

B. external nodes on extended tree
C. vanished on extended tree
D. None of above
71. The postfix form of A*B+C/D is
A. *AB/CD+ B. AB*CD/+
C. A*BC+/D D. ABCD+/*
72. For the bubble sort algorithm, what is the time complexity of the best/worst case?
(assume that the computation stops as soon as no more swaps in one pass)
(a) best case: O(n) worst case: O(n*n)

(b) best case: O(n) worst case: O(n*log(n))
(c) best case: O(n*log(n)) worst case: O(n*log(n))
(d) best case: O(n*log(n)) worst case: O(n*n)
Answer : A
73. For the quick sort algorithm, what is the time complexity of the best/worst case?
(a) best case: O(n) worst case: O(n*n)

(b) best case: O(n) worst case: O(n*log(n))
(c) best case: O(n*log(n)) worst case: O(n*log(n))
(d) best case: O(n*log(n)) worst case: O(n*n)
Answer : D
74. In
an arbitrary tree ( not a search tree) of order M. Its size is N, and its height is K.
The computation time needed to find a data item on T is
(a) O(K*K)
(b) O(M*M)
(c) O(N)
(d) O(K)
Answer : C
67
75. When we organize our data as an ordered list, what is the time complexity of
inserting/deleting a data item to/from the list?
(a) O(length_of_list*length_of_list)
(b) O(length_of_list)
(c) O(log(length_of_list * length_of_list))
(d) O(1)
Answer : B
76. Five statements about B-trees are below. Four of them are correct. Which one is
INCORRECT?
(a) All B-trees are also search trees

(b) The word B-tree stands for balanced tree
(c) The word B-tree also stands for binary tree
(d) All leaves of a B-tree must be on the same level
Answer : C
77. For any B-tree of height H (H>1), after inserting a new key, is it possible for a key, K,
which was located in a leaf-node to move up to the root in this regard which of the
following is correct?
(a) Cant be defined without data

(b) Never
(c) Yes, only if H=2
(d) Yes
Answer : D
78. When we say the order of a tree is M, we mean
(a) Every non-leaf node must have M subtrees

(b) Every non-leaf node must have M keys
(c) Every non-leaf node can have at most M subtrees
(d) Every non-leaf node can have at most M keys
Answer : C
79. T
is a search tree of order M, its size is N, and its height is K. The computation time
needed to INSERT/DELETE a data item on T is
(a) O( 1 )
(b) O( M )
(c) O( Log K )
(d) O( K )
Answer : D
68
80. Suppose that we have a data file containing records of famous people, and we need to
build a hash table to find a record from the person's birthday. The size of the hash table is
4096. The following are hash functions which convert a birthday to an integer. Which of
the following function is the best?
(a) h1( day/month/year ) = day + month + year

(b) h2( day/month/year ) = day + month*31 + year
(c) h3( day/month/year ) = (day + month*31 + year*365) mod 4096
(d) h4( day/month/year ) = (day + month*31 + year*365) mod 4093
Answer : D
COMPILER DESIGN
1.Which of the following statements is false ?

(A) An unambiguous grammar has same left most and right most derivation
(B) An LL(1) parser is a top-down parser
(C) LALR is more powerful than SLR
(D) An ambiguous grammar can never be LR (K) for any k
SOLUTION
So (A) & (C) are, true.
An ambiguous grammar cant be LR (K)
So option (A) is false since an unambiguous grammar has unique right most
derivation & left most derivations but both are not same. Hence (A) is correct
option
2. Dynamic linking can cause security concerns because
(A) Security is dynamic
(B) The path for searching dynamic libraries is not known till run time.
(C) Linking is insecure
(D) Cryptographic procedures are not available for dynamic linking
SOLUTION
Dynamic linking is type of linking in which libraries required by the program are linked during
run time. But at this time cryptographic procedures are not available, so make this process
insecure.
3. Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?

(A) Removing left recursion alone
69
(B) Factoring the grammar alone
(C) Removing left recursion and factoring the grammar
(D) None of this
SOLUTION
If a grammar has left recursion & left factoring then it is ambiguous. So to convert a CFG to
LL(1) grammar both removal of left recursion & left factoring need to be done.
4. Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2
states. The relationship between n1 and n2 is
(A) n1 is necessarily less than n2
(B) n1 is necessarily equal to n2
(C) n1 is necessarily greater than n2
SOLUTION
SLR parsue is less range of context free languages than LALR but still both n1 & n2 are same for
SLR & LALR respectively.
5. In a bottom-up evaluation of a syntax directed definition, inherited attributes can

(A) always be evaluated
(B) be evaluated if the definition is L-attributed
(C) be evaluated only if the definition has synthesized attributes
(D) never be evaluated
SOLUTION
Every S (synthesized) -attributed definitions is L- attributed. So in a bottom-up evaluation of

SDD inherited attributes can be evaluated only if the definition has synthesized attributes.
6. Which of the following statements is FALSE?

(A) In statically typed language, each variable in a program has a fixed type
(B) In up-typed languages, values do not have any types
(C) In dynamically typed languages, variables have no types
(D) In all statically typed languages, each variable in a program is associated with values of
only a single type during the execution of the program
70
SOLUTION
(1) True for statically typed languages where each variable has fixed type. Similarly (4) is also
correct.
(2) True, in un-typed languages types of values are not defined.
But option (C) is false, since in dynamically typed language variables have dynamically
changing types but not that they have no type.
7.Consider the grammar shown below

S " | EtSS' |
S' " eS |!
E"b
In the predictive parse table M of this grammar the entities M(S) and M[S1,$] respectively are
(A) {s' " eS }and{S' " }
(B) {s' " eS}and{}
(C) {s' " }and{S' " }
(D){s' " eS , S ' " }and{ S' " }
SOLUTION:D
8. Consider the grammar shown below.

S"CC
C " eC | d
The grammar is
(A) LL (1)
(B) SLR (1) but not LL (1)
(C) LALR (1) but not SLR (1)
(D) LR (1) but not LALR (1)
SOLUTION
Given grammar
S " CC
C "cC d
it cant be LL since C " cC is recursive. LR(1) also known as CLR parser, and every CF
71
grammar is CLR grammar.
So (A) is false but (C) & (D) can be correct.
This grammar is CLR and also reducible to LALR without any conflicts. So (D) is false.
Only need to check for SLR(1) or LR(0)
This grammar is not SLR.
Hence (C) is correct option
9. Consider the translation scheme shown below
S " TR
R "+ T {print (+);}R |
T " num {print (num.val);}
Here num is a token that represents an integer and num. val represents the corresponding
integer value. For an input string 9 + 5+ 2, this translation scheme will print
(A) 9 + 5 + 2 (B) 9 5 + 2 +
(C) 9 5 2 ++ (D) ++ 9 5 2
SOLUTION
S " TR
R "+ T {pr int(' + ');}R
T " num{print(num.val);}
Given string 9 + 5 + 2
S " TR
T + TR {print(+);}
T+T+T {print(+);}
9+T+T {print(9);}
9+5 +T {print(5);}
9+5 +2 {print(2);}
So ++ 952 is printed
10. Consider the syntax directed definition shown below

S " id: = E
" newtemp ();
gen(t . place . place;);
.place t}
72
" .place .place;}
Here, gen is a function that generates the output code, and newtemp is a function that returns
the name of a new temporary variable on every call. Assume that t1s are the temporary variable
names generated by newtemp.
For the statement X: = Y + Z , the 3-address code sequence generated by this definition is
(A) X = Y + Z
(B) t1 = Y + Z; X t1
(C) t1 = Y; t2 = t1 + Z; X = t2
(D) t1 = Y; t2 = Z; t3 + t2; X = t3
SOLUTION
In 3-address code we use temporary variables to reduce complex instructions so here

t1 = Y t2 = Z
t 3 = t 1 + t2
x = t3
Solve the problems and choose the correct answers.

The following program fragment is written in a programming language that allows variables
and does not allow nested declarations of functions.
global inti
void
int i
print
i
print
}
main () { (i ) }
11. If the programming language uses static scoping and call by need parameter passing
mechanism, the values printed by the above program are
(A) 115, 220 (B) 25, 220
(C) 25, 15 (D) 115, 105
SOLUTION
In static scoping the variables are initialized at compile time only

73
So i = 100 & j = 5
P (i + j) = P (100 + 5) = P(105)
So x = 105
x + 10 = 105 + 10 = 115
So 115 & 105 will be printed.
12. If the programming language uses dynamic scoping and call by name parameter passing
mechanism, the values printed by the above program are
(A) 115, 220 (B) 25, 220
(C) 25, 15 (D) 115, 105
SOLUTION
In dynamic scoping, the local values are considered & variables are initialized at run time.
Since x = i + j & in P (x)
i = 200 & j = 20 x = 200 + 20 = 220
& printing (x + 10)
x = i + j + 10
= 10 + 5 + 10 = 25
13. Consider the following class definitions in a hypothetical object oriented language that
supports inheritance and uses dynamic binding. The language should not be assumed to be
either Java or C++, thought the syntax is similar
Now consider the following program fragment:

P x =new Q();
Q y =new Q();
74
P z =new Q();
x. f (1);((P) y). f (1);z.f(1);
Here ((P) y) denotes a typecast of y to P. The output produced by executing the above program
fragment will be
(A) 1 2 1 (B) 2 1 1
(C) 2 1 2 (D) 2 2 2
SOLUTION
1. Px = newQ();
2. Qy = newQ();
3. Pz = newQ();
4. x : f(1); print 2 # i = 2
5. ((P) y) : f(1);
6. z : f(1) print 2 # i = 2
but line 5. will print 2 because typecast to parent class cant prevent over ridding. So function
f(1) of class Q will be called not f(1) of class P .
14. Which of the following is NOT an advantage of using shared, dynamically linked libraries
as opposed to using statically linked libraries?
(A) Smaller sizes of executable
(B) Lesser overall page fault rate in the system
(C) Faster program startup
(D) Existing programs need not be re-linked to take advantage of newer versions of libraries
SOLUTION
The advantages of shared dynamically linked libraries include.

(A) smaller size of executable since less data
(B) lesser overall page fault rate.
(C) No need for re-linking if newer versions of libraries are there.
But since compilation time doesnt include linking so a long linking time required during
runtime in DLL ' s so slow startup.
15. Which of the following grammar rules violate the requirements of an operator grammar? P,
Q, R are non-terminals, and r, s, t are terminals
75
.
(i) P " QR (ii) P " Q s R
(iii) P " (iv) P " Q t R r

(A) (i) only (B) (i) and (iii) only
(C) (ii) and (iii) only (D) (iii) and (iv) only
SOLUTION
(I) P " QR is not possible since two NT should include one operator as Terminal.
(II) Correct
(III) Again incorrect. (IV) Correct.
16. 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
(A) Edit-time (B) Compile-time
(C) Link-time (D) Load-time
SOLUTION
The two modules needed to be linked since definition exist & M2 & M1 refers it. So during
linking phase M1 links to M2.
17. 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
(A) E1 should be evaluated first
(B) E2 should be evaluated first
(C) Evaluation of E1 and E2 should necessarily be interleaved
(D) Order of evaluation of E1 and E2 is of no consequence
SOLUTION
E1 is to be kept in accumulator & accumulator is required for operations to evaluate E2 also. So

E2 should be evaluated first & then E1, so finally E1 will be in accumulator, otherwise need to
use move & load instructions.
76
18. Consider the grammar with the following translation rules and E as the start symbol.
E " E 1 #T value = .value * .value}
.value = .value}
" .value = .value + .value}
.value = .value}
"num .value =num.value}
Compute E . value for the root of the parse tree for the expression: 2
# 3 # & 5 # 6 & 4.
(A) 200 (B) 180
(C) 160 (D) 40
SOLUTION
The parse tree would be.
Now we evaluate bottom up
77
LL " left to right left most derivation no ambignity should be there
SLR or LR(0) L to R reverse right sentential form create LR(0) items.

CLR or LR(1) create LR(1) items no bound
LALR reduced CLR if while reducing any conflict found then not
LALR
19. The grammar A " AA |( A)| is not suitable for predictive-parsing

78
because the grammar is
(A) ambiguous (B) Left-recursive
(C) right-recurisve (D) an operator-grammar
SOLUTION
The grammar is definitely left & right recursive but it is not suitable for predictive parsing
because it is ambiguous.
20. Consider the grammar E " E + n | E # n | n

For a sentence n + n, the handles in the right-sentential form of the reduction are
(A) n, E + n and E + n # n B) n , E + n and E + E # n
(C) n , n + n and n + n # n (D) n , E + n and E # n
SOLUTION
Given grammar
E "E+n
E "E#n
E "n
String = n + n # n
Right sentential so right most non terminal will be used.
E"E#n {E " E # n}
E+n#n {E " E + n}
n+n#n {E " n}
So during reduction the order is reverse.
So {E " n , E " E + n, E " E # n}
21. Consider the grammar
S " (S)| a
Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar n1 n2 and n3
respectively. The following relationship holds good
(A) n1 < n2 < n3 (B) n1 = n3 < n2
(C) n1 = n2 = n3 (D) n1 $ n3 $ n2
SOLUTION
The no. of states for SLR(1) & LALR(1) are equal so n 1 = n3, but CLR(1) or LR(1) will have no.
of states greater than LALR & LR(0) both.
79
22. Consider line number 3 of the following C-program.
Identify the compilers response about this line while creating the object-module
(A) No compilation error
(B) Only a lexical error
(C) Only syntactic errors
(D) Both lexical and syntactic errors
SOLUTION
There are no lexical errors for C because all the wrong spelled keywords would be considered
as identifiers until the syntax is checked.
So the compiler would give syntax errors.
Data for Q. 23 & 24 are given below.

Consider the following expression grammar. The semantic rules for expression calculation are
stared next to each grammar production.
E " number Eval number val

E E .val E .VAL E .val
E # E E .val E .VAL E .val
23. The above grammar and the semantic rules are fed to a yacc tool (which is an LALR(1)
parser generator) for parsing and evaluating arithmetic expressions. Which one of the following
is true about the action of yacc for the given grammar?
(A) It detects recursion and eliminates recursion
(B) It detects reduce-reduce conflict, and resolves
(C) It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce
80
action
(D) It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift
action
SOLUTION
Yace tool is used to create a LALR(1) parser. This parser can detect the conflicts but to resolve
the conflicts it actually prefers shift over reduce action.
24. Assume the conflicts part (a) of this question are resolved and an LALR(1) parser is
generated for parsing arithmetic expressions as per the given grammar. Consider an expression
3 # 2 + 1. What precedence and associativity properties does the generated parser realize?
(A) Equal precedence and left associativity; expression is evaluated to 7
(B) Equal precedence and right associativity, expression is evaluated to 9
(C) Precedence of 'x' is higher than that of +, and both operators are left associative;
expression is evaluated to 7
(D) Precedence of ' # ' is higher than that of #, and both operators are left associative;
expression is evaluated to 9
SOLUTION
The grammar has equal precedence and it is also ambiguous. Since LALR(1) parser prefer shift
over reduce so + operation will be executed here before ). 2 + 1 = 3 & 3 # 3 = 9 also the
operators are right associative.
25. Consider the following grammar.

S "S*E
S "E
E"F+EE"F
F " id
Consider the following LR(0) items corresponding to the grammar above.
(i) S " S * .E
(ii) E"F.+E
(iii) E " F + .E
Given the items above, which two of them will appear in the same set in the canonical sets-of-
items for the grammar?
81
(A) (i) and (ii) (B) (ii) and (iii)
(C) (i) and (iii) (D) None of these
SOLUTION
If S " S ): E is in LR(0) then E " F +: E will also be there because both of them has ' : ' before E .
26. Consider the following grammar

S " FR
R " * S | F " id
In the predictive parser table, M , of the grammar the entries M [ S, id] and M [ R,$] respectively
(A) {S " FR} and {R " } (B) {S " FR} and {}
(C) {S " FR} and {R " * S} (D) {F " id} and {R " }
SOLUTION
The predictive parser table is given as.

Non Terminal ) id $
S S " FR
F F " id
R R ") S R "! R "!
M [ S, id] =
So at { S " FR}
M [ R,$] = {R "!}
27. Consider the following translation scheme.

S " ER
R " * E{print{ * );R | f
E " F + E{print( + ); | F
F " (S) | id{print(id.value);}
Here id is a taken that represents an integer and id. value represents the corresponding integer
value. For an input 2 * 3 + 4, this translation scheme prints
(A) 2 * 3 + 4 (B) 2 * + 3 4
(C) 2 3 * 4 + (D) 2 3 4 + *
82
SOLUTION
Input string 2 ) 3 + 4
S " ER
FR
idR {print(2)}
id)ER {print())}
id) F+ER {print(+)}id)
id + ER {print(3)} id) id ) id +id
So 2 )+ 3 4 are printed
28. Consider the following C code segment.

for
for
if i
#i
}
}
}
Which one to the following false?

(A) The code contains loop-in variant computation
(B) There is scope of common sub-expression elimination in this code
(C) There is scope strength reduction in this code
(D) There is scope of dead code elimination in this code
SOLUTION
All the statements are true except option (D) since there is no dead code to get eliminated.
29. Which one of the following grammars generates the language
L = (a i b i | i ! j}?
(A) S " AC | CB (B) S " aS | Sb | a | b

C " aCb | a | b
A " aA |
B " Bb |
(C) S " ACCB (D) S " AC | CB

83
C " aCb |! C " aCb |!
A " aA |! A " aA | a
B " Bb |! B " bB | b
SOLUTION
The grammar
S " AC CB
C "aCb ! A "aA a B " bB b
Consider string aaabb
S " AC AaCb
AaaCbb
Aaabb aaabb
But string aabb
S " AC
And this string is not derivable. Hence (D) is correct option.
30.In the correct grammar above, what is the length of the derivation
(number of steps starting from S to generate the string al bm with
l ! m?
(A) max (l, m) + 2 (B) l+m+2
(C) l + m + 3 (D) max (l, m) + 3
SOLUTION
It is very clear from the previous solution that the no. of steps required depend upon the no. of
a' s & b ' s which ever is higher & exceeds by 2 due to S " AC CB & C "!
So max(l , m) + 2
31. Which one of the following is a top-down parser?

(A) Recursive descent parser (B) Operator precedence parser
(C) An LR(k) parser (D) An LALR(k) parser
SOLUTION
Clearly LR & LALR are not top down they are bottom up passers. Also not operator
precedence parser.
ut yes recursive descent parser is top down parser. Starts from start symbol & derives the
terminal string.
84
32.Consider the grammar with non-terminals N = {S , C , S}, terminals
T = {a, b , i , t, e}, with S as the start symbol, and the following of rules
S " iCtSS1 | a S1 " eS |
C"b
The grammar is NOTLL(1) because:
(A) It is left recursive (B) It is right recursive
(C) It is ambiguous (D) It is not context-free
SOLUTION
The grammar has production

S " iCtSS1 here the right hand side of grammar has the same symbol as left side. So the
grammar is left recursive.
The grammar is not ambiguous. Hence (A) is correct option.
33.Consider the following two statements:

P: Every regular grammar is LL(1)
Q: Every regular set has LR(1) grammar
Which of the following is TRUE?
(A) Both P and Q are true (B) P is true and Q is false
(C) P is false and Q is true (D) Both P and Q are false
SOLUTION
LL(1) parsers can recognize the regular grammars also LL(1) is subset of LR(1) or CLR
grammar so it also recognizes regular sets. So both accept regular grammar.
34. In a simplified computer the instructions are:

OP R j , Ri Performs Rj OP Ri and stores the result in register Ri
OP m, Ri Performs val OP Ri abd stores the result in Ri. value
denotes the content of memory location m.
MCVm, Ri Moves the content off memory loction m to register Ri .
MCVm, Ri , m Moves the content of register Ri to memory location m.
The computer has only two registers, and OP is either ADD or SUB. Consider the following
basic block:
85
t1 = a + b t2 = c + d
t 3 = e t2
t 4 = t 1 t2
Assume that all operands are initially in memory. The final value of the computation should be
in memory. What is the minimum number of MOV instructions in the code generated for this
basic block?
(A) 2 (B) 3
(C) 5 (D) 6
SOLUTION
The operation sequence would be

MOV a, R1
ADD b , R1 {R 1 = t1
MOV c , R2
ADD d, R2 {R 2 = t2
SUB e , R2 {t 3 = e R 2 = R2
SUB R 1, R2 {R 2 = t4
MOV R 2, t4 {finally in memory
Totally no. of move operation are 3

Consider the CFG with {S, A, B} as the non-terminal alphabet, {a, b} as the terminal alphabet,
S as the start symbol and the following set of production rules
35.Which of the following strings is generated by the grammar?

(A) aaaabb (B) aabbbb
(C) aabbab (D) abbbba
SOLUTION
aabbab
86
S " aB
" aaBB
" aabSB
" aabbAB
" aabbab
36.For the correct answer string to Q. 9 how many derivation trees are there?
(A) 1 (B) 2
(C) 3 (D) 4
SOLUTION
For the derivation two trees are possible
So due to ambiguity 2 trees are possible

37. Which of the following describes a handle (as applicable to LR-parsing) appropriately?
(A) It is the position in a sentential form where the next shift or reduce operation will occur
(B) It is a non-terminal whose production will be used for reduction in the next step
(C) It is a production that may be used for reduction in a future step along with a position in the
sentential form where the next shift or reduce operation will occur.
(D) It is the production p that will be used for reduction in the next step along with a position in
the sentential form where the right hand side of the production may be found
SOLUTION
Handles are the part of sentential form, & they are identified as the right side of any given
production which will be used for reduction in the net step.
87
38.Some code optimizations are carried out on the intermediate code because
(A) They enhance the portability of the complier to other target processors
(B) Program analysis is name accurate on intermediate code than on machine code
(C) The information from data flow analysis cannot otherwise be used for optimization
(D) The information from the front end cannot otherwise be used for optimization
SOLUTION
Code optimizations are carried out on the intermediate code
because program analysis is more accurte on intermediate code than on machine code.
39. Which of the following are true?

(i) A programming language option does not permit global variables of any king and has no
nesting of procedures/functions, but permits recursion can be implemented with static
storage allocation
(ii) Multi-level access link (or display) arrangement is needed to arrange activation records-
only if the programming language being implemented has nesting of procedures/function
(iii) Recursion in programming languages cannot be implemented with dynamic storage
allocation
(iv) Nesting of procedures/functions and recursion require a dynamic heap allocation scheme
and cannot be implemented with a stack-based allocation scheme for activation records
(v) Languages which permit a function to return a function as its result cannot be implemented
with a stack-based storage allocation scheme for activation records
(A) (ii) and (v) only (B) (i), (iii) and (iv) only
(C) (i), (ii) and (v) (D) (ii), (iii) and (v) only
SOLUTION
I. Statement is false since global variables are required for

recursions with static storage. This is due to unavailability of stack in static storage.
II. This is true
III. In dynamic allocation heap structure is used, so it is false. IV. False since recursion
can be implemented.
V. Statement is completely true. So only II & V are true.
88
40. An LALR(1) parser for a grammar can have shift-reduce (S-R)
conflicts if and only if
(A) The SLR(1) parser for G has S-R conflicts
(B) The LR(1) parser for G has S-R conflicts
(C) The LR(0) parser for G has S-R conflicts
(D) The LALR(1) parser for G has reduce-reduce conflicts
SOLUTION
LALR parser is reduced form of CLR or LR(1) parser, LALR parser uses the LR(1) items of CLR
parser & of any shift reduce conflicts are there then it is due to LR(1) parser.
41. Which of the following statements are TRUE ?

There exist parsing algorithms 3for some programming languages
hose complex are less than (n )
II A programming language which allows recursion can be implemented with static storage
allocation
III No L-attributed definition can be evaluated in the framework of bottom-up parsing
IV Code improving transformations can be performed at both source
language and intermediate code level
(A) I and II (B) I and IV
(C) III and IV (D) I, III and IV
SOLUTION
I. Statement is true since there are some parsers which take
0(n log2n) time for parsing.
II. Completely false, since there is no use of stack which is required for recursion.
III. False
IV. True since both types of optimizations are applied Hence (B) is correct
option.
42.What data structure in a complier is used for managing information about variables and their
attributes?
(A) Abstract syntax tree (B) Symbol table
(C) Semantic stack (D) Parse table
SOLUTION
Symbol table is used for storing the information about variables and their attributes by
89
compiler.
43. Which languages necessarily need heap allocation in the runtime environment ?
(A) Those that support recursion
(B) Those that use dynamic scoping
(C) Those that allow dynamic data structure
(D) Those that use global variables
SOLUTION
Dynamic memory allocation is maintained by heap data structure. So to allow dynamic data
structure heap is required.
OPERATING SYSTEMS
YEAR 2001
Question. 1
Which of the following statements is false ?
(A)Virtual memory implements the translation of a programs address space into physical memory
address space.
(B)Virtual memory allows each program to exceed the size of the primary memory.
(C)Virtual memory increases the degree of multi-programming
(D)Virtual memory reduces the context switching overhead.
SOLUTION
Virtual memory enables a program to exceed the size of primary memory so it increases degree
of multi-programming.
Since data required by executing program is available here so context switching is reduced.
But virtual memory doesnt translate programs address space into physical memory.
Question. 2
90
Consider a set of n tasks with known runtimes r1,r2,........rn to be run on a uniprocessor
machine. Which of the following processor scheduling algorithms will result in the maximum
throughput ?
(A) Round-Robin (B) Shortest-Job-First

(C) Highest-Response-Ratio-Next (D) First-come-First-Served
SOLUTION
Here the running times r1....rn are already known, single processor system. In this scenario,
throughput i.e. CPU is maximum utilized in shortest job first scheduling.
Question. 3
Where does the swap space reside ?
(A) RAM (B) Disk

(C) ROM (D) On-chip cache
SOLUTION
Swap space is the memory space where the part of the program not currently in main memory
for execution is stored, this program part can be swapped into memory when required.
This space is generally in disk.
Question. 4
Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page
access pattern, increasing the number of page frames in main memory will.
(A)Always decrease the number of page faults

(B)Always increase the number of page faults
(C)Sometimes increase the number of page faults
(D)Never affect the number of page faults
SOLUTION
During F1F0 page replacement policy, due to increase in the no. of page frames in memory
should decrease the no. of page faults since more frames can be kept there.
But due to Beladys Anomaly after certain limit or in some page access instances no. of page
faults are high.
91
Question. 5
Consider a machine with 64 MB physical memory and a 32-bit virtual address space. If the
page size is 4 KB, what is the approximate size of the page table ?
(A) 16 MB (B) 8 MB
(C) 2 MB (D) 24 MB
SOLUTION
Size of main memory = 64 MB

Size of virtual memory = 232 B
No. of pages = 232/212
= 220 pages
Required 1 M enteries.
But each entry has both a virtual address & corresponding physical address.
Total bits in each entry = 32 +26 (Physical) = 58
= 58/8 = 8 Bytes.
So total memory = 8*1 MB= 8 MB
Question. 6
Consider Petersons algorithm for mutual exclusion between two concurrent processes i and j.
The program executed by process is shown below.
repeat
ag[i]=true;
turn=j;
while(p)do no-op;
Enter critical section, perform actions, then
exit critical section
Flag[i]=false;
Perform other non-critical section actions.
Until false;
For the program to guarantee mutual exclusion, the predicate P in the while loop should be
(A) flag [j]= true and turn =j (B) flag [j]=true and turn =j
(C) flag [i]=true and turn=j (D) flag [i]=true and turn=i
SOLUTION
92
While loop if true predicate then the program enters into critical region. This program enters
into critical region of flag [i]=true act as semaphore, & true =j, the requirement of resource is
by some other process.
YEAR 2002
Question. 7
Which of the following scheduling algorithms is non-preemptive ?

(A) Round Robin
(B) First-In First-Out
(C)Multilevel Queue Scheduling
(D)Multilevel Queue Scheduling with Feedback
SOLUTION
Round robin is preemptive since processes are cycled for CPU time, & run for a particular time
stamp in one cycle. Multilevel queue scheduling maintains various quenes, each having
different priorities. But in FIFO scheme, only the process which enters once, would be
completed first, so no. preemption.
Hence (B) is correct option.Question. 8
The optimal page replacement algorithm will select the page that
(A)Has not been used for the longest time in the past.
(B)Will not be used for the longest time in the future.
(C)Has been used least number of times.
(D)Has been used most number of times
SOLUTION
Optimal page replacement algorithm assumes that the pages that will come in future are already
known, so replacement of the page which will not be used in future occurs.
Question. 9
Which combination of the following features will suffice to characterize an OS as a multi-

programmed OS ? More than one program may be loaded into main memory at the same time
for execution. (B) If a program waits for certain events such as I/O, another program is
immediately scheduled for execution. (C) If the execution of a program terminates, another
program is immediately scheduled for execution.
93
(A) A (B) A and B
(C) A and C (D) A, B and C
SOLUTION
Multi-programmed:- More than one program can run on single CPU, when one is blocked.
(A)Is true and a characteristic of multi-programmed
(B)Is true & also characterize a multi-programmed OS
(C)Is true but no necessary for this type this happens in all OS, even in batch processor.
Question. 10
In the index allocation scheme of blocks to a file, the maximum possible size of the file depends on
(A)The size of the blocks, and the size of the address of the blocks
(B)The number of blocks used for the index, and the size of the blocks.
(C)The size of the blocks, the number of blocks used for the index, and the size of the address of the
blocks.
(D)None of the above.
SOLUTION
When indexes are created, the maximum no. of blocks given to a file are totally dependent upon
size of the index which tells how many blocks can be there, & size of each block.
YEAR 2003
Question. 11
Using a larger block size in a fixed block size file system leads to
(A)better disk throughput but poorer disk space utilization
(B)better disk throughput and better disk space utilization
(C)poorer disk throughput but better disk space utilization
(D)poorer disk throughput and poorer disk space utilization
SOLUTION
Using larger block size in a fixed block size system lead to poor disk space utilization due to
data items which are very small comparable to block size cause fragmentation. But it leads to
better disk through put since no. of blocks needs to fetch & replace become less.
94
Question. 12
In a system with 32 bit virtual addresses and 1 KB page size, use of one-level page tables for virtual to
physical address translation is not practical because of
(A)the large amount of internal fragmentation
(B)the large amount of external fragmentation
(C)the large memory overhead in maintaining page tables
(D)the large computation overhead in the translation process
SOLUTION
32 bit virtual address, i.e. 232 kB of virtual memory & 1 kB page size.
So total pages = 232.
So. we need to maintain a page table of 232 rows, this require 4 GB main memory which is quite
impractical due to large memory overhead.
Question. 13
A uni-processor computer system only has two processes, both of which alternate 10 ms CPU
bursts with 90 ms I/O bursts. Both the processes were created at nearly the same time. The I/O
of both processes can proceed in parallel. Which of the following scheduling strategies will
result in the least CPU utilizations (over a long period of time) for this system ?
(A)First come first served scheduling

(B)Shortest remaining time first scheduling
(C)Static priority scheduling with different priorities for the two processes
(D)Round robin scheduling with a time quantum of 5 ms.
SOLUTION
There should be no doubt that round robin scheduling would lead to maximum CPU
utilization, but since in FCFS one task would starve for a long time so min CPU utilization
would be in this case.
A processor uses 2-level page table fro virtual to physical address translation. Page table for
both levels are stored in the main memory. Virtual and physical addresses are both 32 bits wide.
The memory is byte addressable. For virtual to physical address translation, the 10 most
95
significant bits of the virtual address are used as index into the first level page table while the
next 10 bits are used as index into the second level page table. The 12 least significant bits of
the virtual address are used as offset within the page. Assume that the page table entries in both
levels of page tables are 4 a bytes wide. Further, the processor has a translation look aside
buffer(TLB), with a hit rate of 96%. The TLB caches recently used virtual page numbers and
the corresponding physical page numbers. The processor also has a physically addressed cache
with a bit ratio of 90%. Main memory access time is 10 ns, cache access time is 1 ns, and {LB
access time is also 1ns.
Question. 14
Assuming that no page faults occur, the average time taken to access a virtual address is
approximately (to the nearest 0.5 ns)
(A) 1.5 ns (B) 2 ns

(C) 3 ns (D) 4 ns
SOLUTION
TLB is successfully 96% of total request & for remaining 4%. RAM is accessed twice.
So average time taken.
=0.96(1 +(0.9*1) +0.1*(1 +10))+0.04(21 +(0.9*0.1)) +0.1*(1 +10)
=.96(1 +.9 +1.1) +0.4(21 +.09 +1.1)
=.96*3 +0.4*23
=2.88 +0.92
=3.804 ns (Nearest .5)
Question. 15
Suppose a process has only the following pages in its virtual address space; two contiguous
code pages starting at virtual address 0x0000000, two contiguous data pages starting at virtual
address 0x00400000, and a stack page starting at virtual address 0xFFFFF000. The amount of
memory required for storing the page tables of this process is
(A)8 KB (B) 12KB (C) 16 KB (D) 20KB
SOLUTION
Total no. of pages required = 5

But due to 2 level page table = 2*4 Kb*2
=16 kB
96
Suppose we want to synchronize two concurrent processes P and Q using binary semaphores S
and T. The code for the processes P and Q is shown below.
Process P Process Q:
while(1) { while(1) {
W: Y:
print 0; print 1
print 0; print 1
X: Z:
} }
Synchronization statements can be inserted only at points W, X, Y and Z.
Question. 16
Which of the following will always lead to an output staring with 001100110011?
(A) P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
(B) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T initially 0
(C)P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1
(D)P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T initially 0
SOLUTION
For output string 001100110011 alternatingly we require process P & Q to execute.

For this to happen P(s) with S = 1 should be placed at W. At the same time P(T) with T = 0 will be at Y.
At X we have V(T) which will have T = 1 so process Q starts.
At the same time at Z we have V(s) which make S = 0 to stop process P.
Question. 17
Which of the following will ensure that the output string never contains a substring of the form
0.1 or 101 where n is odd?
(A)P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1

(B)P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1
(C)P(S) at W, V(S) at X, P(T) at Y, V(S) at Z, S initially 1
(D)(S) at W, V(T) at X, P(T) at Y, P(S) at Z, S and T initially 1
SOLUTION
To ensure this condition that substring of form 01n0 or 10n1, where n is odd S should be
initially 1, we will case only 1 semaphore S.
So at W P(s), at X V(s) whereas at Y P(s), at Z V(s)

97
YEAR 2004
Question. 18
Consider the following statements with respect to user-level threads and kernel-supported threads
(i)Context which 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?
(A) (ii),(iii) and (iv) only (B) (ii) and (iii) only
(C) (i) and (iii) only (D) (i) and (ii) only
SOLUTION
(I)It is false, context switch is not faster in support of kernel threads.

(II)A system call can truly block the user level threads, since they dont have permission to do that.
(III)True since kernel supported threads have their independent memory & resources.
(IV) False since user level threads might need support of kernel threads.
Question. 19
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 Fist (SSTF), claimed by the vendor to given 50% better
beachmark results, what is the expected improvement in the I/O performance of user programs?
(A) 50% (B) 40%

(C) 25% (D) 0%
SOLUTION
I/O performance is not entirely dependent upon disk access, it has effect of various other
devices, so using SSTF in place of FCFS may reduce disk access time but no improvement in
the I/O is done.
Question. 20
The minimum number of page frames that must be allocated to a running process in a virtual
memory environment is determined by
(A)the instruction set architecture
98
(B)page size
(C)physical memory size
(D)number of processes in memory
SOLUTION
Page frames are allocated in main memory, for virtual memory pages. This no. of page frames
depends upon the instruction set architecture.
Question. 21
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?
(A) 5.50 (B) 5.75

(C) 6.00 (D) 6.25
SOLUTION
Then around time = (Submit time finish time)
Gantt chart for the scheduler.
T.A time for P1 = 12 0 = 12
P2 = 4 1 = 3
P3 = 8 2 = 6
99
P4 = 5 4 = 1
Total = 22
Average turnaround time = 22/4
= 5.5
Question. 22
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 99%, and the page
fault rate is one in every 10,000 instructions. What is the effective average instruction execution
time?
(A) 645 nanoseconds (B) 1050 nanoseconds

(C) 1215 nanoseconds (D) 1230 nanoseconds
SOLUTION
Memory access time
=0.90*150 +0.10*(150 +150)
=135 +30
=165 ns
The error rate = 1/10000 = 104
CPU burst time = 100 ns
Total execution time
=[100 +2[165] +104*8*106]
=100 +330 +800
=100 +1130
=1230 ns
Question. 23
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
semaphore operators, where P decrements the semaphore value, and V increments the
semaphore value. The pseudo-code of P1 and P2 is as follows:
P1: P 2:
{ {
while true do while true do
L1: L3:
L2: L4:
X = X+1; Y = Y+1;
Y = Y-1; X = Y-1;
V(Sx); V(Sy);
V(Sy); V(Sx);
} }
100

Pgtrbcomputerscience

Uploaded by

Copyright:

Available Formats

Pgtrbcomputerscience

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Pgtrbcomputerscience

Uploaded by

Copyright:

Available Formats

Table of Contents

Mathematical Logic: Propositional Logic; First Order Logic.

Combinatorics: Permutations; Combinations; Counting; Summation; generating functions;

Numerical Methods: LU decomposition for systems of linear equations; numerical solutions

Computer Science and Information Technology

Programming and Data Structures: Programming in C; Functions, Recursion, Parameter

Compiler Design: Lexical analysis, Parsing, Syntax directed translation, Runtime

Operating System: Processes, Threads, Inter-process communication, Concurrency,

Information Systems and Software Engineering: information gathering, requirement and

Web technologies: HTML, XML, basic concepts of client-server computing.

Common Data Questions 6 & 7:

voidfind_and_replace( char *A, char *oldc, char *newc)

The procedure is tested with the following four test cases

COMMON DATA QUESTIONS 10 & 11

// p[3] is 'E' and p[1] is 'A'.

16. WhatisthevalueprintedbythefollowingCprogram? (GATE 2010)

1)19 2)21 3)20 4)10

20.The following program is to be tested for statement coverage : (GATE 2010)

Statement for Linked Answer Questions 21 & 22 (GATE 2010)

Statement for Linked Answer Question 26 & 27 (GATE 2009)

(A) x= 3,y = 4,z = 2 (B) x = 6,y = 5,z = 3

30. What is printed by the following C program? (GATE 2008)

/*below line changes value of c to 5. Note that x remains unaffected

/* changes c to 7, x is not changed */

To add 7, 2, 10, 4 we add the node at the end of array

Since 10 >9, we interchange and we get

(A) abc#+def ^^ (B) abc#+de^f^

(C) ab+c#de^f^ (D) +a#bc^^def

45.Consider the following C program (GATE 2004)

The program computers

P. Functional 1. Command-based, procedural

Q. Logic 2. Imperative, abstract data types

R. Object-oriented 3. Side-effect free, declarative,

49)Consider the following three functions. (2001)

50)Consider the following program (2001)

52)Consider the following declaration of a two-dimensional array in C. (2002)

53) Consider the following C function.(2003)

2 x)x/2 : 1 = x2/2 : 1 1 + x + x2/2

3 x2/2)x/3 = x3/3 : 2 : 1 1 + x + x2/2! + x3/3!

4 x3/3! x/4 x4/4! 1 + x + x2/2! + x3/3! + x4/4!

Thus it can be checked for every value.

54)Assume the following C variable declaration (2003)

58) Consider the C program shown below.

60) The goal of structured programming is to (2004)

61) Consider the following C function (2004)

63) The best data structure to check whether an arithmetic expression

63) Consider the following C function

65)Consider the following C program segment. (2003)

67) Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that

(D) None of the above

Hence (C) is correct option.

A. O (1) B. O (n) C. O (log2 n) D .O (n log2 n)

A. f(n) x g(n) B. Max ( f(n),g(n)) C. Min (f(n),g(n)) D. f(n) + g(n)

3.Two main measures for the efficiency of an algorithm are

4.The total number of comparisons in a bubble sort is

A. 0(log n) B. 0(n log n) C. 0(n) D. None of the above

A. ( 1 2 ) O N B. O(N) C. O(log N) D. None of these

6.The upper bound of computing time of m coloring decision problem is

A. O(nm) B .O(nm) C. O(nmn) D. O(nmmn)

voidfind_and_replace( char A, char oldc, char *newc)