Graphic Era Hill University, Dehradun Campus

Department of CSE

TCS302: Data Structures using C

Assignment 2
Last date of submission: 05.12.2023
1. Explain various types of linked lists and their uses.
2. Write an algorithm to merge two sorted arrays into a third array. Do not sort
the third array.
3. Write functions in C for Linked List (Insertion and Deletion) operations.
4. What data structure would you mostly likely see in a non recursive
implementation of a recursive algorithm?
5. List out the areas in which data structures are applied extensively?
6. If you are using C language to implement the heterogeneous linked list, what
pointer type will you use?
7. What is the data structures used to perform recursion?
8. What are the disadvantages array implementations of linked list?
9. Whether Linked List is linear or Non-linear data structure? Justify your
answer.
10. What is the difference between a grounded header link list and a circular
header link list?
11. How do you find the complexity of an algorithm? What is the relation
between the time and space complexities of an algorithm? Justify your
answer with an example.
12. Compare two functions n2 and 4n for various values of n. Determine when
second becomes larger than first.
13. Explain an efficient way of storing a sparse matrix in memory. Write a
module to find the transpose of a sparse matrix stored in this way.
14. Evaluate postfix expression 6 2 3 + - 3 8 2 / + * 2 3 +
15. List out the types of collision resolution techniques in hashing.
16. Which data structure is needed to convert infix notations to post fix
notations?
17. Parenthesis are never needed in prefix or postfix expressions. Why?
18. What is the minimum number of queues needed to implement the priority
queue?
19. What are the methods available in storing sequential files?
20. Write an algorithm for finding solution to the Tower’s of Hanoi problem.
Explain the working of your algorithm (with 4 disks) with diagrams.
21. Convert the following infix expressions into its equivalent postfix
expressions.

(i) (A+B-C)/E –(F+G)

(ii) A*(B(D/ E –(F*G) +H)* K)

22. Execute your algorithm to convert an infix expression to a postfix expression

with the following infix expression as input A+B-C/D*E*F*G/H
23. Given a set of input representing the nodes of a binary tree, write a non
recursive algorithm that must be able to output the three traversal orders.
24. What is a Binary Search Tree (BST)? Make a BST for the following
sequence of numbers: 45, 36, 76, 23, 89, 115, 98, 39, 41, 56, 69, 48
25. Traverse the following binary tree in Preorder, In-order and post-order.

26. Apply Prim’s and Kruskal’s algorithms to find the minimum spanning tree
of the following graph.
27. What is the maximum number of nodes in an M-ary tree that has N levels?
Note that the root is level (zero).
28. Write a Binary Search algorithm assuming the data are stored in a binary
search tree.
29. Why rotation of nodes in a Binary search Tree is required? Explain right and
left rotations with the help of an example.
30. How many different binary trees and binary search trees can be constructed
from four nodes that contain the key values 1, 2 3 and 4?
31. Construct a binary tree whose nodes in in-order and preorder are given as
follows:
In-order: 10, 15, 17, 18, 20, 25, 30, 35, 38, 40, 50 and
Preorder: 20, 15, 10, 18, 17, 30, 25, 40, 35, 38, 50
32. Construct a BST for the following sequence of numbers.
32,90,34,68,72,15,24,30,66,11,50,10.
33. Construct a complete binary tree with depth 3 for this tree which is
maintained in memory using linked representation. Make the adjacency list
and adjacency matrix for this tree.
34. Construct the binary tree for the following sequence of nodes in preorder
and in-order respectively.
Preorder : G, B, Q, A, C, K, F, P, D, E, R, H
In-order: Q, B, K, C, F, A, G, P, E, D, H, R
35. What is a height balanced tree? Explain how the height is balanced after
addition/deletion of nodes in it?
36. What are the different ways of representing a graph? Represent the
following graph using those ways.
37. Write an algorithm which does depth first search through a non-weighted
connected graph.
38. Write an algorithm to sort a given list using Quick sort method. Describe the
behavior of Quick sort when input is already sorted.
39. Sort the following list using Heap Sort 66, 33, 40, 20, 50, 88, 60, 11, 77, 30,
45, 65.
40. Explain various graph traversal schemes and write their merits and demerits.
41. Which sorting algorithm is easily adaptable to singly linked lists? Explain
your answer.
42. Bubble sort algorithm is inefficient because it continues execution even after
an array is sorted by performing unnecessary comparisons. Therefore, the
number of comparisons in the best and worst cases are the same. Modify the
algorithm in such a fashion that it will not make the next pass when the array
is already sorted.
43. What are B-trees? Construct a B-Tree of order 3 for the following set of
input data: 69, 19, 43, 16, 25, 40, 132, 100, 145, 7, 15, 18.
44. Draw the 11 item hash table resulting from hashing the keys: 12, 44, 13, 88,
23, 94, 11, 39, 20, 16 and 5 using the hash function h(i) = (2i+5) mod 11.
45. Sort the following list using Heap Sort technique, displaying each step. 20,
12, 25 6, 10, 15, 13.
46. Show the result of inserting the keys. F, S, Q, K, C, L, H, T, V, W, M, R, N ,
P, A, B, X, Y, D, Z, E in the order to an empty B-tree of degree-3.
47. Sort the following sequence of keys using merge sort. 66, 77, 11, 88, 99, 22,
33, 44, 55
48. Draw a B-tree of order 3 for the following sequence of keys: 2, 4, 9, 8, 7, 6,
3, 1, 5, 10
49. Create a max-heap with following list of keys: 8, 20, 9, 4, 15, 10, 7, 22, 3,
12.
50. The following values are to be stored in a hash table: 25, 42, 96, 101, 102,
162, 197. Describe how the values are hashed by using division method of
hashing with a table size of 7. Use chaining as the method of collision
resolution.

+++++++++++++++++