Back to Subject

Unit 3: Logic Gates and Recurrence Relations - Practice Quiz

MTH136 — Discrete Structures 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 Which logic gate produces an output of only when all of its inputs are ?

introduction to logic gates Easy
A. OR gate
B. NOT gate
C. AND gate
D. XOR gate

2 The output of an OR gate is only when:

introduction to logic gates Easy
A. All inputs are
B. Any one input is
C. All inputs are
D. Any one input is

3 A NOT gate is also commonly known as a(n):

introduction to logic gates Easy
A. Comparator
B. Multiplexer
C. Inverter
D. Buffer

4 The Boolean expression for a two-input AND gate with inputs and is:

introduction to logic gates Easy
A.
B.
C.
D.

5 Which gate outputs when its two inputs are different?

introduction to logic gates Easy
A. NOR gate
B. NAND gate
C. AND gate
D. XOR gate

6 A NAND gate is equivalent to which combination of gates?

combination of gates Easy
A. OR gate followed by NOT gate
B. AND gate followed by OR gate
C. AND gate followed by NOT gate
D. NOT gate followed by AND gate

7 A NOR gate is formed by combining which gates?

combination of gates Easy
A. AND gate followed by NOT gate
B. NOT gate followed by OR gate
C. OR gate followed by NOT gate
D. OR gate followed by AND gate

8 Which gate is called a universal gate because any circuit can be built using only it?

combination of gates Easy
A. NOT gate
B. NAND gate
C. AND gate
D. XOR gate

9 The Boolean expression for a NOR gate with inputs and is:

combination of gates Easy
A.
B.
C.
D.

10 The output of a two-input XNOR gate is when:

combination of gates Easy
A. Both inputs are equal
B. Both inputs are different
C. Any input is
D. Any input is

11 In a switching circuit, two switches connected in series represent which logic operation?

implementation of logic gates to the switching circuits Easy
A. XOR
B. AND
C. NOT
D. OR

12 In a switching circuit, two switches connected in parallel represent which logic operation?

implementation of logic gates to the switching circuits Easy
A. NAND
B. NOT
C. AND
D. OR

13 In switching circuit notation, a closed switch (current flows) is usually represented by the value:

implementation of logic gates to the switching circuits Easy
A.
B.
C.
D.

14 A switching circuit with a single switch whose state is the opposite of the input represents which gate?

implementation of logic gates to the switching circuits Easy
A. AND gate
B. OR gate
C. NOT gate
D. XOR gate

15 A function that is defined in terms of itself is called a:

introduction to recursion Easy
A. Linear function
B. Iterative function
C. Recursive function
D. Constant function

16 Every valid recursive definition must contain a:

introduction to recursion Easy
A. Global variable
B. Loop counter
C. Base case
D. Return array

17 A recurrence relation defines each term of a sequence using:

recurrence relation Easy
A. A fixed constant only
B. One or more previous terms
C. The sum of all future terms
D. Only the first term

18 The Fibonacci sequence is defined by the recurrence:

recurrence relation Easy
A.
B.
C.
D.

19 A closed-form solution of a recurrence relation gives the -th term:

solving recurrence relation Easy
A. Directly without previous terms
B. Only for the base case
C. As an approximate estimate only
D. Only after computing all previous terms

20 For the linear homogeneous recurrence , the associated equation used to find the solution is called the:

linear homogenous recurrence relation with constant coefficient and their solution Easy
A. Normal equation
B. Characteristic equation
C. Generating equation
D. Differential equation

21 For inputs and , what is the output of a NAND gate?

introduction to logic gates Medium
A. Undefined
B.
C.
D. Depends on a third input

22 Which gate produces an output of only when its two inputs are different?

introduction to logic gates Medium
A. AND
B. XOR
C. NOR
D. XNOR

23 A NOR gate output is HIGH () under which condition for inputs and ?

introduction to logic gates Medium
A. When both and
B. When both and
C. When
D. For any combination of inputs

24 The Boolean expression is equivalent to which single gate?

combination of gates Medium
A. NAND gate
B. NOR gate
C. XOR gate
D. AND gate

25 Which combination of gates behaves as a universal gate, capable of implementing any Boolean function on its own?

combination of gates Medium
A. OR gate
B. NAND gate
C. AND gate
D. XNOR gate

26 How is a NOT gate constructed using only a single NOR gate?

combination of gates Medium
A. Connect the output back to an input
B. Connect one input to permanently
C. Tie both inputs of the NOR gate together
D. Cascade two NOR gates in series

27 The expression simplifies to which operation?

combination of gates Medium
A.
B.
C.
D.

28 In a switching circuit, two switches connected in series represent which Boolean operation?

implementation of logic gates to the switching circuits Medium
A. XOR
B. NOT
C. OR
D. AND

29 Two switches connected in parallel correspond to which logic gate?

