## CIL 2020

 Question 1

A____is a pictorial depiction of the schema of a database that shows the relations in the databases, their attributes, and primary keys and foreign keys.

 A Relational query languages B Relational algebra C Flow diagram D Schema Diagram
Database-Management-System       Relational Schema
Question 1 Explanation:
In database terms, a schema is the organisation and structure of a database. Both schemas and schemata can be used as plural forms. A schema contains schema objects, which could be tables, columns, data types, views, stored procedures, relationships, primary keys, foreign keys, etc.
A database schema can be represented in a visual diagram, which shows the database objects and their relationship with each other.
 Question 2

Consider the following table of arrival time and burst time for three processes P0,P1,P2

The preemptive shortest job first scheduling algorithm is used scheduling is carried out only at arrival or completion of process. The average waiting time for three process is____.

 A 7 Seconds B 4 seconds C 6 seconds D 5 seconds
Operating-Systems       Process-Scheduling
Question 2 Explanation:

∴ Avg. WT = 4+0+11/3 = 5
 Question 3

According to boolean law: (A')' = ?

 A 0 B A C (A')' D 1
Digital-Logic-Design       Boolean-Expression
Question 3 Explanation:
Complement of any variable even times will give the same variable. And complement of any variable odd times will give the complement of that variable.
Since in the question complement of variable is done 2 times which is even, so will give the same variable.
 Question 4
```int function (int x, int y)
{
if(y<=0) return x;
return function (y, x%y);
} ```

The above recursive function computes ______

 A GCD of X and Y B xy C yx D HCF of x and y E Both A and D
Programming       Functions
Question 4 Explanation:
Let’s take x=3, y=5
 Question 5

The working set model is used in memory management to implement the concept of:

 A Principle of locality B Thrashing C Paging D Segmentation
Operating-Systems       Memory-Management
Question 5 Explanation:
The working set model states that a process can be in RAM if and only if all of the pages that it is currently using (often approximated by the most recently used pages) can be in RAM. The model is an all or nothing model, meaning if the pages it needs to use increases, and there is no room in RAM, the process is swapped out of memory to free the memory for other processes to use.
Or
The working set is the memory that's being accessed "frequently" by an application or set of applications.
Principle of Locality does the same thing as explained above.
In computer science, locality of reference, also known as the principle of locality, is the tendency of a processor to access the same set of memory locations repetitively over a short period of time.There are two basic types of reference locality – temporal and spatial locality. Temporal locality refers to the reuse of specific data, and/or resources, within a relatively small time duration. Spatial locality (also termed data locality) refers to the use of data elements within relatively close storage locations.
 Question 6

Depth first search graph search algorithm uses ____ data structure for its implementation.

 A Stack B Tree C Dequeue D Queue
Data-Structures       Queues-and-Stacks
Question 6 Explanation:
Depth first search algorithm uses stack data structure for its implementation.
Whereas Breadth first search algorithm uses queue data structure for its implementation.
 Question 7

In RSA
1. P and Q are chosen as very large prime number
2. Compute n = p*q and Φ(n) = (n-1)*(q-1)
Letter e encryption key chosen. How is this encryption key selected?

 A e is chosen as a relative prime to q B e is chosen as a relative prime to p C e is chosen as a relative prime to Φ(n) D e is chosen as a relative prime to n
Computer-Networks       Network-Security
Question 7 Explanation:
e or encryption key is chosen which is relatively prime to Φ(n), to satisfy the equation
e*d = 1 mod Φ(n), where e is encryption key and d is decryption key.
 Question 8

Consider the following problem X
"Given a Turing Machine M over the input alphabet Σ any state q of M and word Σ*, does the computation of M on w visit the state q"

 A X is undecidable but partially decidable B X is not a decision problem C X is decidable D X is undecidable but not even partially decidable
Theory-of-Computation       Turing-machines
Question 8 Explanation:
The given problem is state entry problem. And the halting problem of the Turing machine can be reducible to state entry problem. And we know that the halting problem is undecidable, hence the state entry problem is undecidable. But the halting problem is turing recognizable or partially undecidable , hence the state entry problem is also partially decidable.
 Question 9

The expression for commutative law is given by:

 A A+AB=A B A+AB=B C A+B=B+A D AB+AA'=A
Question 9 Explanation:
The commutative law states that,
A op B = B op A
Where op is any operator.
Hence A+B = B+A
 Question 10

Consider the following grammar

` S → m | mn | mno `
Choose correct statement from the following:

 A The grammar is LL(4) B The grammar is LL(3) C The grammar is LL(2) D The grammar is LL(1)
Compiler-Design       Parsers
Question 10 Explanation:
Intersection of first() of any two production of S is ‘m’ which is not equal to {empty}, so not LL(1).
Intersection of second() of second and third production of S is ‘n’ which is not equal to {empty}, so not LL(2).
Intersection of third() of any two production of S is equal to {empty}, so yes LL(3).
 Question 11

 A 0.0.0.0 as network ID and 128.252.252.84 as node ID B 128.0.0.0 as network ID and 128.252.127.84 as node ID C 128.252.144.0 as network ID and 128.252.144.84 as node ID D 128.252.0.0 as network ID and 128.252.144.84 as node ID
Question 11 Explanation:
The range of class B IP addresses is 128-191. So first octet of given IP address is 128 ,hence the given IP address is of class B in which first two octet or first 16 bit is Network ID which remains same for all IP address of that network and rest bits are part of host ID which will be zero for Network ID of the given network.
So the Network ID of given IP address will be 128.252.0.0. And the node ID will be the same as the given IP address which is 128.252.144.84.
 Question 12

Consider the following statement.
I. Packet filter firewall analyzes network traffic at transport layer.
II. Circuit level firewall operate transport and session layer of OSI model.
From the above statement which statement/s is/are TRUE?

 A Only I B Only II C None D I and II
Computer-Networks       Network-Security
Question 12 Explanation:
The first firewalls were packet-filtering firewalls that work at the Network layer of the OSI networking model. They examine the packet headers that contain IP addresses and packet options and block or allow traffic through the firewall based on that information.
A circuit-level gateway is a type of firewall. Circuit-level gateways work at the session layer of the OSI model, or as a "shim-layer" between the application layer and the transport layer of the TCP/IP stack. They monitor TCP handshaking between packets to determine whether a requested session is legitimate.
 Question 13

___ is not a public key cryptosystem

 A EI Gemal B Rabin C AES D RSA
Computer-Networks       Network-Security
Question 13 Explanation:
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1985.
Like all asymmetric cryptosystems, the Rabin system uses a key pair: a public key for encryption and a private key for decryption. The public key is published for anyone to use, while the private key remains known only to the recipient of the message.
AES is a symmetric key cryptosystem or private key encryption.
RSA is one of the first public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and distinct from the decryption key which is kept secret.
 Question 14

Consider the FA shown in fig below which language is accepted by the FA:

 A (a+b)*a B b+(a+b)*b C b+a*b* D b+a*b
Theory-of-Computation       Finite-Automata
Question 14 Explanation:
Option B - ‘b’ is generated which is not accepted by the given FA.
Option C - ‘b’ is generated which is not accepted by the given FA.
Option D- ‘b’ is generated which is not accepted by the given FA.
Option A- All the strings generated by regular expression are accepted by the given FA.
Moreover we can clearly see that given automata accepts all the strings which ends with ‘a’. And regular expression in option A generates all such strings.
 Question 15

Generation of intermediate code based on an abstract machine model is useful in compilers because:

 A It makes implementation of lexical and syntax analysis easier B It is difficult to generate executable code from high level language program C Syntax translations are easier for intermediate code generation D It enhances the portability of the compiler system program
Compiler-Design       Compilers
Question 15 Explanation:
Till intermediate code generation phase the code is independent of the machine hence it enhances the portability of the compiler system program.
 Question 16

The maximum height of a binary tree with 'n' nodes is ____

 A (n+n) B (n+1) C n D (n-1)
Data-Structures       Binary-Trees
Question 16 Explanation:
The maximum height of a binary tree with n nodes is n-1, when the tree is skewed.
 Question 17

In hashing, collision resolution is carried out by close addressing. Which of the following is close addressing technique-
I. Bucket (for contiguous storage)

 A Only I B Only II C I and II D None
Data-Structures       Hashing
Question 17 Explanation:
 Question 18

The main memory of a computer has 2cm blocks while the cache has 2c blocks. If cache uses set associative mapping scheme with two blocks per set, then the block k of the main memory maps to set:

 A (k mod m) of the cache B (k mod c) of the cache C (k mod 2c) of the cache D (k mod 2cm) of the cache
Computer-Organization       Cache
Question 18 Explanation:
No. of sets are = No. of blocks in cache/no. of blocks per set = 2c/2 = c
Therefore the kth block of main memory maps to k mod c of the cache.
 Question 19

Consider the following two statements.
1. A binary tree T is full if each node is either a leaf or possesses exactly two child nodes.
2. A binary tree with n levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side.
Which statement is/are TRUE?

 A Only 2 B Only 1 C 1 and 2 D Neither 1 nor 2
Data-Structures       Binary-Trees
Question 19 Explanation:
S1 is true. The given definition of full binary tree is correct.
S2 is true. The given definition of complete binary tree is correct.
 Question 20

Consider the Unix i-node which uses 12 direct DBAs, 1 single indirect, 1 double indirect, 1 triple indirect. The disk block address requires 32 bits and disk block size is 1 KB. What is the maximum file size?

 A 32 GB B 64 GB C 16 GB D 8 GB
Operating-Systems       File system-I/O-protection
Question 20 Explanation:
Disk block address size = 32 bits = 32/8 B = 4B
No. of addresses that can fit in one block = size of block/size of address = 210B/22B = 28
∴ The maximum file size,
= (Direct address + 1 single indirect + 1 double indirect + 1 triple indirect) × Block size
= (12 + 28 + 28 × 28 + 28 × 28 × 28) × 210
≌ 234 = 16GB
 Question 21

A trigger has three parts.
The ____ describes the change that activates the trigger.
The _____ is a query that is run whenever the trigger is activated.
The ___ is the procedure that is executable if the trigger is activated and the condition is true.

 A event, condition, actor B entity, condition, action C event, question, action D event, condition, action
Question 21 Explanation:
The event describes the change that activates the trigger.
The condition is a query that is run whenever the trigger is activated.
The action is the procedure that is executable if the trigger is activated and the condition is true.
 Question 22

Which layer is associated with log in and log out from the network?

 A Presentation B Transport C Data link D Session
Computer-Networks       OSI-TCP-layers
Question 22 Explanation:
Login and Logout is done for authentication of the user, and authentication and authorization is the responsibility of session layer.
 Question 23

Digital certificates are described using ____ format.

 A X.509 B X.510 C X.508 D X.409
Computer-Networks       Network-Security
Question 23 Explanation:
In cryptography, a public key certificate, also known as a digital certificate or identity certificate, is an electronic document used to prove the ownership of a public key. The most common format for public key certificates is defined by X.509.
 Question 24

___ command is used to enable, disable, modify or drop a constraint in SQL

 A MODIFY Table B DEFINE Table C ADD Column D ALTER Table
Database-Management-System       SQL
Question 24 Explanation:
The SQL ALTER TABLE command is used to add, delete or modify columns in an existing table. You should also use the ALTER TABLE command to add and drop various constraints on an existing table.
 Question 25

Which is equivalent CFG without useless symbols for the given grammar:

`S → PQ | p, P → p `
 A S → PQ B S → p C S → P, P → p D S → P | p, P → p
Theory-of-Computation       Context-Free-Grammar
Question 25 Explanation:
A useless symbol is the one which does not derive any string or which is not reachable from starting symbol.
Since Q does not derive any string, hence the productions related to it will be removed. Now the productions remaining,
S → p
P → p
Now we can see that P is not reachable from the starting symbol S hence the productions related to P will be removed. So finally the answer will become,
S → p
 Question 26

Which of the following derivations does a top-down parser use while parsing a input string?
The input is assumed to be scanned in left to right order.

 A Topmost derivation B Leftmost derivation traced out in reverse C Leftmost derivation D Rightmost derivation
Compiler-Design       Parsers
Question 26 Explanation:
Top down parser use left most derivation while Bottom up parser use reverse of right most derivation.
 Question 27

Polynomial addition is implemented using ___ data structure.

 A Trees B Queue C Linked List D Stack
Question 27 Explanation:
Polynomial addition algorithm is implemented using either array or linked list data structure.
Time complexity of the above algorithm and program is O(m+n) where m and n are orders of two given polynomials.
 Question 28

A ____ of a relation is a set of one or more attributes whose values are guaranteed to identify tuples in the relation uniquely.

 A Foreign key B Super key C Scheme D key
Database-Management-System       Keys
Question 28 Explanation:
Superkey is the superset of the candidate keys or keys having one or more attributes whose values are guaranteed to identify tuples in the relation uniquely.
 Question 29

For implementation of recursion system uses ____ data structure.

 A Linked list B Deque C Stack D Queue
Data-Structures       Queues-and-Stacks
Question 29 Explanation:
Stack. Because of its LIFO (Last In First Out) property it remembers its 'caller' so knows whom to return when the function has to return. Recursion makes use of system stack for storing the return addresses of the function calls.
 Question 30

Which of the following statement is true?

 A The parsers canonical LR and LALR have the same power B LALR parser is more important than canonical LR parser C SLR parser is more powerful than LALR parser D Canonical LR parser is more powerful than LALR parser
Compiler-Design       Parsers
Question 30 Explanation:
The power of parsers is given by
CLR > LALR > SLR
 Question 31

Page fault occurs when

 A The page is an main memory B The page has an address, which cannot be loaded C The page is not in main memory D The page is not in cache memory
Operating-Systems       Memory-Management
Question 31 Explanation:
A page fault occurs when a program attempts to access a block of memory that is not stored in the physical memory, or RAM. The fault notifies the operating system that it must locate the data in virtual memory, then transfer it from the storage device, such as an HDD or SSD, to the system RAM.
 Question 32

Queue structure is used in ____

 A Polynomial addition B Recursion C Depth First search algorithm D Breadth First search algorithm
Data-Structures       Queues-and-Stacks
Question 32 Explanation:
Recursion uses stack data structure.
Depth first search algorithm uses stack data structure.
Breadth first search algorithm uses queue data structure.
 Question 33

In RSA algorithm if p=7, q=11 and e=13 then what will be the value of d?

 A 23 B 40 C 37 D 13
Computer-Networks       Network-Security
Question 33 Explanation:
We know that in RSA algorithm,
e * d ≡ 1 mod φ(n)
Lets first find φ(n),
φ(n) = (p-1)(q-1)
= (7-1)(11-1)
= 60
Now,
e * d ≡ 1 mod φ(n)
13 * d ≡ 1 mod 60
For d = 37 the above equation satisfies.
 Question 34

Consider the following statements:
Arithmetic Logic Unit(ALU)
1. Performs arithmetic operations
2. performs comparisons
3. Communicates with I/O devices
4. Keeps watch on the system
Which of these statements are correct?

 A 1 only B 1 and 2 only C 1 and 4 D 2 and 3
Computer-Organization       I/O-Devices
Question 34 Explanation:
An arithmetic logic unit (ALU) is a digital circuit used to perform arithmetic and logic operations. It represents the fundamental building block of the central processing unit (CPU) of a computer. Modern CPUs contain very powerful and complex ALUs.
 Question 35

The term cycle stealing is used in context of:

 A Interrupt based data transfer B Polling mode data transfer C DMA based data transfer D clock cycle overriding
Computer-Organization       DMA
Question 35 Explanation:
In DMA based data transfer, the transfer operation is carried out by the DMA controller which acts as a master in the microprocessor based system. The data is transferred directly between I/O and memory and data transfer is controlled by either I/O device or DMA controller.
There are two types of transfer modes in DMA:
1. Cycle stealing mode
2. Burst mode
DMA controllers can operate in a cycle stealing mode in which they take over the bus for each byte of data to be transferred and then return control to the CPU. They can also operate in burst mode in which a block of data is transferred before returning bus control to the CPU.
 Question 36

For following logic diagram which expression is true?

 A (AB) (AB.)' B ((A'B'),(AB.))' C ((A'B')+(AB.))' D (AB)'.AB
Digital-Logic-Design       Boolean-Expression
 Question 37

Excess-3 code of decimal number 2 is:

 A 0101 B 1010 C 1100 D 0011
Digital-Logic-Design       Number-Systems
Question 37 Explanation:
To find Excess-3 code, add 3 to the given decimal no. and then find the binary form of that no.
2+3 = 5
Binary form of 5 is 0101.
 Question 38

Consider a system with page fault service time(S)=100 ns, main memory access time(M)=20 ns, and page fault rate(P)=65%. Calculate the effective memory access time.

 A 62 ns B 82 ns C 80 ns D 72 ns
Operating-Systems       Memory-Management
Question 38 Explanation:
Let page fault rate = p
EMAT = (1 - p) × M + p・S
= 0.35 × 20 + 0.65 × 100
= 7 + 65
= 72 ns
 Question 39

Solve the following recurrence relation:
T(n) = 4T(n/2) + n2

 A Θ(n3) B Θ(n2 logn) C Θ(n2 /2) D Θ(n2)
Algorithms       Recurrences
Question 39 Explanation:
T(n) = 4T(n/2) + n2
a = 4, b = 2, k = 2, p = 0
So, a = bk and p > -1
According to master’s theorem,
= O(nlogba logp+1n)
= O(n2log n)
 Question 40

In ____balance factor of a node is the difference between left subtree and right subtree.

 A Red Balck tree B B+ Tree C AVL tree D 2-3 Tree
Data-Structures       Binary-Trees
Question 40 Explanation:
For a node in a binary tree, the difference between the heights of its left subtree and right subtree is known as balance factor of the node. In a balanced binary tree the heights of two subtrees of every node never differ by more than 1, and this tree is known as AVL tree.
 Question 41

The language generated by following grammar is:
S --> aSa | bSb | ε

 A Even length palindrome B a^m b^n n>=0, m>=0 C Odd length palindrome D a^n b^m n>=1, m>=1
Theory-of-Computation       Languages-and-Grammars
Question 41 Explanation:
The strings generated by the grammar is
{ε,aa,bb,abba,baab,aaaa,bbbb,aaaaaa,bbbbbb,aabbaa,abbbba,baaaab,bbaabb,........}.
So the given grammar generates all even length palindromes.
 Question 42

The language {am bn cm+n | m, n>=1} is:

 A Regular B Type 0 but context sensitive C Context free but not regular D Context sensitive but not context free
Theory-of-Computation       Languages-and-Grammars
Question 42 Explanation:
The given language is not regular because there are infinite dependencies between a, b and c.
But the given language is context free, because the given language can be identified using stack. First push a’s in the stack, then push b,s in the stack, now on looking c’s pop b,s and then on looking c’s pop a’s. If nothing is left on the stack and c’s are finished then the string is accepted else not accepted.
 Question 43

Which of the following affects the processing power of CPU
1. Data bus width
II. Clock speed

 A I and III B I, II and III C Only I D Only II
Computer-Organization       I/O-Devices
 Question 44

In D flip flop the out-put state Q is related with D input in what way?

 A Q is dependent of D B Q is same as D C Q is independent of D D Q is complement of D
Digital-Logic-Design       Sequential-Circuits
 Question 45

____includes a query language and commands to insert tuples into, delete tuples from, and modify tuples in the database.

 A Query language B Data-manipulation language C Data-Definition language D Data-calculation language
Database-Management-System       SQL
Question 45 Explanation:
Data manipulation language includes commands,
SELECT
INSERT
UPDATE
DELETE
 Question 46

Which grammar rules violate the requirement of the operator grammar? A,B,C are variables and a,b,c are terminals.

```I. A → BC
II. A → CcBb
III. A → BaC
IV. A → ε ```
 A I only B I and II C I and III D I and IV
Compiler-Design       Parsers
Question 46 Explanation:
In operator grammar there should be no epsilon or empty string in the production, and also there should be no two non-terminals adjacent to each other in the LHS.
(I) violates the operator grammar condition as it contains two adjacent non terminals on LHS.
(IV) violates the operator grammar condition as it contains epsilon.
 Question 47

Principle of locality is used in ___

 A Registers B DMA C Cache Memory D Interrupt
Computer-Organization       Cache
Question 47 Explanation:
In computer science, locality of reference, also known as the principle of locality, is the tendency of a processor to access the same set of memory locations repetitively over a short period of time. There are two basic types of reference locality – temporal and spatial locality. Temporal locality refers to the reuse of specific data, and/or resources, within a relatively small time duration. Spatial locality (also termed data locality) refers to the use of data elements within relatively close storage locations. Sequential locality, a special case of spatial locality, occurs when data elements are arranged and accessed linearly, such as, traversing the elements in a one-dimensional array.
Principle of locality is used in cache.
 Question 48

In____authentication, the claimant proves that she knows the secret without sending it to the verifier.

 A Asymmetric B Zero knowledge C Symmetric D Challenge response
Computer-Networks       Network-Security
Question 48 Explanation:
In password authentication ,the claimant proves her identity by demonstrating that she knows the secret, the password.However, because the claimant reveals this secret , it is susceptible to interception by the adversary.In challenge response authentication , the claimant proves that she knows the secret without sending it. In other words the claimant does not send the secret to the verifier, the verifier either has it or finds it.
In challenge response authentication, the claimant proves that she knows the secret without sending it to the verifier.
 Question 49

The following is the sequence of insertion in a binary search tree.

`45, 65, 35, 40, 33, 70, 60, 75, 69 `
How many numbers of nodes in Left Sub Tree(LST) and Right Sub Tree(RST) of root node.

 A LST-6, RST-2 B LST-5, RST-3 C LST-3, RST-5 D LST-2, RST-6
Data-Structures       Binary-Trees
Question 49 Explanation:
The given sequence of numbers is,
45, 65, 35, 40, 33, 70, 60, 75, 69
Now let’s draw binary search tree,

So LST contains 3 nodes and RST contains 5 nodes.
 Question 50

Find the output of the following

```#include
int main()
{
int x=5, y=9;
x=(x=x+y)-(y=x-y);
printf("%d%d", x,y);
return 0;
} ```
 A 5 14 B 5 9 C 14 5 D 9 5
Programming
Question 50 Explanation:
int x=5, y=9;
x=(x=x+y)-(y=x-y); // Since ‘-’ is left associative so x=x+y will be calculated first and the value of x will become (x=5+9=14). Now y=x-y will be calculated and the value of y will become (y=14-9=5). And finally the value (14-5) will be stored in x which is 9. Hence the final value of x and y is 9 and 5.
printf("%d%d", x,y); // So finally the value printed will be 9 and 5.
return 0;
 Question 51

Solve the following recurrence relation

T(n) = 4T(n/2) + n
 A O(n2) B O(n/2) C O(n) D O(logn)
Algorithms       Recurrences
Question 51 Explanation:
T(n) = 4T(n/2) + n
a = 4, b = 2, k = 1
Now, a> bk
So according to master’s theorem,
O(nlogba) = O(n2)
 Question 52

A ___ is the combination of one or more column values in a table that make a row of data unique within the table

 A Foreign key B Natural key C Candidate Key D Primary Key
Database-Management-System       Keys
Question 52 Explanation:
CANDIDATE KEY is a set of attributes that uniquely identify tuples in a table. Candidate Key is a super key with no repeated attributes. The Primary key should be selected from the candidate keys. Every table must have at least a single candidate key. A table can have multiple candidate keys but only a single primary key.
 Question 53

Write true (T) / false (F) for each of the following statements:
A. Symbol table is used only in the first phase of a compiler.
B. A pretty printer analyses a program and prints it in such a way that the structure of the program becomes early visible.
C. YACC build up LALR parsing table
D. If a grammar is LALR(1), it is not necessarily SLR(1)

 A T T F T B F T T T C T T T F D F T T F
Compiler-Design       Parsers
Question 53 Explanation:
A- False, Symbol table can be used in all the phases of the compiler.
B- True.
C- True, YACC is a tool to build the LALR parsing table.
D- True. If a grammar is LALR(1), it is not necessarily SLR(1). Below diagram is the parsers according to their powers and it justifies the given statement.
 Question 54

The following grammar is:

```S →  Aa | bAc | Bc | bBa
A →  d
B →  d ```
 A Not LR(1) but LALR(1) B Neither LR(1) nor LALR(1) C LR(1) and LALR(1) D LR(1) but not LALR(1)
Compiler-Design       Parsers
Question 54 Explanation:
Let's draw automata for LR(1),

Since there is no RR or SR conflict hence the given grammar is LR(1).
Now, for LALR(1) let’s combine I1 & I3,

Since there is RR conflict in state I13, hence not LALR(1).
 Question 55

Let L be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite state automaton accepting languages is ____

 A 2 B 5 C 8 D 3
Theory-of-Computation       Finite-Automata
Question 55 Explanation:

So the minimum state deterministic finite state automaton accepting language is 5.
 Question 56

____ is First in last out kind of data structure.

 A Stack B Array C Deque D Queue
Data-Structures       Queues-and-Stacks
Question 56 Explanation:
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).
 Question 57

What is meant by stable sorting algorithm?

 A A sorting algorithm is stable if it preserves the order of all keys B A sorting algorithm is stable if it preserves the order of non-duplicate keys C A sorting algorithm is stable if it preserves the order of duplicate keys D A sorting algorithm is stable if it doesn't preserve the order of duplicate keys
Algorithms       Sorting
Question 57 Explanation:
A sorting algorithm is called stable if it preserves the order of duplicate keys.
The examples of sorting algorithms are insertion sort,merge sort,counting sort etc.
 Question 58

Consider the following Inorder and Preorder traversal of a tree

```Inorder- D B E F A G H C
Pre Order- A B D E F C G H ```
What is the postorder traversal of the same tree?

 A D F E B H C G A B D F E B G H C A C D F E H B G C A D D F E B H G C A
Data-Structures       Binary-Trees
Question 58 Explanation:
Inorder - D B E F A G H C
Preorder - A B D E F C G H
Using the Inorder and Preorder we will get the tree as,

Now traversing the tree, we will get postorder traversal as,
D F E B H G C A
 Question 59

In SQL-the function -avg,min,max,sum,count are called as ____

 A Aggregate function B Adjunct function C Scalar operation D Set Operation
Database-Management-System       SQL
Question 59 Explanation:
In SQL the function avg, min, max, sum, count are called as aggregate function.
 Question 60

What is the output of the following C program

```#include
int main()
{
int i=5;
printf("%d%d%d", i++, i ,++i);
return 0;
} ```
 A 7 6 6 B 6 7 8 C 6 7 7 D 5 6 7
Programming       Operator
Question 60 Explanation:
int i=5;
printf("%d%d%d", i++, i ,++i);
In printf() the firstly the calculation is done from right to left and then printing is done from left to right.
So first ++i will increase the value of i by 1 and make it 6. Now the i will be read simply for second calculation.And now i++ will be calculated which will increment the value of i by 1 and make it 7, but since it is post increment so first 6 will be printed and then increment will be done and then for rest two 7 and 7 will be printed .Hence the output will be 6,7,7.
 Question 61

What is the number of page faults by least recently used page replacement for a memory with 4 frames for the page reference string 2, 0, 1, 2, 4, 0, 5, 1, 4, 6, 4, 2, 1, 3, 0?

 A 9 B 7 C 8 D 10
Operating-Systems       Page-Replacement-algorithm
Question 61 Explanation:
The given page reference string is,
2, 0, 1, 2, 4, 0, 5, 1, 4, 6, 4, 2, 1, 3, 0
In the least recently used page replacement algorithm, whenever there is page fault then the least recently used page will be replaced.

So, 10 page faults are there.
 Question 62

Relations and fields can be renamed in relational algebra using the renaming operator

 A p B σ C Θ D ⟕
Database-Management-System       Relational-Algebra
 Question 63

Consider the binary search tree with n elements. The time required to search given element is ___

 A O(logn) B O(n logn) C O(n2 logn) D O(n2)
Data-Structures       Binary-search-tree
Question 63 Explanation:
The worst case time complexity required to search the element in a binary search tree is O(n) when the tree is skewed. But since O(n) is not given in the option, the best other option will be O(n logn).
 Question 64

In database management system ACID property refers to:

 A Authenticity, consistency, Isolation and Durability B Atomicity, Confidentiality, Isolation and Durability C Atomicity, consistency, Isolation and Durability D Atomicity, Confidentiality, Integrity and Durability
Database-Management-System       Transactions
Question 64 Explanation:
A transaction is a very small unit of a program and it may contain several low level tasks. A transaction in a database system must maintain Atomicity, Consistency, Isolation, and Durability − commonly known as ACID properties − in order to ensure accuracy, completeness, and data integrity.
Atomicity − This property states that a transaction must be treated as an atomic unit, that is, either all of its operations are executed or none. There must be no state in a database where a transaction is left partially completed. States should be defined either before the execution of the transaction or after the execution/abortion/failure of the transaction.
Consistency − The database must remain in a consistent state after any transaction. No transaction should have any adverse effect on the data residing in the database. If the database was in a consistent state before the execution of a transaction, it must remain consistent after the execution of the transaction as well.
Durability − The database should be durable enough to hold all its latest updates even if the system fails or restarts. If a transaction updates a chunk of data in a database and commits, then the database will hold the modified data. If a transaction commits but the system fails before the data could be written on to the disk, then that data will be updated once the system springs back into action.
Isolation − In a database system where more than one transaction are being executed simultaneously and in parallel, the property of isolation states that all the transactions will be carried out and executed as if it is the only transaction in the system. No transaction will affect the existence of any other transaction.
 Question 65

Which of the following statements is true?

 A Any logic expression can be implemented using only NAND gates B Any logic expression can be implemented using only EXNOR gates C Any logic expression can be implemented using only NOT gates D Any logic expression can be implemented using only XOR gates
Digital-Logic-Design       Functional-Completeness
Question 65 Explanation:
The NAND Boolean function has the property of functional completeness. This means, any Boolean expression can be re-expressed by an equivalent expression utilizing only NAND operations. ... In the field of digital electronic circuits, this implies that we can implement any Boolean function using just NAND gates.
 Question 66

Mutual Exclusion problem occurs ______

 A Between two processes that use different resources of different machines B Between two disjoint processes that do not interact C Among processes that share resources D Among processes that do not use the same resource
Operating-Systems       Process-Synchronization
Question 66 Explanation:
Mutual exclusion problem occurs when two or more processes try to access the same shared resource, but only one process can access it at a time.
 Question 67

The time complexity of searching an element in linked n will be:

 A O(nlogn) B O(logn) C O(n) D O(n2)
Question 67 Explanation:
The worst case time complexity of searching an element in a linked list of n elements is O(n), just traversing the list one by one and comparing with the required element.
 Question 68

Consider the disk which has average seek time of 32 ns and rotational rate of 360 rpm (round per minute), each track of the disk has 512 sectors, each of size 512 bytes.
What is the time taken to read four continuous sectors? And what is the data transfer rate?

 A 0.0443s and 936 Kbps B 0.0843s and 1536 Kbps C 0.1043s and 1736 kbps D 0.0943s and 1636 kbps
Computer-Organization       Secondary-Memory
 Question 69

MSB stands for

 A Middle significant bit B Measured Significant bit C Maximum significant bit D Most significant bit
Digital-Logic-Design       Number-Systems
Question 69 Explanation:
MSB stands for Most Significant Bit. It is the left most bit of any binary string.
LSB stands for Least Significant Bit. It is the right most bit of any binary string.
 Question 70

Which scheduling algorithm gives a minimum average waiting time?

 A RR B Priority C SJF D FCFS
Operating-Systems       Process-Scheduling
Question 70 Explanation:
Shortest Job First (SJF) is an algorithm in which the process having the smallest execution time is chosen for the next execution. This scheduling method can be preemptive or non-preemptive. It significantly reduces the average waiting time for other processes awaiting execution.
 Question 71

Consider the following statements
1. Insertion sort and merge sort are stable
2. Heap sort is inherently unstable
3. Selection sort is not inherently stable, but may be coded in such a way that it is stable

 A Only statement 1 is correct B All statements are correct C Statement 3 is not correct D Only statement 1 and 2 is correct
Algorithms       Sorting
Question 71 Explanation:
A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.
S1 is true.
S2 is True, Heapsort is not stable because operations on the heap can change the relative order of equal items. From here: When sorting (in ascending order) heapsort first peaks the largest element and put it in the last of the list.
S3 is True. Selection sort is unstable by nature but can be stable by making some changes in the algorithm. Hence not inherently unstable.
Inherently unstable algorithm is an algorithm which cannot be made stable even by modifying the algorithm.
 Question 72

Which of the following statement is false?

 A Every regular language is also a context free language B Every non deterministic turing machine can be converted to an equivalent deterministic Turing machine C Every subset of recursively enumerable set is recursive D Every NFA can b converted into equivalent DFA
Theory-of-Computation       Languages-and-Grammars
Question 72 Explanation:
A is true.
B is true because non deterministic Turing machines and deterministic Turing machines are equal in power.
C is false, because there are some recursively enumerable sets which are not recursive.
D is true, because NFA and DFA are equal in power.
 Question 73

A tuple relational calculus query is expressed as ___

 A {T | p(T)} B { P() | T } C { p() | T} D {T | P() | T}
Database-Management-System       Relational-Calculus
Question 73 Explanation:
The tuple relational calculus is based on specifying a number of tuple variables. Each tuple variable usually ranges over a particular database relation, meaning that the variable may take as its value any individual tuple from that relation. A simple tuple relational calculus query is of the form:
{t | P(t)}
where t is a tuple variable and P(t) is a conditional (Boolean) expression involving t that evaluates to either TRUE or FALSE for different assignments of tuples to the variable t. The result of such a query is the set of all tuples that evaluate P(t) to TRUE. These tuples are said to satisfy P(t).
 Question 74

Consider the grammar

```S --> AbBaCc |ε
A --> aAb | ba
B --> bBC | cb
C --> cCa | ac ```
Find the first() of S

 A {a, b, ε} B {ε} C {a,ε} D {a,b,c,ε}
Compiler-Design       Parsers
Question 74 Explanation:
First(S) = First(A) ∪ {∊}
First(A) = {a,b}
∴ First(S) = {a,b} ∪ {∊}
= {a,b,∊}
 Question 75

Calculate the link utilization (throughput) for stop and wait flow control mechanism if the frame size is 4800 bits, bit rate is 9600 bps, and distance between the devices is 2000 km.
Given propagation speed is 200000 km/s.

 A 0.92 B 0.82 C 0.96 D 0.86
Computer-Networks       Stop-and-Wait-ARQ
 Question 76

Which is the correct method to obtain 10's complement of a decimal number?

 A The minuend is added to the 10's complement of the subtrahend and carry is dropped B The 10's complement of a decimal number is equal to 9's complement of given number minus one C The subtrahend is added to the 10's complement of the minuend and carry is dropped D The 10's complement of a decimal number is equal to 9's complement of given number plus one
Digital-Logic-Design       Number-Systems
Question 76 Explanation:
The 10’s complement of a decimal no. is equal to the 9’s complement of given number plus 1.
 Question 77

Maximum throughput of slotted ALOHA network is:

 A 18.4% B 36.8% C 50% D 35.8%
Computer-Networks       Access-Control-Methods
Question 77 Explanation:
Maximum throughput of slotted aloha is 36.8%.
And maximum throughput of pure aloha is 18.4%.
 Question 78

Which one of the following is TRUE?

 A Every regular grammar is LL(1) and every regular set does not have an LR(1) grammar B Every regular grammar is not LL(1) and every regular set does not have an LR(1) grammar C Every regular grammar is LL(1) and every regular has an LR(1) grammar D Every regular grammar is not LL(1) and every regular set has an LR(1) grammar
Theory-of-Computation       Regular-Language
Question 78 Explanation:
Since the regular grammar may be ambiguous so it cannot be LL(1) , because ambiguous grammar cannot be LL(1).So we can say that every regular grammar is not LL(1).
Every regular set (or language) has a right-linear deterministic (or left-factored) unambiguous grammar and thus, every regular language can have an LL(1) grammar. Since every LL(1) grammar is also LR(1).
 Question 79

A computer uses RAM chips of 1024x1 capacity.
How many chips are needed to provide memory capacity of 16K bytes?

 A 8 B 1024 C 16 D 128
Computer-Organization       RAM-capacity
Question 79 Explanation:
No. of chips required = Memory capacity/Chip capacity
= 214 Bytes/210 bits
= 214×23bits/210bits
= 27
= 128
 Question 80

Number of states in DFA accepting the following languages is:
L = {an b2m | n, m>=1}

 A m B n C 5 D 2
Theory-of-Computation       Finite-Automata
Question 80 Explanation:

∴ No. of states in DFA for the language L = {anb2m | n,m ≥ 1} is 5.
 Question 81

Which of the following has lowest access time?

 A Main Memory B Optical disk C Cache D Registers
Computer-Organization       Types-of-Memory
Question 81 Explanation:
Below is the sequence according to their access time(lowest to highest),
Registers < cache < main memory < optical disk
 Question 82

Which of the following is equivalent to the boolean expression given below?

` A+A'.B+A.B' `
 A A+B B A+B' C B+A' D B'+A'
Digital-Logic-Design       Boolean-Expression
Question 82 Explanation:
A + A’B + AB’
= (A + A’) (A + B) + AB’
= 1 ∙ (A + B) + AB’ (∴ A + A’ = 1)
= (A + B) + AB’
= A + (B + A) (B + B’) (∴ B + B’ = 1)
= A + (B + A) ∙ 1
= A + B + A
= A + B
 Question 83

Which of the following is/are correct
I. A language is context free if and only if it accepted by PDA
II. PDA is a finite automata with push down stack

 A Only II is true B Both I and II are false C Both I and II are true D Only I is true
Theory-of-Computation       Context-Free-Language
Question 83 Explanation:
S1 is true, because if a language is not accepted by PDA that means it is not context free. So we can say that a language is context free if and only if it is accepted by PDA.
S2 is true, Pushdown Automata is a finite automata with extra memory called stack which helps Pushdown automata to recognize Context Free Languages. A Pushdown Automata (PDA) can be defined as : ... In a given state, PDA will read input symbol and stack symbol (top of the stack) and move to a new state and change the symbol of stack.
 Question 84

With respect to deque which of the following is true?

 A Insertion is done from front end B Insertion and deletion can be done at front and rear ends C Deletion is done from rear end D Insertion is done only from rear end
Data-Structures       Queues-and-Stacks
 Question 85

A negative edge triggered flip flop transfers data from input on the:

 A LOW to HIGH transition of clock pulse B BEFORE transition of clock pulse C HIGH to LOW transition of clock pulse D WITHOUT transition of clock pulse
Digital-Logic-Design       Sequential-Circuits
Question 85 Explanation:
A negative edge triggered flip flop transfers data from input on the high to transition of clock pulse.
 Question 86

Consider the following relational schema

```Sailors(sid, sname, rating, age)
Reserves(sid, bid, day)
Boats(bid, bname, color) ```

What is the equivalent of following relational algebra query in SQL query

`Πsname((σcolor='red'Boats)⨝ Reserves ⨝ Sailors) `
 A SELECT S.sname, S.rating FROM Sailors S, Reserves R WHERE S.sid=R.sid AND R.bid = B.bid AND B.color='red' B SELECT S.sname FROM Sailors S, Reserves R, Boats B WHERE S.sid=R.sid AND R.bid = B.bid AND B.color='red' C SELECT S.sname FROM Sailors S, Reserves R, Boats B WHERE S.sid=R.sid AND B.color='red' D SELECT S.sname FROM Sailors S, Reserves R, Boats B WHERE R.bid=B.bid AND B.color='red'
Database-Management-System       SQL
Question 86 Explanation:
The given relational algebra query is equivalent to the sql query given in option B.
 Question 87

What is the complexity of merge sort?

 A O(n) B O(n2 logn) C O(nlogn) D O(n2)
Algorithms       Sorting
Question 87 Explanation:
Worst case time complexity of merge sort is O(nlogn).
 Question 88

___ of graph is a vertex whose removal disconnects graph

 A Start vertex B Middle point C Terminal vertex D Articulation point/Cut vertex
Engineering-Mathematics       Graph-Theory
Question 88 Explanation:
An articulation point (or cut vertex) is defined as a vertex which, when removed along with associated edges, makes the graph disconnected (or more precisely, increases the number of connected components in the graph).
 Question 89

Canonical SOP form of logic expression consists of only ____

 A Maxterms B Laterals C Cell D Minterms
Digital-Logic-Design       Boolean-Expression
Question 89 Explanation:
There are 2 steps to derive the Canonical Sum of Products Form from its truth table.
1. A Minterm is a product (AND) term containing all input variables of the function in either true or complemented form. A variable appears in complemented form ~X if it is a 0 in the row of the truth-table, and as a true form X if it appears as a 1 in the row.
Examples
A=0, B=1, C=0 -> ~A*B*~C
A=1. B=0, C=0 -> A*~B*~C
2. The canonical form is obtained by taking the sum (OR) of the minterm of the rows where a 1 appears in the output.
 Question 90

The following grammar is:

```S →  Aa | b Ac | dc | bda
A →  a ```
 A Neither LALR(1) nor SLR(1) B LALR(1) but not SLR(1) C Not LALR(1) but SLR(1) D LALR(1) and SLR(1)
Compiler-Design       Parsers
Question 90 Explanation:
Let’s check for SLR(1),

No SR or RR conflict, hence SLR(1).
Every SLR(1) grammar is LALR(1).
Hence given grammar is also LALR(1).
 Question 91

A relation is in ____ form if every field consists only of atomic values, that is, not lists or sets.

 A First normal B Third normal C Second normal D Fourth normal
Database-Management-System       Normalization
Question 91 Explanation:
If every field consists only of atomic values (i.e. no composite values) ,then that relation is in first normal form.
 Question 92

In hashing, collision results when ____

 A An attempt is made to delete a record at full primary bucket B An attempt is made to insert a record at full primary bucket C An attempt is made to insert a record anywhere in primary bucket D An attempt is made to insert a record at empty primary bucket
Data-Structures       Hashing
Question 92 Explanation:
When the primary bucket is full then if a record is allowed to insert anywhere in the primary bucket then there will definitely be collision because no empty place is available in that bucket.
 Question 93

In SQL, the ___ command is used to recompile view

 A ALTER VIEW B COMPILE VIEW C CREATE VIEW D DEFINE VIEW
Database-Management-System       SQL
 Question 94

The multiplicand register and multiplier register of hardware circuit implementation of booth's algorithm have (11101) and (1100). the result shall be:

 A (812)10 B (-812)10 C (-12)10 D (12)10
Digital-Logic-Design       Number-Systems
Question 94 Explanation:
In Booth’s multiplication the binary nos. are in 2’s complement form.
Hence the decimal value of multiplicand,
11101 = 101 = -3
The decimal value of multiplier,
1100 = 100 = -4
Hence the required result is,
-3 × -4 = 12
 Question 95

The ____ defines a set of operations on relations, paralleling the usual algebraic operations such as addition, subtraction or multiplication, which operates on numbers.

 A Relational calculus B Referential Integrity C Relational Algebra D Relations
Database-Management-System       Relational-Algebra
 Question 96

The class of context-free grammar is not closed under ____ operations

 A Concatenation B Intersection C Star D Union
Theory-of-Computation       Context-Free-Grammar
Question 96 Explanation:
Context free grammar is closed under concatenation, kleene star, union but not closed under intersection.
 Question 97

Which of the following is a unary operation?

 A Intersection B Projection C Join D Cartesian Product
Database-Management-System       Relational-Algebra
Question 97 Explanation:
Intersection, join , cartesian product is performed between two relations. But projection is just used to select a few columns from a relation.
 Question 98

Which of the following statement is false about Prim's algorithm?

 A Initially the roots key and nodes are initialized to zero B It may use binomial max heap to represent the primary queue C The complexity is O(E log V) using binary heap D The time complexity is O(E + V log V) using Fibonacci Heap
Algorithms       Greedy-approach
Question 98 Explanation:
S1 is false because only the root key is initialized to zero so that it can be picked first and the rest nodes are initialized to infinity.
The time complexity of Prim's algorithm using binary heap is O( E log V).
And the time complexity of prim's algorithm using Fibonacci heap is O(E + V log V) because the decrease key operation takes O(1) time in Fibonacci heap whereas using binary heap it takes O(log n) time.
 Question 99

Which of the following problems are undecidable?

I. Membership problem in context-free languages
II. Whether a given context-free languages is regular
III. Whether a finite state automation halts on all inputs
IV. Membership problem for type 0 languages
 A III and IV B I and IV C I and II D II and IV
Theory-of-Computation       Decidability-and-Undecidability
Question 99 Explanation:
Membership problems in context free languages are decidable because we have a CYK algorithm to check the membership.
Whether a given context-free language is a regular problem is undecidable.
Whether a finite state automaton halts on all inputs is decidable because if the string is accepted then it will halt on final state and if the string is not accepted then it will halt on non-final state.
Membership problems for type 0 languages are undecidable.
 Question 100

During DMA transfer, DMA controller transfers data ___

 A Directly from CPU to memory B Directly from memory to CPU C Directly between memory and registers D Directly between the I/O module and main memory
Computer-Organization       DMA
Question 100 Explanation:
The data transfer between a fast storage media such as magnetic disk and memory unit is limited by the speed of the CPU. Thus we can allow the peripherals directly communicate with each other using the memory buses, removing the intervention of the CPU. This type of data transfer technique is known as DMA or direct memory access. During DMA the CPU is idle and it has no control over the memory buses. The DMA controller takes over the buses to manage the transfer directly between the I/O devices and the memory unit.
There are 100 questions to complete.