1
GATE CSE 2006
+2
-0.6

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.

Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?

A
1, 3, 5, 6, 8, 9
B
9, 6, 3, 1, 8, 5
C
9, 3, 6, 8, 5, 1
D
9, 5, 6, 8, 3, 1
2
GATE CSE 2006
+2
-0.6
Given two arrays of numbers a1,......,an and b1,......, bn where each number is 0 or 1, the fastest algorithm to find the largest span (i, j) such that ai+ai+1......aj = bi+bi+1......bj or report that there is not such span,
A
Takes O(3n) and $$\Omega(2^{n})$$ time if hashing is permitted
B
Takes O(n3) and $$\Omega(n^{2.5})$$ time in the key comparison model
C
Takes θ(n) time and space
D
Takes $$O(\sqrt n)$$ time only if the sum of the 2n elements is an even number
3
GATE CSE 2006
+2
-0.6

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.

Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max heap found in the previous question. Which one of the following is the sequence of items in the array representing the resultant heap?

A
10, 7, 9, 8, 3, 1, 5, 2, 6, 4
B
10, 9, 8, 7, 6, 5, 4, 3, 2, 1
C
10, 9, 4, 5, 7, 6, 8, 2, 1, 3
D
10, 8, 6, 9, 7, 2, 3, 4, 1, 5
4
GATE CSE 2006
+2
-0.6
Consider the following recurrence:
$$T\left( n \right){\rm{ }} = {\rm{ 2T(}}\left\lceil {\sqrt n } \right\rceil {\rm{) + }}\,{\rm{1 T(1) = 1}}$$
Which one of the following is true?
A
$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(loglogn)}}$$
B
$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(logn)}}$$
C
$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(}}\sqrt n {\rm{)}}$$
D
$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \,{\rm{(}}n {\rm{)}}$$
GATE CSE Papers
2023
2022
2020
2019
2018
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
2000
1999
1998
1997
1996
1995
1994
1993
1992
1991
1990
1989
1988
1987
EXAM MAP
Medical
NEET