Solution

Following 3-ary Max Heap can be constructed from sequence given option.

Solution

Following is algorithm for building a Heap of an input array A.

BUILD-HEAP(A)

heapsize := size(A);

for i := floor(heapsize/2) downto 1

do HEAPIFY(A, i);

end for

END

Although the worst case complexity looks like O(nLogn), the upper bound of time complexity is O(n).

Solution

BFS stands for Breadth First Search is a vertex based technique for finding a shortest path in graph. It uses a Queue data structure which follows first in first out. In BFS, one vertex is selected at a time when it is visited and marked then its adjacent are visited and stored in the queue. It is slower than DFS.

DFS stands for Depth First Search is an edge based technique. It uses the Stack data structure, performs two stages, first visited vertices are pushed into the stack and second if there are no vertices then visited vertices are popped.

Solution

For BFS:

Queue graphTraversal.add(firstVertex);

// This while loop will run N times, where N is total number of vertices in graph.

while(graphTraversal.isEmpty == false)

currentVertex = graphTraversal.getVertex();

// This while loop will run Maj times, where Maj is number of adjacent edges to current vertex.

while(currentVertex.hasAdjacentVertices)

graphTraversal.add(adjacentVertex);

graphTraversal.remove(currentVertex);

Time complexity is as follows:

N * (O(1) + O(Maj) + O(1))

N + N * Maj + N

2N + M(total number of edges in graph)

N + M

For DFS:

Time complexity: O(N + M), where N is the number of vertices and M is the number of edges in the graph.

Solution

We can use both traversals to find if there is a path from s to t.

Either Breadth First Search (BFS) or Depth First Search (DFS) can be used to find path between two vertices. Take the first vertex as a source in BFS (or DFS), follow the standard BFS (or DFS). If the second vertex is found in our traversal, then there exists a path from source to second vertex

Solution

A complete graph can have a maximum edges for ‘n’ nodes as each node is connected to every other node. So, for n nodes, max nodes possible will be

Solution

Using given hash function h(x) = x mod 10

h(679) = 679%10 = 9

h(989) = 989%10 = 9

h(199) = 199%10 = 9

h(471) = 471%10 = 1

h(171) = 171%10 = 1

As we can see, 9679, 1989 and 4199 hash to same value 9. Also, 1471 and 6171 hash to same value 1. Therefore, statement (i) and (ii) are correct which match with option c.

Solution

Hence no. of rotations = 1.

Solution

Solution

The inorder traversal of a BST is sorted sequence, hence inorder traversal of a given preorder traversal is: 18, 55, 58, 60, 64, 67, 79, 80, 84, 88, 90

Preorder: 67, 60, 55, 48, 58, 64, 80, 74, 84, 88, 90

Using the inorder and preorder we can derive a tree as follows:

Draw the BST from the Preorder & then write postorder.

∴ Postorder traversal of the tree is

48, 58, 55, 64, 60, 74, 90, 88, 84, 80, 67.

Solution

Solution

Preorder: root-left-right

Inorder: left-root-righ

Inorder: 1, 2, 13, 14, 15, 16, 17, 18

Preorder: 15, 13, 1, 2, 14, 17, 16, 18

Hence 15 is root as it is first element in Preorder.

Now, check inorder. As 15 is root of the tree we can say

Again check the sequence 1,2,13,14 in preorder: 15, 13, 1, 2, 14, 17, 16, 18

Now 13 is parent for 1,2,14 and 1,2 are left children of 13 and 14 is right child of 13, similarly 17 parent for 16, 18. Hence tree becomes:

Preoder: 15, 13, 1, 2, 14, 17, 16, 18

As 1 and 16 come first in the sequence, they are parents for underlined sequences respectively.

Solution

We are given no. of 1 degree node =4, no. of 2 degree nodes =8.

Total no. of edges =1∗4+2∗8=20 (In tree degree is for outgoing edges only, and hence each degree corresponds to an edge)

So, total no. of nodes =20+1=21 (No. of nodes in a tree is 1 more than no. of edges).

Now, no. of leaf nodes (nodes with 0 degree) =21−4−8=9.

Solution

Expected number of comparisons = (1*1 + 2*2 + 3*3 + 4*1)/7 = 18/7 = 2.57

You count the for every element 𝑋 in the tree the number of comparisons it takes to locate it, say 𝐶(𝑋). Then

𝐸[# of comparisons]=∑𝑋∈{𝐴,…,𝐻}𝑝𝑋⋅𝐶(𝑋),

where 𝑝𝑥 denotes the probability that 𝑋 is chosen, which is the same for all 𝑋, namely 1/8. In other words, you compute the average over the 𝐶(𝑋)s.

for level 1 only one comparison because only 1 node (root) at level 1 => 1*1

then at level 2 we gave 2 nodes hence 2*2...

in this way we will calculate all combinations

Solution

Algorithm for DFS:

Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.

Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.)

Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.

Starting vertex is a, hence we will start with a. {b,c} are adjacent vertices to a. Hence all possible DFS traversals are ab….. Or ac……

Without solving further we can say option d is not the DFS as d is not the adjacent node to a.