## Nielit Scientist-C 2016 march

Question 1 |

The advantage of better testing in software development is in

Waterfall model | |

Prototyping | |

Iterative | |

All of these |

Question 1 Explanation:

● Iterative development was created as a response to inefficiencies and problems found in the waterfall model. A simplified version of a typical iteration cycle in agile project management.

● The basic idea behind this method is to develop a system through repeated cycles (iterative) and in smaller portions at a time (incremental), allowing software developers to take advantage of what was learned during development of earlier parts or versions of the system. Learning comes from both the development and use of the system, where possible key steps in the process start with a simple implementation of a subset of the software requirements and iteratively enhance the evolving versions until the full system is implemented. At each iteration, design modifications are made and new functional capabilities are added.

● The basic idea behind this method is to develop a system through repeated cycles (iterative) and in smaller portions at a time (incremental), allowing software developers to take advantage of what was learned during development of earlier parts or versions of the system. Learning comes from both the development and use of the system, where possible key steps in the process start with a simple implementation of a subset of the software requirements and iteratively enhance the evolving versions until the full system is implemented. At each iteration, design modifications are made and new functional capabilities are added.

Question 2 |

The file manager is responsible for

naming files | |

saving files | |

deleting files | |

all the above |

Question 2 Explanation:

● A file manager is a software program that helps a user manage all the files on their computer. For example, all file managers allow the user to view, edit, copy, and delete the files on their computer storage devices.

● Note: Although a file manager helps the user view and manage their files, it is the operating system that is responsible for accessing and storing the files on a storage device.

● Note: Although a file manager helps the user view and manage their files, it is the operating system that is responsible for accessing and storing the files on a storage device.

Question 3 |

Every Boyce-Codd Normal Form(BCNF) decomposition is

dependency preserving | |

not dependency preserving | |

need be dependency preserving | |

none of these |

Question 3 Explanation:

Normalization requires definitely loss less decomposition but not dependency preserving. But BCNF need to be functional dependency.

Question 4 |

A functional dependency of the form x → y is trivial if

y ⊆ x | |

y ⊂ x | |

x ⊆ y | |

x ⊂ y and y ⊂ x |

Question 4 Explanation:

Trivial − If a functional dependency (FD) X → Y holds, where Y is a subset of X, then it is called a trivial FD. Trivial FDs always hold.

Question 5 |

A primary key, if combined with a foreign key creates

parent child relationship between the tables that connect them | |

many-to-many relationship between the tables that connect them | |

network model between the tables connect them | |

none of these |

Question 5 Explanation:

Using the two relationships mother and father provides us a record of a child’s mother, even if we are not aware of the father’s identity; a null value would be required if the ternary relationship parent is used. Using binary relationship sets is preferable in this case.

Question 6 |

Memory mapped displays

are utilized for high resolution graphics such as maps | |

uses ordinary memory to store the display data in character form | |

stores the display data as individual bits | |

are associated with electromechanical teleprinters |

Question 6 Explanation:

● Graphs can be displayed on a screen by writing character values into a special area of RAM within the video controller.
● Prior to cheap RAM that enabled bit-mapped displays, this character cell method was a popular technique for computer video displays.

Question 7 |

In real time operating systems, which of the following is the most suitable scheduling scheme?

Round Robin | |

First come first serve | |

preemptive | |

random scheduling |

Question 7 Explanation:

● A real-time operating system (RTOS) is any operating system (OS) intended to serve real-time applications that process data as it comes in, typically without buffer delays.

● Processing time requirements (including any OS delay) are measured in tenths of seconds or shorter increments of time.

● A real time system is a time bound system which has well defined fixed time constraints. Processing must be done within the defined constraints or the system will fail. They either are event driven or time sharing.

● Event driven systems switch between tasks based on their priorities while time sharing systems switch the task based on clock interrupts. Most RTOS’s use a pre-emptive scheduling algorithm.

● Processing time requirements (including any OS delay) are measured in tenths of seconds or shorter increments of time.

● A real time system is a time bound system which has well defined fixed time constraints. Processing must be done within the defined constraints or the system will fail. They either are event driven or time sharing.

● Event driven systems switch between tasks based on their priorities while time sharing systems switch the task based on clock interrupts. Most RTOS’s use a pre-emptive scheduling algorithm.

Question 8 |

If there are 32 segments, each of size 1 K byte, then the logical address should have

13 bits | |

14 bits | |

15 bits | |

16 bits |

Question 8 Explanation:

There are 32 segments which is equal to 2

Each segment size 1K byte =2

Then total number of bits that logical address consists is 15 bits.

^{5}Each segment size 1K byte =2

^{ 10}Then total number of bits that logical address consists is 15 bits.

Question 9 |

Which of the following can be accessed by transfer vector approach of linking?

External data segments | |

External subroutines | |

data located in other procedure | |

All of these |

Question 9 Explanation:

● The transfer vector approach is straightforward, but requires additional memory at execution time for the transfer vector and additional time due to the indirect references. Indexing or indirection on externals may not occur correctly with the transfer vector approach.

● Data segment stores program data. This data could be in form of initialized or uninitialized variables, and it could be local or global.

● External subroutines are routines/procedures that are created and maintained separately from the program that will be calling them

● Data segment stores program data. This data could be in form of initialized or uninitialized variables, and it could be local or global.

● External subroutines are routines/procedures that are created and maintained separately from the program that will be calling them

Question 10 |

Relocation bits used by relocating loader are specified by

relocating loader itself | |

Linker | |

Assembler | |

Macro Processor |

Question 10 Explanation:

● A linker or link editor is a computer utility program that takes one or more object files generated by a compiler and combines them into a single executable file, library file, or another 'object' file.

