DSA (Data Structure and Algorithm) Questions

DSA (Data Structure and Algorithm) Questions.
University Assignment/Homework Questions.
Stack, Queue , Binary Tree, Heap, AVL, Linked List.
Important DSA Questions to boost the concept.

1. 1. Given the following sequence of letters and asterisks: EAS*Y*QUE***ST***IO*N***

(a) Consider the stack data structure, supporting two operations push and pop, as discussed in
class. Suppose that for the above sequence, each letter (such as E) corresponds to a push of that
letter onto the stack and each asterisk (*) corresponds to a pop operation on the stack. Show the
sequence of values returned by the pop operations.


(b) Consider the queue data structure, supporting two operations insert and remove, as discussed
in class. Suppose that for the above sequence, each letter (such as E) corresponds to an insert of
that letter into the queue and each asterisk (*) corresponds to a remove operation on the queue.
Show the sequence of values returned by the remove operations.

Answer:
a).answer for stack Output: SYEUQTSAONIE.
b).answer for Queue Output: EASYQUESTION

2.Suppose you were asked to write a method that will take two sorted stacks A and B (min on top)
and create one stack that is sorted (min on top). You are allowed to use only the stack operations
such as pop, push, size and top. No other data structure such as arrays are not allowed. You are
allowed to use stacks. Note that elements on the stack can be compared using compareTo.

Public Stack mergeSortedStacks(Stack A, Stack B)
{
…...
}
Answer:



3. Evaluate the postfix expression: 10 5 + 60 6 / * 8 -

2. Answer :142

4.Write a recursive delete method for singly-linked lists with integer data that deletes the
first occurrence of a given integer from the list and returns the resulting list.
class ListNode
{
private int value; //data value
Public ListNode next; //next element of list, or null if last
public ListNode(int v)
{
value = v;
}
public int value()
{
return value;
}
}

Answer :
static ListNode delete(int i, ListNode s)
{
if (s == null)
return s;
if (s.value() == i)
return s.next;
s.next = delete(i, s.next);
return s;
}

5.If the sequence of operations - push (1), push (2), pop, push (1), push (2), pop, pop, pop, push
(2), pop are performed on a stack, then what will be the sequence of popped out values?

Answer:



Qusetion 6 :-Suppose you want to get from s to t on weighted graph G with
nonnegative edge weights, but you would like to stop by u if it isn’t too
inconvenient. (Here too inconvenient means that it increases the length of

3. your travel by more than 10%.) Describe an efficient algorithm that would
determine an optimal s to t path given your preference for stopping at u along
the way if not too inconvenient. It should either return the shortest path from s
to t, or the shortest path from s to t containing u.

Solution: Run Dijkstra’s algorithm twice, once from s and once from u. The
shortest path from s to t containing u is composed of the shortest path from s
to u and the shortest path from u to t. Compare the length of this path with the
length of the path from s to t, and choose the one to return based on their
lengths.

Question 7 :- Construct a Binary Tree From Inorder and Preorder Traversal
Inorder Traversal: {4,2,17,5,8,3,6}
Preorder Traversal :{1,2,4,3,5,7,8,6}

Answer:























Question 8 :- Write a recursive solution to ​Check whether a binary tree is a 
complete tree or not.
Hint:(A complete binary tree is a binary tree whose all levels except the last 
level are completely filled and all the leaves in the last level are all to the left 
side.)
 
Solution: 

4. https://www.geeksforgeeks.org/check-whether-binary-tree-complete-not-set-
2-recursive-solution/


Ques​tion 9:-​List the nodes of the tree below in preorder, postorder, and breadth-first
ord​er














Answer :-
Preorder: L,K,A,J,B,C,I,H,E,D,F,G
Postorder: A,B,C,J,K,I,D,E,F,G,H,L.
Breadth-first: L,K,I,H,A,J,E,F,G,B,C,D

Question 10 :-In the binary search tree below, carry out the following operations in
sequence: Add 5, add 17, delete 23, delete 9.














Answer: There is more than one way to do the deletes, so the final answer is not
unique, but here is one:

5. Question 11:-​T ​is a min heap of height 3. What is the largest number of nodes that
T​can have? What is the smallest number?

Answer:​The first three levels (including the root) must be fully filled out, giving a
total of 7 nodes. The 4th level has between 1 node and 8 nodes. So the total number
of nodes in the heap is between 8 and 15.
Question 12 : For each of the directed graphs shown below:
If it is acyclic, give a topological sort.
If it is not acyclic, find a cycle.

