Q. The solution of recurrence relation:

T(n) = 2T(sqrt(n)) + lg (n)

is

View solution

Q. The elements 42,25,30,40,22,35,26 are inserted one by one in the given order into a max-heap. The resultant max-heap is sorted in an array implementation as

View solution

Q. Consider the following postfix expression with single digit operands:

623∗/42∗+68∗−

The top two elements of the stack after the second ∗ is evaluated, are:

View solution

Q. A binary search tree is constructed by inserting the following numbers in order:

60, 25, 72, 15, 30, 68, 101, 13, 18, 47, 70, 34

The number of nodes in the left subtree is

View solution

Q. In a ternary tree, the number of internal nodes of degree 1, 2, and 3 is 4, 3, and 3 respectively. The number of leaf nodes in the ternary tree is

View solution

Q. Match List-I with List-II and choose the correct answer from the code given below:

List I (Graph Algorithm) List II (Time Complexity)
(a) Dijkstra’s algorithm (i) O(E lg E)
(b) Kruskal’s algorithm (ii) Θ(V3)
(c) Floyd-Warshall algorithm (iii) O(V2)
(d) Topological sorting (iv) Θ(V+E)

where V and E are the number of vertices and edges in graph respectively.

View solution

Q. In K-coloring of an undirected graph G=(V,E) is a function. c:V→{0,1,…,K−1} such that c(u)≠c(v) for every edge (u,v)∈E.

Which of the following is not correct?

View solution

Q. Consider a singly linked list. What is the worst case time complexity of the best-known algorithm to delete the node a, pointer to this node is q, from the list?

View solution

Q. The second smallest of n elements can be found with ............... comparisons in the worst case.

View solution

Q. Consider the following statements related to AND-OR Search algorithm.

S1: A solution is a subtree that has a goal node at every leaf.
S2: OR nodes are analogous to the branching in a deterministic environment.
S3: AND nodes are analogous to the branching in a non-deterministic environment.

Which of the following is true referencing the above statements?

View solution

Q. The solution of the recurrence relation
T(m) = T(3m/4) + 1 is:

View solution

Q. Consider the array A=<4, 1, 3, 2, 16, 9, 10, 14, 8, 7>. After building heap from the array A, the depth of the heap and the right child of max-heap are .............. and .................. respectively. (Root is at level 0).

View solution

Q. A hash function h defined 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?

View solution

Q. Which of the following algorithms solves the single-source shortest paths?

View solution

Q. A text is made up of the characters A, B, C, D, E each occurring with the probability 0.08, 0.40, 0.25, 0.15 and 0.12 respectively. The optimal coding technique will have the average length of:

View solution

Q. A binary search tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 19 leaves:

View solution

Q. Match the following with respect to algorithm paradigms :

List - I
(a) The 8-Queen’s problem
(b) Single-Source shortest paths
(c) STRASSEN’s Matrix multiplication
(d) Optimal binary search trees

List - II
(i) Dynamic programming
(ii) Divide and conquer
(iii) Greedy approach
(iv) Backtracking

Code:
(a) (b) (c) (d)

View solution

Q. The maximum number of comparisons needed to sort 9 items using radix sort is (assume each item is 5 digit octal number):

View solution

Q. A 5-ary tree is tree in which every internal node has exactly 5 children. The number of left nodes in such a tree with 8 internal nodes will be:

View solution

Q. Consider a Boolean function of ‘n’ variables. The order of an algorithm that determines whether the Boolean function produces a output 1 is:

View solution