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
Previous GATE 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
+3
votes
5
answers
1
GATE201940
Consider the following statements: The smallest element in a maxheap is always at a leaf node The second largest element in a maxheap is always a child of a root node A maxheap can be constructed from a binary search tree in $\theta(n)$ time A binary search tree can be ... time Which of te above statements are TRUE? I, II and III I, II and IV I, III and IV II, III and IV
asked
Feb 7, 2019
in
DS
by
Arjun
Veteran
(
432k
points)

3.1k
views
gate2019
datastructures
heap
+15
votes
7
answers
2
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
+1
vote
0
answers
3
GATE199716
In this GATE ques Part a) For Size balanced tree the recurrence (max height) is T(h)=T(h1) +T(h2) +1, solving which we get T(0)=1, T(1)=2,T(2)=1+2+1=4, T(3)=4+2+1=7 Here, T(0),T(1),T(2) are of the form 2h but T(3) is not equal to 23 then how can we claim that "sizebalance binary tree of height 'h' contain at least 2h nodes." ?
[closed]
asked
Mar 14, 2018
in
DS
by
Mamta Satywali
Active
(
2.9k
points)

261
views
gate1997
datastructures
binarytree
+11
votes
5
answers
4
GATE201820
The postorder traversal of a binary tree is $\text{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 _____
asked
Feb 14, 2018
in
DS
by
gatecse
Boss
(
17.5k
points)

2.5k
views
gate2018
datastructures
binarytree
numericalanswers
+16
votes
4
answers
5
GATE20183
A queue is implemented using a noncircular 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 ... $\Theta(1), \Theta(1)$ $\Theta(1), \Theta(n)$ $\Theta(n), \Theta(1)$ $\Theta(n), \Theta(n)$
asked
Feb 14, 2018
in
DS
by
gatecse
Boss
(
17.5k
points)

3.8k
views
gate2018
algorithms
datastructures
queues
normal
linkedlists
+53
votes
8
answers
6
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
+21
votes
5
answers
7
GATE2017236
The preorder traversal of a binary search tree is given by $12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20$. Then the postorder 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$
asked
Feb 14, 2017
in
DS
by
Arjun
Veteran
(
432k
points)

3k
views
gate20172
datastructures
binarysearchtree
+23
votes
6
answers
8
GATE2017120
Let $T$ be a tree with $10$ vertices. The sum of the degrees of all the vertices in $T$ is ________
asked
Feb 14, 2017
in
DS
by
Arjun
Veteran
(
432k
points)

4.6k
views
gate20171
datastructures
trees
numericalanswers
+21
votes
9
answers
9
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
10
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
+3
votes
3
answers
11
GATE19887iii
Consider the tree given in the below figure, insert $13$ and show the new balance factors that would arise if the tree is not rebalanced. Finally, carry out the required rebalancing of the tree and show the new tree with the balance factors on each mode.
asked
Dec 19, 2016
in
DS
by
jothee
Veteran
(
106k
points)

499
views
gate1988
normal
descriptive
datastructures
binarytree
+1
vote
2
answers
12
GATE19887ii
Mark the balance factor of each on the tree given on the below figure and state whether it is heightbalanced.
asked
Dec 19, 2016
in
DS
by
jothee
Veteran
(
106k
points)

174
views
gate1988
normal
descriptive
binarytree
0
votes
1
answer
13
GATE19887i
Define the height of a binary tree or subtree and also define a heightbalanced (AVL) tree.
asked
Dec 19, 2016
in
DS
by
jothee
Veteran
(
106k
points)

197
views
gate1988
normal
descriptive
datastructures
binarytree
+20
votes
1
answer
14
GATE199911b
Write a constant time algorithm to insert a node with data $D$ just before the node with address $p$ of a singly linked list.
asked
Dec 17, 2016
in
DS
by
Arjun
Veteran
(
432k
points)

707
views
gate1999
datastructures
linkedlists
+2
votes
1
answer
15
GATE19894xi
Provide short answers to the following questions: Express the following list in terms of a linked list structure suitable for internal representation. $(((ab)c)d((e)))$
asked
Nov 30, 2016
in
DS
by
makhdoom ghaya
Boss
(
30.9k
points)

229
views
gate1989
descriptive
datastructures
linkedlists
unsolved
+15
votes
1
answer
16
GATE200677
Statement for Linked Answer Questions 76 & 77: 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 ... $10, 9, 4, 5, 7, 6, 8, 2, 1, 3$ $10, 8, 6, 9, 7, 2, 3, 4, 1, 5$
asked
Nov 27, 2016
in
DS
by
Arjun
Veteran
(
432k
points)

1.4k
views
gate2006
datastructures
heap
normal
+7
votes
2
answers
17
GATE19893ixa
Answer the following: Which one of the following statements (s) is/are FALSE? Overlaying is used to run a program, which is longer than the address space of the computer. Optimal binary search tree construction can be performed efficiently by using dynamic ... components of a graph. Given the prefix and postfix walls over a binary tree, the binary tree can be uniquely constructed.
asked
Nov 27, 2016
in
DS
by
makhdoom ghaya
Boss
(
30.9k
points)

1k
views
normal
gate1989
binarytree
graphsearch
+7
votes
2
answers
18
GATE199013a
Consider the heightbalanced tree $T_{t}$ with values stored at only the leaf nodes, shown in Fig.4. (i) Show how to merge to the tree, $T_{1}$ elements from tree $T_{2}$ shown in Fig.5 using node D of tree $T_{1}$. (ii) What is the time complexity of ... $T_{1}$ and $T_{2}$ are of height $h_{1}$ and $h_{2}$ respectively, assuming that rotation schemes are given. Give reasons.
asked
Nov 26, 2016
in
DS
by
makhdoom ghaya
Boss
(
30.9k
points)

814
views
gate1990
descriptive
datastructures
trees
+7
votes
3
answers
19
GATE19903iv
Choose the correct alternatives (More than one may be correct). The total external path length, EPL, of a binary tree with $n$ external nodes is, $EPL= \sum_{w} Iw$, where $I_{w}$ is the path length of external node $w$), $\leq n^{2}$ always. $\geq n \log_{2} n$ always. Equal to $n^{2}$ always. $O(n)$ for some special trees.
asked
Nov 22, 2016
in
DS
by
makhdoom ghaya
Boss
(
30.9k
points)

