CSE334 - ETE - PracticeSet - Quizizz

5/14/24, 11:19 PM CSE334_ETE_PracticeSet | Quizizz
Worksheets Name
CSE334_ETE_PracticeSet
Class
Total questions: 50
Worksheet time: 2hrs 54mins
Date
Instructor name: Mr. Pushpendra Pateriya
1. Consider the following two-process synchronization solution

Process 0
Entry: loop while (turn == 1);
(critical section)
Exit: turn = 1;
Process 1
Entry: loop while (turn == 0);
(critical section)
Exit: turn = 0;
The shared variable turns in initialized to zero.
Which one of the following is TRUE?
a) This is a correct two-process synchronization b) This solution violates mutual exclusion

solution. requirement.
c) This solution violates progress requirement. d) This solution violates bounded wait
requirement.
2.
Consider the methods used by processes P1 and P2

for accessing their critical sections whenever
needed, as given below. The initial values of shared
boolean variables S1 and S2 are randomly assigned.
Which one of the following statements describes
the properties achieved?
a) Mutual exclusion but not progress b) Progress but not mutual exclusion
c) Neither mutual exclusion nor progress d) Both mutual exclusion and progress
https://quizizz.com/print/quiz/66437054540ae33980f90e67 1/16
3.
The following two functions P1 and P2 that share a

variable B with an initial value of 2 execute
concurrently.
The number of distinct values that B can possibly take
after the execution is _______.
a) 1 b) 4
c) 2 d) 3
4. Suppose a semaphore 𝑆S is initialized to 10. Two processes 𝑃1P1and 𝑃2P2operate as follows:

Process P1performs P(S) three times and then V(S) twice.
Process P2performs V(S) four times and then P(S) five times.
If P1and P2execute their operations sequentially in that order, what is the final value of S?
a) 7 b) 9
c) 11 d) 8
5. If an array is unsorted, what is the best time complexity to find an element using any
algorithm?
a) O(n log n) b) O(n)
c) O(log n) d) O(1)
6. Which sorting algorithm would you use if you need to maintain the relative order of equal
elements (i.e., stability) and also require the algorithm to be efficient in terms of time
complexity?
a) Quick Sort b) Merge Sort
c) Selection Sort d) Heap Sort
7. What is the time complexity of the following code?

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// constant time operations
}
}
a) O(n) b) O(n^2)
c) O(n log n) d) O(n^3)

for (int i = 1; i < n; i *= 2) {
for (int j = 0; j < n; j++) {
}
}
a) O(n log n) b) O(n^2)
c) O(n) d) O(log n)

for (int i = 1; i < n; i *= 2) {
for (int j = i; j < n; j++) {
for (int k = 0; k < j; k++) {
}
}
}
a) O(n^3 log n) b) O(n^3)
c) O(n^2 log n) d) O(n log n)
10. The minimum complexity of sorting n character strings, each of length n, in chronological order can
be analyzed by considering comparison-based sorting algorithms
a) O(n^2) b) O(n)
c) O(nlogn) d) O(n^2 logn)
11. Match the following
Quick Sort O(nlogn)
Bubble Sort O(n^2)
Selection Sort O(n^2)
Merge Sort O(n^2)
Insertion Sort O(n^2)
12. Match the following recurrence relations
Quick Sort (Average) F(n)=F(n−1)+F(n−2)
Towers of Hanoi T(n)=2T(n−1)+1
Fibonacci Series T(n)=2T(n/2)+O(n)
Factorial T(n) = n * T(n-1)
13. Which of the following statements is/are TRUE with

respect to deadlocks?
a) Circular wait is a necessary condition for the b) In a system where each resource has more
formation of deadlock. than one instance, a cycle in its wait-for
graph
indicates the presence of a deadlock.
c) If the current allocation of resources to d) In the resource-allocation graph of a system,

