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.
Relational query languages  
Relational algebra
 
Flow diagram  
Schema Diagram 
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____.
7 Seconds  
4 seconds
 
6 seconds
 
5 seconds 
∴ Avg. WT = 4+0+11/3 = 5
Question 3 
According to boolean law: (A')' = ?
0  
A  
(A')'
 
1 
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 ______
GCD of X and Y
 
x^{y}  
y^{x}  
HCF of x and y  
Both A and D 
Question 5 
The working set model is used in memory management to implement the concept of:
Principle of locality
 
Thrashing
 
Paging
 
Segmentation

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.
Stack
 
Tree  
Dequeue
 
Queue 
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) = (n1)*(q1)
Letter e encryption key chosen. How is this encryption key selected?
e is chosen as a relative prime to q
 
e is chosen as a relative prime to p  
e is chosen as a relative prime to Φ(n)
 
e is chosen as a relative prime to n

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"
X is undecidable but partially decidable
 
X is not a decision problem
 
X is decidable
 
X is undecidable but not even partially decidable

Question 9 
The expression for commutative law is given by:
A+AB=A
 
A+AB=B
 
A+B=B+A  
AB+AA'=A

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  mnoChoose correct statement from the following:
The grammar is LL(4)
 
The grammar is LL(3)  
The grammar is LL(2)  
The grammar is 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 
Consider the classful addressing, the IP address 128.252.144.84 denotes:
0.0.0.0 as network ID and 128.252.252.84 as node ID  
128.0.0.0 as network ID and 128.252.127.84 as node ID  
128.252.144.0 as network ID and 128.252.144.84 as node ID
 
128.252.0.0 as network ID and 128.252.144.84 as node ID

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?
Only I  
Only II  
None  
I and II

A circuitlevel gateway is a type of firewall. Circuitlevel gateways work at the session layer of the OSI model, or as a "shimlayer" 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
EI Gemal
 
Rabin  
AES  
RSA

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 publickey 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+b)*a  
b+(a+b)*b  
b+a*b*  
b+a*b

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:
It makes implementation of lexical and syntax analysis easier  
It is difficult to generate executable code from high level language program
 
Syntax translations are easier for intermediate code generation
 
It enhances the portability of the compiler system program 
Question 16 
The maximum height of a binary tree with 'n' nodes is ____
(n+n)  
(n+1)
 
n  
(n1)

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)
II. Chains (for linked storage)
Only I  
Only II
 
I and II
 
None 
Hence Chains use close addressing whereas bucket uses open addressing.
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:
(k mod m) of the cache
 
(k mod c) of the cache  
(k mod 2c) of the cache
 
(k mod 2cm) of the cache

Therefore the k^{th} 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?
Only 2  
Only 1  
1 and 2
 
Neither 1 nor 2

S2 is true. The given definition of complete binary tree is correct.
Question 20 
Consider the Unix inode 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?
32 GB  
64 GB  
16 GB
 
8 GB

No. of addresses that can fit in one block = size of block/size of address = 2^{10}B/2^{2}B = 2^{8}
∴ The maximum file size,
= (Direct address + 1 single indirect + 1 double indirect + 1 triple indirect) × Block size
= (12 + 2^{8} + 2^{8} × 2^{8} + 2^{8} × 2^{8} × 2^{8}) × 2^{10}
≌ 2^{34} = 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.
event, condition, actor
 
entity, condition, action  
event, question, action  
event, condition, action 
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?
Presentation  
Transport  
Data link  
Session

Question 23 
Digital certificates are described using ____ format.
X.509
 
X.510  
X.508  
X.409 
Question 24 
___ command is used to enable, disable, modify or drop a constraint in SQL
MODIFY Table
 
DEFINE Table
 
ADD Column  
ALTER Table

Question 25 
Which is equivalent CFG without useless symbols for the given grammar:
S → PQ  p, P → p
S → PQ  
S → p  
S → P, P → p  
S → P  p, P → p 
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 topdown parser use while parsing a input string?
The input is assumed to be scanned in left to right order.
Topmost derivation  
Leftmost derivation traced out in reverse
 
