As Per the University Syllabus
Subject Name (Code): Data Structure using C ( NCS-301)
Assignment 1
Q1. Implement a data structure that supports the following operations insert, findMin,
findMax, deleteMin, deleteMax, is Empty, makeEmpty.
You must use the following algorithm:
Maintain a sorted array.
Insert new items into the correct position in the array, sliding elements over one
position to the right, as needed.
findMin and findMax, and deleteMax are trivial.
For deleteMin remove the item in position 0, and slide over all the other items one
position to the left.
The program should display the following menu:
Welcome!
Press 1 to insert a new item
Press 2 to find minimum Element
Press 3 to find maximum Element
Press 4 to delete minimum Element
Press 5 to delete maximum Element
Press 6 to determine whether the array is empty or not.
Press 7 to empty the array.
Press 9 to quit
OBJECTIVE
To make students understand representation, implementation and Basic operations
that can be performed on Arrays.
OUTCOME
Student would be able to understand and use Arrays.
Student will get more practice on defining and manipulating arrays.
Mapping of CO, PO and PSO with the Questions:
Q1
CO 1,2
PO 1,2,3,4,12
PSO 1,2,4
Assignment 2
Q1. Evaluate the following postfix expression using a stack and show the contents of stack
after execution of each operation:
50, 40, +, 18, 14,-, *, +
Q2. Write a procedure to implement a circular queue.
Q3. Covert the given expression into prefix using stack.
(a+b)+c ↑ (d+e)+f ↑ (g+h)
OBJECTIVE
To make students understand representation, implementation and Basic operations
that can be performed on Stacks.
To make students understand the differences between the various tree Data Structures.
OUTCOME
Student would be able to understand and use Stacks and Queue.
Student will get more practice on the operations that can be performed on Stack.
Mapping of CO, PO and PSO with the Questions:
Q1 Q2 Q3
CO 4 4 4
PO 1,2,3,4,12 1,2,3,4,12 1,2,3,4,12
PSO 1,2,4 1,2,4 1,2,4
Assignment 3
Q1. Construct an AVL search tree by inserting the following elements in the order of their
occurrence. 64, 1, 44 , 26, 13, 110, 98, 85.
Q2. Draw a binary tree T with given the inorder and postorder traversal
Inorder: D K I B A E G H J F C
Post order: K D I E A G B F C J H
Q3. Suppose characters a, b, c, d, e, f have probabilities 0.07, 0.09, 0.12, 0.22, 0.23, 0.27
respectively. Find an optimal Huffman code and draw the Huffman tree
OBJECTIVE
To make students understand the differences between the various tree Data Structures.
OUTCOME
To understand the concept of tree traversing, Height Balance tree and data
compression.
Mapping of CO, PO and PSO with the Questions:
Q1 Q2 Q3
CO 4 4 4
PO 1,2,3,4,12 1,2,3,4,12 1,2,3,4,12
PSO 1,2,4 1,2,4 1,2,4
Assignment 4
Q1. Find Minimum spanning tree using Kruskal’s Algorithm of given graph.
Q2. Trace the DFS, BFS on the following graph
OBJECTIVE
To get more practice on Linked Lists and Graphs.
OUTCOME
Students get a hand on Practice on Linked List & Graph, BFS and DFS.
Mapping of CO, PO and PSO with the Questions:
Q1 Q2
CO 5 5
PO 1,2,3,4,12 1,2,3,4,12
PSO 1,2,4 1,2,4
Assignment 5
Q 1. Translate insertion sort into a subprogram INSERTCOUNT (A, N, NUMB) which
sorts the array A with N elements and which also counts the number NUMB of
comparisons.
Q 2. Suppose an array contains N elements. Given a number X that may occur several
times in the array. Find
a. The number of occurrence of X in the array.
b. The position of first occurrence of X in the array.
OBJECTIVE
To enable the students to learn the various sorting and searching algorithms and their
concepts.
OUTCOME
The students will get a clear idea on some sorting techniques.
Students will get more practice on the looping concepts.
Mapping of CO, PO and PSO with the Questions:
Q1 Q2
CO 2,6 2,6
PO 1,2,3,4,12 1,2,3,4,12
PSO 1,2,4 1,2,4
Assignment 6
Q1. Given input(4371, 1323, 6173, 4199, 4344, 9679,1989} and a Hash function h(X)=
X(mod 10). Show the resulting :
a. Open Addressing Hash Table using Linear Probing.
b. Open Addressing Hash Table using Quadratic Probing.
c. Open Addressing Hash table with second hash function h2(X)=7-(X mod 7).
Q2. Construct a BTree of order 3 for the following set of input data
69,19,43,16,25,40,132,100,145,7,15,18 and delete 69,15
OBJECTIVE
Understand the concept of trees and the operations that can be performed on trees.
Understand the concept of Hashing and probing
OUTCOME
Students get a clear concept of the trees and their operations.
Get a clear idea of the Hashing & Collision Resolution techniques.
Mapping of CO, PO and PSO with the Questions:
Q1
CO 4,7
PO 1,2,3,4,12
PSO 1,2,4
