Q. 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 cannot be implemented in O(1) time ?

View solution

Q. Consider an undirected graph G where self-loops are not allowed. 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 or |b–d| ≤ 1. The number of edges in this graph is

View solution

Q. The runtime for traversing all the nodes of a binary search tree with n nodes and printing them in an order is

View solution

Q. 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 ?

View solution

Q. Given the following prefix expression:

* + 3 + 3 ↑ 3 + 3 3 3

What is the value of the prefix expression?

View solution

Q. A priority queue is implemented as a max-heap. Initially, it has five elements. The level-order traversal of the heap is as follows:

20, 18, 15, 13, 12

Two new elements ‘10’ and ‘17’ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the element is:

View solution

Q. If there are n integers to sort, each integer has d digits, and each digit is in the set  {1, 2, …, k}, radix sort can sort the numbers in:

View solution

Q. Match the following:

a. Prim’s algorithm                  i. O(V^2E)
b. Bellman-Ford algorithm     ii. O(VE lgV)
c. Floyd-Warshall algorithm   iii. O(E lgV)
d. Johnson’s algorithm           iv. O(V^3)

Where V is the set of nodes and E is the set of edges in the graph.

Codes :
     a    b   c   d

View solution

Q. Constructors have ............. return type.

View solution

Q. Method over-riding can be prevented by using final as a modifier at ...............

View solution

Q. Which of the following is a correct statement?

View solution

Q. Which of the following is not a correct statement?

View solution

Q. Given the following statements:

(a) To implement Abstract Data Type, a programming language require a syntactic unit to encapsulate type definition.
(b) To implement ADT, a programming language requires some primitive operations that are built in the language processor.
(c) C++, Ada, Java 5.0, C#2005 provide support for parameterised ADT.

Which one of the following options is correct?

View solution

Q. Match the following types of variables with the corresponding programming languages:

(a) Static variables                   (i) Local variables in Pascal
(b) Stack dynamic                    (ii) All variables in APL
(c) Explicit heap dynamic       (iii) Fortran 77
(d) Implicit heap dynamic       (iv) All objects in JAVA

Codes:
      (a)   (b)   (c)   (d)

View solution

Q. The number of different binary trees with 6 nodes is .............

View solution

Q. Let A[1...n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i,j) is called an inversion of A. What is the expected number of inversions in any permutation on n elements?

View solution

Q. Which one of the following array represents a binary max-heap?

View solution

Q. Match the following:

(a) Huffman codes                              (i) O(n2)
(b) Optimal polygon triangulation     (ii) θ(n3)
(c) Activity selection problem             (iii) O(nlgn)
(d) Quicksort                                         (iv) θ(n)

Codes:
      (a)   (b)   (c)   (d)

View solution

Q. Suppose that we have numbers between 1 and 1000 in a binary search tree and want to search for the number 364. Which of the following sequences could not be the sequence of nodes examined?

View solution

Q. A triangulation of a polygon is a set of T chords that divide the polygon into disjoint triangles. Every triangulation of n-vertex convex polygon has ................ chords and divides the polygon into ............... triangles.

View solution