CS3301-DATA STRUCTURES

UNIT-I
PART-A

1. What is called as a Data Structure?

A Data Structure defines a way of representing or organizing all data that contains both
the data items and their relationship with each other.

2. Give examples of Linear and Non-Linear Data Structures.

• Linear Data Structures
i) Linked Lists(Singly & Doubly Linked Lists)
ii) Circular Linked Lists(Circular-singly&Circular-doubly
Linked Lists).
• Non-Linear Data Structures
i) Trees
ii) Graphs.

3. What do you mean by Abstract Data Types?

Classes encapsulate all the essential properties of the objects that are to be created.
Since the classes use the concept of data abstraction, they are known as Abstract Data Types
(ADT).
4. Give some applications of stack.
• Evaluation of Expressions.
• Expression conversion.
• Balancing of symbols.
Function Calls.

5. Define Dequeue.
A dequeue is an ordered list in which additions and deletions may be carried out at either end.

6. State the difference between array and linked list.

Array Linked List

Contiguous memory location Memory location need not be
necessarilycontiguous
Operations such as insertion and deletion Insertion and deletions are easier and
are ineffective since the memory locations needsonly one pointer assignment.
need to be moved up and down
respectively.
Inefficient use of memory space. A small amount of memory is been wasted
for storing a pointer, which is been
associated with each node.
7. What are the advantages and disadvantages of linked list?
Advantages:
a. Memory location for a linked list is dynamic, that is memory allocation is done during run
time. So memory will not be wasted.
b. Data movements during insertion and deletion will be eliminated. So time will not be wasted.
c. Memory allocation for each node of a linked list need not be continuous.

Disadvantages:
d. Nodes of a linked list cannot be accessed directly. To access a particular node accessing
should start only from the beginning.
e. To store a single data, along with data, memory must be allocated for a pointer also, which
wastes memory.
8. Define Singly Linked List.
A singly linked list is a list structure in which each node contains a single pointer field
that points to the next node in the list, along with a data field.

9. Define Doubly Linked List.

A doubly linked list is a list structure in which each node contains two pointer fields
along with a data field namely,
BLINK – Points to the previous node in the list
FLINK – Points to the successive node in the list

PART-B
1. Develop an algorithm for operations in a singly linked list.
2. Describe in detail about Polynomial manipulation in linked list.
3. Examine the algorithms to implement the doubly linked list and perform all the
operations on the created list.
4. Develop an algorithm for operations in a circularly linked list.
 UNIT- 2
PART-A

1. Define stack?
Stack is an ordered collection of items into which new items may be inserted and from
which items may be deleted at one end, called the top of stack.

2. Define Circular Queue.

In array based implementation of queue, inefficiency arises only when the value of the rear
pointer exceeds maximum size during insertion. This can be rectified if we logically consider the
queue to be circular.
In circular queue, once the rear pointer reaches the maximum size, the next location I the first
one (index 0), provided the first location is vacant. The specific location is calculated by mod (%)
operator.
3. Convert the infix (a+b)*(c+d)/f into postfix & prefix expression
Postfix : ab+cd+* f/
4. DistiPnrgeufiixsh betwee:n/ s*ta+cak ban
+dcqdufeue.
STACK QUEUE
Insertion and deletion are made at one end. Insertion at one end rear and deletion at
other end front.
The element inserted last would be The element inserted first would be
removed first. So LIFO structure. removed first. So FIFO structure.
Full stack condition: Full stack condition:
If(top==Maxsize) If(rear = = Maxsize)
Physically and Logically full stack Logically full. Physically may or may not
be full.

5. Define Dequeue.
A dequeue is an ordered list in which additions and deletions may be carried out at either end.

6. What are the limitations in the stack, when array used as home of stack?
The Array is finite collection of elements and in stack the number of elements is
unlimited. As the stack dynamically changes the attempts to insert more elements than the
array size cause overflow

7. Why infix expression should be converted to Prefix / Postfix?

In Infix, operator precedence can be set only after scanning the expression for several
times. But, conversion of Infix to Postfix or Prefix with use of stack, help to set precedence
based on order of arrangement in a single scanning

8. Define Queue?
A queue is an ordered collection of items from which items may be inserted at one end
called rear end and into which items may be deleted at the other end called the front end.