processes leads the system to unsafe state, if every edge is an assignment edge, then the
then deadlock will necessarily occur. system is not in deadlock state.
14. A system has 6 identical resources and N processes competing for them. Each process can
request at
most 2 resources. Which one of the following values of N could lead to a deadlock?
a) 1 b) 4
c) 2 d) 3
15. In the context of operating systems, which of the following statements is/are correct with respect to
paging?
a) Paging helps solve the issue of external b) Page size has no impact on internal
fragmentation fragmentation
c) Paging incurs memory overheads d) Multi-level paging is necessary to support

pages
of different sizes
16. The essential content(s) in each entry of a page table is/are
a) Virtual page number b) Page frame number
c) Both virtual page number and page frame d) Access right information
number
17. Consider a C program that uses structures to manage student records:

struct Student {
int rollNumber;
char name[50];
float marks;
};
Calculate the total memory size occupied by the structure Student on a machine where int is 2
bytes, char is 1 byte, and float is 4 bytes. Assume there is no padding.
a) 52 bytes b) 60 bytes
c) 48 bytes d) 56 bytes
18. Which is not a bottom up parser?
a) Recursive descent parser b) Shift-reduce parser
c) LR(0) parser d) SLR parser
19. YACC uses which type of parsing?
a) SLR b) LALR
c) LL d) LR
20.
Consider the problem of reversing a singly linked list. To take an example, given the linked list
below.
Which one of the following statements is TRUE about the time complexity of algorithms that solve
the above problem in O(1) space?
a) The best algorithm for the problem takes b) The best algorithm for the problem takes
theta(n) time in the worst case. theta(n
log n) time in the worst case.
c) The best algorithm for the problem takes d) It is not possible to reverse a singly linked
theta(n^2) time in the worst case. list in O(1) space.
21. What is the worst case time complexity of inserting n elements into an empty linked list, if the linked
list
needs to be maintained in sorted order?
a) theta(n) b) theta(n log n)
c) theta(n^2) d) theta(1)
22. Suppose a circular queue of capacity (n-1) elements is implemented with an array of n elements.
Assume
that the insertion and deletion operations are carried out using REAR and FRONT as array index
variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue
empty are
a) Full: (REAR + 1) mod n = = FRONT b) Full: (REAR + 1) mod n = = FRONT

Empty: REAR = = FRONT Empty: (FRONT + 1) mod n = = REAR
c) Full: REAR = = FRONT d) Full:(FRONT + 1) mod n = = REAR

Empty:(REAR + 1) mod n = = FRONT Empty: REAR = = FRONT
23. A circular queue has been implemented using a singly linked list where each node consists of a
value and a single pointer pointing to the next node. We maintain exactly two external pointers
FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which
of the following statements is/are CORRECT for such a circular queue, so that insertion and
deletion operations can be performed in O(1) time?
I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node
a) I only b) II only
c) Both I and II d) Neither I nor II
24. The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same
tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest path from the root to any
leaf.
The height of the binary tree above is ______
Ans.
25. Match the algorithms with their time complexities:
(P) Tower of Hanoi with n disks. theta(2^n)
(S) Addition to two n × n matrices theta(log n)
(R) Heap sort given n numbers at

theta(n log n)
the worst case.
(Q) Binary search given n sorted

theta(n^2)
numbers
26. Consider the following statements regarding the front-end and back-end of a compiler.
S1: The front-end includes phases that are independent of the target hardware.
S2: The back-end includes phases that are specific to the target hardware.
S3: The back-end includes phases that are specific to the programming language used in the
source
code.
Identify the CORRECT option.
a) Only S1 is TRUE b) Only S1 and S2 are TRUE
c) S1, S2, and S3 are all TRUE d) Only S1 and S3 are TRUE
27. Match the following according to input from List-I to the compiler phase in the List-II that processes
it:
P: Lexical analysis (iii) Regular expressions
Q: Top down parsing (i) Leftmost derivation
S: Runtime environment (ii) Type checking
R: Semantic analysis (iv) Activation records
28. In a compiler, keywords of a language are

recognized during
a) syntactic analysis b) lexical analysis
c) code generation d) semantic analysis
29. expr -> expr '+' term | expr '-' term | term
term -> term '*' factor | term '/' factor | factor
factor -> '-' factor | '(' expr ')' | NUMBER
According to given grammar which one is the highest precedence operator.
a) / b) binary -
c) unary - d) *
30. Consider the following grammar:

