UGC NET COMPUTER SCIENCE SOLVED PAPERS 2014-16 - UGC NET Computer Science Paper 2 August 2016

21. Consider an implementation of unsorted single linked list. Suppose it has its representation with a head and a tail pointer (i.e. pointers to the first and last nodes of the linked list). Given the representation, which of the following operation can not be implemented in O(1) time ?

  • Option : D
  • Explanation :
    Deletion of the last node of the linked list, we need address of second last node of single linked list to make NULL of its next pointer. Since we can not access its previous node in singly linked list, so need to traverse entire linked list to get second last node of linked list. So, option (D) is correct.
Cancel reply
Cancel reply

22. Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {i,f): 1 ≤ i ≤ 12 , 1 ≤ j ≤ 12}. There is an edge between (a,b) and (c,d) if |a - c| ≤ 1 and |b - d| ≤ 1 . The number of edges in the graph is _____________.

  • Option : C
  • Explanation :
    The vertex set of G is {(i, j): 1 <= i <= 12, 1 <= j <= 12}.
    There is an edge between (a, b) and (c, d) if |a − c| <= 1 and
    |b − d| <= 1.

    There can be total 12*12 possible vertices. The vertices are (1, 1),
    (1, 2) ....(1, 12) (2, 1), (2, 2), ....

    The number of edges in this graph?
    Number of edges is equal to number of pairs of vertices that satisfy above conditions. For example, vertex pair {(1, 1), (1, 2)} satisfy above condition.

    For (1, 1), there can be an edge to (1, 2), (2, 1), (2, 2). Note that there can be self-loop as mentioned in the question.
    Same is count for (12, 12), (1, 12) and (12, 1)

    For (1, 2), there can be an edge to (1, 1), (2, 1), (2, 2), (2, 3), (1, 3)
    Same is count for (1, 3), (1, 4)....(1, 11), (12, 2), ....(12, 11)

    For (2, 2), there can be an edge to (1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), (3, 3)
    Same is count for remaining vertices.

    For all pairs (i, j) there can total 8 vertices connected to them if i and j are not in {1, 12}

    There are total 100 vertices without a 1 or 12. So total 800 edges.

    For vertices with 1, total edges = (Edges where 1 is first part) +
    (Edges where 1 is second part and not first part)
    = (3 + 5*10 + 3) + (5*10) edges

    Same is count for vertices with 12
    Total number of edges:
    = 800 + [(3 + 5*10 + 3) + 5*10] + [(3 + 5*10 + 3) + 5*10]
    = 800 + 106 + 106
    = 1012
    Since graph is undirected, two edges from v1 to v2 and v2 to v1 should be counted as one.
    So total number of undirected edges = 1012/2 = 506.
Cancel reply
Cancel reply

24. Consider the following statements: S1: A queue can be implemented using two stacks. S2: A stack can be implemented using two queues. Which of the following is correct?

  • Option : C
  • Explanation :
    A queue can be implemented using minimum two stacks. A stack can be implemented using minimum two queues. Both staement are true. So, option (C) is correct.
Cancel reply
Cancel reply

25. Given the following prefix expression: * + 3 + 3 ↑ 3 + 3 3 3 What is the value of the prefix expression ?

  • Option : C
  • Explanation :
    We have prefix expression:
    * + 3 + 3 ↑ 3 + 3 3 3
    = * + 3 + 3 ↑ 3 6 3
    = * + 3 + 3 729 3
    = * + 3 732 3
    = * 735 3
    = 2205
    So, option (C) is correct.
Cancel reply
Cancel reply