U.G.C. NET Exam. Dec. 2020-June 2021 Paper II (COMPUTER SCIENCE & APPLICATIONS)

Total Questions: 100

41. The postfix form of the expression (A + B) * (C * D ‐ E) * F / G is _______ .

Correct Answer: (c) A B + C D * E – * F * G /
Solution:

postfix expression-
⇒ ((A + B) *((C + D) – E)) * F)/G
⇒ ((AB + ) * ((CD * ) E – )) F * ) G/
⇒ ((AB + ) (CD * E –) * )) F * ) G /
⇒ AB + CD * E – * F * G /

42. A double‐ended queue (dequeue) supports adding and removing items from both the ends of the queue. The operations supported by dequeue are AddFront(adding item to front of the queue), AddRear(adding item to the rear of the queue), RemoveFront(removing item from the front of the queue), and RemoveRear(removing item from the rear of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What’s the time complexity of performing AddFront() and AddRear() assuming m is the size of the stack and n is the number of elements?

Correct Answer: (b) O(1) and O(n)
Solution:O(1) and O(n)

43. Two balanced binary trees are given with m and n elements, respectively. They can be merged into a balanced binary search tree in ____ time.

Correct Answer: (b) O(m+n)
Solution:

First we store the inorder traversals of both the trees in two separate arrays and then we can merge these sorted sequences in O(m+n) time. And then we construct the balanced tree from this final sorted array.

44. A data structure is required for storing a set of integers such that each of the following operations can be done in O(log n) time, where n is the number of elements in the set.

• Deletion of the smallest element
• Insertion of an element if it is not already present in the set
Which of the following data structures can be used for this purpose?

Correct Answer: (b) A balanced binary search tree can be used but not a heap.
Solution:A balanced binary search tree can be used but not a heap.

45. Consider the following graph.

Correct Answer: (d) I, III, and IV only
Solution:I, III, and IV only

46. Given below are two statements

Statement I: In an undirected graph, number of odd degree vertices is even.
Statement II: In an undirected graph, sum of degrees of all vertices is even.
In light of the above statements, choose the correct answer from the options given below

Correct Answer: (a) Both Statement I and Statement II are true.
Solution:

47. Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?

Correct Answer: (a) C, B, D, A
Solution:

48. The order of a leaf node in a B+ tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the value field is 9 bytes long and a block pointer is 6 bytes long, what is the order of the leaf node?

Correct Answer: (a) 63
Solution:

Disk block size = 1024 bytes.
Data record pointer size, r = 7 bytes
Value size, V = 9 bytes
Disk Block ptr, P = 6 bytes.
Let order of leaf be m.A leaf node in B + tree contains at most m record pointers, at most m values, and one disk block pointer.
r × m + V × m + P < = 1024
16 m < = 1018
m = < 63

49. A hash function h defined as h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18?

Correct Answer: (c) 5
Solution:

Keys 44, 45, 79, 55, 91, 18, 63
h (key) = key mod 7
h (44) = 44 mod 7 = 2
h (45) = 45 mod 7 = 3
h (79) = 79 mod 7 = 2
but 2 is already filled 44, linear probing is applied but 3 is also filled.
So 79 will occupy 4
h (55) = 55 mod 7 = 6
h (91) = 91 mod 7 = 0
h (18) = 18 mod 7 = 4
but 4 is occupied by 79 So, it will occupy 5.
h (63) = 63 mod 7 = 0 , 0 is also occupied so, it will occupy1.

50. In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Here, n and m are number of vertices and edges, respectively. Match each algorithm with its time complexity.


Choose the correct answer from the options given below :

Correct Answer: (a) A ‐ III, B ‐ I, C ‐ II, D ‐ IV
Solution: