MatchtheFollowing
Question 1 
P→(ii), Q→(iv), R→(i), S→(iii)  
P→(ii), Q→(i), R→(iv), S→(iii)  
P→(ii), Q→(iv), R→(iii), S→(i)  
P→(iii), Q→(iv), R→(i), S→(ii) 
Question 1 Explanation:
Static char var:
⇾ A variable located in Data Section of memory
P→(ii), Q→(iv), R→(i), S→(iii)
⇾ A variable located in Data Section of memory
P→(ii), Q→(iv), R→(i), S→(iii)
Question 2 
Match the algorithms with their time complexities:
Algorithm Time complexity (P) Towers of Hanoi with n disks (i) Θ(n^{2}) (Q) Binary search given n stored numbers (ii) Θ(n log n) (R) Heap sort given n numbers at the worst case (iii) Θ(2^{n}) (S) Addition of two n×n matrices (iv) Θ(log n)
P→(iii), Q→(iv), R→(i), S→(ii)  
P→(iv), Q→(iii), R→(i), S→(ii)  
P→(iii), Q→(iv), R→(ii), S→(i)  
P→(iv), Q→(iii), R→(ii), S→(i) 
Question 2 Explanation:
In this problem, we have to find Average case of different algorithms
→ Tower of Hanoi with n disks takes θ(2^{n}) time
It is a mathematical game or puzzle.
It consists of three rods and a number of disks of different sizes, which can slide onto any rod.
The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
3. No disk may be placed on top of a smaller disk.
With 3 disks, the puzzle can be solved in 7 moves.
The minimal number of moves required to solve a Tower of Hanoi puzzle is 2^{n}1, where n is the number of disks.
→ Binary Search given n sorted numbers takes Ɵ(log_{2} n)
→ Heap sort given n numbers of the worst case takes Ɵ(n log n)
→ Addition of two n×n matrices takes Ɵ(n^{2})
→ Tower of Hanoi with n disks takes θ(2^{n}) time
It is a mathematical game or puzzle.
It consists of three rods and a number of disks of different sizes, which can slide onto any rod.
The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
3. No disk may be placed on top of a smaller disk.
With 3 disks, the puzzle can be solved in 7 moves.
The minimal number of moves required to solve a Tower of Hanoi puzzle is 2^{n}1, where n is the number of disks.
→ Binary Search given n sorted numbers takes Ɵ(log_{2} n)
→ Heap sort given n numbers of the worst case takes Ɵ(n log n)
→ Addition of two n×n matrices takes Ɵ(n^{2})
Question 3 
E  P, F  R, G  Q, H  S  
E  R, F  P, G  S, H  Q  
E  R, F  P, G  Q, H  S
 
E  P, F  R, G  S, H  Q

