Explore topic-wise InterviewSolutions in .

Correct answer is (c) priority QUEUE data structure

Easy explanation: The time complexity of Prim’s algorithm depends on the data structures used for the graph and for ORDERING the edges by weight, which can be done USING a priority queue. In GENERAL, a priority queue will be quicker at finding the vertex in the SPANNING tree with minimum cost. The choice of data structures for implementation will lead to varying time complexity.

Correct OPTION is (d) maximum weight

Best EXPLANATION: A maximum spanning tree can be computed by negating the weights for each edge and APPLYING KRUSKAL’s algorithm. Thus, it is a spanning tree of a WEIGHTED graph having maximum weight assigned to all the edges.

Right CHOICE is (a) one ADDITIONAL edge makes a CYCLE in the TREE

For explanation I would say: A connected graph G can have more than one spanning tree. Removing one edge from the spanning tree will make the graph disconnected and the spanning tree is MINIMALLY connected. Adding one edge to the spanning tree will create a circuit or loop and the spanning tree is maximally acyclic.

The correct OPTION is (b) n^n-2

The explanation is: The spanning TREE does not CONTAIN any cycle. If a spanning tree has n nodes, there are n-1 edges. A COMPLETE graph can have a maximum of n^n-2number of spanning trees.

Right option is (c) true

To ELABORATE: If the edge was not included in the MST, removing any of the (larger COST) edges in the cycle formed after adding E to the MST, would yield a spanning tree of smaller weight. Thus, if the minimum cost edge e of a graph is unique, then this edge is included in any MST.

Correct choice is (a) O((V+E)logV)

To elaborate: In Prim’s Algorithm, we will start with an arbitrary node (TAKE any point to start) and mark it. In each ITERATION, a new VERTEX is marked that is adjacent to the one that we have already marked. Each vertex is inserted in the priority queue only once and insertion in priority queue take logarithmic time. Hence, the time COMPLEXITY of Prim’s Algorithm is O((V+E)logV).

Correct option is (c) 3

Easiest explanation: If GRAPH is CONNECTED and has ‘n’ edges, there will be EXACTLY one cycle, if n vertices are there. A different spanning TREE can be constructed by removing one edge from the cycle, one at a time. The minimum cycle length can be 3. So, there MUST be at least 3 spanning trees in any such Graph. Consider a Graph with n = 4, then 3 spanning trees possible at maximum (removing edges of cycle one at a time, alternatively). So, any Graph with minimum cycle length ‘3’ will have at least 3 spanning trees.

Right answer is (a) O(ElogV)

The best explanation: In KRUSKAL’s algorithm, at each iteration, we will select the edge with the lowest WEIGHT. So, we will START with the lowest weighted edge first. After that we will select the second lowest weighted edge. In Kruskal’s algorithm, most time consuming OPERATION is sorting because the total COMPLEXITY of the Disjoint-Set operations will be O(ElogV)and it is the overall Time Complexity of the algorithm.

Correct CHOICE is (b) cannot BELONG to an minimum spanning tree

For explanation I would say: For any cycle C in the graph, if the weight of an edge e of C is larger than the individual weights of all other edges of C, then this edge cannot belong to an MST.

Correct choice is (B) from left to right

The explanation is: Expressions are usually EVALUATED from left to right manner. Prefix expressions follow the normal RULE i.e from left to right. POSTFIX expressions can be evaluated from right to left.

The correct answer is (d) 2 4 * 5 7 3 4 ^ / + – 8 – 10

For explanation: By SOLVING we can have,

(2*4-(5+7/3^4)-8)10

= (2*4-(5+7/34^)-8)10

= (2*4-(5+734^/)-8)10

= (2*4-(5734^/+)-8)10

= (2*45734^/+–8)10

= 2*45734^/+-8-10

= 24*5734^/+-8-10

So the output is: 2 4 * 5 7 3 4 ^ / + – 8 – 10.

The correct choice is (a) A B + C D E / * – F +