Leftmost derivation  
Rightmost derivation

Question 27 
Polynomial addition is implemented using ___ data structure.
Trees  
Queue  
Linked List  
Stack

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.
Foreign key  
Super key
 
Scheme  
key

Question 29 
For implementation of recursion system uses ____ data structure.
Linked list
 
Deque  
Stack  
Queue

Question 30 
Which of the following statement is true?
The parsers canonical LR and LALR have the same power
 
LALR parser is more important than canonical LR parser
 
SLR parser is more powerful than LALR parser
 
Canonical LR parser is more powerful than LALR parser

CLR > LALR > SLR
Question 31 
Page fault occurs when
The page is an main memory
 
The page has an address, which cannot be loaded
 
The page is not in main memory  
The page is not in cache memory 
Question 32 
Queue structure is used in ____
Polynomial addition  
Recursion
 
Depth First search algorithm
 
Breadth First search algorithm

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?
23  
40  
37  
13 
e * d ≡ 1 mod φ(n)
Lets first find φ(n),
φ(n) = (p1)(q1)
= (71)(111)
= 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?
1 only  
1 and 2 only
 
1 and 4
 
2 and 3

Question 35 
The term cycle stealing is used in context of:
Interrupt based data transfer
 
Polling mode data transfer
 
DMA based data transfer  
clock cycle overriding

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?
(AB) (AB.)'
 
((A'B'),(AB.))'
 
((A'B')+(AB.))'  
(AB)'.AB 
Question 37 
Excess3 code of decimal number 2 is:
0101  
1010
 
1100
 
0011 
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.
62 ns  
82 ns
 
80 ns
 
72 ns

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) + n^{2}
Θ(n^{3})  
Θ(n^{2} logn)  
Θ(n^{2} /2)  
Θ(n^{2})

a = 4, b = 2, k = 2, p = 0
So, a = b^{k} and p > 1
According to master’s theorem,
= O(n^{logba} log^{p+1}n)
= O(n^{2}log n)
Question 40 
In ____balance factor of a node is the difference between left subtree and right subtree.
Red Balck tree
 
B+ Tree  
AVL tree
 
23 Tree

Question 41 
The language generated by following grammar is:
S > aSa  bSb  ε
Even length palindrome  
a^m b^n n>=0, m>=0
 
Odd length palindrome
 
a^n b^m n>=1, m>=1 
{ε,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 {a^{m} b^{n} c^{m+n}  m, n>=1} is:
Regular
 
Type 0 but context sensitive
 
Context free but not regular  
Context sensitive but not context free

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
III. Address bus width
I and III
 
I, II and III  
Only I
 
Only II 
Question 44 
In D flip flop the output state Q is related with D input in what way?
Q is dependent of D
 
Q is same as D  
Q is independent of D
 
Q is complement of D

Question 45 
____includes a query language and commands to insert tuples into, delete tuples from, and modify tuples in the database.
Query language
 
Datamanipulation language
 
DataDefinition language
 
Datacalculation language

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 → ε
I only
 
I and II
 
I and III  
I and IV

(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 ___
Registers
 
DMA  
Cache Memory
 
Interrupt

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.
Asymmetric  
Zero knowledge
 
Symmetric  
Challenge response

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, 69How many numbers of nodes in Left Sub Tree(LST) and Right Sub Tree(RST) of root node.
LST6, RST2  
LST5, RST3
 
LST3, RST5
 
LST2, RST6

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=xy); printf("%d%d", x,y); return 0; }
5 14  
5 9  
14 5  
9 5

x=(x=x+y)(y=xy); // 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=xy will be calculated and the value of y will become (y=149=5). And finally the value (145) 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) + nO(n^{2})
 
O(n/2)  
O(n)
 
O(logn)

a = 4, b = 2, k = 1
Now, a> b^{k}
So according to master’s theorem,
O(n^{logba}) = O(n^{2})
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
Foreign key  
Natural key  
Candidate Key  
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)
T T F T
 
F T T T  
T T T F
 
F T T F 
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
Not LR(1) but LALR(1)  
Neither LR(1) nor LALR(1)  
LR(1) and LALR(1)
 
