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
| |
xy | |
yx | |
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) = (n-1)*(q-1)
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 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
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 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+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 | |
(n-1)
|
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 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?
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 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?
32 GB | |
64 GB | |
16 GB
| |
8 GB
|
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.
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 top-down 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) = (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?
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 |
Excess-3 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) + n2
Θ(n3) | |
Θ(n2 logn) | |
Θ(n2 /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.
Red Balck tree
| |
B+ Tree | |
AVL tree
| |
2-3 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 {am bn cm+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 out-put 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
| |
Data-manipulation language
| |
Data-Definition language
| |
Data-calculation 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.
LST-6, RST-2 | |
LST-5, RST-3
| |
LST-3, RST-5
| |
LST-2, RST-6
|
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; }
5 14 | |
5 9 | |
14 5 | |
9 5
|
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) + nO(n2)
| |
O(n/2) | |
O(n)
| |
O(logn)
|
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
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 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 ____
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 non-duplicate 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 SQL-the 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(n2 logn) | |
O(n2) |
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(n2)
|
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 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?
8 | |
1024 | |
16 | |
128 |
= 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}
m | |
n | |
5 | |
2 |

∴ 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?
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(n2 logn)
| |
O(nlogn)
| |
O(n2)
|
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 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
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 context-free 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 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
III and IV | |
I and IV | |
I and II
| |
II and IV |
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 ___
Directly from CPU to memory | |
Directly from memory to CPU
| |
Directly between memory and registers
| |
Directly between the I/O module and main memory
|