● Relocating loader in which some of the addresses in the program to be loaded are expressed relative to the start of the program rather than in absolute form.

● An assembler is a type of computer program that interprets software programs written in assembly language into machine language, code and instructions that can be executed by a computer.

● A macro processor is a program that copies a stream of text from one place to another, making a systematic set of replacements as it does so. Macro processors are often embedded in other programs, such as assemblers and compilers. Sometimes they are standalone programs that can be used to process any kind of text.

● Relocating loader in which some of the addresses in the program to be loaded are expressed relative to the start of the program rather than in absolute form.

● An assembler is a type of computer program that interprets software programs written in assembly language into machine language, code and instructions that can be executed by a computer.

● A macro processor is a program that copies a stream of text from one place to another, making a systematic set of replacements as it does so. Macro processors are often embedded in other programs, such as assemblers and compilers. Sometimes they are standalone programs that can be used to process any kind of text.

Question 11 |

The most powerful parser is

SLR | |

LALR | |

Canonical LR | |

Operator Precedence |

Question 11 Explanation:

Canonical LR is more powerful than SLR as every grammar which can be parsed by SLR parser, can also be parsed by CLR parser.

So CLR > LALR > SLR

In computer science, a canonical LR parser or LR(1) parser is an LR(k) parser for k=1, i.e. with a single lookahead terminal. The special attribute of this parser is that any LR(k) grammar with k>1 can be transformed into an LR(1) grammar.However, back-substitutions are required to reduce k and as back-substitutions increase, the grammar can quickly become large, repetitive and hard to understand. LR(k) can handle all deterministic context-free languages.

So CLR > LALR > SLR

In computer science, a canonical LR parser or LR(1) parser is an LR(k) parser for k=1, i.e. with a single lookahead terminal. The special attribute of this parser is that any LR(k) grammar with k>1 can be transformed into an LR(1) grammar.However, back-substitutions are required to reduce k and as back-substitutions increase, the grammar can quickly become large, repetitive and hard to understand. LR(k) can handle all deterministic context-free languages.

Question 12 |

YACC builds up

SLR parsing table | |

Canonical LR parsing table | |

LALR parsing table | |

None of these |

Question 12 Explanation:

● YACC (Yet Another Compiler-Compiler) is a computer program.

● It is a Look Ahead Left-to-Right (LALR) parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specifically a LALR parser, based on an analytic grammar written in a notation similar to Backus–Naur Form (BNF)

● It is a Look Ahead Left-to-Right (LALR) parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specifically a LALR parser, based on an analytic grammar written in a notation similar to Backus–Naur Form (BNF)

Question 13 |

Context free grammar can be recognized by

finite state automaton | |

2-way linear bounded automata | |

pushdown automata | |

Both (B) and (C) |

Question 13 Explanation:

Question 14 |

If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called

Decidable | |

Undecidable | |

interpretive | |

non-deterministic |

Question 14 Explanation:

● A decision problem is a function that associates with each input instance of the problem a truth value true or false.

● A decision problem is decidable if there exists a decision algorithm for it. Otherwise it is undecidable.

● For simple machine models, such as finite automata or pushdown automata, many decision problems are solvable. In the case of deterministic finite automata, problems like equivalence can be solved even in polynomial time

● A decision problem is decidable if there exists a decision algorithm for it. Otherwise it is undecidable.

● For simple machine models, such as finite automata or pushdown automata, many decision problems are solvable. In the case of deterministic finite automata, problems like equivalence can be solved even in polynomial time

Question 15 |

The defining language for developing a formalism in which language definitions can be stated, is called

Syntactic meta language | |

Decidable language | |

Intermediate language | |

High level language |

Question 15 Explanation:

● A high-level language is any programming language that enables development of a program in a much more user-friendly programming context and is generally independent of the computer's hardware architecture.

● Intermediate language (IL) is an object-oriented programming language designed to be used by compilers for the .NET Framework before static or dynamic compilation to machine code. The IL is used by the .NET Framework to generate machine-independent code as the output of compilation of the source code written in any .NET programming language.

● A language L is called Turing-decidable (or just decidable), if there exists a Turing Machine M such that on input x, M accepts if x ∈ L, and M rejects otherwise. L is called undecidable if it is not decidable.

● From the perspective of a syntactic meta language the grammatical sentences are a certain subset of the set of all possible strings of primitive symbols and the transformation rules depict certain relations between such strings of symbols

● Intermediate language (IL) is an object-oriented programming language designed to be used by compilers for the .NET Framework before static or dynamic compilation to machine code. The IL is used by the .NET Framework to generate machine-independent code as the output of compilation of the source code written in any .NET programming language.

● A language L is called Turing-decidable (or just decidable), if there exists a Turing Machine M such that on input x, M accepts if x ∈ L, and M rejects otherwise. L is called undecidable if it is not decidable.

● From the perspective of a syntactic meta language the grammatical sentences are a certain subset of the set of all possible strings of primitive symbols and the transformation rules depict certain relations between such strings of symbols

Question 16 |

In propositional logic, which of the following is equivalent to p → q?

~p → q | |

~p V q | |

~p V ~q | |

p → ~q |

Question 16 Explanation:

We can use a truth table to determine if two compound propositions are logically equivalent, i.e if they always have the same truth values.

Question 17 |

Regular expression (a|b)(a|b) denotes the set

{a,b,ab,aa} | |

{a,b,ba,bb} | |

{a,b} | |

{aa,ab,ba,bb} |

Question 17 Explanation:

● The Regular expression (a|b)(a|b) generates strings of length of 2.

