DATA STRUCTURES

Unit - I
1.Define an Algorithm.
It is a step by step procedure, which is designed to handle a specific
problem.
2.Define Data Structures.
A way of organizing, storing and retrieving data and their relationship with
each other.
3.List out the applications of Data Structures.
Operating systems
Compiler design
DBMS
Network Analysis
Expert Systems
4.Write the classification of Data Structure.
Data structure
Primitive data structure Non - Primitive Data
structure
Int float char pointer Linear Non Linear
Stack array linked list Queue Trees Graphs
5.List out the problem solving strategies.
Divide & conquer
Dynamic programming
Greedy Technique
Back tracking
Branch & bound techniques
6.Define the Top - down design strategy.
Other name is called step wise refinement. It is a strategy that can apply
to the problem, into the small subtasks. It allows us to build our solutions to a
problem in a stepwise fashion.
7.What is meant by problem solving?
It is a creative process which largely defines systematization and
mechanization.
8.What are the various aspects of the problem solving strategies?
Problem definition phase
Getting started on a problem
Use of specific examples
Simulation among problems
Working backwards from the solution
General problem solving strategies.
9.Write an algorithm to find the factorial of a given number.
Fact(n)
F=1;
For(i=1;i<=n;i++)
F=f*I;
Return f;
10.What is program testing?
Testing is to test whether or not a program will handle all cases of problem
to solve.
11.What is program verification?
To verify whether the program works correctly or not.
12.What are the various phases in the program verification?
Input & output assertion
Computer model for program execution
Implications and symbolic executions
Verification of straight line program segments
Verification of program segments with branches
Verification of program segments with loops
Verification of program segments that employ array
Proof of termination
13.Define Time complexity & Space Complexity.
Time complexity It is the amount of time it needs to � run the algorithm
Space complexity � It is the amount of memory it needs to run the algorithm.
14.Write a note on Asymptotic notation.
It is used to estimate and represent the efficient of an algorithm.
Complexity of an algorithm is usually represented O,o,?,? notations.
15.What is Big O Notation?
It is used to define the worst case running time of an algorithm and
concerned with very large values of N.
T(N) =O(f(N) if +ve constants C and n0 such that T(N) <=Cf(N) when N>=n0
16.What is Big ? Notation?
It is used to describe the best case running time of an algorithm and
concerned with very large values of N.
T(N) =?(f(N) if +ve constants C and n0 such that T(N) >=Cf(N) when N>=n0
17.What is Big ? Notation?
It is used to describe the average case running time of an algorithm and
concerned with very large values of N.
T(N) =?(f(N) if +ve constants C1,C2 and n0 such that T(N) =O(F(N)) and
T(N)=?(F(N)) for all N>=n0
18.What is little o Notation?
It is used to describe the worst case running time of an algorithm and
concerned with small values of N.
T(N) =o(F(N)) if T(N)=O(FN)) and T(N) !=?(T(N))
Unit -II
1.Define ADT.
ADT Abstract Data Type. It is a set of operations � such as Union,
Intersection, Complement etc., It is an extension of modular design.
2.Define Modularity.
In programming, each problem can be divided in small sub modules. Each
module is a logical unit and do the specific job & it will call another module.
3.Comparison between Linked list and Arrays.
S.No Linked List Arrays
1 Continuous memory allocation Dynamic memory allocation
2 Size declared before compilation Size declared during run time
3 Accessing the element is fast Accessing the element is slow
4 Wastages of memory No wastages
5 Direct accessing the element is possible Direct accessing the element
is not possible
4.Define Linked list.
It is nothing but the collection of nodes. A node consists of data field &
address field.
5.What are the types of linked list?
Singly, doubly, & Circular linked list.
6.What are the advantages & disadvantages of singly linked list over doubly linked
list?
List Advantages Disadvantages
Singly Less memory space. One data & one address unit.Time complexity is
less. Because we can travel only one side.
Doubly We can travel both directions. So accessing the data is easy.
Extra memory unit for the address of previous node.
7.What are the advantages & disadvantages in Circular linked list?
List Advantages Disadvantages
Circular To move immediately from Ist node to last node.If we lose header
position, may not be able to find out where it begins & ends.
8.List out applications of Linked list.
Radix sort
Multi list
Polynomial ADT
9.What do u mean by cursor implementation of list?
It maintains a list of free cells called cursors space in which slot 0 is
considered as a header and next is equivalent to the pointer which points to the
next slot.
10.Define Stack.
It is a linear data structure. It is based on the concept of Last In First
Out ( LIFO). Insertion & deletion can be done at same end called top.
11.Define Top.
It is a position, where the insertion & deletion takes place in stack called
top.
12.What are the operations of stack & its exceptional condition?
Push to insert a new data � in to the stack
Pop � to delete the data from the stack
Exceptional condition
Overflow � Stack is full. We can�t push new element
Underflow � Stack is empty. We can�t pop any data from the stack.
13.List out the application of stack.
Convert infix to postfix
Balanced parenthesis
Towers of Hanoi
Evaluation of postfix expression
8 Queen�s problem
14.What is the reverse polish notation & polish notation?
Polish notation � prefix notation, operators come before the operands.
Reverse polish notation � postfix notation, operators come after the
operands.
15.Convert the following infix expressions in to postfix expressions.
((A+B)/D) * ((E-F)*G) ((A*C) +B/D^E)*F)
AB+D/EF-G** AC*BDE^/+F*
To evaluate the postfix expression for the following expressions.
632*+
Result is 12
16.Define Queue.
Queue is a linear data structure. It is based on the First In First Out
(FIFO) concept. Insert & Delete operations performed on different ends called rear
& Front respectively.
17.What are the operations in Queue?
Insert (or) Enqueue, Delete (or) Dequeue, Search
18.Give some applications for Queue.
Priority queue
Batch processing in an operating system
Queuing Theory
Computer networks in job scheduling
simulation
19.Define DEQUE.
It refers to Double Ended Queue. Insertion & Deletion operations are performed at
both ends.
20.Define Circular Queue.
In Circular Queue, the insertion of new element is performed at rear
position. When the rear exceeds the max limit of an array, it just goes back to
the first position. If it is empty, the element will be inserting into the first
position of the array. Otherwise, it is full.
21.What is mean by Priority Queue?
It is a Queue, which inserting & deleting an element can be performed from
any position based on some priority.
(or)
It is a Queue, which is most higher priority element will be executed first.
22.Compare Stack & Queue.
S.NO STACK QUEUE
1 Linear Data Structure Linear Data Structure
2 LIFO FIFO
3 Insertion & Deletion is done at only one end Insertion & Deletion is
done at different ends
4 Operations are PUSH & POP Operations are Insert (or) Enqueue,
Delete (or) Dequeue
5 Top is a position where insertion & deletion takes place Insertion
takes place at rear and Deletion takes place at Front.