## UPPCL AE 2022

Question 1 |

Which of the following sequences of operations is followed in the instruction cycle?

00: Fetch Cycle 00: Execute Cycle 10: Interrupt Cycle 11: Indirect Cycle | |

00: Fetch Cycle 01: Interrupt Cycle 10: Indirect Cycle 11: Execute Cycle | |

00: Fetch Cycle 01: Execute Cycle 10: Indirect Cycle 11: Interrupt Cycle | |

00: Fetch Cycle 01: Indirect Cycle 10: Execute Cycle 11: Interrupt Cycle |

Question 2 |

Consider the Grammar G (V-(S, A,B,C), T-(a,b),S,P) where V is a non-empty set of variables or non-terminals, T is a set of terminals, S is a start symbol and P is a set of production des given as follows.
Which of the following strings is in L(G)

aaa | |

ababbab | |

null string | |

bbb |

Question 3 |

Let F(x,y) denote the predicate ‘ y is a friend of x’. Which of the following correctly describes' It is impossible that someone does not have any friends’?

For all y there exists x (F(x, y)) | |

There exists y for all x (F(x, y)) | |

There exists x for all y (F(x, y)) | |

For all x there exists y (F(x, y)) |

Question 4 |

2 doctors and 10 nurses attend a small conference. All 12 names are put in a hat and 4 names are randomly picked without replacement. The probability that 1 doctor and 3 nurses are picked is:

Question 5 |

In a __________ graph, vertices can be partitioned into two subsets V1 and V2 suchthat no edge has both endpoints in the same subset, and every possible edge that could connect vertices in different subsets is part of the graph.

complete bipartite | |

clique | |

complete | |

bipartite |

Question 6 |

Let Grammar G(V=(5).T (ab)SP)stere V is a no-empty set of variables or non-terminals. T is a set of terminals. S is a start symbol. λ is a null string and is a set of production rules. If n

_{a}(w), (w) n_{b}represents the number of a's and b'a in string w, then the language derived from set of production rules{W ∈ {a,b} ^{*} : n_{a} (w) = n_{b}(w)} | |