● (a|b) means either a or b.

● The expression consists of two symbols of (a|b),which strings starting with either a or b and ending with either a or b.

● (a|b) means either a or b.

● The expression consists of two symbols of (a|b),which strings starting with either a or b and ending with either a or b.

Question 18 |

Two alternative package A and B are available for processing a database having 10

^{ k}records. Package A requires 0.0001^{2}n time units and package B requires 10nlog_{10}n time units to process n records. What is the smallest value of k for which package B will be preferred over A?12 | |

10 | |

6 | |

5 |

Question 18 Explanation:

As per given information Package B 10nlog

because n

Let n = 10

10(10

10

k ≤ 10

2k−k−1−4

k ≤ 10

k−5

According to the problem value 6 is suitable for K.

_{10} n is lesser than or equals to Package A 0.0001n^{2}0because n

^{2} is asymptotically larger than nlogn. Finally, 10nlog_{10} n ≤ 0.0001n^{2}Let n = 10

^{ k} records. Substitute into 10nlog_{10} n ≤ 0.0001n^{ 2}10(10

^{ k} )log_{ 10} 10^{ }k ≤ 0.0001(10^{ k} )^{ 2}10

^{ k+1} k ≤ 0.0001 × 10^{ 2k}k ≤ 10

2k−k−1−4

k ≤ 10

k−5

According to the problem value 6 is suitable for K.

Question 19 |

When a subroutine is called, then address of the instruction following the CAL instruction is stored in/on the

Stack pointer | |

Accumulator | |

Program Counter | |

Stack |

Question 19 Explanation:

● The program counter (PC), commonly called the instruction pointer (IP) in Intel x86 and Itanium microprocessors, and sometimes called the instruction address register (IAR),
the instruction counter, or just part of the instruction sequencer,is a processor register that indicates where a computer is in its program sequence.

● PC is incremented after fetching an instruction, and holds the memory address of ("points to") the next instruction that would be executed.

● Processors usually fetch instructions sequentially from memory, but control transfer instructions change the sequence by placing a new value in the PC. These include branches (sometimes called jumps), subroutine calls, and returns..

● PC is incremented after fetching an instruction, and holds the memory address of ("points to") the next instruction that would be executed.

● Processors usually fetch instructions sequentially from memory, but control transfer instructions change the sequence by placing a new value in the PC. These include branches (sometimes called jumps), subroutine calls, and returns..

Question 20 |

Start and stop bits are used in serial communication for

Error detection | |

Error Correction | |

Synchronization | |

Slowing down the communication |

Question 20 Explanation:

● The start and stop bits are used in asynchronous communication as a means of timing or synchronizing the data characters being transmitted.

● Without the use of these bits, the sending and receiving systems will not know where one character ends and another begins.

● Without the use of these bits, the sending and receiving systems will not know where one character ends and another begins.

Question 21 |

Repeaters function in

Physical layer | |

Data link layer | |

Network layer | |

Both (A) and (B) |

Question 21 Explanation:

● A repeater is an electronic device that receives a signal and retransmits it.

● Repeaters are used to extend transmissions so that the signal can cover longer distances or be received on the other side of an obstruction.

● Physical layer in the OSI model plays the role of interacting with actual hardware and signaling mechanism

● Repeaters are used to extend transmissions so that the signal can cover longer distances or be received on the other side of an obstruction.

● Physical layer in the OSI model plays the role of interacting with actual hardware and signaling mechanism

Question 22 |

What are the primary characteristics that distinguish a cell from a packet?

Cells are generally smaller that packets | |

Cells do not incorporate physical address | |

all cell have the same fixed length | |

packet cannot be switched |

Question 22 Explanation:

● Frames and packets, in general, can be of variable length, depending on their contents; in contrast, a cell is most often a message that is fixed in size.

● For example, the fixed-length, 53-byte messages sent in Asynchronous Transfer Mode (ATM) are called cells. Like frames, cells usually are used by technologies operating at the lower layers of the OSI model.

● For example, the fixed-length, 53-byte messages sent in Asynchronous Transfer Mode (ATM) are called cells. Like frames, cells usually are used by technologies operating at the lower layers of the OSI model.

Question 23 |

The graph theoretic concept will be useful in software testing is

Cyclomatic number | |

Hamiltonian Circuit | |

Eulerian cycle | |

None of these |

Question 23 Explanation:

● Cyclomatic complexity is a software metric used to indicate the complexity of a program.

● It is a quantitative measure of the number of linearly independent paths through a program's source code.

● Cyclomatic complexity is computed using the control flow graph of the program: the nodes of the graph correspond to indivisible groups of commands of a program, and a directed edge connects two nodes if the second command might be executed immediately after the first command.

● Cyclomatic complexity may also be applied to individual functions, modules, methods or classes within a program

● It is a quantitative measure of the number of linearly independent paths through a program's source code.

● Cyclomatic complexity is computed using the control flow graph of the program: the nodes of the graph correspond to indivisible groups of commands of a program, and a directed edge connects two nodes if the second command might be executed immediately after the first command.

● Cyclomatic complexity may also be applied to individual functions, modules, methods or classes within a program

Question 24 |

In testing phase, the effort distribution is upto

10% | |

20% | |

40% | |

50% |

Question 24 Explanation:

● Effort estimation is the process of predicting the most realistic amount of effort (expressed in terms of person-hours or money) required to develop or maintain software based on incomplete, uncertain and noisy input.

● Effort estimates may be used as input to project plans, iteration plans, budgets, investment analyses, pricing processes and bidding rounds.

● The strong overconfidence in the accuracy of the effort estimates is illustrated by the finding that, on average, if a software professional is 90% confident or “almost sure” to include the actual effort in a minimum-maximum interval, the observed frequency of including the actual effort is only 60-70%.

● Currently the term “effort estimate” is used to denote as different concepts such as most likely use of effort (modal value), the effort that corresponds to a probability of 50% of not exceeding (median), the planned effort, the budgeted effort or the effort used to propose a bid or price to the client

● Effort estimates may be used as input to project plans, iteration plans, budgets, investment analyses, pricing processes and bidding rounds.

● The strong overconfidence in the accuracy of the effort estimates is illustrated by the finding that, on average, if a software professional is 90% confident or “almost sure” to include the actual effort in a minimum-maximum interval, the observed frequency of including the actual effort is only 60-70%.

● Currently the term “effort estimate” is used to denote as different concepts such as most likely use of effort (modal value), the effort that corresponds to a probability of 50% of not exceeding (median), the planned effort, the budgeted effort or the effort used to propose a bid or price to the client

Question 25 |

How many flip-flop are needed to divide the input frequency by 64?

4 | |

5 | |

6 | |

8 |

Question 25 Explanation:

Giving an output frequency of 2

^{n}where “n” is the number of flip flops used in the sequence. 64=2^{6} .So the number of flip-flop required are 6.Question 26 |

The range of the numbers which can be stored in an eight bit register is

-128 to +127 | |

-128 to +128 | |

-999999 + +999999 | |

none of these |

Question 26 Explanation:

There are 2

^{8} (256) different possible values for 8 bits. When unsigned, it has possible values ranging from 0 to 255; when signed, it has -128 to 127.Question 27 |

The excess 3 code is also called

Cyclomatic redundancy code | |

Weighted code | |

Self complementing code | |

algebraic code |

Question 27 Explanation:

Excess-3 is a self-complementing code. This is because in Excess-3 code we get the 9's complement of a number by just complementing each bit that means by replacing a '0' by '1' and '1' by '0'

Question 28 |

Serial access memories are useful in applications where

data consists of numbers | |

short access time is required | |

each stored word is processed differently | |

data naturally needs to flow in and out in serial form |

Question 28 Explanation:

In serial-access media the access time depends on the data’s location and the position of the read-write head. The typical serial-access medium is magnetic tape.

Question 29 |

An external variable

is globally accessible by all functions | |

has a declaration "extern" associated with it when declared within a function | |

will be initialized to 0 if not initialized | |

All of these |

Question 29 Explanation:

An external variable can be accessed by all the functions in all the modules of a program. It is a global variable. For a function to be able to use the variable, a declaration or the definition of the external variable must lie before the function definition in the source code. Or there must be a declaration of the variable, with the keyword extern, inside the function.

Question 30 |

Micro programming is a technique for

Writing small programs effectively | |

Programming output/input routines | |

programming the microprocessors | |

Programming the control steps of a computer |

Question 30 Explanation:

● Microprogramming is a technique to implement the control logic necessary to execute instructions within a processor.

● It is based on the general idea of fetching low-level microinstructions from a control store and deriving the appropriate control signals to be active for a single clock cycle, as well as microprogram sequencing information, from each microinstruction.

● Although hybrid techniques exist, microprogramming is generally contrasted with hardwired implementation techniques.

● It is based on the general idea of fetching low-level microinstructions from a control store and deriving the appropriate control signals to be active for a single clock cycle, as well as microprogram sequencing information, from each microinstruction.

● Although hybrid techniques exist, microprogramming is generally contrasted with hardwired implementation techniques.

Question 31 |

A full binary tree with n non-leaf nodes contains

log _{2} n nodes | |

n+1 nodes | |

2n nodes | |

2n+1 nodes |

Question 31 Explanation:

● A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children

● In a binary tree - a tree where each non-leaf node has exactly two sons - number of leaves is n+1. Total number of nodes is 2n+1.

In the above tree,non-leaf nodes are 7 so total nodes are 2x7+1=15

● In a binary tree - a tree where each non-leaf node has exactly two sons - number of leaves is n+1. Total number of nodes is 2n+1.

**Full Binary Tree:**In the above tree,non-leaf nodes are 7 so total nodes are 2x7+1=15

Question 32 |

Two finite state machines are said to be equivalent if they

have same number of states | |

have same number of edges | |

have same number of states and edges | |

recognized same set of tokens |

Question 32 Explanation:

Two automata M

_{ 0} and M_{1} are said to be equivalent to each other if both accept exactly the same set of input strings.Question 33 |

In networking terminology UTP means

Unshielded twisted pair | |

Ubiquitous Teflon port | |

Uniformly Terminating port | |

Unshielded T-connector port |

Question 33 Explanation:

● Unshielded twisted pair, a popular type of cable that consists of two unshielded wires twisted around each other.

● Due to its low cost, UTP cabling is used extensively for local-area networks (LANs) and telephone connections

● Due to its low cost, UTP cabling is used extensively for local-area networks (LANs) and telephone connections

Question 34 |

Given following relation instance:
Which of the following functional dependencies are satisfied by the instance?

XY→ Z and Z → Y | |

YZ →X and Y → Z | |

YZ → X and X→ Z | |

XZ→ Y and Y → X |

Question 34 Explanation:

Functional dependency is represented by an arrow sign (→) that is, X→Y, where X functionally determines Y.

The left-hand side attributes determine the values of attributes on the right-hand side.

The left-hand side attributes determine the values of attributes on the right-hand side.

Question 35 |

Consider the schema R=(S,T,U,V) and the dependencies S→ T, T→ U, U→ V and V→ S. If R=(R1 and R2) be a decomposition such that R1 ∩R2= ∅ , then decomposition is

not in 2 NF | |

in 2 NF but not in 3 NF | |

in 3 NF not in 2 NF | |

in both 2NF and 3 NF |

Question 35 Explanation:

● R1 ∩ R2 = ∅. This makes the decomposition lossless join, as all the attributes are keys, R1 ∩ R2 will be a key of the decomposed relations (lossless condition says the common attribute must be a key in at least one of the decomposed relation).

● Now, even the original relation R is in 3NF (even BCNF) as all the attributes are prime attributes (in fact each attribute is a candidate key). Hence, any decomposition will also be in 3NF (even BCNF).

● Now, even the original relation R is in 3NF (even BCNF) as all the attributes are prime attributes (in fact each attribute is a candidate key). Hence, any decomposition will also be in 3NF (even BCNF).

Question 36 |

Odd parity of word can be conveniently tested by

OR gate | |

AND gate | |

NOR gate | |

XOR gate |

Question 36 Explanation:

● The Odd Parity gate and the XOR gate behave identically with two inputs; similarly, the even parity gate and the XNOR gate behave identically.

● But if there are more than two specified inputs, the XOR gate will emit 1 only when there is exactly one 1 input, whereas the Odd Parity gate will emit 1 if there are an odd number of 1 inputs.

● The XNOR gate will emit 1 only when there is not exactly one 1 input, while the Even Parity gate will emit 1 if there are an even number of 1 inputs.

● But if there are more than two specified inputs, the XOR gate will emit 1 only when there is exactly one 1 input, whereas the Odd Parity gate will emit 1 if there are an odd number of 1 inputs.

● The XNOR gate will emit 1 only when there is not exactly one 1 input, while the Even Parity gate will emit 1 if there are an even number of 1 inputs.

Question 37 |

What will be the value of x and y after execution of the following statement (C language)

n=5;

x=n++;

y=-x;

n=5;

x=n++;

y=-x;

5,-4 | |

6,-5 | |

6,-6 | |

5,-5 |

Question 37 Explanation:

Given statements are n=5, x=n++ and y=-x.

N++ is post increment statement, so first “n” will store into variable into “x” and later “n” value is incremented.

X value becomes 5 and y value become -5.

N++ is post increment statement, so first “n” will store into variable into “x” and later “n” value is incremented.

X value becomes 5 and y value become -5.

Question 38 |

How many bits are required to encode all twenty six letters, ten symbols, and ten numerals?

5 | |

6 | |

7 | |

46 |

Question 38 Explanation:

● It is 26 letters ×2 (Capital and small letters) plus twenty characters in total, so the total is 52+20=72.

● To find how many bits you would need, you would need to find the power of 2 that is equal to or the one immediately larger than your number. The number of bits would be the exponent of the power.

● In our case, since 128=2

● If you don’t want to codify both capital letters and small letters but only one family of 26 letters and be done with it, then you have 26+20=46 symbols. This time 2

● To find how many bits you would need, you would need to find the power of 2 that is equal to or the one immediately larger than your number. The number of bits would be the exponent of the power.

● In our case, since 128=2

^{7} >72>64=2^{6} , the power immediately larger than 72 would be 128=27, so you would need 7 bits, which can codify 128 symbols.● If you don’t want to codify both capital letters and small letters but only one family of 26 letters and be done with it, then you have 26+20=46 symbols. This time 2

^{6} =64>46>32=2^{5} , so the power immediately larger than 46 would be 64=2^{6} ; so 6 bits needed .Question 39 |

In C programming language, if the first and the second operands of operator + are of types int and float, respectively, the result be of type

int | |

float | |

char | |

long int |

Question 39 Explanation:

Expressions don’t have a type. Expressions can result in a value which has a type.

The rules for implicit type casting are as follows:

Integer Promotion: All types below int, like char and short are converted to int.

If still types other than int remain, following rules are executed by order

● If long double exists, all are converted to long double.

● If double exists, all are converted to double.

● If float exists, all are converted to float, and so on.

The rules for implicit type casting are as follows:

Integer Promotion: All types below int, like char and short are converted to int.

If still types other than int remain, following rules are executed by order

● If long double exists, all are converted to long double.

● If double exists, all are converted to double.

● If float exists, all are converted to float, and so on.

Question 40 |

If the input J is Connected through K input of J-K, then flip-flop will behave as a

D type flip-flop | |

T type flip-flop | |

S-R flip flop | |

Toggle switch |

Question 40 Explanation:

If J=K=1,then Q

_{n+1} = (Q_{n} ) ’ , so that the J-K Flip-Flop is converted into a T-type Flip-Flop. This unit changes state with each clock pulse and hence it acts as a toggle switch.Question 41 |

To build a mod-19 counter the number of flip-flop required is

3 | |

5 | |

7 | |

8 |

Question 41 Explanation:

For a mod N counter the number of flip flops required is less than or equal to 2 raised to power n where n is a positive integer.

N<= 2

Hence,

For a mod 10 counter, 10< 2

For a mod 16 counter, 16=2

For a mod 32 counter, 32=2

N<= 2

^{n}Hence,

For a mod 10 counter, 10< 2

^{4} . So 4 flip flops are required.For a mod 16 counter, 16=2

^{ 4} . So again 4 flip flops are required.For a mod 32 counter, 32=2

^{5} . So 5 flip flops are required.Question 42 |

A stable multivibrator are used as

comparator circuit | |

squaring circuit | |

frequency to voltage converter | |

voltage to frequency converter |

Question 42 Explanation:

● A multivibrator is a one type of electronic circuit, that is used to implement a two state system like flip-flops, timers and oscillators.

● Multivibrators are classified into three types based on the circuit operation, namely Astable multivibrators, Bistable multivibrators and Monostable multivibrators.

● The astable multivibrator is not stable and it repeatedly switches from one state to the other. In monostable multivibrator, one state is stable and remaining state is unstable.

● When the power is turned ON consider the flip flop is cleared initially, then the o/p of the inverter will be high. The charging of the capacitor will be done using two resistors R1& R2. When the voltage of the capacitor goes above 2/3 Vcc, then the output of the higher comparator will be High, it changes the control flip flop

● Multivibrators are classified into three types based on the circuit operation, namely Astable multivibrators, Bistable multivibrators and Monostable multivibrators.

● The astable multivibrator is not stable and it repeatedly switches from one state to the other. In monostable multivibrator, one state is stable and remaining state is unstable.

● When the power is turned ON consider the flip flop is cleared initially, then the o/p of the inverter will be high. The charging of the capacitor will be done using two resistors R1& R2. When the voltage of the capacitor goes above 2/3 Vcc, then the output of the higher comparator will be High, it changes the control flip flop

Question 43 |

The astable multivibrator has

two quasi stable states | |

two stable states | |

one stable and one quasi-stable state | |

none of these |

Question 43 Explanation:

A multivibrator is an electronic circuit used to implement a variety of simple two-state devices such as relaxation oscillators, timers and flip-flops. It consists of two amplifying devices (transistors, vacuum tubes or other devices) cross-coupled by resistors or capacitors.

Question 44 |

For x and y are variables as declared below
double x=0.005, y=-0.01;
what is the value of ceil(x+y), where is a function to compute ceiling of a number?

1 | |

0 | |

0.005 | |

0.5 |

Question 44 Explanation:

x+y = 0.005-0.01 =-0.005

Description

CEIL(x) rounds the number x up.

Examples

CEIL(1.3) equals 2

CEIL(-1.6) equals -1

Description

CEIL(x) rounds the number x up.

Examples

CEIL(1.3) equals 2

CEIL(-1.6) equals -1

Question 45 |

An instruction used to set the carry flag in a computer can be classified as

data transfer | |

process control | |

logical | |

program control |

Question 45 Explanation:

● The carry flag is a single bit in a system status register/flag register used to indicate when an arithmetic carry or borrow has been generated out of the most significant arithmetic logic unit (ALU) bit position.

● The carry flag enables numbers larger than a single ALU width to be added/subtracted by carrying (adding) a binary digit from a partial addition/subtraction to the least significant bit position of a more significant word.

● It is also used to extend bit shifts and rotates in a similar manner on many processors (sometimes done via a dedicated X flag).

● For subtractive operations, two (opposite) conventions are employed as most machines set the carry flag on borrow while some machines (such as the 6502 and the PIC) instead reset the carry flag on borrow (and vice versa).

● The carry flag enables numbers larger than a single ALU width to be added/subtracted by carrying (adding) a binary digit from a partial addition/subtraction to the least significant bit position of a more significant word.

● It is also used to extend bit shifts and rotates in a similar manner on many processors (sometimes done via a dedicated X flag).

● For subtractive operations, two (opposite) conventions are employed as most machines set the carry flag on borrow while some machines (such as the 6502 and the PIC) instead reset the carry flag on borrow (and vice versa).

Question 46 |

Micro program is

the name of source program in micro computers | |

the set of instructions indicating the primitive operations in a system | |

primitive form of macros used in assembly language programming | |

program of very small size |

Question 46 Explanation:

● Micro program is a set of microinstructions that defines the individual operations that a computer carries out in response to a machine-language instruction.

● A microinstruction is a bit pattern in which each bit (or combination of bits) drives the control signals of the hardware.

● A microinstruction is a bit pattern in which each bit (or combination of bits) drives the control signals of the hardware.

Question 47 |

If a processor does not have any stack pointer register, then

if cannot have subroutine call instruction | |

it can have subroutine call instruction, but no nested subroutine calls are possible, but no nested subroutine calls | |

nested subroutine calls are possible, but interrupts are not | |

all sequences of subroutine calls and also interrupts are possible |

Question 47 Explanation:

● A subroutine is a reusable program module. A main program can call or jump to the subroutine one or more times.

● The stack is an area of memory; the stack pointer is the address of the last value pushed onto the stack

● The main thing you will be using the stack for is saving data when a subroutine is called.

● You call a subroutine that is going to calculate some value and pass it back to the main program. After you call the subroutine, you can just push all the data onto the stack before executing any instructions in the subroutine. The subroutine can then use all the registers for its internal use and store the data that the main program needs in one of the memory locations. At the end of the subroutine, you can pop the stored data off of the stack and then return control to the main program.

● If stack pointer register is not available then activation records in the stack cannot be created. So it cannot have subroutine call instruction.

● The stack is an area of memory; the stack pointer is the address of the last value pushed onto the stack

● The main thing you will be using the stack for is saving data when a subroutine is called.

● You call a subroutine that is going to calculate some value and pass it back to the main program. After you call the subroutine, you can just push all the data onto the stack before executing any instructions in the subroutine. The subroutine can then use all the registers for its internal use and store the data that the main program needs in one of the memory locations. At the end of the subroutine, you can pop the stored data off of the stack and then return control to the main program.

● If stack pointer register is not available then activation records in the stack cannot be created. So it cannot have subroutine call instruction.

Question 48 |

In a microcomputer, WAIT states are used to

make the processor wait during a DMA operation | |

make the processor wait during a power interrupt processing | |

make the processor wait during a power shutdown | |

interface slow peripherals to the processor |

Question 48 Explanation:

● A wait state is a situation in which a computer program or processor is waiting for the completion of some event before resuming activity. A program or process in a wait state is inactive for the duration of the wait state.

● A wait state is a delay experienced by a computer processor when accessing external memory or another device that is slow to respond.

● A wait state is a delay experienced by a computer processor when accessing external memory or another device that is slow to respond.

Question 49 |

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. Total time required for this is

O(logn) | |

O(n) | |

O(nlogn) | |

O(n ^{2} ) |

Question 49 Explanation:

Possibility-1: Inserting an element into binary(either max or min) heap takes O(logn) for all cases, but in question they clearly mentioned that n elements. O(n) complexity can be to take
the ‘n’ elements of the heap and other ‘n’ elements together and construct heap So, O(n).

Possibility-2: If you inserted one after the other then time complexity will be O(nlogn). For one insertion it will take O(logn) because need to apply maxHeapify. For n elements it will be O(nlogn)

Note: We can also insert all the elements once, there will be no difference on time complexity.

But according GATE solution they given possibility-1.

Possibility-2: If you inserted one after the other then time complexity will be O(nlogn). For one insertion it will take O(logn) because need to apply maxHeapify. For n elements it will be O(nlogn)

Note: We can also insert all the elements once, there will be no difference on time complexity.

But according GATE solution they given possibility-1.

Question 50 |

You are given the postorder traversal,p, of a binary search tree on the n elements 1,2,..,n. You have to determine the unique binary search tree has P as its postorder
traversal. What is the time complexity of the most efficient algorithm for doing this?

O(logn) | |

O(n) | |

O(nlogn) | |

none of the above, as the tree cannot be be uniquely determined. |

Question 50 Explanation:

Last element in post order is the root of tree- find this element in inorder-log n time. Now as in quick sort consider this as pivot and split the post order array into 2. All elements smaller than pivot goes to left and all elements larger than pivot goes to right and suppose we have k elements smaller than pivot, these elements will be same in both in-order as well as post order. Now, we already got the root, now left child is the left split and right child is the right split.

T(n) = T(k) + T(n-k-1) + logn

In worst case T(n) = O(nlogn), when k=0

But searching for an element in the in-order traversal of given BST can be done in O(1) because we have n elements from 1...n so there is no need to search an element- if last element in post order is say 5 we take it as root and since 4 elements are split the post order array into two (first 4 elements), (6th element onward) and solve recursively. Time complexity for this would be

T(n) = T(k) + T(n-k-1)+O(1)

Which gives T(n) = O(n)

since we know that all elements must be traversed at least once T(n) = θ(n)

T(n) = T(k) + T(n-k-1) + logn

In worst case T(n) = O(nlogn), when k=0

But searching for an element in the in-order traversal of given BST can be done in O(1) because we have n elements from 1...n so there is no need to search an element- if last element in post order is say 5 we take it as root and since 4 elements are split the post order array into two (first 4 elements), (6th element onward) and solve recursively. Time complexity for this would be

T(n) = T(k) + T(n-k-1)+O(1)

Which gives T(n) = O(n)

since we know that all elements must be traversed at least once T(n) = θ(n)

Question 51 |

The most efficient algorithm for finding the number of connected components in a n undirected graph on n vertices and m edges has time complexity

O(n) | |

O(m) | |

O(m+n) | |

O(mn) |

Question 51 Explanation:

To find the number of connected components using either BFS or DFS time complexity is θ(m+n).

Suppose if we are using Adjacency matrix means it takes θ(n

Suppose if we are using Adjacency matrix means it takes θ(n

^{2} ).Question 52 |

Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the position for the newly inserted element, the number of comparisons performed is

O(log _{2} n) | |

O(nlog _{2} n) | |

O(n) |

Question 52 Explanation:

Max heap is the complete binary tree that means each node has either zero children or two children except last level. So in worst case insertion of element is at last level. So, number of comparisons required at each level starting from root is equal to 1+2+4+8+16+---- this series is equal to "logn".

Note: If you apply linear search it will take O(logn) and binary search it will take O(loglogn). If you want to insert an element into already created heap is O(logn) because you need to apply

Note: If you apply linear search it will take O(logn) and binary search it will take O(loglogn). If you want to insert an element into already created heap is O(logn) because you need to apply

**maxheapify.**Question 53 |

An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

solves it in linear time using a left to right pass of the array | |

solves in linear time using a right to left pass of the array | |

solves it using divide and conquer in time O(nlogn) | |

solves it in time O(n ^{2} ) |

Question 53 Explanation:

Algorithm to solve the problem :

● Start from the right keeping track of largest element (currentLeader). If a larger element is found, then print it and set currentLeader to the current element.

● We can consider the last element is a leader since there is no element to its right. Solves it in linear time using a right to left pass of the array will takes time complexity is O(n).

● Start from the right keeping track of largest element (currentLeader). If a larger element is found, then print it and set currentLeader to the current element.

● We can consider the last element is a leader since there is no element to its right. Solves it in linear time using a right to left pass of the array will takes time complexity is O(n).

Question 54 |

In a circularly linked list organization, insertion of a record involves the modification of

no pointer | |

1 pointer | |

2 pointer | |

3 pointer |

Question 54 Explanation:

Suppose we have to insert node “x” after node “n1” then

x → next = n1 → next

n1 → next = x

So, we need to modify two pointers only to insert node into the linked list.

x → next = n1 → next

n1 → next = x

So, we need to modify two pointers only to insert node into the linked list.

Question 55 |

To sort many large objects or structures, it would be most efficient to place

them in an array and sort the array | |

pointers to them in an array and sort the array | |

them in a linked list and sort the linked list | |

references to them in an array and sort the array |

Question 55 Explanation:

● Pointers will point to large objects or structures.

● By using pointers we will easily access the large objects or structures with the help the addresses pointing to them.

● If you made any changes to the elements in the array, it automatically reflect as these are pointed by the pointers

● By using pointers we will easily access the large objects or structures with the help the addresses pointing to them.

● If you made any changes to the elements in the array, it automatically reflect as these are pointed by the pointers

Question 56 |

The average search time of hashing, with linear probing will be less if the load factor

is far less than one | |

equals one | |

is far greater than one | |

none of these |

Question 56 Explanation:

A critical statistic for a hash table is the load factor, defined as

Load factor= n / k

where

● n is the number of entries occupied in the hash table.

● k is the number of buckets.

As the load factor grows larger, the hash table becomes slower, and it may even fail to work (depending on the method used)

The load factor is the number of keys stored in the hash table divided by the capacity. The size should be chosen so that the load factor is less than 1

Load factor= n / k

where

● n is the number of entries occupied in the hash table.

● k is the number of buckets.

As the load factor grows larger, the hash table becomes slower, and it may even fail to work (depending on the method used)

The load factor is the number of keys stored in the hash table divided by the capacity. The size should be chosen so that the load factor is less than 1

Question 57 |

If initialization is a part of declaration of a structure, then storage class can be

automatic | |

register | |

static | |

anything |

Question 57 Explanation:

Storage class specifiers available in C programming language include 'auto', 'register', 'static' and 'extern'.Depending upon the developer requirement , the storage class is anything.

Question 58 |

Which of the following conditions must be met to avoid race around problem?

△t < t _{p} < T | |

T > △t > t _{ p} | |

2t _{p} < △t < T | |

none of these |

Question 58 Explanation:

When we are using T > △t > tp this condition, we will avoid race around condition.

Question 59 |

If a clock with time period "T" is used with n stage shift register, then output of final stage will be delayed by

nT sec | |

(n-1)T sec | |

n/Tsec | |

(2n-1)T sec |

Question 59 Explanation:

Number of stages = Number of flip-flops in register= no.of bits that can be stored in register.

The data can be shifted one position towards left or right in each clock.

Consider right shift operation.

Initially, data in LSB position is read or accessed.

After each shift the next significant bit moves to LSB position and the bit in LSB is read.

After n-1 shifts i.e after T(n-1) seconds, the last element moves to LSB position.

The data can be shifted one position towards left or right in each clock.

Consider right shift operation.

Initially, data in LSB position is read or accessed.

After each shift the next significant bit moves to LSB position and the bit in LSB is read.

After n-1 shifts i.e after T(n-1) seconds, the last element moves to LSB position.

Question 60 |

A sequential circuit outputs a ONE when an even number (>0) of one's are input; Otherwise the output is ZERO. The minimum number of states required is

0 | |

1 | |

2 | |

3 |

Question 60 Explanation:

Let S_e and S_o are the two states with S_0 is the initial state(with zero ones).

Question 61 |

A hash table with 10 buckets with one slot per bucket is depicted. The symbols, S1 to S7 are initially emerged using a hashing function with linear probing. Maximum number of comparisons needed in searching an item that is not present is

6 | |

5 | |

4 | |

3 | |

None of the above |

Question 61 Explanation:

Question and options are wrong. So, excluded for evaluation.

Question 62 |

The process of entering data into a storage location

causes variation in its address number | |

adds to the contents of the location | |

is called a readout operation | |

is destructive of previous contents |

Question 62 Explanation:

The process of entering data into a storage location is destructive of previous contents using memory management techniques. In paging we are using LRU for replacing existing data.

Question 63 |

The seek time of a disk is 30ms. It rotates at the rate of 30 rotations/second. The capacity of each track is 300 words. The access time is (approximately)

62ms | |

60ms | |

50ms | |

47ms |

Question 63 Explanation:

Hard Disk Access time is the total elapsed time between the initiation of a particular request for data and receipt of the first bit of that data.

Given seek time of disk = 30ms

Rotation rate is 30 rotations/second.

The capacity of each track is 300 words

Given seek time of disk = 30ms

Rotation rate is 30 rotations/second.

The capacity of each track is 300 words

Question 64 |

Which of the following is FALSE?

Read ⋀ as AND, ⋁ as OR, ~ as NOT, → as one way implication and ⬌ as two way implication?

Read ⋀ as AND, ⋁ as OR, ~ as NOT, → as one way implication and ⬌ as two way implication?

((x→ y)⋀ x)->y | |

((~x→ y)⋀(~x⋀~y)) → x | |

(x→ (x ⋁ y)) | |

((x ⋁ y) ⬌ (~x ⋁ ~y)) |

Question 64 Explanation:

Question 65 |

If f:{a,b}

^{*}→ {a,b}^{*}be given by f(n)=ax for every value of n∈{a,b}, then f is{a,b,ab,aa} | |

{a,b,ba,bb} | |

{a,b} | |

{aa,ab,ba,bb} |

Question 65 Explanation:

f:{a,b}* → {a,b}* be given f(n)=ax

→ In option B and D, "ba" is presented which is generated by f. So, we can conclude based on this, option B and D are false.

→ "ab" can be generated by f but which is not present in the option C. So, we can conclude option C is wrong.

→ Option A satisfying all the favorable cases which is generated by f.

→ In option B and D, "ba" is presented which is generated by f. So, we can conclude based on this, option B and D are false.

→ "ab" can be generated by f but which is not present in the option C. So, we can conclude option C is wrong.

→ Option A satisfying all the favorable cases which is generated by f.

There are 65 questions to complete.