LR(1) but not LALR(1)

Since there is no RR or SR conflict hence the given grammar is LR(1).
Now, for LALR(1) let’s combine I_{1} & I_{3},
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 ____
2  
5  
8  
3 
So the minimum state deterministic finite state automaton accepting language is 5.
Question 56 
____ is First in last out kind of data structure.
Stack  
Array  
Deque
 
Queue

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 sorting algorithm is stable if it preserves the order of all keys  
A sorting algorithm is stable if it preserves the order of nonduplicate keys  
A sorting algorithm is stable if it preserves the order of duplicate keys
 
A sorting algorithm is stable if it doesn't preserve 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 HWhat is the postorder traversal of the same tree?
D F E B H C G A  
D F E B G H C A
 
D F E H B G C A
 
D F E B H G C A

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 SQLthe function avg,min,max,sum,count are called as ____
Aggregate function  
Adjunct function  
Scalar operation
 
Set Operation

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; }
7 6 6
 
6 7 8  
6 7 7  
5 6 7

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?
9  
7  
8  
10 
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
p
 
σ  
Θ  
⟕

Question 63 
Consider the binary search tree with n elements. The time required to search given element is ___
O(logn)  
O(n logn)
 
O(n^{2} logn)  
O(n^{2}) 
Question 64 
In database management system ACID property refers to:
Authenticity, consistency, Isolation and Durability
 
Atomicity, Confidentiality, Isolation and Durability
 
Atomicity, consistency, Isolation and Durability
 
Atomicity, Confidentiality, Integrity and Durability

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?
Any logic expression can be implemented using only NAND gates  
Any logic expression can be implemented using only EXNOR gates
 
Any logic expression can be implemented using only NOT gates
 
Any logic expression can be implemented using only XOR gates

Question 66 
Mutual Exclusion problem occurs ______
Between two processes that use different resources of different machines  
Between two disjoint processes that do not interact
 
Among processes that share resources
 
Among processes that do not use the same resource 
Question 67 
The time complexity of searching an element in linked n will be:
O(nlogn)
 
O(logn)
 
O(n)
 
O(n^{2})

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?
0.0443s and 936 Kbps
 
0.0843s and 1536 Kbps
 
0.1043s and 1736 kbps  
0.0943s and 1636 kbps

Question 69 
MSB stands for
Middle significant bit
 
Measured Significant bit  
Maximum significant bit
 
Most significant bit

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?
RR
 
Priority
 
SJF
 
FCFS

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
Only statement 1 is correct
 
All statements are correct
 
Statement 3 is not correct
 
Only statement 1 and 2 is correct

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?
Every regular language is also a context free language
 
Every non deterministic turing machine can be converted to an equivalent deterministic Turing machine
 
Every subset of recursively enumerable set is recursive  
Every NFA can b converted into equivalent DFA

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 ___
{T  p(T)}
 
{ P()  T }
 
{ p()  T}
 
