## Data-Structures

Question 1 |

I. The smallest element in a max-heap is always at a leaf node.

II. The second largest element in a max-heap is always a child of the root node.

III. A max-heap can be constructed from a binary search tree in Θ(n) time.

IV. A binary search tree can be constructed from a max-heap in Θ(n) time.

Which of the above statements are TRUE?

I, II and III | |

II, III and IV | |

I, III and IV | |

I, II and IV |

(ii) TRUE: The second smallest element in a heap is always a child of root node.

(iii) TRUE: Converting from binary search tree to max heap will take O(n) time as well as O(n) space complexity.

(iv) FALSE: We can’t convert max heap to binary search tree in O(n) time.

Question 2 |

Let T be a full binary tree with 8 leaves. (A full binary tree has every level full). Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) _____.

5.54 | |

1.34 | |

4.25 | |

3.82 |

__uniformly & independently__chosen leaf nodes.

A node can be chosen twice and the path from that node to itself will be zero.

∴ Path 1 = 0

Similarly,

Path 2 = 2

Path 3 = 4

Path 4 = 4

Path 5 = 6

Path 6 = 6

Path 7 = 6

Path 8 = 6

∴ Expected value = Σ Path length × Probability of selecting path

= 2×1/8 + 4×2/8 + 6×4/8 + 0×1/8

= 1/4 + 1/1 + 3/1 + 0

= 4 + 1/4

= 17/4

= 4.25

Question 3 |

The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is _______.

1 | |

2 | |

3 | |

4 |

In – 8 6 9 4 7 2 5 1 3

Post: 8 9 6 7 4 5 2 3

__1__→(root)

In: 8 6 9 4 7 2

__5__→(left subtree)

__13__→(right subtree)

Question 4 |

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let 'enqueue' be implemented by inserting a new node at the head, and 'dequeue' be implemented by deletion of a node from the tail.

Which one of the following is the time complexity of the most time-efficient implementation of 'enqueue' and 'dequeue, respectively, for this data structure?

θ(1), θ(1) | |

θ(1), θ(n) | |

θ(n), θ(1) | |

θ(n), θ(n) |

But if we have pointer to the tail of the list in order to delete it, we need the address of the 2

^{nd}last node which can be obtained by traversing the list which takes O(n) time.

Question 5 |

_{D}be a depth first search tree of G. Let T

_{B}be a breadth first search tree of G. Consider the following statements.

(I) No edge of G is a cross edge with respect to T

_{D}.(A cross edge in G is between two nodes neither of which is an ancestor of the other in T

_{D}.)