P → xQRS
Q → yz | z
R→w|ε
S→y
What is FOLLOW(Q)?
a) {R} b) {w}
c) {w,y} d) {w,$}
31.
For the grammar below, a partial LL(1) parsing table is also presented along with the grammar.
Entries
that need to be filled are indicated as E1, E2 and E3. ε is the empty string, $ indicates end of input,
and |
separates alternate right hand sides of productions.
S → aAbB | bAaB | ε
A→S
B→S
The FIRST and FOLLOW sets for the nonterminals A and B are
a) FIRST (A)={a, b, ε}=FIRST (B) b) FIRST (A)={a, b, $}

FOLLOW (A)={a, b} FIRST (B)={a, b, ε}
FOLLOW (B)={a, b, $} FOLLOW (A)={a,b}
FOLLOW (B)={$}
c) FIRST (A)={a, b, ε}=FIRST (B), d) FIRST (A)={a,b}=FIRST (B)

FOLLOW (A)={a,b} FOLLOW (A)={a, b}
FOLLOW (B)=$ FOLLOW (B)={a, b}
32. Which one of the following kinds of derivation is used by LR parsers?
a) Leftmost b) Leftmost in reverse
c) Rightmost d) Rightmost in reverse
33. Consider the following grammar:

S → aSB | d
B→b
The number of reduction steps taken by a bottom-up
parser while accepting the string aaadbbb is ______.
Ans.
34. Consider the grammar defined by the following

production rules, with two operator * and +
S→T*P
T→U|T*U
P→Q+P|Q
Q → Id
U → Id
Which one of the following is TRUE?
a) + is left associative, while * is right b) + is right associative, while * is left

associative associative
c) Both + and * are right associative d) Both + and * are left associative
35.
The attributes of three arithmetic operators in some programming language are given below.
The value of the expression 2 – 5 + 1 – 7 * 3 in this language is ________.
Ans.
36. One of the purposes of using intermediate code in compilers is to
a) make parsing and semantic analysis simpler. b) improve error recovery and error reporting.
c) increase the chances of reusing the machine d) improve the register allocation.
independent
code optimizer in other compilers
37.
Consider the DFA A given below. Which of the following are FALSE?
1. Complement of L(A) is context-free.
2. L(A) = L((11*0 + 0) (0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal DFA
4. A accepts all strings over {0, 1} of length at least 2.
a) 1 and 3 only b) 2 and 4 only
c) 2 and 3 only d) 3 and 4 only
38.
The above DFA accepts the set of all strings over {0,1} that
a) Begin either with 0 or 1. b) End with 0.
c) End with 00. d) Contain the substring 00.
39.
What is the complement of the language accepted by the NFA shown below?
Assume Σ = {a} and ε is the empty string.
a) ϕ b) {ε}
c) a* d) {a, ε}
40. Consider the following grammar for arithmetic expressions:

E→E+E
E→E*E
E→(E)
E → id
Which of the following statements is true regarding the given grammar?
a) The grammar is unambiguous and generates b) The grammar is ambiguous and can
unique parse trees for each valid expression. generate multiple parse trees for some
expressions.
c) The grammar does not generate expressions d) The grammar cannot generate expressions
with addition and multiplication. with parentheses.
41. Given the grammar:

E→E+T|T
T→T*F|F
F → ( E ) | id
Which non-terminal(s) in the given grammar exhibit left recursion?
a) E only b) T only
c) Both E and T d) F only
42.
Which of the regular expressions given below represent the following DFA?
I. 0* 1(1 + 00* 1)*
II. 0* 1* 1 + 11* 0* 1
III. (0 + 1)* 1
a) I and II only b) I and III only
c) II and III only d) I, II and III
43.
Which of the following languages is/are regular?
a) L1 and L3 only b) L2 only
c) L2 and L3 only d) L3 only
44.
Which of the following are regular sets?
a) I and IV only b) I and III only
c) IV only d) III only
45. Consider the following statements:

