1.
Limitations
of arrays
·
Arrays
have a fixed dimension. Once the size of an array is decided it cannot be
increased or decreased during execution.
·
Array
elements are always stored in contiguous memory locations. So it need
contiguous locations otherwise memory will not be allocated to the arrays
·
Operations
like insertion of a new element in an array or deletion of an existing element
from the array are pretty tedious. This is because during insertion or deletion
each element after the specified position has to be shifted one position to the
right or one position to the left.
1. Define Data Structure.
A data structure is a way of
organizing data that considers not only the items stored, but also their
relationship to each other. Advance knowledge about the relationship between
data items allows designing of efficient algorithms for the manipulation of
data.
2. Why do we need data structures?
v
Data structures allow us to achieve an important goal: component
reuse
v Once each data
structure has been implemented once, it can be used over and over again in
various applications.
3. Simple Classification of Data
Structure.
The data structure can be
classified into two types as follows:
a) Linear Data Structures – All
the elements are formed in a sequence or maintain a linear ordering
i.
Arrays
ii.
Linked
Lists
iii.
Stacks
iv.
Queues
b) Non-Linear Data Structures –
All the elements are distributed on a plane i.e. these have no such sequence of
elements as in case of linear data structure.
i.
Trees
ii.
Graphs
iii.
Sets
4. List the operations performed
in the Linear Data Structure
a) Traversal – Processing each
element in the list
b) Search – Finding the location
of the element with a given value.
c) Insertion / Storing – Adding a
new element to the list.
d) Deletion – Removing an element
from the list.
e) Sorting – Arranging the
elements in some type of order.
f) Merging – Combining two lists
into a single list.
5. Explain Linked List
v A linked list is a list of
elements in which the elements of the list can be placed anywhere in memory,
and these elements are linked with each other using an explicit link field,
that is by storing the address of the next element in the link field of the
previous element.
v A linked list is a
self-referential data type because it contains a pointer or link to another
data of the same type. This permit insertion and removal of nodes at any point
in the list in constant time, but do not allow random access.
6. What is a node?
Each element structure in a
slinked list called node, containing two fields one is data and another is
address of next data.
7. Advantages of Linked List
- Linked List is dynamic data structure; the size of a list can grow or shrink during the program execution. So, maximum size need not be known in advance.
- The Linked List does not waste memory
- It is not necessary to specify the size of the list, as in the case of arrays.
- Linked List provides the flexibility in allowing the items to be rearranged.
8. What are the pitfalls encountered
in single linked list?
- A singly linked list allows traversal of the list in only one direction.
- Deleting a node from a list requires keeping track of the previous node, that is, the node whose link points to the node to be deleted.
- If the link in any node gets corrupted, the remaining nodes of the list become unusable.
9. Define Stack
v Stack is a linear data
structure and is an ordered collection of homogeneous data elements, where the
insertion and deletion operations takes place at one end called top of the
stack.
v A stack data structure exhibits
the LIFO (Last In First Out) property.
10. What are operations allowed in
a Stack?
- PUSH : This operation is used to add an item into the top of the stack.
- POP : This operation is used to remove an item from the top of the stack.
- PEEK : This operation is used to display the top item in the stack.
11. List the notations used to
represent the arithmetic expressions.
1. Infix:
operator
Ex: A + B
2. Prefix: operator
(also called as polish notation) Ex: +AB
3. Postfix:
operator
Ex: AB+
12. Rules for converting an Infix
notation to postfix form
- Assume, the fully parenthesized version of the Infix expression
- Move all operator, so that they replace their corresponding right part of parenthesis
- Remove all parenthesis
Example: ((A+((B^C)-D))*(E-(A/C))) Ã ABC^D-+EAC/-*
13.
Define
Queue
Queue is an ordered collection
of homogeneous data elements, in which the element insertion and deletion takes
place at two ends called front and rear. The elements are ordered in linear
fashion and inserted at REAR end and deleted FRONT end. This exhibits FIFO
(First In First Out) property.
14. Applications
of Queue
Applications of queue as a data
structure are more common.
a) Within a computer system there
may be queues of tasks waiting for the line printer, or for access to disk
storage, or in a time-sharing system for use of the CPU.
b) Within a single program, there
may be multiple requests to be kept in a queue, or one task may create other
tasks, which must be done in turn by keeping them in a queue.
15. What
is the need of Circular Queue?
4 Queue implemented using an
array suffers from one limitation i.e. there is a possibility that the queue is
reported as full (since rear has reached
the end of the array), even though in actuality there might be empty slots
at the beginning of the queue. To overcome this limitation circular queue is needed.
4 Now the queue would be reported
as full only when all the slots in the array stand occupied.
16. What
is deque?
v The word deque is a short form
of double-ended
queue and defines a data structure in which items can be added or
deleted at either the front or rear end, but no changes can be made elsewhere
in the list.
v Thus a deque is a
generalization of both a stack and a queue.
17. Types
of Linked Lists:
a) Linear Singly Linked List
b) Circular Linked List
c) Two-way or doubly linked lists
d) Circular doubly linked lists
18. What
are the Applications of linked list?
a) Implementation of Stack
b) Implementation of Queue
c) Implementation of Tree
d) Implementation of Graph
19. Applications of Stack
a) It is very useful to evaluate
arithmetic expressions. (Postfix Expressions)
b) Infix to Postfix Transformation
c) It is useful during the
execution of recursive programs
d) A Stack is useful for designing
the compiler in operating system to store local variables inside a function
block.
e) A stack can be used in function
calls including recursion.
f) Reversing Data
g) Reverse a List
h) Convert Decimal to Binary
i) Parsing – It is a logic that
breaks into independent pieces for further processing
j)
Backtracking
No comments:
Post a Comment