Recent questions and answers in DS - GATE CSE Doubts

0 votes

0 answers

Data Structures

asked 6 days ago in DS by Relon (5 points) | 7 views

0 votes

0 answers

gate overflow book
https://gateoverflow.in/4208/gate2000-2-19 The above is the link of the question. In the question it is given that DFS results in a DFS tree T. Does this strictly imply that the graph is connected? Because if not then we can even have a disconnected graph as a counter example

asked Feb 4 in DS by hadarsh (5 points) | 31 views

0 votes

1 answer

Applied GATE test series
Que Consider a circular queue which is of capacity 100 elements and is implemented on an array a[0...99], at a particular instant the front pointer is pointing to index 20 and the rear is pointing at index 10 the number of elements present in the queue is. 10 90 91 None

answered Jan 16 in DS by Abhisheksmile94 (347 points) | 67 views

0 votes

1 answer

#gate2000#cse#graph
Why b option is incorrect Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following ... u is a leaf in T (D) If {u,v} is not an edge in G then u and v must have the same parent in T

answered Jan 14 in DS by zxy123 (3.6k points) | 31 views

0 votes

0 answers

self doubt madeeasy test series
https://gateoverflow.in/311536/made-easy-test-series-binary-tree how tree will look like ...please see

asked Jan 12 in DS by eyeamgj (29 points) | 28 views

0 votes

0 answers

SELF DOUBT HASHING
https://gateoverflow.in/57653/cormen-2nd-edition-exercise-11-2-1 WHY WE CANT DO LIKE THIS …...NUMBER OF COLLISIONS(X) : 0 1 2 3 4 …………………...N-1 P(X): 0/M 1/M 2/M…………………… … ………….(N-1)/M

asked Jan 12 in DS by eyeamgj (29 points) | 25 views

0 votes

0 answers

AVL PREVIOUS YEAR DATA STRUCTURE SELF DOUBT
https://gateoverflow.in/86224/gate1990-13a for tym complexity ..is it like …..n times we need to search position so O(nlogn) n insertion so O(n) and only two rotation so O(logn)...because i m not rotating for each iteration just doing at last so overall O(nlogn)...please look...

asked Jan 8 in DS by eyeamgj (29 points) | 10 views

0 votes

1 answer

Applied Test series Data Structure
Maximum no of elements which can be inserted in a queue which is implemented using a circular queue on an array of size 10. Answer given was: (9) The maximum number of elements which can be stored in a circular queue of array of size n is n-1

answered Jan 3 in DS by Abhisheksmile94 (347 points) | 26 views

0 votes

1 answer

Gate previous year question
Q. Let Q denote a queue containing 16 numbers and S be an empty stack. Head(Q) returns the element at the head of queue Q without removing it from Q. similarly Top(S) returns the element at the top of S without removing it from S. consider ... else x:=Pop(S); Enqueue(Q,x); end end The maximum possible number of iteration of the while loop in the algorithm is_________

answered Jan 1 in DS by wander (301 points) | 26 views

0 votes

2 answers

ACE test Series
Suppose that a tree T has N1 vertices of degree 1, 2 vertices of degree 2 , 4 vertices of degree 3 And 3 vertices of degree 4. Number of vertices in the tree is ? Answer given is 21

answered Dec 22, 2020 in DS by toxicdesire (555 points) | 38 views

0 votes

0 answers

#Self Doubt #Data_Strct #Binary_Tree
Maximum number of node at level I is 2^I. Prove

asked Dec 19, 2020 in DS by ApolloXYZ (1 point) | 11 views

0 votes

0 answers

#Self Doubt #Data_Strct #Binary_Tree
What are the total number of nodes in a binary tree of height K ?

asked Dec 19, 2020 in DS by ApolloXYZ (1 point) | 10 views

0 votes

2 answers

#Self Doubt #DataStruct
The degree of a node is the no. of children it has. Show that in any binary tree the number of leaves is 1 more than the no. of nodes of degree 2.

answered Dec 17, 2020 in DS by Sahil91 (683 points) | 39 views

0 votes

1 answer

#Self Doubt #Data Struct
Prove by Induction that if T us a binary tree with n internal nodes, I its internal path lane and P its external path lane then E=I+2n, where n>=0

answered Dec 17, 2020 in DS by gajendercse (41 points) | 13 views

0 votes

0 answers