9. Define Priority Queue?

Priority queue is a data structure in which the intrinsic ordering of the elements
determines the results of the basic operations like insertion and removal.

10. What are the two types of priority queues? Briefly

explain?Two types of priority queues are,
i) Ascending priority queue – In this queue, the items can be inserted arbitrarily
and only the smallest item will be removed.
ii) Descending priority queue- This allows insertion of items arbitrarily, and only
the maximum element from queue will be removed first.

11. What is the difference between queue and priority queue?

In queue the elements can be inserted only at rear end and can be removed only at front
end. But in priority queue, elements can be arbitrarily inserted. But the complete queue is
searched for removal of high priority element.

PART-B

1. Describe about stack ADT using array in detail.

2. i)Give an algorithm for push and pop operations on stack using a linked list with an
example.
3. i)Discuss the process of evaluating postfix expression with an example.
4. Briefly describe the operations of queue with example.

UNIT-III
PART-A
1. Define Tree.
A Tree is a collection of one or more nodes with a distinct node called the root , while
remaining nodes are partitioned as T1 ,T2, ..,Tk , K≥ 0 each of which are sub trees, the edges of
T1,T2,…,Tk are connected the root.

2. Give some applications of Trees.

1. Implementing the file system of several operating systems.
2. Evaluation of arithmetic expression.
Set representation.
Gaming/Decision making problems.
3. Define node, degree, siblings, depth/height, level.
Node: A node is an item of information with branches to other items.
Degree: The number of subtrees of a node is called is degree.
Siblings: The children of the same parent is said to be siblings.
Level: The level of a node is defined recursively by assuming the level of the root to be one
and if a node is at level l, then its children at level l+1.
 Depth/Height: The depth/height of a tree is defined to be the level of a node which is
maximum.
4. Define a path in a tree.
A path in a tree is a sequence of distinct nodes in which successive nodes are connected
by edges in the tree.
5. Define a Binary Tree.
A Binary Tree is a tree,which has nodes either empty or not more than two child
nodes,each of which may be a leaf node.
6. Define a full binary tree.
A full binary tree,is a tree in which all the leaves are on the same level and every non-leaf
node has exactly two children.
7. Define a complete binary tree.
A complete binary tree is a tree in which every non-leaf node has exactly two children
not necessarily to be on the same level.
1. Maximum No. of nodes on level n of a binary tree is 2^(n-1),where n>=1.
2. Maximum No. of nodes in a Binary tree of height is 2^(n-1),where n>=1.
3. For any non-empty tree,nl=nd+1 where nl is the number of leaf nodes and nd is the no. of
nodes of degree 2.
8. Define Traversal.
Traversal is an operation which can be performed on a binary tree is visiting all the
nodes exactly once.
Inorder: traversing the LST, visiting the root and finally traversing the RST.
Preorder: visiting root, traversing LST and finally traversing RST.
Post- order: traversing LST, then RST and finally visiting root.
9. Define a Binary Search Tree.
A Binary Search Tree is a special binary tree,which is either empty or if it is
empty it should satisfy the conditions given below:
1. Every node has a value and no two nodes should have the same value(Values should be
distinct).

The value in any left subtree is less than the value of its parent node.
The value in any right subtree is greater than the value of its parent node.
10.Define balanced search tree.
Balanced search tree have the structure of binary tree and obey binary search tree properties
with that it always maintains the height as O(log n) by means of a special kind of rotations. Eg.
AVL, Splay, B-tree.

11. Define AVL tree.

An empty tree is height balanced. If T is a non-empty binary tree with TL and TR as
Its left and right subtrees, then T is height balanced if
1. TL and TR are height balanced.
2. | hL - hR | ≤ 1.
Where hl and hr are the height of TL and TR respectively.
12. What is a heap?
A heap is a partially ordered data structure, and can be defined as a binary tree
assigned to its nodes, one key per node, provided the following two conditions
are met
❖ The tree’s shape requirement-The binary tree is essentially complete, that is all the
leaves are full except possibly the last level, where only some rightmost leaveswill
be missing.
❖ The parental dominance requirement-The key at each node is greater that or equal
to the keys of its children

13.What is a min-heap?
A min-heap is a mirror image of the heap structure. It is a complete binary tree in which
every element is less than or equal to its children. So the root of the min-heap contains the
smallest element.A B-tree of order m in an m-way search tree that is either empty or is of height
≥1 and