I. If L1 <UNION> L2 is regular, then both L1 and L2 must be regular.
II. The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE?
a) Both I and II b) II only
c) I only d) Neither I not II
46. S → aSa | bSb | a | b

The language generated by the above grammar over the alphabet {a, b} is the set of
a) All palindromes b) All odd length palindromes
c) Strings that begin and end with the same d) All even length palindromes
symbol
47.
Which of the following languages are context-free
a) L1 and L2 only b) L1 and L3 only
c) L2 and L3 only d) L3 only
48. Which one of the following is FALSE?
a) There is a unique minimal DFA for every b) Every NFA can be converted to an equivalent
regular language. PDA.
c) Complement of every context-free language d) Every nondeterministic PDA can be

is recursive. converted
to an equivalent deterministic PDA.
49. Which of the following pairs have DIFFERENT expressive power
a) Deterministic finite automata (DFA) and b) Deterministic push down automata (DPDA)
Nondeterministic and
finite automata (NFA) Non-deterministic push down automata
(NPDA)
c) Deterministic single-tape Turing machine and d) Single-tape Turing machine and multi-tape
Non-deterministic single – tape Turing Turing machine
machine
50. Which of the following statements is false?
a) Every NFA can be converted to an equivalent b) Every non-deterministic Turing machine can
DFA. be
converted to an equivalent deterministic
Turing
machine.
c) Every regular language is also a context-free d) Every subset of a recursively enumerable set
language. is
recursive.
Answer Keys
1. c) This solution violates 2. a) Mutual exclusion but not 3. d) 3

progress requirement. progress
4. d) 8 5. b) O(n) 6. b) Merge Sort
7. b) O(n^2) 8. a) O(n log n) 9. c) O(n^2 log n)
10. d) O(n^2 logn) 11. Merge Sort - O(nlogn), 12. Fibonacci Series -
F(n)=F(n−1)+F(n−2),
Quick Sort - O(n^2),
Towers of Hanoi -
Insertion Sort - O(n^2), T(n)=2T(n−1)+1,
Selection Sort - O(n^2), Quick Sort (Average) -

T(n)=2T(n/2)+O(n),
Bubble Sort - O(n^2)
Factorial - T(n) = n * T(n-1)
13. a) Circular formation , In the

14. b) 4if every system 15. a) Paging fragmentation , Paging
wait is a of d) resource- edge is an is not in helps c) incurs
necessary deadlock. allocation assignment deadlock solve memory
condition graph of edge, then state. the overhea
for the a the issue of
system, external
16. b) Page frame number 17. d) 56 bytes 18. a) Recursive descent

parser
19. b) LALR 20. a) The best theta(n) 21. c) theta(n^2)

algorithm for time in
the problem the worst
takes case.
22. a) Full: (REAR Empty: 23. b) II only 24. 4

+ 1) mod n = REAR =
= FRONT = FRONT
25. (P) Tower of Hanoi with n 26. b) Only S1 and S2 are 27. P: Lexical analysis -
disks. TRUE
(iii) Regular expressions,
- theta(2^n),
(Q) Binary search given n Q: Top down parsing -
sorted numbers
- theta(log n), (i) Leftmost derivation,
(R) Heap sort given n
R: Semantic analysis -
numbers at the worst
case. (ii) Type checking,

- theta(n log n),
S: Runtime environment -
(S) Addition to two n × n
matrices (iv) Activation records
- theta(n^2)
28. b) lexical analysis 29. c) unary - 30. c) {w,y}
31. a) FIRST FOLLOW FOLLOW

32. d) Rightmost in reverse 33. 7
(A)={a, b, (A)={a, b} (B)={a, b,
ε}=FIRST $}
(B)
34. b) + is right associative, 35. 9 36. c) increase the code

while * is left chances of optimizer
associative reusing the in other
machine compilers
independent
37. d) 3 and 4 only 38. c) End with 00. 39. b) {ε}
40. b) The grammar is 41. c) Both E and T 42. b) I and III only
ambiguous and can
generate multiple parse
trees for some
expressions.
43. a) L1 and L3 only 44. a) I and IV only 45. d) Neither I not II
46. b) All odd length 47. b) L1 and L3 only 48. d) Every to an