{T  P()  T} 
{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  acFind the first() of S
{a, b, ε}  
{ε}  
{a,ε}  
{a,b,c,ε}

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.
0.92  
0.82  
0.96
 
0.86

Question 76 
Which is the correct method to obtain 10's complement of a decimal number?
The minuend is added to the 10's complement of the subtrahend and carry is dropped  
The 10's complement of a decimal number is equal to 9's complement of given number minus one
 
The subtrahend is added to the 10's complement of the minuend and carry is dropped  
The 10's complement of a decimal number is equal to 9's complement of given number plus one 
Question 77 
Maximum throughput of slotted ALOHA network is:
18.4%
 
36.8%  
50%
 
35.8%

And maximum throughput of pure aloha is 18.4%.
Question 78 
Which one of the following is TRUE?
Every regular grammar is LL(1) and every regular set does not have an LR(1) grammar
 
Every regular grammar is not LL(1) and every regular set does not have an LR(1) grammar  
Every regular grammar is LL(1) and every regular has an LR(1) grammar
 
Every regular grammar is not LL(1) and every regular set has an LR(1) grammar 
Every regular set (or language) has a rightlinear deterministic (or leftfactored) 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?
8  
1024  
16  
128 
= 2^{14} Bytes/2^{10} bits
= 2^{14}×2^{3}bits/2^{10}bits
= 2^{7}
= 128
Question 80 
Number of states in DFA accepting the following languages is:
L = {a^{n} b^{2m}  n, m>=1}
m  
n  
5  
2 
∴ No. of states in DFA for the language L = {a^{n}b^{2m}  n,m ≥ 1} is 5.
Question 81 
Which of the following has lowest access time?
Main Memory
 
Optical disk
 
Cache
 
Registers

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+B  
A+B'  
B+A'  
B'+A'

= (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
Only II is true  
Both I and II are false
 
Both I and II are true
 
Only I is true

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?
Insertion is done from front end
 
Insertion and deletion can be done at front and rear ends  
Deletion is done from rear end
 
Insertion is done only from rear end

Question 85 
A negative edge triggered flip flop transfers data from input on the:
LOW to HIGH transition of clock pulse
 
BEFORE transition of clock pulse
 
HIGH to LOW transition of clock pulse
 
WITHOUT 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)
SELECT S.sname, S.rating FROM Sailors S, Reserves R WHERE S.sid=R.sid AND R.bid = B.bid AND B.color='red'  
SELECT S.sname FROM Sailors S, Reserves R, Boats B WHERE S.sid=R.sid AND R.bid = B.bid AND B.color='red'  
SELECT S.sname FROM Sailors S, Reserves R, Boats B WHERE S.sid=R.sid AND B.color='red'  
SELECT S.sname FROM Sailors S, Reserves R, Boats B WHERE R.bid=B.bid AND B.color='red' 
Question 87 
What is the complexity of merge sort?
O(n)
 
O(n^{2} logn)
 
O(nlogn)
 
O(n^{2})

Question 88 
___ of graph is a vertex whose removal disconnects graph
Start vertex
 
Middle point
 
Terminal vertex
 
Articulation point/Cut vertex

Question 89 
Canonical SOP form of logic expression consists of only ____
Maxterms  
Laterals
 
Cell
 
Minterms 
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 truthtable, 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
Neither LALR(1) nor SLR(1)
 
LALR(1) but not SLR(1)
 
Not LALR(1) but SLR(1)
 
LALR(1) and 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.
First normal
 
Third normal
 
Second normal
 
Fourth normal

Question 92 
In hashing, collision results when ____
An attempt is made to delete a record at full primary bucket  
An attempt is made to insert a record at full primary bucket
 
An attempt is made to insert a record anywhere in primary bucket
 
An attempt is made to insert a record at empty primary bucket

Question 93 
In SQL, the ___ command is used to recompile view
ALTER VIEW
 
COMPILE VIEW
 
CREATE VIEW  
DEFINE VIEW

Question 94 
The multiplicand register and multiplier register of hardware circuit implementation of booth's algorithm have (11101) and (1100). the result shall be:
(812)_{10}  
(812)_{10}
 
(12)_{10}
 
(12)_{10}

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.
Relational calculus  
Referential Integrity
 
Relational Algebra  
Relations

Question 96 
The class of contextfree grammar is not closed under ____ operations
Concatenation
 
Intersection
 
Star  
Union

Question 97 
Which of the following is a unary operation?
Intersection  
Projection
 
Join  
Cartesian Product

Question 98 
Which of the following statement is false about Prim's algorithm?
Initially the roots key and nodes are initialized to zero
 
It may use binomial max heap to represent the primary queue
 
The complexity is O(E log V) using binary heap
 
The time complexity is O(E + V log V) using Fibonacci Heap

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 contextfree languages
II. Whether a given contextfree languages is regular
III. Whether a finite state automation halts on all inputs
IV. Membership problem for type 0 languages
III and IV  
I and IV  
I and II
 
II and IV 
Whether a given contextfree 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 nonfinal state.
Membership problems for type 0 languages are undecidable.
Question 100 
During DMA transfer, DMA controller transfers data ___
Directly from CPU to memory  
Directly from memory to CPU
 
Directly between memory and registers
 
Directly between the I/O module and main memory
