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.

## No comments:

Post a Comment