palindromes nondeterministic equivalent
PDA can be deterministic
converted PDA.
49. b) Deterministic Non- 50. d) Every subset recursive.

push down deterministic of a
automata push down recursively
(DPDA) and automata enumerable
(NPDA) set is

CSE334 - ETE - PracticeSet - Quizizz

Uploaded by

Copyright:

Available Formats

CSE334 - ETE - PracticeSet - Quizizz

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CSE334 - ETE - PracticeSet - Quizizz

Uploaded by

Copyright:

Available Formats

5/14/24, 11:19 PM CSE334_ETE_PracticeSet | Quizizz

1. Consider the following two-process synchronization solution

a) This is a correct two-process synchronization b) This solution violates mutual exclusion

Consider the methods used by processes P1 and P2

The following two functions P1 and P2 that share a

4. Suppose a semaphore 𝑆S is initialized to 10. Two processes 𝑃1P1​and 𝑃2P2​operate as follows:

a) O(n log n) b) O(n)

a) Quick Sort b) Merge Sort

c) Selection Sort d) Heap Sort

7. What is the time complexity of the following code?

c) O(n log n) d) O(n^3)

8. What is the time complexity of the following code?

a) O(n log n) b) O(n^2)

9. What is the time complexity of the following code?

a) O(n^3 log n) b) O(n^3)

c) O(n^2 log n) d) O(n log n)

c) O(nlogn) d) O(n^2 logn)

11. Match the following

Quick Sort O(nlogn)

Bubble Sort O(n^2)

Selection Sort O(n^2)

Merge Sort O(n^2)

Insertion Sort O(n^2)

12. Match the following recurrence relations

Quick Sort (Average) F(n)=F(n−1)+F(n−2)

Towers of Hanoi T(n)=2T(n−1)+1

Fibonacci Series T(n)=2T(n/2​)+O(n)

Factorial T(n) = n * T(n-1)

13. Which of the following statements is/are TRUE with

c) If the current allocation of resources to d) In the resource-allocation graph of a system,

c) Paging incurs memory overheads d) Multi-level paging is necessary to support

16. The essential content(s) in each entry of a page table is/are

a) Virtual page number b) Page frame number

17. Consider a C program that uses structures to manage student records:

18. Which is not a bottom up parser?

a) Recursive descent parser b) Shift-reduce parser

c) LR(0) parser d) SLR parser

19. YACC uses which type of parsing?

a) theta(n) b) theta(n log n)

a) Full: (REAR + 1) mod n = = FRONT b) Full: (REAR + 1) mod n = = FRONT

c) Full: REAR = = FRONT d) Full:(FRONT + 1) mod n = = REAR

c) Both I and II d) Neither I nor II

25. Match the algorithms with their time complexities:

(P) Tower of Hanoi with n disks. theta(2^n)

(S) Addition to two n × n matrices theta(log n)

(R) Heap sort given n numbers at

(Q) Binary search given n sorted

a) Only S1 is TRUE b) Only S1 and S2 are TRUE

P: Lexical analysis (iii) Regular expressions

Q: Top down parsing (i) Leftmost derivation

S: Runtime environment (ii) Type checking

R: Semantic analysis (iv) Activation records

28. In a compiler, keywords of a language are

a) syntactic analysis b) lexical analysis

c) code generation d) semantic analysis

30. Consider the following grammar:

a) FIRST (A)={a, b, ε}=FIRST (B) b) FIRST (A)={a, b, $}

c) FIRST (A)={a, b, ε}=FIRST (B), d) FIRST (A)={a,b}=FIRST (B)

32. Which one of the following kinds of derivation is used by LR parsers?

4. Suppose a semaphore 𝑆S is initialized to 10. Two processes 𝑃1P1and 𝑃2P2operate as follows:

Fibonacci Series T(n)=2T(n/2)+O(n)