#Self Doubt #DataStrct
Prove that Maximum no. of node at level I is 2^I

asked Dec 16, 2020 in DS by ApolloXYZ (1 point) | 15 views

0 votes

0 answers

#Self Doubt #DS-BinaryTree
Prove by Induction that if T is a binary tree with n internal nodes, I (its internal path lane) and P (its external path lane), then E=I+2n where n>=0

asked Dec 16, 2020 in DS by ApolloXYZ (1 point) | 6 views

0 votes

1 answer

Made Easy Test Series
The average successful search time taken by binary search on a sorted array of 10 items is ___________

answered Dec 3, 2020 in DS by ijnuhb (747 points) | 62 views

0 votes

1 answer

NIELIT NIC scientist-B 2020 set-C ques 82
Suppose we have to insert the following sequence of keys into an empty binary search tree: 5, 7, 45, 60, 50, 23, 15, 54 What would be the height of binary search tree?

answered Nov 26, 2020 in DS by zxy123 (3.6k points) | 20 views

0 votes

0 answers

Source: http://www.cs.iit.edu/~iraicu/teaching/EECS211/quiz4-sol.pdf

asked Nov 18, 2020 in DS by rish-18 (9 points) | 53 views

+1 vote

1 answer

NIC Testbook test series
The post order traversal of a heap is ACEDBHIGF. The possible pre-order traversal is: 1. ABCDEFGHI FBEACDGHI FBEADCGHI ABDCEFGIH

answered Nov 10, 2020 in DS by zxy123 (3.6k points) | 43 views

0 votes

1 answer

DU M.Sc (C.S) Exam
When inorder traversal of a tree is given by OBAXVRZPW, the preorder traversal will yield: 1. XABOVZRWP 2. XABOVZRPW 3. XOBAZRPWV 4. XOBAVRZPW

answered Oct 18, 2020 in DS by kalin (155 points) | 42 views

0 votes

0 answers

https://gateoverflow.in/113877/b-tree-deletion-doubt

asked Oct 6, 2020 in DS by TechLover (5 points) | 10 views

0 votes

0 answers

Self Doubt (PYQ)
https://gateoverflow.in/2716/gate1996-1-12 In this question it is said that linked list is more efficient that array for basic operations. If I consider the operations Insert, Delete (pointer given), Find the time complexities are as follows – Insert – LL → O(1), Array → O(n) Delete – LL → O(n), Array → O(1) Find – LL → O(n), Array → O(n). How is linked list more efficient.

asked Sep 24, 2020 in DS by Mellophi (363 points) | 42 views

0 votes

1 answer

Previous Year Gate Question(2007)
A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L=41, and I=10, what is the value of n: (a) 3 (b) 4 (c ) 5 (d) 6

answered Sep 21, 2020 in DS by Musa (5 points) | 91 views

0 votes

0 answers

ACE PRACTISE BOOK
Nine nodes labeled 1,2,3…...9 are used to construct different binary trees. How many such binary trees can be constructed whose pre-order traversal 1,2,3….9.

asked Sep 20, 2020 in DS by Vishal_kumar98 (37 points) | 34 views

+1 vote

1 answer

Self Doubt - Classification of Edges in DFS
Source: Cormen. Back edges are those edges (u,v) connecting a vertex u to an ancestor v in a depth-first tree. We consider self-loops, which may occur in directed graphs, to be back edges. Forward edges are those non-tree edges (u, ... doubt: Why there is a difference in the definition of the highlighted part? Back edges are also non-tree edges, isn't it?

answered Sep 8, 2020 in DS by ijnuhb (747 points) | 106 views

0 votes

2 answers

Madeeasy GATE youtube video discussion and also Madeeasy test series.

answered Aug 26, 2020 in DS by Scion_of_fire (49 points) | 118 views

0 votes

0 answers

Cormen:Edition 3:Exercise 2.2:Page number-40
Bubblesort is a popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order. $BUBBLESORT(A)$ 1 for i=1 to A.length􏰐-1 2 for j=A.length downto i+1 3 if A[j]<A[j-1] ... allow you to prove in- equality (2.3). Your proof should use the structure of the loop invariant proof presented in this chapter.

asked Aug 26, 2020 in DS by srestha (1k points) | 13 views

0 votes

3 answers

made easy test series 2021
Consider a 2 dimensional array A[0 --- 39, 0 --- 39] in lower triangular matrix representation. The size of each element in the array is 1 byte. If the array is implemented in the memory in the form of row major order and base address of the ... 500. The address of A[15][25] will be _____. [Note: Only lower triangular elements of the matrix are stored in contiguous array]

answered Aug 25, 2020 in DS by varsha394 (11 points) | 287 views

0 votes

1 answer

UGC NET CS 2016 July – III
Let A[1...n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. What is the expected number of inversions in any permutation on n elements ? A) n(n-1)/2 B) n(n-1)/4 C n(n+1)/4 D 2n[logn]