1. The root node has at least 2 children

2. All nodes other than the root node and failure nodes have at least m/2 children.

3. All failure nodes are at same level.

14.Define Binary Heap?

A Binary Heap is a complete binary tree in which the key value of any node must be
lesser than its children is called min heap. If the key value of any node is greater than its children
is called max heap.Binary heap is also called as partially ordered tree.

15.Explain AVL rotation.

Manipulation of tree pointers is centered at the pivot node to bring the tree back into height
balance. The visual effect of this pointer manipulation so to rotate the sub tree whose root is the
pivot node. This operation is referred as AVL rotation.

PART-B

1. Write an algorithm for preorder, inorder and postorder traversal of a binary tree.
2. Write an algorithm for inserting and deleting a node in a binary search tree.
3. Construct B Tree of order m=5 for the following keys
1,12,8,2,25,5,14,28,17,7,52,16,48,68,3,26,29,53,55,45.Delete the keys 8 and 55.State
therules for deletion.
4. Discuss how to insert an element in a AVL tree and explain with algorithm.
5. Write suitable operations for percolate up and percolate down operations in a binary heap.
 UNIT - 4

PART-A

1. Define Graph.
A Graph G, consists of a set of vertices V, and a set of edges E.V is a finite non-empty set
consisting of vertices of vertices of the graph. The set of edges E consists of a pair of vertices
from the vertex set.

2. Define a weighted graph.

A graph is said to be weighted graph if every edge in the graph is assigned some weight or
value.The weight of an edge is a positive value that may be representing the distance between the
vertices or the weights of the edges along the path.

3. Define undirected graph / directed graph.

If G=(V, E) is a graph. The edge between v1and v2is represented as (v1, v2). If the edges of the
form (v1, v2) and (v2, v1) are treated as the same edge, then G is said to be an undirected graph.
In case of a directed graph, the edge <v1, v2>and <v2, v1>are different.
4. List out the graph traversals of graph search?
The two methods of traversal is,
-Depth First Search (DFS)
-Breadth First Search (BFS)

5. Define Shortest path problem?

For a given graph G=(V, E), with weights assigned to the edges of G, we have to find the
shortest path (path length is defined as sum of the weights of the edges) from any given source
vertex to all the remaining vertices of G.
6. Define minimum cost spanning tree?
A spanning tree of a connected graph G, is a tree consisting of edges and all the vertices of
G.
In minimum spanning tree T, for a given graph G, the total weights of the edges of the
spanning tree must be minimum compared to all other spanning trees generated from G.
-Prim’s and Kruskal is the algorithm for finding Minimum Cost Spanning Tree.
7. What is the use of Kruskal’s algorithm and who discovered it?
Kruskal’s algorithm is one of the greedy techniques to solve the minimum spanning
tree problem. It was discovered by Joseph Kruskal when he was a second-year graduate student.

8. Define Shortest path problem?

For a given graph G=(V, E), with weights assigned to the edges of G, we have to find the
shortest path (path length is defined as sum of the weights of the edges) from any given source
vertex to all the remaining vertices of G.

9. What is the use of Dijksra’s algorithm?

Dijkstra’s algorithm is used to solve the single-source shortest-paths problem: for a
given vertex called the source in a weighted connected graph, find the shortest path to all
its other vertices. The single-source shortest-paths problem asks for a family of paths, each
leading from the source to a different vertex in the graph, though some paths may have edges in
common.
 PART-B

1. Discuss in detail about depth-first search and breadth-first search traversal of a graph with suitable
examples.
2. Discuss any two applications of Graph with example.

3. Discuss how to find Euler circuit with an example.

4. Explain in detail about Dijikrtas and kruskals algorithm

UNIT-V

PART-A

1. Define sorting
Sorting arranges the numerical and alphabetical data present in a list in a specific order
or sequence. There are a number of sorting techniques available. The algorithms can be
chosen based on the following factors
– Size of the data structure
– Algorithm efficiency
– Programmer’s knowledge of the technique.

2. What do you mean by internal and external sorting?