{W ∈ {a, b} ^{*} : n_{a} (w) # n_{b} (w)} | |

{W ∈ {a, b} ^{*} : n_{a} (w) < n_{b}(w)} | |

{W ∈ {a, b} ^{*} : n_{a} (w) > n_{b}(w)} |

Question 7 |

Literals can also be called

constants | |

keywords | |

identifiers | |

special characters |

Question 8 |

Simplify the logic expression F = a 'bc + a 'bc' + ac.

b + ca' = 1 | |

ab + b 'c=1 | |

a + b' c | |

a 'b + ac |

Question 9 |

Consider the following schema
(staff, name, street, city)
serves(name, c_ name, salary)
company (c_ name, city)
manages (name, manager-name)
Find the names and cities of the residence of all the staffs who work for Shankar.

Question 10 |

Which of the following is the application of stack data structure?

data transfer | |

resource scheduling | |

disk scheduling | |

evaluation of expressions |

Question 11 |

Which of the following principles is used by divide and conquer technique?

Recursively define the values of optimal solutions | |

Divide the problem into a number of subproblems | |

An equation or inequality describes a function in terms of its values on smaller inputs | |

Construct an optimal solution from computed information |

Question 12 |

The number of elements in the adjacency matrix of a graph having 6 vertices is_______

36 | |

12 | |

216 | |

24 |

Question 13 |

Find the combination of the inputs (X and Y) for which the Q output is set to 1 for the latch as shown.

1 ,0 | |

1, 1 | |

0, 1 | |

0,0 |

Question 14 |

Which of the following is a partition of the set S = {2,4,6,8,10}?

{2, 4}, {2, 6, 8}, {10} | |

{4, 6}, {4, 8, 10} | |

{2, 8}, {4}, {6, 10} | |

{2, 10}, {4}, (6} |

Question 15 |

For which of the following functions is Rolle’s theorem applicable?

f(x)=x ^{3} in [1,2] | |

f(x)=x ^{2} in [-1,1] | |

f(x) = tan x in [0, π] | |

f(x)=x ^{13} in [−1,1] ^{1/3} |

Question 16 |

_______specifies the address in memory for a read or write operation.

Memory Buffer Register (MBR) | |

Address register | |

Memory Address Register (MAR) | |

Program Counter (PC) |

Question 17 |

In which of the following gates, the output is 0 if and only if at least one input is 0?

NOR | |

OR | |

XOR | |

AND |

Question 18 |

Which of the following is NOT a property of context free language that can be generated from context free grammar G ?

There are no productions of the form ABC where A and B are variables | |

Each variable and each terminal of G appears in the derivation of some word in L. | |

There are no productions of the form A-→> B where A and B are variables | |

If is not in L, there needs be no productions of the form A- £. |

Question 19 |

In dynamic programming, the technique of storing the previously calculated values in called:

storing value property | |

mapping dynamic programming paradigm | |

saving value property | |

Memorization |

Question 20 |

For all sets A, B, C, which of the following does NOT hold?

(B ∩ C) ∪ A = (B ∪ A) ∩ (C ∪ A) | |

A ∩ B = B ∩ A | |

A ∪ (B ∪ C) = (A ∪ B) ∪ C | |

A ∩ (B ∩ C) = (A ∩ B) ∪ C |

Question 21 |

_______are very versatile and are a basic component of inter process and intersystem communication. They also provide point-to-point, two-way communication between two processes.

Monitors | |

Shared memories | |

Sockets | |

Semaphores |

Question 22 |

The number 101010101010 is a 12-bit binary number in 2’s complement form. If it is stored in a 16-bit register, with what would you fill bit 12 to bit 15 (4-bits), so that the value of the number is unchanged?

0101 | |

0000 | |

1111 | |

1010 |

Question 23 |

The giver table describes the rate of economic growth (x) and the rate of return on the S&P 500(y) of a sample. The covariance between these two is :

1.36 | |

1.53 | |

1.47 | |

1.27 |

Question 24 |

Which is the next step that comes after the intermediate code generator in the phases of a compiler?

Machine - independent code optimizer | |

Semantic analyzer | |

Machine - dependent code optimizer | |

Code generator |

Question 25 |

Match the following pairs with respect to 10 G Ethernet:

I - A, II - B, III - D, IV - C | |

I - A, II - D, III - B, IV - C | |

I - A, II - B, III - C, IV - D | |

I - A, II - C, III - B, IV - D |

Question 26 |

The identity elements of OR and AND operations are ______ and ______, respectively.

zero, zero | |

one, zero | |

one, one | |

zero, one |

Question 27 |

The dual of the expression x + x

^{2}= 1 is:x - x ^{2} = 1 | |

x. x ^{2} = 0 | |

x. x ^{1} = 1 | |

x - x = 0 |

Question 28 |

Which of the following is a scalar matrix?
(given k is constant)

Question 29 |

Which of the following is a decidable problem?

Determine whether a language generated by Turing Machine M is finite. | |

Determine whether a language L generated by Unrestricted Grammar is empty. | |

Determine whether language over ∑ (where ∑ is a set of input alphabet) is not recursively enumerable. | |

Determine whether a context sensitive grammar accepts the input string |

Question 30 |

The time complexity of constructing a single-tape Turing Machine and a two-tape Turing Machine for the language L = {a" b": n ≥ 1), respectively, are:

Question 31 |

Protocols in which the sender sends one frame and then waits for an acknowledgement before proceeding are called protocols.

stop-and-wait | |

Go-back-n | |

store and forward | |

sliding window |

Question 32 |

A complete graph G with 5 vertices has___________ spanning trees. Ans:

125 | |

15 | |

3 | |

25 |

Question 33 |

Consider the grammar G (V = {S, A, B, C, D, E, T = { a, b }, S, p ) where V is a non -empty set of variables or non- terminals, T is a set of terminals, S is a start symbol and P is a set of production rules given as follows:

S→AB,A →a, B→C, B →b, C →D,D,→E,E →a.

The equivalent grammar after eliminating the unit productions is:

S→AB,A →a, B→C, B →b, C →D,D,→E,E →a.

The equivalent grammar after eliminating the unit productions is:

S→AB, A →a, B→C, B →b, C →a, D ,→E, E →a | |

S→AB, A → a, B →a, B →b, C →a, D →a, E → a | |

S→BC, A →a, B → a, Bb, C →a, D → E, E → a | |

S →ab, A →a, B →a, B → b, Ca, D →E, E → a. |

Question 34 |

Suppose a d-regular graph on n vertices (n is even) is disconnected. Which of the following can be the maximum value of d?

Question 35 |

The type of information stored in computer words______________

is data only | |

are data and instruction | |

depends on the type of memory | |

is instruction only |

Question 36 |

Which of the following is a process that reduces computing time but increases the amount of memory needed?

Lookup tables or recalculation | |

Compressed data | |

Re-rendering | |

Smaller code |

Question 37 |

A string of terminals in the context-free grammar is represented by:

a combination of lowercase Greek and uppercase letters | |

uppercase letters | |

lowercase Greek letters | |

lowercase letters |

Question 38 |

Find the minimum number of additions and multiplications needed to evaluate a degree 5 polynomial at any point x0.

5 additions, 15 multiplications | |

5 additions, 5 multiplications | |

5 additions, 4 multiplications | |

4 additions, 15 multiplications |

Question 39 |

Using a dual 8:1 MUX, what are the extra logic gates required to implement a full- adder?

One 2-input XOR | |

One 2-input AND | |

One 2-input OR | |

None |

Question 40 |

The linear transformation has a matrix.if it transforms all the points of circle with equation x

^{2}+ Y^{2}=4,then the curve is:9x ^{2} + 4y^{2} =288 | |

9x ^{2} + 4y^{2} = 24 | |

x ^{2} + y^{2} = 12 | |

9x ^{2} + 4y^{2} = 576 |

Question 41 |

12 | |

11 | |

10 | |

13 |

Question 42 |

Each field of k bits allows for________________ micro-operations. Ans

k | |

2k+1 | |

2k – 1 | |

2k |

Question 43 |

Consider the indirect addressing mode instruction "Load RI. (M)"

The task of the instruction: Load the content of memory location MI to register RI. There are five control steps after fetch) that are required to execute the instruction "LOAD RI, (M)", as given below.

1. IRout, MARI, Read

2 WAFC

3._______

4. WMFC

5. MDRout, Rin

Which of the following fits appropriately in step 3 of the given set of instructions?

The task of the instruction: Load the content of memory location MI to register RI. There are five control steps after fetch) that are required to execute the instruction "LOAD RI, (M)", as given below.