answered Aug 21, 2020 in DS by Arkaprava (801 points) | 37 views

0 votes

1 answer

GeekForGeeks
Consider an array consisting of –ve and +ve numbers. What would be the worst case time complexity of an algorithm to segregate the numbers having same sign altogether i.e all +ve on one side and then all -ve on the other ? A) O(N) B) O(N Log N) C) O(N * N) D) O(N Log Log N)

answered Aug 21, 2020 in DS by Ollie (525 points) | 93 views

0 votes

1 answer

Self doubt on Addressing of Two dimensional Array
Please explain me row major and column major in lower and upper triangular matrix.

answered Aug 16, 2020 in DS by Arkaprava (801 points) | 28 views

0 votes

1 answer

In a Binary tree, given Leaf nodes = 200 then how many nodes will be of degree 1?

answered Aug 16, 2020 in DS by jayeshasawa001 (2.5k points) | 31 views

0 votes

2 answers

#datastructure #madeeasy
here L = no of leaves, n = n ary, i = no of internal node so L = (n-1)*i +1 L = (3-1)*10 +1 L = 2*10 +1 = 21 so total no of leaf node = 21?? please clear my doubt

answered Aug 16, 2020 in DS by jayeshasawa001 (2.5k points) | 21 views

0 votes

2 answers

#datastructure #madeeasy #binarytree
sir max height of AVL tree is 1.44*log2 n. 1.44log2 36 = 7.44 so here maximum height of AVL tree with 36 node is 7?

answered Aug 16, 2020 in DS by jayeshasawa001 (2.5k points) | 31 views

0 votes

1 answer

#MadeEasy #Arrays
Professor Pradhumn decides to make quick sort stable by changing each key A[i] in array A[1:n] to (n*A[i]) +i-1, so that all the new keys are distinct(call the modified array A'[1:n] and then sorting A' (Assume A is subset of integers). Then ... each i. (c) A' does not always contain distinct keys. (d) A' contains distinct elements but it is not possible to restore original keys.

answered Aug 15, 2020 in DS by Arkaprava (801 points) | 78 views

0 votes

1 answer

#MadeEasy #Arrays
In a compact single dimensional array representation for lower triangular matrices( i.e. all the elements above the diagonal are zero of sign n*n, none zero elements (i.e. elements of the lower triangle) of each row are stored one after another, starting from the first row, the index of the (i,j) th ... new representation is (a) i+j (b) i+1-1 (c) j+(i(i-1) /2) (d) i+(j(j-1) /2)

answered Aug 15, 2020 in DS by Arkaprava (801 points) | 24 views

0 votes

2 answers

#MadeEasyBook #Arrays
Let A[1:n] be an array such that A[i] = i. An algorithm randomly permutes the elements of A, call the resulting array A'. Let X denote the number of locations such that A'[i] = i. What is expectation of X. (a) n² (b) n/2 (c) n (d) 1

answered Aug 15, 2020 in DS by jayeshasawa001 (2.5k points) | 35 views

0 votes

2 answers

#MadeEasyBook #Arrays
Suppose we want to arrange the n numbers stored in an array such that all negative value occur before all positive ones, minimum number of exchanges required in the worst case is (a) n-1 (b) n (c) n+1 (d) n+(n+1) /2

answered Aug 15, 2020 in DS by jayeshasawa001 (2.5k points) | 41 views

0 votes

1 answer

#MadeEasy #Arrays
What is the output of the below program? Assume array begin at address 54572. Main() { Int a[3] [4] = [ 1 2 3 4 5 6 7 8 9 10 11 12] printf("\n %u %u", a+1, &a+1) ; }

answered Aug 15, 2020 in DS by Arkaprava (801 points) | 20 views

To see more, click for all the questions in this category.

Recent questions and answers in DS

9,197 questions

3,182 answers

14,686 comments

96,162 users