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
Most answered 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
+93
votes
14
answers
1
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.8k
views
gate20162
datastructures
binarysearchtree
normal
numericalanswers
+29
votes
11
answers
2
GATE2007IT28
Consider a hash function that distributes keys uniformly. The hash table size is $20$. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed $0.5$. $5$ $6$ $7$ $10$
asked
Oct 30, 2014
in
DS
by
Ishrat Jahan
Boss
(
16.3k
points)

6.8k
views
gate2007it
datastructures
hashing
probability
normal
+42
votes
11
answers
3
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
+33
votes
11
answers
4
GATE201010
In a binary tree with $n$ nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child? $0$ $1$ $\frac{(n1)}{2}$ $n1$
asked
Sep 29, 2014
in
DS
by
jothee
Veteran
(
106k
points)

3.9k
views
gate2010
datastructures
binarytree
normal
+19
votes
10
answers
5
GATE2015210
A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.
asked
Feb 12, 2015
in
DS
by
jothee
Veteran
(
106k
points)

4.9k
views
gate20152
datastructures
binarytree
normal
numericalanswers
+21
votes
9
answers
6
GATE201716
Let $T$ be a binary search tree with $15$ nodes. The minimum and maximum possible heights of $T$ are: Note: The height of a tree with a single node is $0$. $4$ and $15$ respectively. $3$ and $14$ respectively. $4$ and $14$ respectively. $3$ and $15$ respectively.
asked
Feb 14, 2017
in
DS
by
Arjun
Veteran
(
432k
points)

4.1k
views
gate20171
datastructures
binarysearchtree
easy
+20
votes
9
answers
7
GATE2017213
A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of ... node points to the front node. (I) only. (II) only. Both (I) and (II). Neither (I) nor (II).
asked
Feb 14, 2017
in
DS
by
Madhav
Active
(
1.6k
points)

8.5k
views
gate20172
datastructures
queues
+47
votes
9
answers
8
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
(
106k
points)

7k
views
datastructures
hashing
normal
gate2010
+74
votes
9
answers
9
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.2k
views
gate20161
datastructures
queues
difficult
numericalanswers
+23
votes
9
answers
10
GATE199819b
Compute the post fix equivalent of the following expression $3^*\log(x+1)\frac{a}{2}$
asked
Aug 29, 2015
in
DS
by
Arjun
Veteran
(
432k
points)

3.6k
views
gate1998
stack
infixpostfix
+35
votes
9
answers
11
GATE2004IT13
Let $P$ be a singly linked list. Let $Q$ be the pointer to an intermediate node $x$ in the list. What is the worstcase time complexity of the bestknown algorithm to delete the node $x$ from the list ? $O(n)$ $O(\log^2 n)$ $O(\log n)$ $O(1)$
asked
Nov 2, 2014
in
DS
by
Ishrat Jahan
Boss
(
16.3k
points)

5.4k
views
gate2004it
datastructures
linkedlists
normal
ambiguous
+55
votes
9
answers
12
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
(
106k
points)

6.8k
views
gate20141
datastructures
binarytree
numericalanswers
normal
+45
votes
9
answers
13
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
+53
votes
8
answers
14
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.9k
views
gate20171
datastructures
linkedlists
normal
+28
votes
8
answers
15
GATE2015325
Consider a binary tree T that has $200$ leaf nodes. Then the number of nodes in T that have exactly two children are ______.
asked
Feb 14, 2015
in
DS
by
jothee
Veteran
(
106k
points)

4.5k
views
gate20153
datastructures
binarytree
normal
numericalanswers
+46
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
(
106k
points)

3.9k
views
gate20152
databases
arrays
normal
numericalanswers
+100
votes
8
answers
17
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)

13k
views
gate2007it
datastructures
binarysearchtree
normal
+29
votes
8
answers
18
GATE201129
We are given a set of $n$ distinct elements and an unlabeled binary tree with $n$ nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree? $0$ $1$ $n!$ $\frac{1} {n+1} .^{2n}C_n$
asked
Sep 29, 2014
in
DS
by
jothee
Veteran
(
106k
points)