6. Answer​: Graph 1: Acyclic. Topological sort: A, B, D, C.
Graph 2: Cyclic. Cycle: F,H,G,F
Graph 3: Acyclic. There are several different topological sorts. I,J,K,L,M is one.

Question 13 :-​Describe an efficient method to merge two balanced binary
search trees with n elements each into a balanced BST. Give its running time.
Answer:-We can start by doing an in-order walk of both trees concurrently. At
each step, we compare the two tree elements and add the smaller one into a
list, L, before calling that element’s successor. When we finish walking both
trees, L will contain a sorted list of elements from both trees. This takes O(n +
n) = O(n) total time. Now, from the sorted list, we want to create a balanced
binary tree, which is the same problem as described in problem set 2. We can
do this by setting the root as the middle element of the list, and letting the first
half of the list be its left subtree and the second half be its right subtree
(recursively creating the balanced subtrees as well). This also takes O(n + n)
= O(n) time. The total time for this algorithm is therefore O(n).

Question 14 :-Ben Bitdiddle recently learned about heaps and binary search
trees in his algorithms class. He was so excited about getting to know about
them, he thought of an interesting way to combine them to create a new
hybrid binary tree called a treap. The treap T has a tuple value stored at each
node (x, y) where he calls x the key, and y the priority of the node. The keys
follow the BST property (maintain the BST invariant) while the priorities
maintain the min-heap property. An example treap is shown below:

7. Answer:-Insert the new node according to the standard BST INSERT procedure. This
preserves the BST property, but may result in a violation of the heap property. Now,
we need to fix the heap property by moving the new node up in the treap until it
reaches the correct place. Do this by repeatedly rotating on the node’s parent, moving
the node up one level while preserving the BST invariant. The BST insertion requires
O(h) time. Each rotation takes O(1), and O(h) rotations are required, so the total
insertion time is O(h).

Question 15 :-​Demonstrate what happens when we insert the keys 
5,28,19,15,20,33,12,17,10​into a hash table with collisions resolved by chaining. Let the table 
have ​9 ​slots, and let the hash function be ​h ​(​k ​)=​k ​mod9​.
 
Solution: 
Let us number our slots ​0,1,…,8​. 
Then our resulting hash table will look like following: 
 








Question – 16 ts) ​Say the following tree was obtained by inserting the element
42 into an AVL tree. The tree no longer satisfies the AVL invariant, but the
invariant can be reestablished by performing two rotate operations. Show the
resulting tree after this is done

8. Answer:-






Question 17-Run Dijkstra’s algorithm on the following directed graph, starting
at vertex S. What is the order in which vertices get removed from the priority
queue? What is the resulting shortest-path tree?







Answer:-Dijkstra will visit the vertices in the following order: S, C, A, D, F, E,
B. Dijkstra will relax the edge from D to E before the edge from F to E, since
D is closer to S than F is. As a result, the parent of each node is:






Question 18:-The following describes an execution of MAKESET UNION and
FIND operations on a set of elements labeled through MAKESET assigns

9. rank to an element and UNION breaks ties by putting the tree whose root has
the larger label as the parent of the other.
for j= 1 to 10
MAKESET(j)
end for
UNION(1,2) ; UNION(1,3); UNION(4,5); UNION(4,6); UNION(1,6); UNION(7,8);
UNION(9,10); UNION(7,10); UNION(3,8); FIND(4); FIND(3);
Give the tree from executing the above steps using union-by-rank with no
path-compression Be sure to label the nodes in the final tree including their final ranks.

Give the tree from executing the above steps using union-by-rank with path-compression
Be sure to label the nodes in the final tree including their final ranks.

Answer:

Question:19 ) Draw the Huffman tree corresponding to the encoding table below.
char freq encoding
B 2 01111
F 1 01110
H 3 0110
I ? 00
L 5 010
M 15 10
S 15 11

which one or more of the following are possible values for the frequency of the character I.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Answer:

10. 6 ≤ freq(I) ≤ 15.
Since I is not touched until after merging L with {B, F, H}, freq(I) ≥ freq(L) = 5 and freq(I) ≥
freq({B, F, H}) = 2 + 1 + 3 = 6. • Since I is merged with {B, F, H, L} instead of M or S, freq(I)
≤ freq(M) = 15 and freq(I) ≤ freq(S) = 15

Question 20:-What is the max-heap resulting from performing on the node storing 6?














Answer: will swap 6 with its larger child until 6 reaches a position where it satisfies the
max-heap property. The correct heap is:

11. Question 21:-What binary search tree is obtained after the root of this tree is deleted?














