# Recent questions tagged data-structures

Please solve the following question: Evaluate the Infix expression /-*25*12-119 ?
In Mid Square Method(Hashing), we square the given number and then use appropriate bits from the middle. Can we have so many answers for a particular question? On what basis we choose the middle digit? What if the square is 4 digit 1234, then what will be the middle value? Will it be 23 or 2 or 3. Please explain.
In avl tree can we take base case for minimum height as n(1)=2 rather than n(0)=1 in the recurrence relation : n(h)=2n(h-1)+1 where h is height of the tree.
1 vote
I have a very generic doubt about the Trees concept in Data structures subject, Are Trees in the subject implicitly assumed to be directed unless mentioned otherwise? Say for example, with Binary Trees or K-ary Trees the degree of child nodes are taken to be 0 without explicitly stating that the Tree is directed, Am I missing something.
True/False 1) Multiplying all edge weight by a positive number might change the graph MST. 2) If all edge in a graph have distinct weight than the shortest path between two vertices is unique. Please answer with reason. Thanks
1 vote
​​​​​Let $H$ be a binary min-heap consisting of $n$ elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in $H$? $\Theta (1)$ $\Theta (\log n)$ $\Theta (n)$ $\Theta (n \log n)$
Consider a complete binary tree with $7$ nodes. Let $A$ denote the set of first $3$ elements obtained by performing Breadth-First Search $\text{(BFS)}$ starting from the root. Let $B$ denote the set of first $3$ elements obtained by performing Depth-First Search $\text{(DFS)}$ starting from the root. The value of $\mid A-B \mid$ is _____________
Let $P$ be an array containing $n$ integers. Let $t$ be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of $n$ elements. Which one of the following choices is correct? $t>2n-2$ ... $t>n \text{ and } t\leq 3\lceil \frac{n}{2}\rceil$ $t>\lceil \log_2(n)\rceil \text{ and } t\leq n$
A binary search tree $T$ contains $n$ distinct elements. What is the time complexity of picking an element in $T$ that is smaller than the maximum element in $T$? $\Theta(n\log n)$ $\Theta(n)$ $\Theta(\log n)$ $\Theta (1)$
Consider the following sequence of operations on an empty stack.$\textsf{push}(54);\textsf{push}(52);\textsf{pop}();\textsf{push}(55);\textsf{push}(62);\textsf{s}=\textsf{pop}();$ ... $\textsf{s+q}$ is ___________.
An $articulation$ $point$ in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let $T$ be a $\text{DFS}$ tree obtained by doing $\text{DFS}$ in a connected undirected graph $G$. Which of the following ... and $y$ is a descendent of $u$ in $T$, then all paths from $x$ to $y$ in $G$ must pass through $u$.
1 vote
"Consider the following array of elements <40, 35, 20, 10, 15, 16, 17, 8, 4, 30>. The minimum number of interchanges needed to convert it into a min-heap is _________ using built heap method." I am getting 7.
The number of min heap trees are possible with 15 distinct elements such that every leaf node must be greater than all non-leaf nodes of the tree are ________. According to me, the answer should be 80* 8! The given answer is different.
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
4.9. Suppose that G1 = (V1, {a, b}, S1, P1) and G2 = (V2, {a, b}, S2, P2) are CFGs and that V1 ∩ V2 = ∅. a. It is easy to see that no matter what G1 and G2 are, the CFG Gu = (Vu, {a, b}, Su, Pu) defined by Vu = V1 ∪ V2, Su = S1, and Pu = P1 ∪ P2 ∪ {S1 → S2} ... = P1 ∪ {S1 → S1S1 | } generates every string in L(G1) ∗. Find a grammar G1 with V1 = {S1} and a string x ∈ L(G ∗ ) such that x /∈ L(G) ∗.
Maximum number of node at level I is 2^I. Prove
What are the total number of nodes in a binary tree of height K ?
c+ = p&1; //c and p are integers How the above statement is executed..either c= (c+p)&1 or c= c+(p&1).
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
Prove that Maximum no. of node at level I is 2^I
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
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.
I am getting 48 as a answer! please clear whether the given answer is correct or there is any mistake?
I gave a madeeasy subject-wise test of programming and ds, and it had the following question copied from a quiz of Illinois Institute of Technology CS Dept (Source: http://www.cs.iit.edu/~iraicu/teaching/EECS211/quiz4-sol.pdf) Multiple Select Question(as modified by madeeasy, the ... root and another to the leaf), so shouldn't option A be incorrect, as 2 nodes out of 3 don't have multiple links?
select the correct statements .binary search trees(regardless of the order in which values are inserted into the tree). a)always have multiple links per node b)can be sorted efficiently c)always have the same shape for a particular set of data d)are non linear data structures ans is a,b,d can someone explain a,b part?
1 vote
Polynomial addition is implemented using which data structure? $(a)$ Queue $(b)$ Linked List $(c)$ Tree $(d)$ Stack Here My ans was Tree but given ans is Linked List Which one correct? Explaination according to them
1 vote
The post order traversal of a heap is ACEDBHIGF. The possible pre-order traversal is: 1. ABCDEFGHI FBEACDGHI FBEADCGHI ABDCEFGIH
What will be the output of the following program? main( ) { main( ); } (A) overflow error (B) syntax error (C) returns 0 (D) returns 1
What would be the answer? I got 32, but it’s wrong.
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 array is 500. The address of A[15][25] will be _____. [Note: Only lower triangular elements of the matrix are stored in contiguous array]
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?
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
Source : https://gateoverflow.in/2075/gate2014-3-41 While solving this question I consider this LC-RS representation (I have not considered node 7,8,9 just for simplicity. So just ignore them) and got the final value as $4.$ In the best answer answer given as $D)$ $\#$ of leaf ... be converted to leaf? $3)$ How can 5 OR 3 be a leaf nodes? $4)$ How are we defining a leaf node for such a tree?
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.