The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Highest voted questions in DS
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
+100
votes
8
answers
1
GATE2007IT29
When searching for the key value $60$ in a binary search tree, nodes containing the key values $10, 20, 40, 50, 70, 80, 90$ are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value $60$? $35$ $64$ $128$ $5040$
asked
Oct 30, 2014
in
DS
by
Ishrat Jahan
Boss
(
16.3k
points)

12.8k
views
gate2007it
datastructures
binarysearchtree
normal
+93
votes
14
answers
2
GATE2016240
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$.
asked
Feb 12, 2016
in
DS
by
Akash Kanase
Boss
(
41.9k
points)

13.6k
views
gate20162
datastructures
binarysearchtree
normal
numericalanswers
+74
votes
9
answers
3
GATE2016141
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$. ... else x:= Pop(S); Enqueue (Q, x); end end The maximum possible number of iterations of the while loop in the algorithm is _______.
asked
Feb 12, 2016
in
DS
by
Sandeep Singh
Loyal
(
7.2k
points)

10.1k
views
gate20161
datastructures
queues
difficult
numericalanswers
+65
votes
6
answers
4
GATE2014339
Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$ and $H$. Suppose there are $m$ such numbers in $T$. If the tightest upper bound on the time to compute the sum is $O(n^a\log^bn+m^c\log^dn)$, the value of $a+10b+100c+1000d$ is ______.
asked
Sep 28, 2014
in
DS
by
jothee
Veteran
(
105k
points)

10.6k
views
gate20143
datastructures
binarysearchtree
numericalanswers
normal
+63
votes
5
answers
5
GATE200846
You are given the postorder traversal, $P$, of a binary search tree on the $n$ elements $1, 2, \dots, n$. You have to determine the unique binary search tree that has $P$ as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this? $\Theta(\log n)$ $\Theta(n)$ $\Theta(n\log n)$ None of the above, as the tree cannot be uniquely determined
asked
Sep 12, 2014
in
DS
by
Kathleen
Veteran
(
52.2k
points)

11.8k
views
gate2008
datastructures
binarysearchtree
normal
+57
votes
3
answers
6
GATE20022.12
A weightbalanced tree is a binary tree in which for each node, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such ... by which of the following? $\log_2 n$ $\log_{\frac{4}{3}} n$ $\log_3 n$ $\log_{\frac{3}{2}} n$
asked
Sep 16, 2014
in
DS
by
Kathleen
Veteran
(
52.2k
points)

7.1k
views
gate2002
datastructures
binarytree
normal
+55
votes
9
answers
7
GATE2014112
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^bn)$. Then the value of $a+10b$ is __________.
asked
Sep 26, 2014
in
DS
by
jothee
Veteran
(
105k
points)

