At ProProfs Quizzes, our dedicated in-house team of experts takes pride in their work. With a sharp eye for detail, they meticulously review each quiz. This ensures that every quiz, taken by over 100 million users, meets our standards of accuracy, clarity, and engagement.
If L is context-free language, then, is L' also context-free?
If L is regular language, then, is L' also regular?
If L is recursive language, then, is L' also recursive?
A.
1,2,3,4
B.
1,2
C.
2,3,4
D.
3,4
Correct Answer D. 3,4
Explanation The correct answer is 3,4.
3. If L is a context-free language, then L' is also a context-free language. This is because the complement of a context-free language is also context-free.
4. If L is a regular language, then L' is also a regular language. This is because the complement of a regular language is also regular.
Rate this question:
2.
Given the language L={ab, aa, baa}, which of the following strings are in L*?
abaabaaabaa
aaaabaaaa
baaaaabaaaab
baaaaabaa
A.
1,2 and 3
B.
2,3 and 4
C.
1,2 and 4
D.
1,3 and 4
Correct Answer C. 1,2 and 4
Explanation The language L* represents the set of all possible combinations of strings from L, including the empty string. In this case, the strings "ab", "aa", and "baa" are all elements of L. Therefore, the strings 1, 2, and 4 are in L* because they can be formed by concatenating these elements of L.
Rate this question:
3.
Register renaming is done in pipelined processors
A.
As an alternative to register allocation at compile time
B.
For efficient access to function parameters and local variables
C.
To handle certain kinds of hazards
D.
As part of address translation
Correct Answer C. To handle certain kinds of hazards
Explanation Register renaming is done in pipelined processors to handle certain kinds of hazards. Hazards occur when there is a dependency between instructions, such as a data dependency or a structural dependency. Register renaming allows the processor to rename the registers, giving each instruction its own unique set of registers, and thus eliminating the hazards. This improves the efficiency of the pipeline by allowing instructions to be executed out of order and in parallel, without causing any conflicts or dependencies. By renaming registers, the processor can ensure that instructions can be executed smoothly and without any stalls or delays.
Rate this question:
4.
The amount of ROM needed to implement a 4 bit multiplier is
A.
64 bits
B.
128 bits
C.
1 Kbits
D.
2 Kbits
Correct Answer D. 2 Kbits
Explanation A 4-bit multiplier is capable of multiplying two 4-bit numbers, resulting in an 8-bit product. Each bit of the product requires a storage location in ROM, so a total of 8 bits are needed. Since 1 kilobit (1 Kbit) is equal to 1024 bits, and 2 Kbits is double that amount, it is sufficient to store the 8-bit product. Therefore, the correct answer is 2 Kbits.
Rate this question:
5.
Let W(n) and A(n) denote respectively, the worst case and average case running time of an
algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?
A.
A(n) =Ω(W(n))
B.
A(n) = Ɵ(W(n))
C.
A(n) = O(W(n))
D.
A(n) = o(W(n))
Correct Answer C. A(n) = O(W(n))
Explanation The statement A(n) = O(W(n)) means that the average case running time of an algorithm is bounded above by the worst case running time. This is always true because in the worst case scenario, the algorithm will take at least as long as the average case scenario. Therefore, the average case running time is always less than or equal to the worst case running time.
Rate this question:
6.
Which of the following statements are TRUE about an SQL query?P : An SQL query can contain a HAVING clause even if it does not have a GROUP BY clauseQ : An SQL query can contain a HAVING clause only if it has GROUP BY clauseR : All attributes used in the GROUP BY clause must appear in the SELECT clauseS : Not all attributes used in the GROUP BY clause need to appear in the SELECT clause
A.
P and R
B.
P and S
C.
Q and R
D.
Q and S
Correct Answer B. P and S
Explanation An SQL query can contain a HAVING clause even if it does not have a GROUP BY clause (P) because the HAVING clause is used to filter the result set based on conditions applied to aggregate functions, and it can be used without a GROUP BY clause.
Not all attributes used in the GROUP BY clause need to appear in the SELECT clause (S) because the GROUP BY clause is used to group the result set based on specific attributes, but it is not necessary to include all of those attributes in the SELECT clause.
Rate this question:
7.
Given the basic ER and relational models, which of the following is INCORRECT?
A.
An attribute of an entity can have more than one value
B.
An attribute of an entity can be composite
C.
In a row of a relational table, an attribute can have more than one value
D.
In a row of a relational table, an attribute can have exactly one value or a NULL value
Correct Answer C. In a row of a relational table, an attribute can have more than one value
Explanation In a row of a relational table, an attribute can have more than one value. This statement is incorrect because in a relational model, each attribute in a row of a table can only have a single value.
Rate this question:
8.
The protocol data unit (PDU) for the application layer in the Internet stack is
A.
Segment
B.
Datagram
C.
Message
D.
Frame
Correct Answer C. Message
Explanation In the Internet stack, the protocol data unit (PDU) for the application layer is a message. The application layer is responsible for providing services directly to the end user, such as email, file transfer, and web browsing. These services require the exchange of messages between the application on one device and the application on another device. Therefore, the PDU at the application layer is a message, which contains the data being exchanged between the applications.
Rate this question:
9.
A process executes the codefork ();fork ();fork ();The total number of child processes created is
A.
3
B.
4
C.
7
D.
8
Correct Answer C. 7
Explanation Each time the fork() function is called, it creates a new child process. In this case, the fork() function is called three times, resulting in the creation of three child processes. However, each child process also executes the fork() function, resulting in the creation of additional child processes. Therefore, the total number of child processes created is 7.
Rate this question:
10.
The decimal value 0.5 in IEEE single precision floating point representation has
A.
Fraction bits of 000…000 and exponent value of 0
B.
Fraction bits of 000…000 and exponent value of -1
C.
Fraction bits of 100…000 and exponent value of 0
D.
No exact representation
Correct Answer B. Fraction bits of 000…000 and exponent value of -1
Explanation The decimal value 0.5 in IEEE single precision floating point representation has fraction bits of 000…000 and exponent value of -1. In IEEE single precision, the fraction bits represent the binary fraction part of the number, and in this case, it is all zeros since 0.5 in binary is 0.1. The exponent value represents the power of 2 to multiply the fraction by, and in this case, it is -1. Therefore, the binary representation of 0.5 in IEEE single precision is 0 01111110 00000000000000000000000.
Rate this question:
11.
Which of the following is TRUE?
A.
Every relation is 3NF is also in BCNF
B.
A relation R is in 3NF if every non-prime attribute of R is fully functionally dependent on
every key of R
C.
Every relation in BCNF is also in 3NF
D.
No relation can be in both BCNF and 3NF
Correct Answer C. Every relation in BCNF is also in 3NF
Explanation The given statement is true because a relation in BCNF (Boyce-Codd Normal Form) is a higher level of normalization than a relation in 3NF (Third Normal Form). BCNF ensures that there are no non-trivial functional dependencies on a candidate key, while 3NF ensures that there are no transitive dependencies. Therefore, if a relation satisfies the requirements of BCNF, it automatically satisfies the requirements of 3NF as well.
Rate this question:
12.
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem
with n discs is
A.
T(n) = 2T(n − 2) + 2
B.
T(n) = 2T(n −1) + n
C.
T(n) = 2T(n / 2) +1
D.
T(n) = 2T(n -1) +1
Correct Answer D. T(n) = 2T(n -1) +1
Explanation The given recurrence relation T(n) = 2T(n -1) +1 represents the optimal execution time of the Towers of Hanoi problem with n discs. This means that to solve the problem with n discs, the optimal execution time is equal to twice the optimal execution time of solving the problem with n-1 discs, plus 1. This relation suggests that for each additional disc, the optimal execution time increases by 2 times the optimal execution time of solving the problem with one less disc, plus 1.
Rate this question:
13.
A scheduling algorithm assigns priority proportional to the waiting time of a process. Every
process starts with priority zero(the lowest priority). The scheduler re-evaluates the process
priorities in every T time units and decides the next process to schedule. Which one of the
following is TRUE if the processes have no I/O operations and all arrive at time zero?
A.
This algorithm is equivalent to the first-come-first-serve algorithm
B.
This algorithm is equivalent to the round-robin algorithm
C.
This algorithm is equivalent to the shortest-job-first algorithm
D.
This algorithm is equivalent to the shortest-remaining-time-first algorithm
Correct Answer B. This algorithm is equivalent to the round-robin algorithm
Explanation The given scheduling algorithm assigns priority based on the waiting time of a process. Since all processes arrive at time zero and there are no I/O operations, the waiting time for each process will be the same. Therefore, all processes will have the same priority and will be scheduled in a round-robin manner. This means that each process will be given a time slice and then the scheduler will move on to the next process in a cyclical manner. Thus, the given algorithm is equivalent to the round-robin algorithm.
Rate this question:
14.
What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type A→€ and A→a) to a
string with n tokens?
A.
N/2
B.
N-1
C.
2n-1
D.
None
Correct Answer B. N-1
Explanation In a bottom-up parser, reduce moves are used to replace a group of symbols with a nonterminal. In a grammar with no epsilon- and unit-productions, each reduce move reduces the number of tokens by 1. Since we want to reduce the string with n tokens to a single nonterminal, we need to perform n-1 reduce moves. Therefore, the maximum number of reduce moves that can be taken by a bottom-up parser for this grammar is n-1.
Rate this question:
15.
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42.
Which one of the following is the postorder traversal sequence of the same tree?
A.
10,20,15,23,25,35,42,39,30
B.
15,10,25,23,20,42,35,39,30
C.
15,20,10,23,25,42,35,39,30
D.
15,10,23,25,20,35,42,39,30
Correct Answer D. 15,10,23,25,20,35,42,39,30
Explanation The given preorder traversal sequence of the binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. To obtain the postorder traversal sequence, we start from the root node (30) and traverse the left subtree first, then the right subtree, and finally the root node. By following this approach, the postorder traversal sequence of the same tree is 15, 10, 23, 25, 20, 35, 42, 39, 30.
Rate this question:
16.
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-independent code optimizer in other
compliers.
D.
Improve the register allocation.
Correct Answer C. Increase the chances of reusing the machine-independent code optimizer in other
compliers.
Explanation Using intermediate code in compilers increases the chances of reusing the machine-independent code optimizer in other compilers. This is because the intermediate code represents a higher-level abstraction of the source code, making it easier to apply optimizations that are independent of the target machine architecture. By reusing the code optimizer, developers can save time and effort in implementing similar optimizations in different compilers, leading to improved efficiency and performance across multiple platforms.
Rate this question:
17.
Which of the following statements are CORRECT?
Static allocation of all data areas by a compiler makes it impossible to implement recursion.
Automatic garbage collection is essential to implement recursion.
Dynamic allocation of activation records is essential to implement recursion.
Both heap and stack are essential to implement recursion.
A.
1 and 2
B.
2 and 3
C.
3 and 4
D.
1 and 3
Correct Answer D. 1 and 3
Explanation Static allocation of all data areas by a compiler makes it impossible to implement recursion because in recursion, a function calls itself repeatedly, and the compiler needs to allocate memory for each function call. With static allocation, the memory is allocated at compile-time and cannot be dynamically adjusted during runtime, which is necessary for recursion. On the other hand, dynamic allocation of activation records is essential to implement recursion because it allows the memory to be allocated and deallocated as needed during runtime. Therefore, statements 1 and 3 are correct.
Rate this question:
18.
In the context of modular software design, which one of the following combinations is
desirable?
A.
High cohesion and high coupling
B.
High cohesion and low coupling
C.
Low cohesion and high coupling
D.
Low cohesion and low coupling
Correct Answer B. High cohesion and low coupling
Explanation High cohesion refers to a module having strong internal unity, where its components are closely related and work together towards a common goal. Low coupling, on the other hand, refers to modules being loosely connected, with minimal dependencies on each other. The combination of high cohesion and low coupling is desirable in modular software design because it promotes better maintainability, flexibility, and reusability. It allows for easier modification of individual modules without affecting others, and facilitates independent development and testing of modules. This combination helps in creating modular systems that are easier to understand, modify, and maintain.
Rate this question:
19.
A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below?4, 7, 6, 1, 7, 6, 1, 2, 7, 2
A.
5
B.
7
C.
3
D.
6
Correct Answer D. 6
Explanation The total number of page faults that will occur while processing the given page reference string is 6. This can be determined by analyzing the sequence of page references and applying the LRU page replacement policy. Initially, all page frames are empty, so the first 3 page references (4, 7, 6) will result in page faults. Then, when page 1 is referenced, it will replace page 4 (the least recently used page). The next reference to page 7 is already present in a page frame, so no page fault occurs. The same applies to the next reference to page 6. However, when page 1 is referenced again, it will replace page 7. The next reference to page 2 will replace page 6. Finally, the last reference to page 7 will replace page 2, resulting in a total of 6 page faults.
Rate this question:
20.
Which one of the following is NOT performed during compilation?
A.
Dynamic memory allocation
B.
Type checking
C.
Symbol table management
D.
Inline expansion
Correct Answer A. Dynamic memory allocation
Explanation During compilation, the code is converted from a high-level language to machine code. Dynamic memory allocation, which involves allocating and deallocating memory at runtime, is not performed during compilation. This task is typically handled by the runtime environment or the operating system when the program is executed. The other options, type checking, symbol table management, and inline expansion, are all tasks that are typically performed during compilation.
Rate this question:
21.
Which one of the following is TRUE?
A.
The requirements document also describes how the requirements that are listed in the
document are implemented efficiently.
B.
Consistency and completeness of functional requirements are always achieved in
practice.
C.
Prototyping is a method of requirements validation.
D.
Requirements review is carried out to find the errors in system design.
Correct Answer C. Prototyping is a method of requirements validation.
Explanation Prototyping is a method of requirements validation because it involves creating a working model or prototype of the system to gather feedback and validate the requirements. By creating a prototype, stakeholders can visually see and interact with the system, allowing them to provide feedback and identify any issues or changes needed in the requirements. This iterative process helps to ensure that the final system meets the desired requirements and user needs.
Rate this question:
22.
Which one of the following is FALSE?
A.
User level threads are not scheduled by the kernel.
B.
When a user level thread is blocked, all other threads of its process are blocked.
C.
Context switching between user level threads is faster than context switching between
kernel level threads.
D.
Kernel level threads cannot share the code segment.
Correct Answer D. Kernel level threads cannot share the code segment.
Explanation Kernel level threads can share the code segment. Kernel level threads are managed and scheduled by the operating system kernel, which means they have direct access to the kernel's resources, including the code segment. User level threads, on the other hand, are scheduled by a thread library in user space and do not have direct access to the kernel's resources. Therefore, the statement that kernel level threads cannot share the code segment is false.
Rate this question:
23.
Which one of the following are used to generate a message digest by the network security protocols?(P) RSA(Q) SHA-1(R) DES(S) MD5
A.
P and R only
B.
Q and R only
C.
Q and S only
D.
R and S only
Correct Answer C. Q and S only
Explanation The network security protocols use SHA-1 and MD5 to generate a message digest. SHA-1 is a cryptographic hash function that produces a 160-bit (20-byte) hash value, while MD5 is a widely used hash function that produces a 128-bit (16-byte) hash value. These message digests are used to ensure the integrity and authenticity of data transmitted over the network. RSA and DES are not used for generating message digests in network security protocols.
Rate this question:
24.
Identify the correct order in which the following actions take place in an interaction between a web browser and a web server.1. The web browser requests a webpage using HTTP.2. The web browser establishes a TCP connection with the web server.3. The web server sends the requested webpage using HTTP.4. The web browser resolves the domain name using DNS.
A.
4,2,1,3
B.
1,2,3,4
C.
4,1,2,3
D.
2,4,1,3
Correct Answer A. 4,2,1,3
Explanation The correct order in which the actions take place in an interaction between a web browser and a web server is as follows: First, the web browser resolves the domain name using DNS (4). Then, the web browser establishes a TCP connection with the web server (2). Next, the web browser requests a webpage using HTTP (1). Finally, the web server sends the requested webpage using HTTP (3).
Rate this question:
25.
A canonical set of items is given below
s→ L. R
Q →R.
On input symbol < the set has
A.
A shift-reduce conflict and a reduce-reduce conflict.
B.
A shift-reduce conflict but not a reduce-reduce conflict.
C.
A reduce-reduce conflict but not a shift-reduce conflict.
D.
Neither a shift-reduce nor a reduce-reduce conflict.
Correct Answer D. Neither a shift-reduce nor a reduce-reduce conflict.
Explanation A shift-reduce conflict occurs when there is a choice between shifting the input symbol or reducing the current stack. A reduce-reduce conflict occurs when there is a choice between two or more reduction rules. In the given canonical set of items, there is no such conflict mentioned. Therefore, the answer is that there is neither a shift-reduce nor a reduce-reduce conflict.
Rate this question:
26.
Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are
resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively,are
A.
3, 0, and 1
B.
3, 3, and 3
C.
4, 0, and 1
D.
3, 0, and 2
Correct Answer A. 3, 0, and 1
Explanation The given answer, 3, 0, and 1, is correct. The hash function h(k) = k mod 9 distributes the keys into the hash table slots based on the remainder of the key divided by 9. The keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum chain length is 3, which occurs at slot 0 with keys 15, 33, and 12. The minimum chain length is 0, which occurs at slot 1, 2, 3, 4, 5, 6, 7, and 8 since no keys are hashed to those slots. The average chain length is 1, calculated by summing up the chain lengths (3+0+1+1+1+1+1+1+1) and dividing by the number of slots (9).
Rate this question:
27.
Consider the following C function in which size is the number of elements in the array E:int MyX(int *E, unsigned int size){int Y = 0;int Z;int i, j, k;for(i = 0; i < size; i++)Y = Y + E[i];for(i = 0; i < size; i++)for(j = i; j < size; j++){Z = 0;for(k = i; k <= j; k++)Z = Z + E[k];if (Z > Y)Y = Z;}return Y;}The value returned by the function MyX is the
A.
Maximum possible sum of elements in any sub-array of array E.
B.
Maximum element in any sub-array of array E.
C.
Sum of the maximum elements in all possible sub-arrays of array E.
D.
The sum of all the elements in the array E.
Correct Answer A. Maximum possible sum of elements in any sub-array of array E.
Explanation The given C function calculates the maximum possible sum of elements in any sub-array of array E. It does this by iterating through each element in the array and adding it to a variable Y. Then, it uses nested loops to check all possible sub-arrays and calculates their sum. If the sum of a sub-array is greater than the current maximum sum (stored in Y), it updates Y with the new maximum sum. Finally, it returns the maximum sum found. Therefore, the correct answer is "maximum possible sum of elements in any sub-array of array E."
Rate this question:
28.
An access sequence of cache block addresses is of length N and contains n unique block
addresses. The number of unique block addresses between two consecutive accesses to the
same block address is bounded above K. What is the miss ratio if the access sequence is
passed through a cache of associativity A≥ k exercising least-recently-used replacement
policy?
A.
N/N
B.
L/N
C.
1/A
D.
K/n
Correct Answer A. N/N
Explanation The miss ratio is determined by the number of unique block addresses (n) divided by the total number of block addresses in the access sequence (N). This ratio represents the proportion of block addresses that were not found in the cache and resulted in a cache miss. Therefore, the miss ratio is n/N.
Rate this question:
29.
Consider two processors P1 and P2 executing the same instruction set. Assume that under
identical conditions, for the same input, a program running on P2 takes 25% less time but
incurs 20% more CPI (clock cycles per instruction) as compared to the program running on
P1. If the clock frequency of P1 is 1GHz, then the clock frequency of P2 (in GHz) is
A.
1.4
B.
1.6
C.
1.2
D.
1
Correct Answer B. 1.6
30.
Consider an undirected random graph of eight vertices. The probability that there is an edge
between a pair of vertices is ½. What is the expected number of unordered cycles of length
three?
A.
3
B.
1
C.
7
D.
8
Correct Answer C. 7
Explanation In an undirected random graph of eight vertices, the probability of an edge between any pair of vertices is 1/2. To find the expected number of unordered cycles of length three, we can use the formula E(X) = p * C(n, k), where E(X) is the expected value, p is the probability of success (in this case, the probability of having an edge between two vertices), n is the total number of vertices, and k is the length of the cycle. In this case, p = 1/2, n = 8, and k = 3. Plugging these values into the formula, we get E(X) = (1/2) * C(8, 3) = 7. Therefore, the expected number of unordered cycles of length three is 7.