U.G.C. NET Exam. December 2023 Paper II (COMPUTER SCIENCE)

Total Questions: 100

21. Let L = {ab, aa, baa}. Which of the following strings are not in L*.

Correct Answer: (c) baaaaabaaaab
Solution:

Any combination of strings in set {ab, aa, baa} will be in L*.
(a) "abaabaaabaa" can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are "ab aa baa ab aa''
(b) "aaaabaaaa" can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are "aa ab aa aa"
(c) "baaaaabaaaab" cannot be partitioned as a combination of strings in set {ab, aa, baa}
(d) "baaaaabaa" can be partitioned as a combination of strings in set {ab, aa, baa}, The partitions are " baa aa ab aa"
So, string' baaaaabaaaab' is not in L* .

22. Let A = {a, b} and L = A*. Let x = {aⁿ bⁿ , n>0}. The languages L U X and X are respectively:

Correct Answer: (c) Regular, Not regular
Solution:

Given-
A = {a, b}
L = A*
X = {aⁿ bⁿ , n > 0},
The language L U X is regular because it is the union of two regular languages, L = A* and x = {aⁿ bⁿ , n > 0}, and regular languages are closed under union.
language X is not regular because it represents the language of strings is the form an b n for n> 0, which cannot be recognized by a finite automation due to the requirement to count the number of a's and b's and ensure they are equal. Therefore, X is not regular.

23. Which of the following symbol table implementation is best suited if access time is to be minimum?

Correct Answer: (c) Hash Table
Solution:

Hash table implementations are best suited for minimizing access time, especially for lookups and inserts, as they provide constant time average case performance for these operations. Its access time is 0(1). However, their performance can degrade if there are many collisions or if the hash function is poorly designed.

24. Consider a Grammar E → E + n E × n n for a sentence n + n × n, the handles in the right sentential form of the reduction are?

Correct Answer: (d) n, E + n and E × n
Solution:

Given the grammar
E → E + n E n n ×
For a sentence n + n × n, the handles in the rightsentential form of the reduction are-
E → E × n                        {Applying E → E × n}
→ E + n × n                     {Applying E → E + n}
→ n + n × n                     {Applying E → n}
Hence, the handles in right sentential form is n, E + n and E × n.

25. Which data structure is typically used to implement hash table?

Correct Answer: (b) Array
Solution:

A Hash table is a data structure that stores some information and the information has basically two main components, i.e. Key and value. The most commonly used data structure to implement a hash table is an array. The efficiency of mapping depends upon the efficiency of the hash function used for mapping.

26. Which collision resolution technique involves maintaining a linked list of collided keys?

Correct Answer: (c) Chaining
Solution:

Chaining is a collision resolution technique used in hash tables. In chaining, when a collision occurs (two keys hash to the same index), the collided keys are stored in linked lists at that index. This allows multiple keys to be stored at the same location in the hash table. when searching for a key, the hash function is used to find the correct index, and then the linked list at that index is traversed to find the desired key.

27. Consider the following functions:

Correct Answer: (d) f(n) is 0 (g(n))
Solution:

28. 2 – 3 – 4 trees are B – trees of order 4. They are isometric of _______trees.

Correct Answer: (d) Red-Black
Solution:

2 – 3 – 4 tree (also called a 2 – 4 tree) is a self-balancing data structure that can be used to implement dictionaries. 2 – 3 – 4 trees are B-trees of order 4, like B-trees in general, they can search, insert and delete in 0 (log n) time, 2 – 3 – 4 trees are isomorphic to Red-Black trees, meaning that they are equivalent data structures. In other words, for every 2 – 3 – 4 tree, there exists at least one and at most one redblack tree with data elements in the same order.

29. The average time required to search a storage location in memory and obtain its contents is called:

Correct Answer: (a) Access time
Solution:

The average time required to search a storage location in memory and abtain its contents is called Access time. Access time is the interval between the beginning of one storage device access and the beginning of the subsequent access.
Access time = Latency time + Transfer time.

30. One of the purposes of using intermediate code in compilers is to:

Correct Answer: (c) increase the chances of reusing the machine independent cede optimizer in other compilers
Solution:

After semantic Analysis, the code is converted into intermediate code which is platform (os + hardware) independent, the advantage of converting into intermediate code is to improve the performance of code generation and to increase the chances of reusing the machine- independent code optimizer in other compilers. So, option (c) is correct.