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