Sal College of Engineering
CE, IT, CSE & ICT Department
Data Structure (3130702)
Assignment-1
1) What do you mean by Data Structure? Give the difference between Primitive and Non-primitive
data structures.
2) Give the classification of data structure. Explain linear and non-linear data structure with
example.
3) What is Algorithm? What is Time Complexity and Space Complexity? Write short note on
performance analysis and performance measurement of an algorithm.
4) Explain asymptotic notations with example. Define Time complexity and Space complexity.
Calculate time complexity for given expression.
for (k=0; k<n; k++)
{
rows[k] = 0; for(j=0; j<n; j++)
{
rows[k] = rows[k] + matrix[k][j];
total = total + matrix[k][j];
}
}
5) What is Array? Explain Multidimensional Array. How it is stored in memory?
6) What is sparse matrix? Explain memory representation of sparse matrix.
7) Solve following problems:
I. Given a two dimensional array Z1(2:9, 9:18) stored in column
Major order with base address 100 and size of each element is 4 bytes, find
address of the element Z1(4, 12).
II. Consider array int a[3][4] declared in C program. if the base address is 1050 find the
address of the element a[3][2] with row major & column major representation.
8) Explain Different between Sparse and Dense Matrix?
Assignment-2
1) What is recursion? Explain Tower of Hanoi Problem with algorithm
2) What is Stack? Write down algorithms for performing PUSH, POP, CHANGE and PEEP
operations on a stack. List out the applications of the stack?
3) Write an algorithm to convert infix expression into postfix expression with parenthesis and
write an algorithm to convert infix to prefix expression and explain it with example.
4) Solve following problems:
I. Translate the following string into polish notation and trace the content of stack
A - (B / C + (D % E * F) / G ) * H
II. Evaluate the following postfix expression using stack
AB+CD/*GH*+ ((where A=2,B=4,C=6,D=3,G=8,H=7)
III. Convert following Infix expression into Postfix expression. Show each step.
A + B ^ C^ D - E * F / G
IV. Evaluate following prefix expression.
+*AB-C+C*BA (A= 4, B=8,C=12)
5) What is Queue? Write an algorithm to implement insert and delete operation into a Simple
Queue using array representation of Queue.
6) Write an algorithm for circular queue that insert an element at rear end.
7) Explain types of Queue? Compare Simple Queue and Circular Queue. Write an algorithm to
implement insert and delete operation into a Double Ended Queue using array representation
of Queue.
8) Differentiate between stack & queue. Also explain priority queue.
Assignment-3
1) What is the purpose of nonlinear data structures?
2) Given the following Traversal, create a binary tree from that.
Post order: H I D E B F G C A
Pre Order: H D I B E A F C G
3) Define following terms:
i. Sibling
ii. Ancestor
iii. Descendants
iv. Leaf node
v. Height of tree
vi. Binary tree
vii. Strict binary tree
viii. Full binary tree
ix. Complete binary tree.
x. Threaded binary tree.
4) Explain Binary Tree Traversal Operations? And Construct Binary search Tree From Following
Elements 50, 80, 60, 40, 90, 20, 10, 30, 70
5) Explain How to convert Binary tree from General Tree.
6) Explain Linear Search and Binary search technique with Example
Assignment-4
1) What is meant by Bubble sort? Sort the Following list of numbers using
Bubble sort technique.52,1,27,85,66,23,13,57
2) Explain Quick sort with appropriate example along with time complexity.
3) Explain Selection sort with appropriate example.
4) Explain Meagre sort with appropriate example.
5) What is time complexity of insertion sort?
6) What is the Time Complexity of Selection sort, bubble sort.
7) What is do you mean by Sorting and Searching? Explain in detail along with appropriate
examples.