(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in T

_{B}, then ∣i−j∣ = 1.

Which of the statements above must necessarily be true?

I only | |

II only | |

Both I and II | |

Neither I nor II |

II. Just draw a triangle ABC. Source is A. Vertex B and C are at same level at distance 1.

There is an edge between B and C too. So here |i - j| = |1 - 1| = 0. Hence, False.

Question 6 |

The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ___________.

80 | |

81 | |

82 | |

83 |

--> After sorting, pick the minimum element and make it the root of the min heap.

--> So, there is only 1 way to make the root of the min heap.

--> Now we are left with 6 elements.

--> Total ways to design a min heap from 6 elements = C(6,3) ∗ 2! ∗ C(3,3) ∗ 2! = 80

Note:

C(6,3)∗2! : Pick up any 3 elements for the left subtree and each left subtree combination can be permuted in 2! ways by interchanging the children and similarly, for right subtree .

Question 7 |

Consider the C code fragment given below.

typedef struct node { int data; node* next; } node; void join(node* m, node* n) { node* p = n; while(p→next !=NULL) { p = p→next; } p→next=m; }

Assuming that m and n point to valid NULL-terminated linked lists, invocation of join will

append list m to the end of list n for all inputs. | |

either cause a null pointer dereference or append list m to the end of list n. | |

cause a null pointer dereference for all inputs. | |

append list n to the end of list m for all inputs. |

So have to consider both the cases.

⇾ 1. Lists are not null, invocation of JOIN will append list m to the end of list n.

m = 1, 2, 3

n = 4, 5, 6

After join, it becomes 4, 5, 6, 1, 2, 3, NULL.

⇾ 2. If lists are null, if the list n is empty, and itself NULL, then joining & referencing would obviously create a null pointer issue.

Hence, it may either cause a NULL pointer dereference or appends the list m to the end of list n.

Question 8 |

Let *T *be a tree with 10 vertices. The sum of the degrees of all the vertices in *T* is _________.

18 | |

19 | |

20 | |

21 |

A tree, with 10 vertices, consists n - 1, i.e. 10 - 1 = 9 edges.

Sum of degrees of all vertices = 2(#edges)

= 2(9)

= 18

Question 9 |

**FRONT**and

**REAR**pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in

*O(1)*time?

I. Next pointer of front node points to the rear node.

II. Next pointer of rear node points to the front node.

I only | |

II only | |

Both I and II | |

Neither I nor II |

2. Next pointer of rear points to the front node.

So if we consider circular linked list the next of 44 is 11.

If you place pointer on next of front node (11) then to reach 44 (last node), we have to traverse the entire list.

For delete O(1), for insert O(n).

It is clearly known that next pointer of rear node points to the front node.

Hence, only II is true.

Question 10 |

The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?

MNOPQR | |

NQMPOR | |

QMNROP | |

POQNMR |

(Do it by option Elimination)

(a) MNOPQR – MNO is not the proper order R must come in between.

(b) NQMPOR – QMP is not the order O is the child of N.

(C) QMNROP – M is not the child of Q, so QMN is false.

(D) POQNMR – P → OQ → NMR is the correct sequence. Hence Option (D).

Question 11 |

The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:

2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20 | |

2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12 | |

7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12 | |

7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12 |

From these 2 orders, we can say 12 is the root & 8 is the root of left subtree & 16 is the root of right subtree.

From 2, 6, 7 we can identify 6 is the root from preorder traversal and from 9, 10 → 9 is root.

From <17, 19, 20>, 19 as root.

Hence, 2,7,6,10,9,8 |,15,17,20,19,16 |12 is the post-order traversal.

Question 12 |

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efﬁciently. Which one of the following statements is **CORRECT** (*n* refers to the number of items in the queue)?

Both operations can be performed in O(1) time | |

At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n) | |

The worst case time complexity for both operations will be Ω(n) | |

Worst case time complexity for both operations will be Ω(logn) |

Hence even the worst case time complexity will be O(1) by the use of the Circular queue there won't be any need of shifting in the array.

Question 13 |

Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is __________.

7 | |

9 | |

8 | |

6 |

It is observed that (a) is the starting vertex & (f) is the final one.

Also observed that c must come after b & e must come after d.

So,

Hence, there are 6 different topological orderings can be derived.

Question 14 |

*G*be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are

**TRUE**?

P: Minimum spanning tree of

*G*does not change

Q: Shortest path between any pair of vertices does not change

P only | |

Q only | |

Neither P nor Q | |

Both P and Q |

Every edge weight is increased by the same value say,

P: Minimum Spanning Tree will not change ABC in both the cases.

Q: Shortest path will change because in 1st figure the path from A to C calculated as ABC but in fig.2, it is AC (Direct path).

Question 15 |

An operator *delete(i)* for a binary heap data structure is to be designed to delete the item in the *i*-th node. Assume that the heap is implemented in an array and *i* refers to the *i*-th index of the array. If the heap tree has depth *d* (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-ﬁx the heap efﬁciently after the removal of the element?

O(1) | |

O(d) but not O(1) | |

O(2 ^{d}) but not O(d) | |

O(d 2 ^{d}) but not O(2^{d}) |

→ Because we first need to find that element, O(n) time

Delete that element O(height) [deleting involves swapping particular element to rightmost leaf and then do heapify on that node].

**but here, we don't need to find that element, because in delete(i), i is index of that element.

Note: Delete time = O(height) = O(d)

Question 16 |

Consider the weighted undirected graph with 4 vertices, where the weight of edge {*i,j*} is given by the entry *W _{ij}* in the matrix

*W*.

The largest possible integer value of *x*, for which at least one shortest path between some pair of vertices will contain the edge with weight *x* is _________.

12 | |

13 | |

14 | |

15 |

x directly connects C to D.

The shortest path (excluding x) from C to D is of weight 12 (C-B-A-D).

Question 17 |

Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q **without** removing it from Q. Similarly Top(S) returns the element at the top of S **without** removing it from S. Consider the algorithm given below.

The maximum possible number of iterations of the **while** loop in the algorithm is _________.

256 | |

257 | |

258 | |

259 |

Try to solve it for 3 numbers [1. 2, 3].

Step 1: Initially Queue contains 3 elements so after 5 while loop iterations queue contains 3, 2 and stack contains 1.

Step 2: Now after 3 more while loop iterations, Queue contains 3 and stack contains 1, 2 (TOS = 2).

Step 3: After 1 more while loop iteration, push 3 onto the stack so queue is empty and stack contains 1, 2, 3 {top = 3}.

So, total number of iterations will be 5 + 3 + 1 = 9

i.e., for 3 it is 9 iterations (3*3)

for 4 it is 16 iterations (4*4)

Given: 16 numbers, so 16 * 16 = 256

Question 18 |

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex *t* at a distance four from the root. If *t* is the *n*-th vertex in this BFS traversal, then the maximum possible value of *n* is _________.

31 | |

32 | |

33 | |

34 |

For distance 1, max possible value is (3).

Similarly, for distance 2, max value is (7).

So, maximum number of nodes = 2

^{(h+1)}- 1

For distance 4, 2

^{(4+1)}- 1 ⇒ 2

^{5}- 1 ⇒ 32 - 1 = 31

31 is the last node.

So for distance 4, the maximum possible node will be 31 & minimum will be 16.

Question 19 |

*N* items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a *decrease-key* operation, a pointer is provided to the record on which the operation is to be performed.

An algorithm performs the following operations on the list in this order: Θ(*N*) *delete*,O(log*N*) *insert*, O(log*N*) *ﬁnd*, and Θ(*N*) *decrease-key*. What is the time complexity of all these operations put together?

O(log ^{2} N) | |

O(N) | |

O(N ^{2}) | |

Θ(N ^{2} logN) |

→ Delete needs O(1) time

→ Insert takes O(N) time

→ Find takes O(N) time

→ Decrease by takes O(N) time

Now number of each operation performed is given, so finally total complexity,

→ Delete = O(1) × O(N) = O(N)

→ Find = O(N) × O(log N) = O(N log N)

→ Insert = O(N) × O(log N) = O(N log N)

→ Decrease key = O(N) × O(N) = O(N

^{2})

So, overall time complexity is, O(N

^{2}).

Question 20 |

A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is _________.

8 | |

9 | |

10 | |

11 |

This is not possible because it violates a property of complete binary tree.

We have total [0, 1023] elements. It means that

∴ 2

^{0}+ 2

^{1}+ 2

^{2}+ ⋯ + 2

^{k}= 1024

Add if 1(2

^{(k+1)}-1)/(2-1) [using formula for sum of k terms k+1 in G.P]

= 2

^{(k+1)}- 1 = 1024 - 1 = 1023

∴ The level ‘9’ at the depth of 8.

Actually we have 1023 elements, we can achieve a complete binary min heap of depth 9, which would cover all 1023 elements, but the max depth of node 9 can be only be 8.

Question 21 |

Consider the following New-order strategy for traversing a binary tree:

- Visit the root;
- Visit the right subtree using New-order;
- Visit the left subtree using New-order;

The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ˆ 6 7 * 1 + - is given by:

+ - 1 6 7 * 2 ˆ 5 - 3 4 * | |

- + 1 * 6 7 ˆ 2 - 5 * 3 4 | |

- + 1 * 7 6 ˆ 2 - 5 * 4 3 | |

1 7 6 * + 2 5 4 3 * - ˆ - |

Given Reverse Polish Notation as:

3 4 * 5 - 2 ^ 6 7 * 1 + -

We know Reverse Polish Notation takes Left, Right, Root.

So the expression tree looks like

From the tree, we can write the New Order traversal as: Root, Right, Left.

- + 1 * 7 6 ^ 2 - 5 * 4 3

Question 22 |

The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is _________.

*Note: The height of a tree with a single node is 0.*

64 | |

65 | |

66 | |

67 |

So to get such tree at each level we should have either maximum or minimum element from remaining numbers till that level. So no. of binary search tree possible is,

1

^{st}level - 2 (maximum or minimum)

⇓

2

^{nd}level - 2

⇓

3

^{rd}level - 2

⇓

4

^{th}level - 2

⇓

5

^{th}level - 2

⇓

6

^{th}level - 2

⇓

7

^{th}level - 2

= 2 × 2 × 2 × 2 × 2 × 2 × 1

= 2

^{6}

= 64

Question 23 |

In an adjacency list representation of an undirected simple graph G = (V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efﬁcient algorithm to set the twin pointer in each entry in each adjacency list?

Θ(n ^{2}) | |

Θ(n+m) | |

Θ(m ^{2}) | |

Θ(n ^{4}) |

Visit every vertex level-wise for every vertex fill adjacent vertex in the adjacency list. BFS take O(m+n) time.

**Note:**

Twin Pointers can be setup by keeping track of parent node in BFS or DFS of graph.

Question 24 |

The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are

63 and 6, respectively | |

64 and 5, respectively | |

32 and 6, respectively | |

31 and 5, respectively |

2

^{h+1}- 1 = 2

^{5+1}- 1 = 63

Minimum number of nodes in a binary tree of height h is

h + 1 = 5 + 1 = 6

Question 25 |

Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4.

Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

40, 30, 20, 10, 15, 16, 17, 8, 4, 35 | |

40, 35, 20, 10, 30, 16, 17, 8, 4, 15 | |

40, 30, 20, 10, 35, 16, 17, 8, 4, 15 | |

40, 35, 20, 10, 15, 16, 17, 8, 4, 30 |

Heapification:

Array representation of above max-heap is (BFS)

40, 35, 20, 10, 30, 16, 17, 8, 4, 15

Question 26 |

A binary tree T has 20 leaves. The number of nodes in T having two children is _________.

19 | |

20 | |

21 | |

22 |

(i) p vertices (i.e., leaves) of degree 1

(ii) one vertex (i.e., root of T) of degree 2

(iii) 'n - p - 1' (i.e., interval) vertices of degree 3

(iv) n - 1 edges

∴ By Handshaking theorem,

p × 1 + 1 × 2 + (n - p - 1) × 3 = 2(n - 1)

⇒n = 2p - 1

= 39 as p = 20

∴ n - p = 19 vertices have exactly two children

Question 27 |

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

Ω(logn) | |

Ω(n) | |

Ω(nlog n) | |

Ω(n ^{2}) |

*log n*time.

Question 28 |

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

h(i) = i ^{2} mod 10 | |

h(i) = i ^{3} mod 10 | |

h(i) = (11 *i ^{2}) mod 10 | |

h(i) = (12 * i) mod 10 |

Question 29 |

Assume that the bandwidth for a TCP connection is 1048560 bits/sec. Let α be the value of RTT in milliseconds (rounded off to the nearest integer) after which the TCP window scale option is needed. Let β be the maximum possible window size the window scale option. Then the values of α and β are

63 milliseconds, 65535×2 ^{14} | |

63 milliseconds, 65535×2 ^{16} | |

500 milliseconds, 65535×2 ^{14} | |

500 milliseconds, 65535×2 ^{16} |

^{16}= 65,535.

The wrap around time for given link = 1048560 * α. The TCP window scale option is an option to increase the receive window size. TCP allows scaling of windows when wrap around time > 65,535.

==> 1048560 * α > 65,535*8 bits

==> α = 0.5 sec = 500 mss

Scaling is done by specifying a one byte shift count in the header options field. The true receiver window size is left shifted by the value in shift count. A maximum value of 14 may be used for the shift count value. Therefore maximum window size with scaling option is 65535 × 2

^{14}.

Question 30 |

A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with ∞, and hence there cannot be any entry to the right of, or below a ∞. The following Young tableau consists of unique entries.

1 2 5 14 3 4 6 23 10 12 18 25 31 ∞ ∞ ∞

When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled in with a ∞). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is ____________.

4 | |

5 | |

6 | |

7 |

Question 31 |

Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is ___________.

80 | |

70 | |

60 | |

50 |

Question 32 |

Consider the following array of elements. 〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉. The minimum number of interchanges needed to convert it into a max-heap is

4 | |

5 | |

2 | |

3 |

→ Swap 100 & 15

→ Swap 100 & 50

→ Swap 89 & 100

∴ Total 3 interchanges are needed.

Question 33 |

While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

65 | |

67 | |

69 | |

83 |

Question 34 |

The result evaluating the postfix expression 10 5 + 60 6 / * 8 - is

284 | |

213 | |

142 | |

71 |

→ '5' is pushed in the stack

→ '+' comes so addition will be done by popping the top two elements in the stackand the result is pushed back into the stack, i.e., 10+5 = 15

→ 60 pushed in the stack

→ 6 pushed in the stack

→ '/' comes. So, 60/6 = 10

→ '*' comes. So, 15 * 10 = 150

→ '8' comes, push in the stack

→ '-' comes. So, 150-8 = 142

So the final result is 142.

Question 35 |

Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ____.

199 | |

198 | |

197 | |

196 |

Question 36 |

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

θ(n) | |

θ(n+m) | |

θ(n ^{2}) | |

θ(m ^{2}) |

^{2}).

Question 37 |

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is O(n^{a}log^{b}n). Then the value of a+10b is ________.

1 | |

2 | |

3 | |

4 |

Substitute into a and b values in equation.

⇒ a+10b

⇒ a*1 + 10*0

⇒ 1+0

⇒ 1

Question 38 |

Consider the directed graph given below.

Which one of the following is TRUE?

The graph does not have any topological ordering. | |

Both PQRS and SRQP are topological. | |

Both PSRQ and SPRQ are topological orderings. | |

PSRQ is the only topological ordering. |

There are no cycles in the graph, so topological orderings do exist.

We can consider P & S as starting vertex, followed by R & Q.

Hence, PSRQ & SPRQ are the topological orderings.

Question 39 |

Let P be a quicksort program to sort numbers in ascending order using the first elements as the pivot. Let t_{1} and t_{2} be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?

t _{1}=5 | |

t _{1} | |

t _{1}>t_{2} | |

t _{1}=t_{2} |

**1**, 2, 3, 4, 5] [

**4**, 1, 5, 3, 2]

