Exercises
1. Define tree.
2. What are the ways to represent Binary trees in memory?
3. Define binary tree.
4. List out few of the Application of tree data-structure?
5. Define expression tree
6. What is a binary search tree?
7. How will you construct binary search tree?
8. What are the non-linear data structures?
9. Write the algorithms for PUSH, POP and change operations on stack. Using these
algorithms, how do you check whether the given string is a palindrome?
10. Evaluate the postfix expression that is obtained in (i) for the values A = 5, B =3, C= 2,
D= 2, E = 4, F = 3, G = 8, H=6
11. Write the algorithm for performing operations in a stack. Trace your algorithm with
suitable example
12. Write the algorithm for converting infix expression to postfix expression with the
suitable example
13. Write the algorithm for evaluating the postfix expression with the suitable example
14. Explain the algorithm for implementing Singly Linked list
15. Write C program to implement a stack using doubly linked lists
16. Write a C program to construct a dequeue data structure in which the following
operations are to be implemented
i. Push(X,D) : Insert X on the front end of deque D ii. Pop(D) :
Remove the front item from deque D and return it iii.
Inject(X,D) : Insert item X on the rear end of deque D iv.
Eject(D) : Remove the rear item from deque D and return it
17. Explain Circular queue operations with algorithm
18. Write an algorithm to find a node in a tree. Show the resulting binary search tree if the
elements are added into it in the following order:
50, 20, 55, 80, 53, 30, 60, 25, 5, …
19. Construct a binary tree given the preorder and in order sequences as below
preorder: A B D G C E H I F, Inorder : D G B A H E I C F
20. What is the representation of binary tree in memory? Explain in detail.
21. Define expression tree. How to construct an expression tree for the post fix expression?
Write steps involved in constructing expression tree.
22. Describe in detail about merge sort with an example
23. What do you meant by Quick Sort? Explain
24. Describe in detail about binary search with an example
25. Consider the following queue of characters, where QUEUE is a circular array which is
allocated six memory cells:
FRONT = 2, REAR = 4 QUEUE: _____, A, C, D, _____, _____ Describe the queue as the
following operations take place:
(i) F is added to the queue. (vi) two letters are deleted.
(ii) two letters are deleted. (vii) S is added to the queue.
(iii) K, L and M are added to the queue. (viii) two letters are deleted.
(iv) two letters are deleted. (ix) one letter is deleted. (v) R is added to
the queue. (x) one letter is deleted.
26 A stack contains the elements [A, C, D, E, F, -, -, -] with the top element being 'I'. Perform a
POP operation and determine:
i. The removed element
ii. The resulting stack
iii. The new top element
27. A stack contains the elements [A, C, D, E, F, -, -, -]. Perform a PUSH operation with the
element 'L' and determine:
i. The resulting stack
ii. The new top element
28. A stack contains the elements [A, C, D, E, F, I, -, -]. Perform the following operations:
1. POP
2. PUSH 'L'
Determine:
i. The removed element
ii. The final stack
iii. The final top element