Twitter Facebook Delicious Digg Stumbleupon Favorites More

Friday, 10 March 2017

IPU BCA/BTech Semester 2 - Data Structures - Abstract Data Type (ADT)

Data Structures - Abstract Data Types (ADT)

IPU BCA/BTech Semester 2 - Data Structures - Abstract Data Type (ADT)

Question: 
(a) What is Abstract Data Type (ADT)? 
(b) Give examples of commonly used ADTs.
(c) What are the advantages of ADTs?


Answer:
(a) An abstract data type (ADT) is a logical description or a specification of components of the data and the operations that are allowed and it is independent of the implementation. An ADT is a user defined data type that are defined along with their operations.

An ADT consists of two parts:
1. Declaration of data
2. Declaration of operations

(b) Commonly used ADTs are:
Linked Lists,
Stacks,
Queues,
Priority Queues,
Binary Trees,
Dictionaries,
Disjoint Sets,
Hash Tables,
Graphs etc.




(c) Advantages of ADTs are:

Encapsulation: The user need not know knowledge of implementing the ADT. Its implementation may be complex but it is be encapsulated in a simple interface while defining it.

Localization of change: Code that uses an ADT object do not require editing if the implementation of the ADT  changes.

Flexibility: Different implementations of an ADT may be more efficient in different situations thus increases the overall efficiency of the program.

Easy to understand and reusable code.


Question: Write down one dimensional array specifications as ADT.

Answer: eltype denotes type of element and ub is the upper bound.

abstract typedef <<eltype, ub>> ARRTYPE(ub, eltype);
condition type(ub) == int;

abstract eltype extract(a, i)  /* written as a[i] */
ARRTYPE(ub, eltype) a;
int i;
precondition 0 <= i < ub;
postcondition extract == a₁

abstract store(a, i, elt)
ARRTYPE (ub, eltype) a;
int i;
eltype elt;
precondition  0 <= i < ub;
postcondition a[i] == elt;



Question: Write down representation of a stack as ADT.

Answer:

abstract typedef <<eltype>> STACK (eltype);

abstract empty(s)
STACK (eltype s)
postcondition (empty == len(s) == 0);

abstract eltype pop(s)
STACK (eltype) s;
precondition empty(s) == FALSE;
postcondition pop == first(s)
s == sub(s', 1, len(s') - 1);


abstract push (s, elt)
STACK (eltype) s;
eltype elt;
postcondition s == <elt> + s';



Question: Represent queue as Abstract Data Type (ADT).

Answer:

abstract typedef <<eltype>> QUEUE (eltype);

abstract empty(q)
QUEUE (eltype) q;
postcondition empty == (len(q) == 0);

abstract eltype remove(q)
QUEUE (eltype) q;
precondition empty(q) == FALSE;
postcondition remove == first(q');
q == sub(q', 1, len(q') - 1);

abstract insert (q, elt)
QUEUE (eltype) q;
eltype elt;
postcondition q = q' + <elt>;


See also:
  - Abstract Data Type Notes by CSE Department IIT Kharagpur
  - Data Structure Notes by IIT Kgp
Share:

0 comments:

Post a Comment

BCE-Hacks Notes

BCE-Hacks Notes
Chemical Engineering Notes

Maths Resources

Maths Resources
Maths Resources

Buy Books

Buy Books
Buy Books

Geography Quiz

Geography Quiz
Geography Quiz

NodeJS Tutorial

NodeJS Tutorial
Developer-Bytes

History MCQs

History MCQs
History Quiz For Competitive exams

Categories

Popular Posts

GooglePlus

Recent Posts

Unordered List

Express Print Zone

Eduvictors Quizzes

Online Quizzes, Study notes for CBSE Class 6 - 12

Text Widget

Compete4Exams

Study notes for Competitive Exams

Developer Bytes

Developer Bytes
Developer Bytes
Powered by Blogger.

Blogger Tutorials

Blogger Templates

Sample Text

Copyright © IP University Musings BCA, MCA, BBA, MBA, BTech Question Papers and Study Notes | Powered by Blogger
Design by SimpleWpThemes | Blogger Theme by NewBloggerThemes.com