531
views
gate1990
normal
datastructures
binarytree
+6
votes
1
answer
20
GATE19902viii
Match the pairs in the following questions: ...
asked
Nov 19, 2016
in
DS
by
makhdoom ghaya
Boss
(
30.9k
points)

890
views
gate1990
matchthefollowing
datastructures
heap
+13
votes
3
answers
21
GATE19877b
Construct a binary tree whose preorder traversal is K L N M P R Q S T and inorder traversal is N L K P R M S Q T
asked
Nov 15, 2016
in
DS
by
makhdoom ghaya
Boss
(
30.9k
points)

872
views
gate1987
datastructures
binarytree
+8
votes
3
answers
22
GATE19876a
A list of $n$ elements is commonly written as a sequence of $n$ elements enclosed in a pair of square brackets. For example. $[10, 20, 30]$ is a list of three elements and $[]$ is a nil list. Five functions are defined below: $car (l)$ returns the first element of its argument list $l$ ... $f ([32, 16, 8], [9, 11, 12])$ (b) $g ([5, 1, 8, 9])$
asked
Nov 14, 2016
in
DS
by
makhdoom ghaya
Boss
(
30.9k
points)

667
views
gate1987
datastructures
linkedlists
+14
votes
3
answers
23
GATE19872g
State whether the following statements are TRUE or FALSE: If the number of leaves in a tree is not a power of 2, then the tree is not a binary tree.
asked
Nov 9, 2016
in
DS
by
makhdoom ghaya
Boss
(
30.9k
points)

934
views
gate1987
datastructures
binarytree
+16
votes
2
answers
24
GATE19872c
State whether the following statements are TRUE or FALSE: It is possible to construct a binary tree uniquely whose preorder and postorder traversals are given?
asked
Nov 9, 2016
in
DS
by
makhdoom ghaya
Boss
(
30.9k
points)

1.2k
views
gate1987
binarytree
datastructures
normal
+13
votes
3
answers
25
GATE19871xv
In a circular linked list oraganisation, insertion of a record involves modification of One pointer. Two pointers. Multiple pointers. No pointer.
asked
Nov 8, 2016
in
DS
by
makhdoom ghaya
Boss
(
30.9k
points)

3.3k
views
gate1987
datastructures
linkedlists
+16
votes
3
answers
26
GATE200960
Consider a binary maxheap implemented using an array. What is the content of the array after two delete operations on $\left\{25,14,16,13,10,8,12\right\}$ $\left\{14,13,12,10, 8\right\}$ $\left\{14,12,13,8,10\right\}$ $\left\{14,13,8,12,10\right\}$ $\left\{14,13,12,8,10\right\}$
asked
Apr 23, 2016
in
DS
by
jothee
Veteran
(
106k
points)

1.5k
views
gate2009
datastructures
heap
normal
+47
votes
9
answers
27
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
+20
votes
2
answers
28
GATE201351
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$. Array $A$ ... cases will be successful in exposing the flaw in this procedure? None $2$ only $3$ and $4$ only $4$ only
asked
Apr 21, 2016
in
DS
by
jothee
Veteran
(
106k
points)

1.3k
views
gate2013
datastructures
arrays
normal
+22
votes
1
answer
29
GATE199114,c
Consider the binary tree in the figure below: Outline a procedure in Pseudocode to delete an arbitrary node from such a binary tree with $n$ nodes that preserves the structures. What is the worstcasetimecomplexity of your procedure?
asked
Apr 18, 2016
in
DS
by
jothee
Veteran
(
106k
points)

850
views
gate1991
normal
datastructures
binarytree
timecomplexity
+13
votes
2
answers
30
GATE199114,b
Consider the binary tree in the figure below: Give different steps for deleting the node with key $5$ so that the structure is preserved.
asked
Apr 18, 2016
in
DS
by
jothee
Veteran
(
106k
points)

791
views
gate1991
datastructures
binarytree
normal
Page:
1
2
3
4
5
6
7
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
Previous GATE Questions in DS
Recent Blog Comments
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.....
Even the post order question also I think.
50,737
questions
57,390
answers
198,589
comments
105,443
users