Question 3 Explanation:
The grammar in S {X →bXb  cXc  ϵ} derives all even length Palindromes, So H matches with S.
F matches with P, Number of formal parameters in the declaration…. matches with {L={ a^{n} b^{m} c ^{n} d^{m}  m,n >=1}
Since, a^{n} b^{m} corresponds to formal parameter (if n=2 and m=1, and “a” is int type and “b”is float type, then it means (int,int,float)) and c^{n} d^{m} corresponds to actual parameter used in function.
Similarly other two can also be argued by their reasons, but with F matches with P and H matches with S implies that option C is the only correct option.
F matches with P, Number of formal parameters in the declaration…. matches with {L={ a^{n} b^{m} c ^{n} d^{m}  m,n >=1}
Since, a^{n} b^{m} corresponds to formal parameter (if n=2 and m=1, and “a” is int type and “b”is float type, then it means (int,int,float)) and c^{n} d^{m} corresponds to actual parameter used in function.
Similarly other two can also be argued by their reasons, but with F matches with P and H matches with S implies that option C is the only correct option.
Question 4 
Ic, IId, IIIb, IVa  
Ia, IId, IIIc, IVb  
Id, IIc, IIIb, IVa  
Ic, IId, IIIa, IVb

Question 4 Explanation:
Note: Out of syllabus.
Question 5 
Ia, IId, IIIc, IVb  
Ib, IId, IIIc, IVa  
Ia, IIc, IIId, IVb  
Ib, IIc, IIId, IVa 
Question 5 Explanation:
(i) Proxy server: Proxy server and firewall are to be combined.
(ii) Kazaa and DC++ are P2P applications.
(iii) P2P slip is a processor of PPP.
(iv) DNS allows caching of entries at local server.
(ii) Kazaa and DC++ are P2P applications.
(iii) P2P slip is a processor of PPP.
(iv) DNS allows caching of entries at local server.
Question 6 
P – 3 Q – 2 R – 1  
P – 1 Q – 2 R – 3
 
P – 2 Q – 3 R – 1
 
P – 1 Q – 3 R – 2

Question 6 Explanation:
⇒ Gang scheduling is used for parallel system that schedules the threads.
⇒ Rate monotonic scheduling is used in Realtime operating system.
⇒ Fair share scheduling distributes the CPU equally among users due to which it generates scheduling process.
⇒ Rate monotonic scheduling is used in Realtime operating system.
⇒ Fair share scheduling distributes the CPU equally among users due to which it generates scheduling process.
Question 7 
P – 2 Q – 1 R – 3 S – 5  
P – 1 Q – 4 R – 2 S – 3
 
P – 1 Q – 4 R – 2 S – 5  
P – 2 Q – 4 R – 1 S – 3 
Question 7 Explanation:
P) SMTP is used for email transmission.
Q) BGP is network layer protocol that manages low packets are routed across the network.
R) TCP is a transport layer protocol.
S) PPP is a data link layer protocol.
Q) BGP is network layer protocol that manages low packets are routed across the network.
R) TCP is a transport layer protocol.
S) PPP is a data link layer protocol.
Question 8 
1R, 2S, 3P, 4Q  
1S, 2R, 3Q, 4P  
1S, 2Q, 3R, 4P  
1S, 2P, 3Q, 4R 
Question 8 Explanation:
Note: Out of syllabus.
Question 9 
(i)  B, (ii)  D, (iii)  E, (iv)  F, (v)  G, (vi)  A  
(i)  C, (ii)  A, (iii)  E, (iv)  D, (v)  H, (vi)  F  
(i)  C, (ii)  F, (iii)  H, (iv)  A, (v)  G, (vi)  D  
(i)  B, (ii)  E, (iii)  C, (iv)  F, (v)  G, (vi)  H 
Question 9 Explanation:
Note: Out of syllabus.
Question 10 
(1, c), (2, b), (3, a)
 
(1, a), (2, c), (3, b)
 
(1, b), (2, c), (3, a)
 
(1, a), (2, b), (3, c)

Question 10 Explanation:
(a) A[i] = B[j]; Indexed, Addressing.
Here using the Index.
(b) while [*A++]; Auto increment.
The memory is increments automatically.
(c) int temp = *x; Indirect Addressing.
Here temp is assigned to integer type of Address contained in x.
Here using the Index.
(b) while [*A++]; Auto increment.
The memory is increments automatically.
(c) int temp = *x; Indirect Addressing.
Here temp is assigned to integer type of Address contained in x.
Question 11 
P  1, Q  4, R  3
 
P  2, Q  4, R  1
 
P  2, Q  3, R  1
 
P  1, Q  3, R  2

Question 11 Explanation:
Data Link Layer :: Second layer of the OSI Model, Responsible for Hop to Hop connection or point to point connection.
Transport Layer :: Fourth layer of the OSI Model, Responsible for Service point addressing/Socket to socket connection or end to end connection with full reliability.
Network Layer :: Third layer of the OSI Model, Responsible for Host to Host.
Transport Layer :: Fourth layer of the OSI Model, Responsible for Service point addressing/Socket to socket connection or end to end connection with full reliability.
Network Layer :: Third layer of the OSI Model, Responsible for Host to Host.
Question 12 
P  2, Q  3, R  4, S  1
 
P  4, Q  3, R  2, S  1
 
P  3, Q  4, R  1, S  2
 
P  3, Q  4, R  2, S  1