1. IRout, MARI, Read

2 WAFC

3._______

4. WMFC

5. MDRout, Rin

Which of the following fits appropriately in step 3 of the given set of instructions?

IRout, MARin, Read | |

MDRin, MARin | |

MDRout, MARin | |

MDRout, MARout |

Question 44 |

UNION operator results in which of the following?

Taking distinct data from the relations. | |

Taking data that is not common from the relations. | |

Taking all data from the relations. | |

Taking common data from the relations. |

Question 45 |

Which of the following options is true in the case of a two-bus organization?

In a two-bus organization, there are two buses. The general-purpose register can read/write from both the buses. In this case, two operands can be fetched at the same time because of the two buses – one bus fetch operand for ALU and another bus fetch for register | |

In a two-bus organization, there are two buses. The general-purpose register can only write from both the buses. In this case, two operands can be fetched at the same time because of the two buses – one bus fetch operand for ALU and another bus fetch for register. | |

In a two-bus organization, there are two buses. The general-purpose register can only read from both the buses. In this case, two operands can be fetched at the same time because of the two buses – one bus fetch operand for ALU and another bus fetch for register. | |

In a two-bus organization, there are two buses. The
Th general-purpose register can only write from both the buses. In this case, two operands can be fetched at the same time because of the two buses – one bus fetch operand for ALU and another bus fetch for memory. |

Question 46 |

Language generated from production P₁ of Grammar is infinite, but the language generated from production P₂ is always finite. | |

Language generated from production P₁ of Grammar is finite, but the language generated from production Grammar is infinite | |

Language generated from productions P₁ and P₂ are always infinite | |

KAMR Language generated from productions P₁ and P₂are always finite. |

Question 47 |

A binary search tree which provides the smallest possible search time for a given sequence of accesses is:

Optimal Binary Search Tree | |

Self-Balancing Binary Search Tree | |

Balanced Binary Tree | |

AVL tree |

Question 48 |

ADD R1,R2 instruction is an example of which of the following addressing modes?

Direct addressing mode | |

Indirect register addressing mode | |

Register addressing mode | |

Immediate addressing mode |

Question 49 |

If 2a + 3b +6c=0, then ax

^{2}+bx+c = 0 has at least one root in:(1 ,2 ) | |

(0 ,1) | |

(2 ,3) | |

(-1, 0) |

Question 50 |

What is the space complexity of the following piece of code?

for ( int i=0;i< N;i++)

V. push _ back(i);

for ( int i=0;i< N;i++)

V. push _ back(i);

O(loan) | |

O(n) | |

O(1)
| |

O(nlogg) |

There are 50 questions to complete.