Simple one: First element is a pivot element. And if we observe first array pivot is small and requires lot of comparisons and whereas it is not the case with 2

^{nd}array through not in sorted manner.

Hence t

_{1}> t

_{2}.

Question 40 |

Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

3, 0, and 1 | |

3, 3, and 3 | |

4, 0, and 1 | |

3, 0, and 2 |

h(k) = k mod 9

Collisions are resolved using chaining.

Keys: 5, 28, 19, 15, 20, 33, 12, 17, 10.

5%9 – 5

28%9 – 1

19%9 – 1

15%9 – 6

20%9 – 2

33%9 – 6

12%9 – 3

17%9 – 8

10%9 – 1

Maximum chain length is 3

Minimum chain length is 0

Average chain length = 0+3+1+1+0+1+2+0+1/ 9 = 1

Question 41 |

Consider the following C function in which size is the number of elements in the array E: The value returned by the function MyX is the

int MyX(int *E, unsigned int size) { int Y = 0; int Z; int i, j, k; for(i = 0; i < size; i++) Y = Y + E[i]; for(i = 0; i < size; i++) for(j = i; j < size; j++) { Z = 0; for(k = i; k <= j; k++) Z = Z + E[k]; if (Z > Y) Y = Z; } return Y; }

maximum possible sum of elements in any sub-array of array E. | |