Question 12 Explanation:
P) Functional programming is declarative in nature, involves expression evaluation and side effect free.
Q) Logic is also declarative but involves theorem proving.
R) Object oriented is imperative statement based and have abstract data types.
S) Imperative programs are made giving commands and follow definite procedure.
Q) Logic is also declarative but involves theorem proving.
R) Object oriented is imperative statement based and have abstract data types.
S) Imperative programs are made giving commands and follow definite procedure.
Question 13 
X – 3 Y – 2 Z  1  
X – 1 Y – 3 Z  2  
X – 2 Y – 3 Z  1  
X – 3 Y – 1 Z  2 
Question 13 Explanation:
Indirect addressing:
Indirect addressing means that the address of the data is held in an intermediate location so that the address is first 'looked up' and then used to locate the data itself.
Immediate addressing:
Immediate Addressing. An immediate operand has a constant value or an expression. When an instruction with two operands uses immediate addressing, the first operand may be a register or memory location, and the second operand is an immediate constant.
Auto increment or decrements can be one by using loops.
Indirect addressing means that the address of the data is held in an intermediate location so that the address is first 'looked up' and then used to locate the data itself.
Immediate addressing:
Immediate Addressing. An immediate operand has a constant value or an expression. When an instruction with two operands uses immediate addressing, the first operand may be a register or memory location, and the second operand is an immediate constant.
Auto increment or decrements can be one by using loops.
Question 14 
X – 1 Y – 3 Z – 2  
X – 2 Y – 1 Z – 3  
X – 3 Y – 2 Z – 1  
X – 3 Y – 1 Z – 2 
Question 14 Explanation:
X → m = NULL will results the loss of memory.
Y → n is pointer to invalid memory, a making it as a dangling pointer.
Z → p is not initialized.
p = malloc (size of(char))p = malloc (size of(char)); should have been used before assigning 'aa' to ∗p.
Y → n is pointer to invalid memory, a making it as a dangling pointer.
Z → p is not initialized.
p = malloc (size of(char))p = malloc (size of(char)); should have been used before assigning 'aa' to ∗p.
Question 15 
X – 1 Y – 2 Z – 3  
X – 3 Y – 1 Z – 2  
X – 3 Y – 2 Z – 1  
X – 2 Y – 3 Z – 1 
Question 15 Explanation:
Stack is used in depth first search.
Queus is used in Queue.
Heap is used in heap.
Queus is used in Queue.
Heap is used in heap.
Question 16 
(A) – 2 (B) – 4 (C) – 3 (D)  1  
(A) – 1 (B) – 2 (C) – 3 (D) – 4  
(A) – 3 (B) – 2 (C) – 4 (D)  1  
(A) – 4 (B) – 1 (C) – 2 (D) – 3 
Question 16 Explanation:
⇒ Threads are handled by CPU.
⇒ Virtual address is a memory type.
⇒ File system is used to manage the disk.
⇒ Interrupt is a signal.
Question 17 
A – R B – P C – Q D – S  
A – R B – P C – S D – Q  
A – P B – R C – S D – Q  
A – P B – S C – R D – Q 
Question 17 Explanation:
Binary search = O(log n)
Selection = O(n)
Merge sort = O(n log n)
Insertion sort = O(n^{2})
Selection = O(n)
Merge sort = O(n log n)
Insertion sort = O(n^{2})
Question 18 
A – 2 B – 4 C – 1 D – 3  
A – 3 B – 4 C – 1 D – 2  
A – 3 B – 4 C – 2 D – 1  
A – 4 B – 1 C – 2 D – 3 
Question 18 Explanation:
All pairs shortest path  Dynamic Programming
Quick sort  Divide and Conquer
Minimum weight Spanning tree  Greedy
Connected components  DepthFirst search
Quick sort  Divide and Conquer
Minimum weight Spanning tree  Greedy
Connected components  DepthFirst search
Question 19 
A – 4 B – 3 C – 1 D – 2  
A – 2 B – 1 C – 3 D – 4
 