6.7k
views
gate20141
datastructures
binarytree
numericalanswers
normal
+54
votes
7
answers
8
GATE200485
A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is: $\Large \min \left ( \substack{\text{number of leafnodes}\\\text{in leftsubtree of $ ... worstcase time complexity of the program is? $\Theta (n)$ $\Theta (n \log n)$ $\Theta(n^2)$ $\Theta (n^2\log n)$
asked
Sep 19, 2014
in
DS
by
Kathleen
Veteran
(
52.2k
points)

9.2k
views
gate2004
binarysearchtree
normal
datastructures
+52
votes
8
answers
9
GATE2017108
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 ... 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.
asked
Feb 14, 2017
in
DS
by
khushtak
Loyal
(
7.1k
points)

8.8k
views
gate20171
datastructures
linkedlists
normal
+50
votes
5
answers
10
GATE2016234
A complete binary minheap 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 _________.
asked
Feb 12, 2016
in
DS
by
Akash Kanase
Boss
(
41.9k
points)

7k
views
gate20162
datastructures
heap
normal
numericalanswers
+50
votes
6
answers
11
GATE2016215
$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 decreasekey 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 ... put together? $O(\log^{2} N)$ $O(N)$ $O(N^{2})$ $\Theta\left(N^{2}\log N\right)$
asked
Feb 12, 2016
in
DS
by
Akash Kanase
Boss
(
41.9k
points)

10.9k
views
gate20162
datastructures
linkedlists
timecomplexity
normal
+50
votes
6
answers
12
GATE200649
An implementation of a queue $Q$, using two stacks $S1$ and $S2$, is given below: void insert (Q, x) { push (S1, x); } void delete (Q) { if (stackempty(S2)) then if (stackempty(S1)) then { print( Q is empty ); return; } else while (!(stackempty(S1))){ x=pop(S1); push(S2 ... $2m\leq y\leq 2n $ $ 2m\leq x<2n $ and $2m\leq y\leq n+m $ $ 2m\leq x<2n $ and $2m\leq y\leq 2n $
asked
Sep 26, 2014
in
DS
by
Rucha Shelke
Active
(
3.3k
points)

7.1k
views
gate2006
datastructures
queues
stack
normal
+46
votes
9
answers
13
GATE201053
A hash table of length $10$ uses open addressing with hash function $h(k) = k \: mod \: 10$, and linear probing. After inserting $6$ ... sequences of the key values using the same hash function and linear probing will result in the hash table shown above? $10$ $20$ $30$ $40$
asked
Apr 21, 2016
in
DS
by
jothee
Veteran
(
105k
points)

7k
views
datastructures
hashing
normal
gate2010
+46
votes
4
answers
14
GATE20036
Let $T(n)$ be the number of different binary search trees on $n$ distinct elements. Then $T(n) = \sum_{k=1}^{n} T(k1)T(x)$, where $x$ is $nk+1$ $nk$ $nk1$ $nk2$
asked
Sep 16, 2014
in
DS
by
Kathleen
Veteran
(
52.2k
points)

5.3k
views
gate2003
normal
binarysearchtree
+46
votes
5
answers
15
GATE201344
Consider the following operation along with Enqueue and Dequeue operations on queues, where $k$ is a global parameter. MultiDequeue(Q){ m = k while (Q is not empty) and (m > 0) { Dequeue(Q) m = m – 1 } } What is the worst case time complexity of a sequence of $n$ queue operations on an initially empty queue? $Θ(n)$ $Θ(n + k)$ $Θ(nk)$ $Θ(n^2)$
asked
Aug 7, 2014
in
DS
by
gatecse
Boss
(
17.5k
points)

8.8k
views
gate2013
datastructures
algorithms
normal
queues
+45
votes
8
answers
16
GATE2015231
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 $\infty$, and hence there cannot be any entry to the right of, or below a $\infty$. The following Young tableau consists of ... $1$) to be shifted, to remove $1$ from the given Young tableau is _____.
asked
Feb 12, 2015
in
DS
by
jothee
Veteran
(
105k
points)

3.9k
views
gate20152
databases
arrays
normal
numericalanswers
+45
votes
9
answers
17
GATE200364
Let S be a stack of size $n \geq1$. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform $n$ pop operations. Assume that Push and Pop operations take $X$ seconds each, and $Y$ seconds elapse between the end of one such stack operation ... from S. The average stacklife of an element of this stack is $n(X+Y)$ $3Y+2X$ $n(X+Y)X$ $Y+2X$
asked
Sep 17, 2014
in
DS
by
Kathleen
Veteran
(
52.2k
points)

7.2k
views
gate2003
datastructures
stack
normal
+44
votes
2
answers
18
GATE2005IT13
A function $f$ defined on stacks of integers satisfies the following properties. $f(∅) = 0$ and $f (push (S, i)) = max (f(S), 0) + i$ for all stacks $S$ and integers $i$. If a stack $S$ contains the integers $2, 3, 2, 1, 2$ in order from bottom to top, what is $f(S)$? $6$ $4$ $3$ $2$
asked
Nov 3, 2014
in
DS
by
Ishrat Jahan
Boss
(
16.3k
points)

4.7k
views
gate2005it
datastructures
stack
normal
+42
votes
11
answers
19
GATE19941.11
In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size $n \times n$ ... new representation is: $i+j$ $i+j1$ $(j1)+\frac{i(i1)}{2}$ $i+\frac{j(j1)}{2}$
asked
Oct 4, 2014
in
DS
by
Kathleen
Veteran
(
52.2k
points)

7k
views
gate1994
datastructures
arrays
normal
+41
votes
3
answers
20
GATE2015233
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 \text{mod } 10$ $h(i) = i^3 \text{mod } 10$ $h(i) = (11 \ast i^2) \text{mod } 10$ $h(i) = (12 \ast i^2) \text{mod } 10$
asked
Feb 12, 2015
in
DS
by
jothee
Veteran
(
105k
points)

4.2k
views
gate20152
datastructures
hashing
normal
+41
votes
3
answers
21
GATE200747
Consider the process of inserting an element into a $Max \: Heap$, where the $Max \: Heap$ is represented by an $array$. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of $comparisons$ performed is: $\Theta(\log_2n)$ $\Theta(\log_2\log_2n)$ $\Theta(n)$ $\Theta(n\log_2n)$
asked
Sep 22, 2014
in
DS
by
Kathleen
Veteran
(
52.2k
points)

5.2k
views
gate2007
datastructures
heap
normal
+40
votes
6
answers
22
GATE200842
$G$ is a graph on $n$ vertices and $2n2$ edges. The edges of $G$ can be partitioned into two edgedisjoint spanning trees. Which of the following is NOT true for $G$? For every subset of $k$ ... are at least $2$ edgedisjoint paths between every pair of vertices. There are at least $2$ vertexdisjoint paths between every pair of vertices.
asked
Sep 27, 2014
in
DS
by
Akshay Jindal
(
385
points)

8.4k
views
gate2008
datastructures
graphs
normal
+40
votes
6
answers
23
GATE200323
In a minheap with $n$ elements with the smallest element at the root, the $7^{th}$ smallest element can be found in time $\Theta (n \log n)$ $\Theta (n)$ $\Theta(\log n)$ $\Theta(1)$
asked
Sep 19, 2014
in
DS
by
Disha
(
81
points)

9.4k
views
gate2003
datastructures
heap
+38
votes
5
answers
24
GATE2016236
Consider the following Neworder strategy for traversing a binary tree: Visit the root; Visit the right subtree using Neworder; Visit the left subtree using Neworder; The Neworder traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5  2 ^ 6 7 * 1 +  is given by: ... $1 \ 7 \ 6 * + \ 2 \ 5 \ 4 \ 3 \ * \  \wedge $
asked
Feb 12, 2016
in
DS
by
Akash Kanase
Boss
(
41.9k
points)

5.3k
views
gate20162
datastructures
binarytree
normal
+38
votes
4
answers
25
GATE2008IT71
A Binary Search Tree (BST) stores values in the range $37$ to $573$. Consider the following sequence of keys. $81, 537, 102, 439, 285, 376, 305$ $52, 97, 121, 195, 242, 381, 472$ $142, 248, 520, 386, 345, 270, 307$ ... sequences list nodes in the order in which we could have encountered them in the search? II and III only I and III only III and IV only III only
asked
Oct 29, 2014
in
DS
by
Ishrat Jahan
Boss
(
16.3k
points)

4k
views
gate2008it
datastructures
binarysearchtree
normal
+38
votes
4
answers
26
GATE200613
A scheme for storing binary trees in an array $X$ is as follows. Indexing of $X$ starts at $1$ instead of $0$. the root is stored at $X[1]$. For a node stored at $X[i]$, the left child, if any, is stored in $X[2i]$ and the right child, if any, in $X[2i+1]$. To be able to store any binary tree on n vertices the minimum size of $X$ should be $\log_2 n$ $n$ $2n+1$ $2^n1$
asked
Sep 17, 2014
in
DS
by
Rucha Shelke
Active
(
3.3k
points)

4.1k
views
gate2006
datastructures
binarytree
normal
+36
votes
3
answers
27
TIFR2013B13
Given a binary tree of the following form and having $n$ nodes, the height of the tree is $\Theta \left(\log n\right)$ $\Theta \left(n\right)$ $\Theta \left(\sqrt{n}\right)$ $\Theta \left(n / \log n\right)$ None of the above.
asked
Nov 7, 2015
in
DS
by
makhdoom ghaya
Boss
(
30.8k
points)

995
views
tifr2013
binarytree
datastructures
+36
votes
6
answers
28
GATE2005IT50
In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most $2$. If the height of the tree is $h > 0$, then the minimum number of nodes in the tree is $2^{h1}$ $2^{h1} + 1$ $2^h  1$ $2^h$
asked
Nov 4, 2014
in
DS
by
Ishrat Jahan
Boss
(
16.3k
points)

4.2k
views
gate2005it
datastructures
binarytree
normal
+36
votes
4
answers
29
GATE2008IT77
A binary tree with $n > 1$ nodes has $n_1$, $n_2$ and $n_3$ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbours. Starting with the above tree, while there remains a node $v$ of degree two in the tree, add an edge ... edges will remain at the end of the process? $2 * n_1 3$ $n_2 + 2 * n_1  2$ $n_3  n_2$ $n_2+ n_1 2$
asked
Oct 29, 2014
in
DS
by
Ishrat Jahan
Boss
(
16.3k
points)

4.1k
views
gate2008it
datastructures
binarytree
normal
+35
votes
3
answers
30
GATE2016110
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. 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 ... for both operations will be $\Omega (n)$. Worst case time complexity for both operations will be $\Omega (\log n)$
asked
Feb 12, 2016
in
DS
by
Sandeep Singh
Loyal
(
7.2k
points)

7.5k
views
gate20161
datastructures
queues
normal
Page:
1
2
3
4
5
6
...
45
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
All categories
General Aptitude
1.9k
Engineering Mathematics
7.5k
Digital Logic
2.9k
Programming and DS
4.9k
Programming
3.5k
DS
1.3k
Algorithms
4.4k
Theory of Computation
6.2k
Compiler Design
2.1k
Operating System
4.5k
Databases
4.1k
CO and Architecture
3.4k
Computer Networks
4.2k
Non GATE
1.4k
Others
1.4k
Admissions
595
Exam Queries
573
Tier 1 Placement Questions
23
Job Queries
72
Projects
18
Follow @csegate
Recent Blog Comments
@MiNiPanda Congrax mate for this success !
Mostly authentic links, it can be Stackoverflow,...
While raising objections what works as...
It is mentioned "Left for Evaluation" so no...
I think this discussion will keep on going till...
50,737
questions
57,324
answers
198,405
comments
105,169
users