maximum element in any sub-array of array E. | |

sum of the maximum elements in all possible sub-arrays of array E. | |

the sum of all the elements in the array E. |

for (i=0; i

for (i=0; i

Z=0;

for(k=i; k<=j; k++)

Z=Z+E[k];

// It calculates the sum of all possible subarrays starting from 0 i.e., the loop will iterate for all the elements of array E and for every element, calculate sum of all sub arrays starting with E[i].

Store the current sum in Z.

If Z is greater than Y then update Y and return Y. So it returns the maximum possible sum of elements in any sub array of given array E.

Question 42 |

Consider the following pseudo code. What is the total number of multiplications to be performed?

D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3

Half of the product of the 3 consecutive integers. | |

One-third of the product of the 3 consecutive integers. | |

One-sixth of the product of the 3 consecutive integers. | |

None of the above. |

for i = 1 to n do

for j = i to n do

for k = j + 1 to n do

D = D * 3;

Also you can try for smaller ‘n’.

Question 43 |

Consider a 6-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on this 6-stage pipeline, the speedup achieved with respect to non-pipelined execution if 25% of the instructions incur 2 pipeline stall cycles is _________.

4 | |

5 | |

6 | |

7 |

There were 2 stall cycles for pipelining for 25% of the instructions.

So pipeline time =(1+(25/100)*2)=3/2=1.5

Speed up =Non-pipeline time / Pipeline time=6/1.5=4

Question 44 |

An access sequence of cache block addresses is of length N and contains n unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by k. What is the miss ratio if the access sequence is passed through a cache of associativity A≥k exercising least-recently-used replacement policy?

n/N | |

1/N | |

1/A | |

k/n |

As the set associativity size keeps increasing then we don't have to replace any block, so LRU is not of any significance here.

Question 45 |

A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

10, 8, 7, 3, 2, 1, 5 | |

10, 8, 7, 2, 3, 1, 5 | |

10, 8, 7, 1, 2, 3, 5 | |

10, 8, 7, 5, 3, 2, 1 |

The level order traversal in this max heap final is:

10, 8, 7, 3, 2, 1, 5.

Question 46 |

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

the shortest path between every pair of vertices. | |

the shortest path from W to every vertex in the graph. | |

the shortest paths from W to only those nodes that are leaves of T. | |

the longest path in the graph. |

But in the given question the BFS algorithm starts from the source vertex w and we can find the shortest path from W to every vertex of the graph.

Question 47 |

The worst case running time to search for an element in a balanced binary search tree with n2^{n} elements is

Θ (n log n) | |

Θ (n2 ^{n}) | |

Θ (n) | |

Θ (log n) |

→ No of elements = n.2

^{n}then search time = (log n.2

^{n})

= (log n + log 2

^{n})

= (log n + n log 2)

= O(n)

Question 48 |

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

T(n) = 2T(n - 2) + 2 | |

T(n) = 2T(n - 1) + n | |

T(n) = 2T(n/2) + 1 | |

T(n) = 2T(n - 1) + 1 |

T(n) = 2T(n – 1) + 1

= 2 [2T(n – 2) + 1] + 1

= 2

^{2}T(n – 2) + 3

⋮

= 2

^{k}T( n – k) + (2

^{k}– 1)

n – k = 1

= 2

^{n-1}T(1) + (2

^{n-1}– 1)

= 2

^{n-1}+ 2

^{n-1}– 1

= 2

^{n}– 1

≌ O(2

^{n})

Question 49 |

Suppose a circular queue of capacity (n - 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect *queue full* and *queue empty* are

full: (REAR+1)mod n == FRONT empty: REAR == FRONT | |

full: (REAR+1)mod n == FRONT empty: (FRONT+1) mod n == REAR | |

full: REAR == FRONT empty: (REAR+1) mod n == FRONT | |

full: (FRONT+1)mod n == REAR empty: REAR == FRONT |

To circulate within the queue we have to write mod n for (Rear + 1).

We insert elements using Rear & delete through Front.

Question 50 |

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.

The appropriate expression for the two boxes B1 and B2 are

B1: (1+height(n→right)) B2: (1+max(h1,h2)) | |

B1: (height(n→right)) B2: (1+max(h1,h2)) | |

B1: height(n→right) B2: max(h1,h2) | |

B1: (1+ height(n→right)) B2: max(h1,h2) |

Now, we analyze the code,

The box B1 gets executed when left sub tree of n is NULL & right subtree is not NULL.

In such case, height of n will be the height of the right subtree + 1.

The box B2 gets executed when both left & right subtrees of n are not NULL.

In such case, height of n will be max of heights of left & right subtrees of n+1.