Answer:- The correct algorithm replaces 7 with the successor (next-largest) node of 7,
which is 10. The right subtree of 10 is moved to the location 10 was originally in.













Alternatively, you can replace 7 with its predecessor 6. (If 6 had a left subtree, it would be
moved to where 6 was originally.)

12. A common mistake on this problem was to use something resembling , recursively moving
the larger child up to replace the deleted parent. This does not result in a valid BST.

Question 22:
1) The number of distinct ​minimum spanning tree​s for the weighted graph below is
 













Answer:​Highlighted (ingreen) are the edges picked to make a MST. In the right side of 
MST, we could either pick edge ‘a’ or ‘b’. In the left side, we could either pick ‘c’ or ‘d’ or ‘e’ 
in MST.
There are 2 options for one edge to be picked and 3 options for another edge to be picked. 
Therefore, total 2*3 possible MSTs.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Question 23:-What is the number of binary search trees with 20 nodes with elements 1, 2, 
3,…..20 such that the root of tree is 12 and the root of left subtree is 7?
 
Answer:Number of nodes in left subtree = 11 {1, 2, 3, 4….11} 
Number of nodes in the right subtree = 8 {13, 14, ….20} 
Since for the left subtree root is 7 
Number of elements in the left part of left subtree = 6 {1, 2, 3..6} 
Number of elements in the right part of left subtree = 4 {8, 9, 10, 11} 
We know number of Binary Search trees with n nodes = (C(2n,n)/n+1) 
Number of BST with 6 nodes = (C(12,6)/7) = 132 
Number of BST with 4 nodes = (C(8,4)/5) = 14 
Number of BST with 8 nodes = (C(16,8)/9) =1430 
Total number of BST = 2642640

13.  
Question 24:-Which among the following is max-heap ?Explain the reason why it is and 
Why it is not ? 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Answer:A binary tree is max-heap if it is a complete binary tree (A complete binary tree is a 
binary tree in which every level, except possibly the last, is completely filled, and all nodes 
are as far left as possible) and it follows the max-heap property (value of each parent is 
greater than or equal to the values of its children).
A) is not a max-heap because it is not a complete binary tree 
B) is a max-heap because it is a complete binary tree and follows max-heap property. 
C) is not a max-heap because 8 is a child of 5 in this tree, so violates the max-heap 
property. 
D) is not a max-heap because 8 is a child of 5 in this tree, so violates the max-heap 
property. There are many other nodes in this tree which violate max-heap property in this 
tree. 
Question 25:-Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The 
collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 
15, 20, 33, 12, 17, 10. What is the maximum, minimum, and average chain lengths in the 
hash table.
 
Answer:-Following are values of hash function for all keys
5---->5
28----->1
19------>1{chained with 28}
15------->6
20------>2
33------>6{chained with 15}
12------>3
17--------->8

14. 10--------->1{chained with 28 and 19}
The maximum chain length is 3. The keys 28, 19 and 10 go to the same slot 1, and form a 
chain of length 3. 
The minimum chain length 0, there are empty slots (0, 4 and 7). 
Average chain length is (0 + 3 + 1 + 1 + 0 + 1 + 2 + 0 + 1)/9 = 1 
 
Question 26:- 
 
 
Use​Kruskal’salgorithmtofindaminimumspanningtree(MST)forthenetworkshown
above.Youshouldlisttheedgesintheorderinwhichyouconsiderthem.Ineachcase,
state whether you are adding the edge to your MST. Draw the resultant MST 

Answer:-
Solution


Edges (in order of consideration Add?
AB Yes
DE Yes
BC Yes
AC No
BD Yes
BE No

15. CE No
CF Yes
FE No
DF No
BF No


Resultant MST:


Note:Asthereareedgeswithequalweights,theremaybemultiplecorrectanswers
possible

Question 27:-
a)​ ​Insert 84 in the given below AVL tree. Re-draw the tree.
b) Delete 66 from the resultant tree in (a). Re-draw the tree.



Solution:-

or (for deletion using predecessor)

16. Question28​PerformtopologicalsortforbelowDAG.Provideatleasttwoorderingsbyshowing
the discovery and finishing times of visit for each node.


Solution
Ordering 1: G A B D C E F
A B C D E F G
D(t) 1 2 3 9 4 5 13
F(t) 12 11 8 10 7 6 14

Ordering 2: A B C G D E F
A B C D E F G
D(t) 9 10 11 2 3 4 1
F(t) 14 13 12 7 6 5 8