An internal sort is any data sorting process that takes place entirely within the main
memory of a computer. This is possible whenever the data to be sorted is small enough
to all be held in the main memory.
External sorting is a term for a class of sorting algorithms that can handle massive
amounts of data. External sorting is required when the data being sorted do not fit into the
main memory of a computing device (usually RAM) and instead they must reside in the
slower external memory (usually a hard drive)

3. Define bubble sort

Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the
list to be sorted, comparing each pair of adjacent items and swapping them if they are in
the wrong order. The pass through the list is repeated until no swaps are needed, which
indicates that the list is sorted. The algorithm gets its name from the way smaller
elements "bubble" to the top of the list.
4. What is meant by shell sort?
Shell sort, also known as Shell sort or Shell's method, is an in-place comparison sort. It
can either be seen as a generalization of sorting by exchange (bubble sort) or sorting
 by insertion (insertion sort).[1] The method starts by sorting elements far apart from
each other and progressively reducing the gap between them. Starting with far apart
elements can move some out-of-place elements into position faster than a simple
nearest neighbor exchange. Donald Shell published the first version of this sort in
1959. The running time of Shell sort is heavily dependent on the gap sequence it uses

5. What are the steps in quick sort?

The steps are:
a. Pick an element, called a pivot, from the list.
b. Reorder the list so that all elements with values less than the pivot come before
the pivot, while all elements with values greater than the pivot come after it
(equal values can go either way). After this partitioning, the pivot is in its final
position. This is called the partition operation.
c. Recursively apply the above steps to the sub-list of elements with smaller values
and separately to the sub-list of elements with greater values.

6. Define radix sort

Radix Sort is a clever and intuitive little sorting algorithm. Radix sort is a non-
comparative integer sorting algorithm that sorts data with integer keys by grouping
keys by the individual digits which share the same significant position and value. Radix
Sort puts the elements in order by comparing the digits of the numbers.
7. Define searching
Searching refers to determining whether an element is present in a given list of
elements or not. If the element is present, the search is considered as successful, otherwise it
is considered as an unsuccessful search. The choice of a searching technique is based on the
following factors
a. Order of elements in the list i.e., random or sorted
b. Size of the list
types of searching
The types are
x Linear search
x Binary search

8. What is meant by linear search?

Linear search or sequential search is a method for finding a particular value in a list
that consists of checking every one of its elements, one at a time and in sequence, until
the desired one is found.

9. What is binary search?

For binary search, the array should be arranged in ascending or descending order.
In each step, the algorithm compares the search key value with the middle element of
 the array. If the key match, then a matching element has been found and its index, or
position, is returned.
Otherwise, if the search key is less than the middle element, then the algorithm repeats its
action on the sub-array to the left of the middle element or, if the search key is greater,on
the sub-array to the right.

10. Define hashing function

A hashing function is a key-to-transformation, which acts upon a given key to compute
the relative position of the key in an array.
A simple hash function
HASH(KEY_Value)= (KEY_Value)mod(Table-size)

11. What is open addressing?

Open addressing is also called closed hashing, which is an alternative to resolve the
collisions with linked lists. In this hashing system, if a collision occurs, alternative cells
are tired until an empty cell is found.
There are three strategies in open addressing:
x Linear probing
x Quadratic probing
x Double hashing

12. What are the collision resolution methods?

The following are the collision resolution methods
x Separate chaining
x Open addressing
x Multiple hashing

13. Define separate chaining

It is an open hashing technique. A pointer field is added to each record location,
when an overflow occurs, this pointer is set to point to overflow blocks making a
linked list.
In this method, the table can never overflow, since the linked lists are only extended
upon the arrival of new keys.
14.Explain Hashing .
Hashing is a technique used to identify the location of an identifier ‘x’ in the
memory bysome arithmetic functions like f(x), which gives address of ‘x’ in the table.
 PART-B
1. Describe about selection sort with suitable example.
2. Examine the algorithm for Insertion sort and sort the following array: 77, 33,
44, 11, 88, 22, 66, 55
3. List the different types of hashing techniques? Explain them in detail with
example.
4. Write a C program to search a number with the given set of numbers using
binary search.
5. Interpret an algorithm to sort a set of ‘N’ numbers using bubble sort and
demonstrate the sorting steps for the following set of numbers:
88,11,22,44,66,99,32,67,54,10.
6. Formulate the rehashing technique with suitable example.