A – 4 B – 3 C – 2 D – 1  
A – 2 B – 3 C – 4 D – 1 
Question 19 Explanation:
DMA I/O → Disk
Cache → High speed RAM
Interrupt I/O → Printer
Condition code register → ALU
Cache → High speed RAM
Interrupt I/O → Printer
Condition code register → ALU
Question 20 
A – 3 B – 4 C – 2 D – 1  
A – 4 B – 3 C – 2 D – 1  
A – 2 B – 4 C – 1 D – 3  
A – 3 B – 4 C – 3 D – 2 
Question 20 Explanation:
Disk scheduling  SCAN
Batch processing  FIFO
Time sharing  Round Robin
Interrupt processing  LIFO
Batch processing  FIFO
Time sharing  Round Robin
Interrupt processing  LIFO
Question 21 
A – 3 B – 4 C – 1 D – 2  
A – 4 B – 3 C – 1 D – 2  
A – 4 B – 3 C – 2 D – 1  
A – 3 B – 4 C – 2 D – 1 
Question 21 Explanation:
Each time a subroutine is called its activation record is created.
An assembler uses location counter value to give address to each instruction which is needed for relative addressing as well as for jump labels.
Reference count is used by garbage collector to clear the memory whose reference count be comes 0.
Linker loader is a loader which can load several compiled codes and link them together into a single executable. Thus it needs to do relocation of the object codes.
An assembler uses location counter value to give address to each instruction which is needed for relative addressing as well as for jump labels.
Reference count is used by garbage collector to clear the memory whose reference count be comes 0.
Linker loader is a loader which can load several compiled codes and link them together into a single executable. Thus it needs to do relocation of the object codes.
Question 22 
(X, III) (Y, I) (Z, II)  
(X, II) (Y, III) (Z, I)  
(X, III) (Y, II) (Z, I)  
(X, I) (Y, III) (Z, II) 
Question 22 Explanation:
⇒ Array implementation can be done by Indexed addressing.
⇒ Writing relocatable code can be done by Base Register addressing by changing the value of Base Register.
⇒ While passing an array as parameter we use pointer and hence can use Indirect addressing.
⇒ Writing relocatable code can be done by Base Register addressing by changing the value of Base Register.
⇒ While passing an array as parameter we use pointer and hence can use Indirect addressing.
Question 23 
(a)  (q), (b)  (p), (c)  (r), (d)  (s) 
Question 24 
(a)  (q), (b)  (r), (c)  (p), (d)  (s) 
Question 24 Explanation:
Secondary index → BTree
Nonprocedural query language → Domain calculus
Closure of set of attributes → Function dependency
Natural join → Relational algebraic operations
Nonprocedural query language → Domain calculus
Closure of set of attributes → Function dependency
Natural join → Relational algebraic operations
Question 25 
(a)  (q), (b)  (r), (c)  (s), (d)  (p) 
Question 25 Explanation:
Pointer data type  Dynamic data structure
Activation record  Recursion
Repeat until  Nondeterministic loop
Coercion  Type conversion
Activation record  Recursion
Repeat until  Nondeterministic loop
Coercion  Type conversion
Question 26 
(a)  (s), (b)  (r), (c)  (p), (d)  (q) 
Question 26 Explanation:
Note: Out of syllabus.
Question 27 
(a)  (r), (b)  (p), (c)  (s), (d)  (q) 
Question 27 Explanation:
Strassen's matrix multiplication algorithm  Divide and Conquer
Kruskal's minimum spanning tree algorithm  Greedy method
Biconnected components algorithm  Depth first search
Floyd's shortest path algorithm  Dynamic programming
Kruskal's minimum spanning tree algorithm  Greedy method
Biconnected components algorithm  Depth first search
Floyd's shortest path algorithm  Dynamic programming
Question 28 
(a)  (q), (b)  (r), (c)  (s), (d)  (p) 
Question 28 Explanation:
Heap construction  O(n)
Constructing Hash table with linear probing  O(n^{2}
AVL tree construction  O(n log_{10} n)
Digital trie construction  Ω(n log_{10} n)
Constructing Hash table with linear probing  O(n^{2}
AVL tree construction  O(n log_{10} n)
Digital trie construction  Ω(n log_{10} n)
Question 29 
(a)  (s), (b)  (p), (c)  (q), (d)  (r) 
Question 29 Explanation:
Lexical analysis  Finite automaton
Code optimization  DAG
Code generation  Syntax tree
Abelian groups  Push down automaton
Code optimization  DAG
Code generation  Syntax tree
Abelian groups  Push down automaton
Question 30 
(a)  (s), (b)  (p), (c)  (q), (d)  (r) 
Question 30 Explanation:
Group  Left inverse
Semigroup  Associative
Monoid  Identity
Abelian group  Commutative
Semigroup  Associative
Monoid  Identity
Abelian group  Commutative
Question 31 
(A)(r), (B)(s), (C)(q), (D)(p) 
Question 31 Explanation:
Question 32 
(A)(s), (B)(r), (C)(p), (D)(q) 
Question 32 Explanation:
Base addressing is a position independent. By changing the value in base register, location of address also be changed.
Indexing mode can be used to access an array whose elements are in successive memory locations.
Stack addressing is a Reentranecy whenever code happens to be used again, address is need not be the same.
Implied addressing belongs to accumulator if an address is not specified, It is assumed implied to be accumulator.
Indexing mode can be used to access an array whose elements are in successive memory locations.
Stack addressing is a Reentranecy whenever code happens to be used again, address is need not be the same.
Implied addressing belongs to accumulator if an address is not specified, It is assumed implied to be accumulator.
Question 33 
(A)(r), (B)(s), (C)(p), (D)(q) 
Question 33 Explanation:
O(log n)  Binary search
O(n)  Selection of the k^{th} smallest element in a set of n elements
O(n log n)  Heapsort
O(n^{2})  Depthfirst search
O(n)  Selection of the k^{th} smallest element in a set of n elements
O(n log n)  Heapsort
O(n^{2})  Depthfirst search
Question 34 
(A)(r), (B)(s), (C)(q), (D)(p) 
Question 34 Explanation:
Virtual Memory  Address Translation
Shared Memory  Mutual Exclusion
Lookahead buffer  Spatial Locality
Lookaside buffer  Temporal Locality
Shared Memory  Mutual Exclusion
Lookahead buffer  Spatial Locality
Lookaside buffer  Temporal Locality
There are 34 questions to complete.