Recent questions and answers in DS - GATE CSE Doubts

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 in DS by kalin (5 points) | 36 views

0 votes

0 answers

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

asked Oct 6 in DS by TechLover (5 points) | 8 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 in DS by Mellophi (333 points) | 31 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 in DS by Musa (5 points) | 41 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 in DS by Vishal_kumar98 (7 points) | 25 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 in DS by Shashank Rustagi (513 points) | 79 views

0 votes

2 answers

Madeeasy GATE youtube video discussion and also Madeeasy test series.

answered Aug 26 in DS by Scion_of_fire (47 points) | 61 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 in DS by srestha (1k points) | 11 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 in DS by varsha394 (11 points) | 163 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 in DS by Arkaprava (711 points) | 27 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 in DS by Ollie (453 points) | 26 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 in DS by Arkaprava (711 points) | 18 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 in DS by jayeshasawa001 (2.5k points) | 28 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 in DS by jayeshasawa001 (2.5k points) | 18 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 in DS by jayeshasawa001 (2.5k points) | 19 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 in DS by Arkaprava (711 points) | 48 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 in DS by Arkaprava (711 points) | 16 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 in DS by jayeshasawa001 (2.5k points) | 18 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 in DS by jayeshasawa001 (2.5k points) | 20 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 in DS by Arkaprava (711 points) | 10 views

0 votes

1 answer

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

answered Aug 15 in DS by Arkaprava (711 points) | 13 views

0 votes

1 answer

#MadeEasyBook #Arrays
Consider the 2 dimensional array. A[-8.....12, -4.....16].Calculate the address of A[1,3].Assume that it is stored in a row major order. Each element occupies 4 byte and starting address of array 2000.

answered Aug 15 in DS by Arkaprava (711 points) | 19 views

0 votes

1 answer

binary trees
what are external path and internal path in binary trees? what are the formulas related to external path length and internal path length?

answered Aug 15 in DS by Arkaprava (711 points) | 17 views

0 votes

1 answer

Self Doubt - Left Child Right Sibling (LC-RS) representation

answered Aug 15 in DS by Mellophi (333 points) | 37 views

0 votes

1 answer

Hashing ,Data Structure
Let H be a finite collection of hash functions that map a universe U of keys into {0,1,…,m-1}. H is said to be universal if for each pair of distinct keys ,k and I belongs to U, the number of hash functions ( h belongs to H) for which h(k)=n(I) is at most: |H| / m2 1 /m2 logm |H| m2 |H|/m

answered Aug 12 in DS by Arkaprava (711 points) | 19 views

0 votes

1 answer

Que on Array doubt

answered Aug 12 in DS by Arkaprava (711 points) | 124 views

0 votes

1 answer

Time complexity to search and add all the elements between two elements in a given BST.

answered Aug 12 in DS by Arkaprava (711 points) | 23 views

0 votes

1 answer

Following is a NP Problem related to Graph
Following is a NP Problem related to Graph A= To find Longest Path B= To find Shortest Path C= To find Minimum Spanning Tree D= To find a Cycle

answered Aug 11 in DS by Arkaprava (711 points) | 12 views

0 votes

2 answers

GATE2014-3-39 Video Solution
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 ______.

answered Aug 11 in DS by SarathBaswa (337 points) | 28 views

0 votes

1 answer

Self doubt in binary search tree
How many distinct binary search trees can be created out of 5 similar keys? and How many binary search trees can be created out of 5 similar keys? and How many binary search trees can be created out of 5 distinct keys?

answered Aug 11 in DS by toxicdesire (459 points) | 70 views

0 votes

1 answer

GATE2016-2-15 Video Solution
$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 decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the ... together? $O(\log^{2} N)$ $O(N)$ $O(N^{2})$ $\Theta\left(N^{2}\log N\right)$

answered Aug 11 in DS by Arkaprava (711 points) | 16 views

0 votes

1 answer

Made Easy Test Series TopicWise

answered Aug 7 in DS by Ashutosh777 (67 points) | 34 views

0 votes

0 answers

MadeEasy Test series - Binary tree question
These are the options given: (a) Print nodes at K distance from root node. (b) Print nodes of Kth level of binary tree. (c)Both a and b (d) None of these I think the answer would be Both (a) and (b), if we consider root node at Level 0. But the answer given is (a) only If someone could explain why (b) is not the answer than it would be great help.

asked Jul 26 in DS by luc_Bloodstone (19 points) | 11 views

0 votes

0 answers

Binary Trees
Which of the following is a true about Binary Trees A Every binary tree is either complete or full. B Every complete binary tree is also a full binary tree. C Every full binary tree is also a complete binary tree. D No binary tree is both complete and full. E ... has 0 or 2 children at each node and Full have only 2 children at each node. Please tell if this statement is true or not.

asked Jul 18 in DS by arpit_18 (5 points) | 20 views

0 votes

0 answers

Locality of Reference(OS+DS) (ACE) #Gate Overflow #Arrays

asked Jul 17 in DS by codelite (5 points) | 28 views

0 votes

0 answers

Book name: algo and ds workbook by made easy, chapter name: algo and ds,exam name: NULL

asked Jul 11 in DS by sayandeb (5 points) | 17 views

0 votes

0 answers

made easy test series :Stacks
S will remain same S will contain only e' S will contain e' followed by previous element of stack in same order S will contain e' followed by previous element of stack in reverse order at 2nd last line S contains only e' then S is ... none of options match the above logic BTW answer given by them is 2 is the question/options incorrect or my reasoning is wrong???

asked Jul 4 in DS by abcd9982 (87 points) | 9 views

0 votes

0 answers

made easy test series : Binary Tree
root → value = SumElements(root → left) root → value = SumElements(root → right) root → value = SumElements(root → left) + SumElements(root → right) SumElements(root → left) + SumElements(root → right) according to me ans shoul be none of ... + SumElements(root → left) + SumElements(root → right) but they have given ans is 3rd option.Am I missing something here??

asked Jul 4 in DS by abcd9982 (87 points) | 24 views

+1 vote

1 answer

GATE2020-CS-5 Video Solution
The preorder traversal of a binary search tree is $15, 10, 12, 11, 20, 18, 16, 19$. Which one of the following is the postorder traversal of the tree? $10,11,12,15,16,18,19,20$ $11,12,10,16,19,18,20,15$ $20,19,18,16,15,12,11,10$ $19,16,18,20,11,12,10,15$

answered Apr 23 in DS by amitkhurana512 (29 points) | 22 views

0 votes

1 answer

Convert infix expression to prefix expression
12/3*6+6+6+8/2

answered Apr 23 in DS by Animesh Sinha (21 points) | 15 views

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

Recent questions and answers in DS

8,430 questions

2,707 answers

13,232 comments

95,451 users