7.3k
views
gate2011
binarytree
normal
+36
votes
8
answers
19
GATE2014342
Consider the C function given below. Assume that the array $listA$ contains $n (>0)$ elements, sorted in ascending order. int ProcessArray(int *listA, int x, int n) { int i, j, k; i = 0; j = n1; do { k = (i+j)/2; if (x <= listA[ ... is an implementation of binary search. It will always find the maximum element in $listA$. It will return −$1$ even when $x$ is present in $listA$.
asked
Sep 28, 2014
in
DS
by
jothee
Veteran
(
106k
points)

4.2k
views
gate20143
datastructures
arrays
easy
+32
votes
8
answers
20
GATE2014241
Suppose a stack implementation supports an instruction $REVERSE$, which reverses the order of elements on the stack, in addition to the $PUSH$ and $POP$ instructions. Which one of the following statements is TRUE (with respect to this modified stack)? A ... $ENQUEUE$ and $DEQUEUE$ take a single instruction each.
asked
Sep 28, 2014
in
DS
by
jothee
Veteran
(
106k
points)

6.6k
views
gate20142
datastructures
stack
easy
+22
votes
8
answers
21
GATE19982.11
A complete $n$ary tree is one in which every node has $0$ or $n$ sons. If $x$ is the number of internal nodes of a complete $n$ary tree, the number of leaves in it is given by $x(n1) +1$ $xn1$ $xn +1$ $x(n+1)$
asked
Sep 26, 2014
in
DS
by
Kathleen
Veteran
(
52.2k
points)

3k
views
gate1998
datastructures
trees
normal
+16
votes
7
answers
22
GATE201946
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$ (ie., the number of edges in the unique path between $a$ and $b$) is (rounded off to $2$ decimal places) _________.
asked
Feb 7, 2019
in
DS
by
Arjun
Veteran
(
432k
points)

6.9k
views
gate2019
numericalanswers
datastructures
binarytree
+9
votes
7
answers
23
ISRO201119
If node A has three siblings and B is parent of A, what is the degree of A? 0 3 4 5
asked
Jun 15, 2016
in
DS
by
shibu
(
47
points)

3.4k
views
isro2011
datastructures
trees
+35
votes
7
answers
24
GATE2016138
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$ ... 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 ___________.
asked
Feb 12, 2016
in
DS
by
Sandeep Singh
Loyal
(
7.2k
points)

8.5k
views
gate20161
datastructures
graphs
normal
numericalanswers
+17
votes
7
answers
25
TIFR2012B15
Let $T$ be a tree of $n$ nodes. Consider the following algorithm, that constructs a sequence of leaves $u_{1}, u_{2}...$. Let $u_{1}$ be some leaf of tree. Let $u_{2}$be a leaf that is farthest from $u_{1}$. Let $u_{3}$ be the leaf ... stays constant. For the same tree, the distance between the last two vertices visited can be different, based on the choice of the first leaf $u_{1}$.
asked
Nov 2, 2015
in
DS
by
makhdoom ghaya
Boss
(
30.9k
points)

1.1k
views
tifr2012
datastructures
trees
+35
votes
7
answers
26
GATE2006IT9
In a binary tree, the number of internal nodes of degree $1$ is $5$, and the number of internal nodes of degree $2$ is $10$. The number of leaf nodes in the binary tree is $10$ $11$ $12$ $15$
asked
Oct 31, 2014
in
DS
by
Ishrat Jahan
Boss
(
16.3k
points)

5.5k
views
gate2006it
datastructures
binarytree
normal
+31
votes
7
answers
27
GATE201350
The procedure given below is required to find and replace certain characters inside an input character string supplied in array $A$. The characters to be replaced are supplied in array $oldc$, while their respective replacement characters are supplied in array $newc$. ... cases given above, how many test cases will be able to capture the flaw? Only one Only two Only three All four
asked
Sep 24, 2014
in
DS
by
Arjun
Veteran
(
432k
points)

3.3k
views
gate2013
datastructures
arrays
normal
+54
votes
7
answers
28
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.3k
views
gate2004
binarysearchtree
normal
datastructures
+29
votes
7
answers
29
GATE200436
A circularly linked list is used to represent a Queue. A single variable $p$ is used to access the Queue. To which node should $p$ point such that both the operations $\text{enQueue}$ and $\text{deQueue}$ can be performed in constant time? rear node front node not possible with a single pointer node next to front
asked
Sep 19, 2014
in
DS
by
Kathleen
Veteran
(
52.2k
points)

6.9k
views
gate2004
datastructures
linkedlists
normal
+23
votes
7
answers
30
GATE20001.14
Consider the following nested representation of binary trees: $(X \ Y \ Z)$ indicates $Y$ and $Z$ are the left and right subtrees, respectively, of node $X$. Note that $Y$ and $Z$ may be $NULL$, or further nested. Which of the following represents a valid binary tree? $(1 \ 2 \ (4 \ 5 \ 6 \ 7))$ ... $(1 \ (2 \ 3 \ 4) \ (5 \ 6 \ 7))$ $(1 \ (2 \ 3 \ NULL) \ (4 \ 5))$
asked
Sep 14, 2014
in
DS
by
Kathleen
Veteran
(
52.2k
points)

2.5k
views
gate2000
datastructures
binarytree
easy
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
@saransh0 ...... I am getting 108... is there any...
Yes you are through! Prepare for Interview
Guys do you think I have a chance? I am getting...
And there is some question like where they...
Yes post order question is also wrong.....
50,737
questions
57,391
answers
198,590
comments
105,442
users