To elaborate: The EXPRESSION is (A+B)-C*(D/E))+F

= (A+B)-C*(DE/)+F

= (A+B)-C*(DE/)F+

= (A+B)-C(DE/)*F+

= (A+B)C(DE/)*-F+

= (AB+)C(DE/)*-F+

So the output is: AB+CDE/*-F+.

Correct CHOICE is (d) in a direct manner

Explanation: In a postfix EXPRESSION, the operators appear after the OPERANDS. Conversion from prefix to postfix is done DIRECTLY which is better than converting the prefix expression in infix and then infix to postfix expression. It gives better EFFICIENCY.

Right choice is (b) two stacks

Best explanation: In the infix EXPRESSION, the operator appears between the operands and in infix NOTATION if the operator appears before the operands in the expression. For the conversion between them two stacks are used efficiently. The IDEA is to use one STACK for operators and other to STORE operands.

Correct choice is (c) -+*45/329

Explanation: The expression=4*5+3/2-9

={(4*5)+(3/2)-9}

={(*45)+(/32)-9}

={+(*45)(/32)}-9

=-{+(*45)(/32)9

So the output is; -+*45/329.

Correct CHOICE is (b) O(nlogn)

Easy explanation: In an n-ary binary TREE, we MUST have to visit all nodes from an adjacent node and repeat the same for next UNVISITED nodes. Hence, in worst case the TIME complexity should be O(nlogn).

Right answer is (b) PEER to peer NETWORKS

Explanation: Breadth FIRST Search traversal has diverse applications such as in the peer to peer networks like BitTorrent, BFS traversal is used to FIND all the NEIGHBOUR nodes of the network.

Right option is (a) count the number of LEAF NODES

Easy explanation: GIVEN an n-ary BINARY TREE, by performing DFS traversal on that tree number of leaf nodes can be calculated and for that we need to maintain an array for the leaf count.

Right choice is (c) 745*-93/+

To explain: FIRST build a BINARY TREE for the expression then find out the postorder traversal of that tree and after that the ANSWER will be 745*-93/+.

Right option is (d) 2

The explanation: If there are k NODES in a binary TREE, maximum height of that tree should be k-1, and MINIMUM height should be FLOOR(log2k). By using the FORMULA, minimum height must be 2 when there are 60 nodes in a tree.

Correct answer is (B) linear ordering

Explanation: TOPOLOGICAL sorting for Directed Acyclic GRAPH (DAG) is a linear ordering of vertices such that for every directed edge uv, VERTEX u comes before V in the ordering. If the graph is not a DAG, topological sorting for a graph is not possible.

Correct option is (b) TRAVERSE the left subtree

Explanation: In a PREORDER traversal of a BINARY tree first is to VISIT the root, second traverse the left subtree of the tree and third traverse the RIGHT subtree of the tree.

Correct OPTION is (d) O(E+VlogV)

For explanation: Time complexity of finding SHORTEST DISTANCE can be O(E + VLogV) using Fibonacci Heap. The reason is that Fibonacci Heap takes O(1) time for decrease-key OPERATION while Binary Heap takes O(logn) time.

Right choice is (C) O(V+E)

For explanation I would say: An undirected graph has Eulerian PATH if the following two conditions are true: -a) All vertices with a non-zero DEGREE are connected. A graph of vertices with zero DEGREES don’t belong to Eulerian Cycle or Path, b) If two vertices have odd degree and all other vertices have even degree. Thus, the time to find whether a graph has a Eulerian path or not is O(V+E) with V vertices and E EDGES.

Right option is (d) 7

To explain: In a CYCLE of a graph G if we join all the vertices to the CENTRE point, then that graph is called a wheel graph. There is always a HAMILTONIAN cycle in a wheel graph and there are n^2-3n+3 CYCLES. So, for order 5 the ANSWER should be 7.

Right answer is (b) 36

Explanation: In a COMPLETE graph of order n, there are n*(n-1) number of EDGES and degree of each vertex is (n-1). HENCE, for a graph of order 9 there should be 36 edges in total.

The correct option is (d) the degree of EVERY VERTEX in G is at least n/2

The best explanation: A simple circuit in a graph G that PASSES through every vertex exactly once is CALLED a Hamiltonian circuit. If there is a vertex of degree ONE in a graph then it is impossible for it to have a Hamiltonian circuit. If G is a simple graph with n-vertices and n>=3 such that the degree of every vertex in G is at least n/2, then G has a Hamiltonian circuit.

Right OPTION is (a) A disconnected GRAPH by DELETING a vertex

To explain: By deletion of a vertex the graph is disconnected and the graph is called separable graph and the vertex is called CUT vertex.

Correct option is (b) vector SPACE

For EXPLANATION I WOULD say: The TERM cycle refers to an element of the cycle space of a graph. There are many cycle spaces. The most common is the binary cycle space, which contains the edge SETS that have even degrees at every vertex and it forms a vector space over the two-element field.

Right answer is (a) O(n)

Explanation: The existence of a cycle in directed and UNDIRECTED graphs can be determined by depth-first search (DFS) of the graph FINDS an edge that points to an ancestor of the current vertex. In an undirected graph, finding any already visited vertex will INDICATE a BACK edge. All the back edges which DFS skips over are PART of cycles. In the case of undirected graphs, only O(n) time is required to find a cycle in an n-vertex graph, since at most n − 1 edges can be tree edges.

Correct option is (c) m*n

Easy EXPLANATION: As there are n possible EDGES to be removed from G and m edges to be removed from G and the rest from a spanning tree so the NUMBER of spanning tree in the new GRAPH is m*n.

The correct answer is (d) a graph which CONTAINS no cycles of odd LENGTH

Explanation: A graph is called a bipartite graph if and only if it contains no cycle of odd length. EVERY TREE is a bipartite graph and a median graph.

Right option is (c) graphs of the two trees are isomorphic and the two trees have the same label

To EXPLAIN I would SAY: The number of LABELED trees of k number of vertices is k^n-2. Two labeled trees are isomorphic if their graphs are isomorphic and the CORRESPONDING points of the two trees have the same labels.

Right answer is (a) n

To elaborate: An n-ary tree is a ROOTED tree in which each vertex has at most n CHILDREN. 2-ary TREES are termed as binary trees, 3-ary trees are sometimes called ternary trees.

Correct answer is (b) true

Easiest explanation: A linear GRAPH ALSO known as a path graph is a graph which consists of k vertices arranged in a LINE, so that vertices from i and i+1 are connected by an edge for i=0,…, k-1.

Right CHOICE is (b) nodes

Easy explanation: Every tree ELEMENT is called a NODE and the lines connecting the elements are called branches. A FINITE tree structure has a member that has no superior and is called the “ROOT” Or root node. Nodes that have no child are called leaf nodes.

Correct option is (a) directed acyclic graph

The explanation: A directed acyclic graph is KNOWN as a POLYTREE whose underlying UNDIRECTED graph is a tree. In other words, a directed tree is a directed graph which WOULD be tree if the directions on the EDGES were ignored.

The correct choice is (a) A TREE having a single INTERNAL VERTEX and n-1 LEAVES

Explanation: A star tree of order n is a tree with as many leaves as possible or in other words a star tree is a tree that consists of a single internal vertex and n-1 leaves. However, an internal vertex is a vertex of DEGREE at least 2.

Correct answer is (b) n-1

For explanation I would SAY: Suppose G is a connected graph which has no cycles. Every subgraph of G INCLUDES at least one VERTEX with zero or one incident edges. It has n vertices and n-1 edges. Generally, the order-zero graph is not considered to be a tree.

Correct answer is (c) tree

Best explanation: An UNDIRECTED GRAPH G which is connected and acyclic is termed as a tree. G CONTAINS no cycles and if any edge is added to G a simple cycle is FORMED.