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