implementation of logic gates to the switching circuits Medium
A. NAND gate
B. NOT gate
C. AND gate
D. OR gate

30 A switching circuit has switch in series with a parallel combination of and . Which Boolean expression represents the circuit?

implementation of logic gates to the switching circuits Medium
A.
B.
C.
D.

31 For the circuit expression , what is the minimal equivalent switching function?

implementation of logic gates to the switching circuits Medium
A.
B.
C.
D.

32 For the recursive definition with , what is ?

introduction to recursion Medium
A.
B.
C.
D.

33 Which component is essential in every recursive definition to prevent infinite recursion?

introduction to recursion Medium
A. A loop counter
B. A base case
C. A return of zero
D. A global variable

34 The factorial function is defined as with . What is the value of ?

introduction to recursion Medium
A.
B.
C.
D.

35 Which of the following is a recurrence relation of order ?

recurrence relation Medium
A.
B.
C.
D.

36 Which recurrence relation is linear, homogeneous, and has constant coefficients?

recurrence relation Medium
A.
B.
C.
D.

37 For the recurrence with , what is the closed-form solution?

solving recurrence relation Medium
A.
B.
C.
D.

38 Using iteration, the solution to with is:

solving recurrence relation Medium
A.
B.
C.
D.

39 What is the characteristic equation of the recurrence ?

linear homogenous recurrence relation with constant coefficient and their solution Medium
A.
B.
C.
D.

40 The characteristic roots of a recurrence are and . What is the general solution form?

linear homogenous recurrence relation with constant coefficient and their solution Medium
A.
B.
C.
D.

41 A logic gate produces output only when its two inputs are different. If this gate is fed with inputs and (the complement of ), what is the output for all values of ?

introduction to logic gates Hard
A. Equal to
B. Always
C. Always
D. Equal to

42 The Boolean expression is functionally equivalent to which single gate output?

combination of gates Hard
A. (XOR)
B. (AND)
C. (NAND)
D. (OR)

43 How many 2-input NAND gates are minimally required to implement a 2-input XOR gate?

combination of gates Hard
A.
B.
C.
D.

44 Which of the following gates is a universal gate, meaning any Boolean function can be built using only copies of it?

introduction to logic gates Hard
A. AND
B. XOR
C. OR
D. NOR

45 In switching-circuit algebra, two switches connected in series correspond to which Boolean operation, and two in parallel to which?

implementation of logic gates to the switching circuits Hard
A. Series = XOR, Parallel = AND
B. Series = AND, Parallel = OR
C. Series = OR, Parallel = XOR
D. Series = OR, Parallel = AND

46 A switching circuit realizes the function . Using Boolean simplification, the minimized form of is:

implementation of logic gates to the switching circuits Hard
A.
B.
C.
D.

47 Consider the recursive function with and (the Lucas sequence). What is ?

introduction to recursion Hard
A.
B.
C.
D.

48 A recursive procedure makes two recursive calls each of size plus work per call. Which closed-form time complexity does this recurrence yield?

introduction to recursion Hard
A.
B.
C.
D.

49 The number of moves required to solve the Tower of Hanoi with disks satisfies with . What is the closed form of ?

recurrence relation Hard
A.
B.
C.
D.

50 Which of the following is a first-order linear non-homogeneous recurrence relation with constant coefficients?

recurrence relation Hard
A.
B.
C.
D.

51 Solve the recurrence with . The general solution has characteristic roots:

solving recurrence relation Hard
A.
B.
C.
D.

52 For the recurrence in the previous style, with , the explicit closed form is:

solving recurrence relation Hard
A.
B.
C.
D.

53 A linear homogeneous recurrence has characteristic equation . What is the correct general form of the solution?

linear homogenous recurrence relation with constant coefficient and their solution Hard
A.
B.
C.
D.

54 The recurrence has characteristic equation with complex roots . The real general solution is:

linear homogenous recurrence relation with constant coefficient and their solution Hard
A.
B.
C.
D.

55 A degree-3 homogeneous recurrence has characteristic roots . Which is the correct general solution?

linear homogenous recurrence relation with constant coefficient and their solution Hard
A.
B.
C.
D.

56 Solve with . The closed form is:

solving recurrence relation Hard
A.
B.
C.
D.

57 A circuit outputs . For how many of the four input combinations does ?

combination of gates Hard
A.
B.
C.
D.

58 A lamp is controlled so that flipping either of two switches toggles the lamp state (a staircase switch). Which Boolean function of the two switch positions and describes the lamp?

implementation of logic gates to the switching circuits Hard
A.
B.
C.
D.

59 The recurrence is being solved. What is the correct form of the particular solution to try?

recurrence relation Hard
A.
B.
C.
D.

60 A recursive definition sets and for . What is the closed-form expression for ?

introduction to recursion Hard
A.
B.
C.
D.
Previous MCQ
Unit 2
Next MCQ
Unit 4