Computer Science Concepts

(1) Let i, j and n be the integer variables of the C program fragment given below.
val (j) = θ (n/2) val (j) = θ (log n) val (j) = θ (2n) val (j) = θ (n)

(2) In a complete binary tree, LASTPOST denotes the last vertex visited in a post order traversal, LASTIN denotes the last vertex visited in an inorder traversal and LASTPRE denotes the last vertex visited in a preorder traversal. The statement, which always holds true, is
LASTIN = LASTPRE LASTPRE = LASTPOST LASTIN = LASTPOST None of the above.

(3) Which one of the following statement is false?
√ logn = O (log log n) 100n log n = O (nlogn/100) 2n ≠ O (nk) If 0x = O (ny)

(4) Consider an unweighted, undirected connected graph. In terms of time complexity, the shortest path from a node S to every other node is most efficiently computed by
Performing a DFS starting from S Performing a BFS starting from S Warshall’s algorithm Dijkstra’s algorithm starting from S

(5) _____________ in place sorting algorithm needs the minimum number of swaps.
Selection sort Quick sort Insertion sort Heap sort

Algorithm questions and answers

(1) Starting from the root and performing ____________, level order traversal of a rooted tree can be done.
Breadth first search Depth first search In-order traversal Pre-order traversal

(2) We have a hash function and a hash table. The size of hash table is 7 with starting index zero. The hash function is (3x+4) mod 7. Assume that initially the hash table is empty and the sequence 1, 3, 8, 10 is inserted into the table using closed hashing. The content of the table is (‘_’ denotes an empty location in the table)
1, _, _, _, _, _, 3 8, _, _, _, _, _, 10 1, 8, 10, _, _, _, 3 1, 10,8, _, _, _, 3

(3) Which one of the following statement is false if G is an undirected graph with distinct edge weight, Emax is the edge with maximum weight and Emin is the edge with minimum weight?
Emin is present in every minimum spanning tree of G Emax is not present in any minimum spanning tree. The removal of Emax must disconnect G, if Emax is in a minimum spanning tree. G has a unique minimum spanning tree.

(4) Consider an array L. If an element in an array L is greater than all elements to the right of it then it is called a leader. The best algorithm to find all leaders in an array
Solves it in time θ (n²) Solves it in linear time using a left to right pass of the array Solves it in linear time using a right to left pass of the array Solves it using divide and conquer in time θ (n logn)

(7) Consider a complete n-array tree. This tree is such that each node has either n number of children or no children. Let l = 10 be the number of internal nodes and L = 41 be the number of leaves in a complete n-array tree. The value of n is
5 4 3 2