(Optional) Other possible ordering: GABCDEF)

Question 29:-

17. a)Eventhoughthegraphhasnegativeweightedges,stepthroughDijkstra’salgorithmto
calculatesupposedlyshortestpathsfromAtoeveryothervertex.Showyoursteps.Cross
outoldvaluesandwriteinnewones,fromlefttorightwithineachcell,asthealgorithm
proceeds. Also list the vertices in the order in which you marked them as known.
Solution:

Correct Order ( 2 Marks, binary ) = A, B, D, F, C, G, E

Distances { 3 mark for all correct,
2 marks if done extra reps,
0 marks otherwise
[ some exceptions on checker discretion ]
}
A 0
B 2
C 7
D 4
E 12 ,​ 9
F 6
G 8 ​, 2

b)Dijkstra’salgorithmfoundthewrongpathtosomeofthevertices.Forjustthevertices
wherethewrongpathwascomputed,indicateboththepaththatwascomputedandthe
correct path. ​[3 marks]


A->D
A->F

Any one correct 1.5 marks

18. Both Correct 3 marks
Mentioned any wrong one with D and F 2.5 marks


c)WhatsingleedgecouldberemovedfromthegraphsuchthatDijkstra’salgorithmwould
happen to compute correct answers for all vertices in the remaining graph.

Solution:


c) The edge E to G

Question30:-DelhiTrafficPolicehasmadeallroadsoneway.TheCMclaimsthatthereisstilla
legalwaytodrivefromonepointofthecitytoanother.Theoppositionisnotconvincedandargues
theCM’sclaimtobefalse.Formulatethisproblemasagraphproblemandgivealineartime
algorithm to check the validity of the claim. Explain the time complexity of your algorithm.

Answer:-Thisproblemcouldberepresentedasadirectedgraphwiththeverticesasthepointsin
thecityandedgefrompointAtoBrepresentingtheonewayroadindirectionfromAtoB.Thetask
istocheckifforallpairsofverticesthereexistsapathornot.ThisisclearlyaproblemonSCC.If
the entire road network(the graph) is one SCC then the CM’s claim is true, else false.

Algorithm1.
ComputefinishingtimeforeveryvertexbycallingDFSongraph.Storetheseverticesin
decreasing order of their finishing time in a List L.
2. Reverse the direction of every edge to get a graph G’
3.RunDFSonG’,selectingverticesasstoredinorderinListL.Maintainacounter(initializedto0)
and for a depth first tree obtained from every white vertex, increment the counter by 1.
4. If after step 3, counter =1 => CM’s claim is true, else false

TimeComplexity:O(V+E)asDFShastimecomplexityofO(V+E)step1andstep3takeO(V+E),
step2isO(E),step4isO(1).Notethatthisislineartimeintermsofsizeofgraph(includingthe
edges and vertices)

Question31:-Assumethistreeisabinarysearchtreeeventhoughyoucannotseewhatthekeys
andvaluesareatthenodes(theletterswewritebelowarejust“names”forthenodesforthe
purpose of answering the questions).

19. (a) What node is the successor of node A?
(b) What node is the successor of node B?
(c) What node is the successor of node C?
(d) What is the height of the tree?
(e)Whatisthemaximumnumberofnodesthatcouldbeaddedtothetreewithoutincreasingits
height?
(f) Is the tree an AVL tree?
(g) If we remove only node H, is the result an AVL tree?
(h) If we remove only node J, is the result an AVL tree?
(i) If we remove only node K, is the result an AVL tree?

Answer:-(a) J
(b) E
(c) K
(d) 4
(e) 18
(f) yes
(g) yes
(h) no
(i) no

Question32:-Supposethereisabinarymin-heapwithexactly4nodes,containingitemswith
priorities 3, 9, 11, and 15.
(a)Showeverypossiblebinarymin-heapthatcouldmatchthisdescription.Foreach,drawthe
appropriatetreeandthearrayrepresentation.(Youcanshowjustthepriorities,notthe
corresponding items.)
(b)Foroneofyouranswerstopart(a),showwhathappenswith4deleteMinoperations.Clearly
indicatewhichheapyouarestartingwithandshowtheheapaftereachdeleteMin.Youcanjust
draw the tree (not the array) after each step.

Solution:

20. Explanation:All4-nodeheapsmusthavetheshapeofthe3heapsinpart(a).Theminimumnode,
3,mustbeattheroot.Themaximumnode,15,mustbeataleaf.Theonlyheapmeetingthese
rules and not listed above does not satisfy the heap property because 11 is above 9:

Question 33:-