MCA2020- ADVANCED DATA STRUCTURE
Q1.) Define Modularity and explain its need in
computer programs.
Ans.) Modularity is the process of dividing a large problem into
sub-problems. Computer programmers use the same concept to divide a complex
program into a number of sub-modules, which are solved individually and then
combined to solve a larger problem.
The
Hierarchical structure is typically divided into the following levels:
- Level 1: It includes a single main module, which provides a general description of the problem.
- Level 2: It includes sub-modules of the main module. These modules provide a more detailed description of the problem than the main module.
- Level 3: It includes sub-modules of the modules at Level-2.
- Level 4: It includes one or more sub-modules of the modules at Level-3.
Its need in computer programs:
Computer programmers used to write large programs to
solve complex problems. Today, computer programmers use the concept of
modularity to simplify the task of writing such programs. In organizing a
solution to a problem which is to be solved with the aid of a computer, we are
confronted with four interrelated sub problems:
First sub problem is to understand the logical relationship between the data elements in
the problem. For which first we have to understand the data itself. Data
consist of a set of elementary items or atoms. An atom usually consists of
single element such as integers, bits, character or set of such items. The
possible ways in which the data items or atoms are logically related define
different data structures.
Second sub problem is that, to decide on operations which must be performed on the data
structures that are to be used. A number of operations can be performed on data
structures like operation to create & destroy operations to insert &
delete, so on. These operations have various functionality for different data
structures.
Third problem
is the representation of a data structure in the memory. The representation of
data structures in memory is called a storage structure. We have many storage structures
for a data structure such as an array & it is possible for two data
structures to be represented by the same storage structure. The data structure
can be stored both in main & the auxiliary memory of the computer. A
storage structure representation in auxiliary memory is often called as file
structure.
Fourth sub problem which is the selection of a programming language to be used in the
solution of the problem. The programming language chosen for the implementation
of an algorithm should posses the particular representation chosen for the data
structures in the problem being solved.
--------------------------------------------------------------------------------------------------------------------------
Q2.) Define Queue and explain how we can
implement the Queue.
Ans.) A queue is a linear list of elements in which deletions can
take place only at one end, called the front & insertions can be place only
at the other end, called the rear. The terms “front” & “rear” are used in
describing a linear list only when it is implemented as a queue. The two
methods by queue for adding & deleting element from the queue are:
·
enqueue
:- add a new item at the back of the queue.
·
dequeue
:- remove the item at the front of the queue.
Queue implementation:-
Queue can be
implemented using an Array, Stack or Linked List. The easiest way of
implementing a queue is by using an Array. Initially the head (FRONT) and the
tail (REAR) of the queue points at the first index of the array (starting the
index of array from 0). As we add elements to the queue, the tail keeps on
moving ahead, always pointing to the position where the next element will be
inserted, while the head remains at the first index.
When we
remove element from Queue, we can follow two possible approaches (mentioned [A]
and [B]). In [A] approach, we remove the element at head
position, and then one by one move all the other elements on position forward.
In approach [B] we remove the element from head position and then move head to
the next position.
In approach [A] there is an overhead of shifting the
elements one position forward every time we remove the first element. In
approach [B] there is no such overhead, but whenever we move head one position
ahead, after removal of first element, the size on Queue is reduced by one
space each time.
--------------------------------------------------------------------------------------------------------------------------
Q3.) List the Advantages and Disadvantages of
Linear and linked representation of tree.
Ans.) Advantages and disadvantages of linear representation:-
Advantages:
1. This representation is very easy to
understand.
2. This is the best representation for
complete and full binary tree representation.
3. Programming is very easy.
4. It is very easy to move from a child
to its parents and vice versa.
Disadvantages:
1. Lot of memory area wasted.
2. Insertion and deletion of nodes needs
lot of data movement.
3. Execution time high.
4. This is not suited for trees other
than full and complete tree.
Advantages and
disadvantages of linked representation :-
Advantages:
1. A particular node can be placed at
any location in the memory.
2. Insertions and deletions can be made
directly without data movements.
3. It is best for any type of trees.
4. It is flexible because the system takes
care of allocating and freeing of nodes.
Disadvantages :-
1. It is difficult to understand.
2. Additional memory is needed for
storing pointers
3. Accessing a particular node is not
easy.
--------------------------------------------------------------------------------------------------------------------------
Q4.) List and explain any five types of graphs.
Ans.) Depending upon the vertices & edges & the weight
associated to it, graphs can be classified as:
1. Undirected graph
2. Directed graph
3. Weighted graphs
4. Multigraph
1.) Undirected graph: - An
undirected graph is a graph where the directions of the edges are not assigned.
In an undirected graph, edge (V1, V2) is equivalent to edge
(V2, V1) since the edges are unassigned.
2.)
Directed graph: - A
directed graph is a graph where each edge is assigned a direction. In a
directed graph, (V1, V2) & (V2, V1)
are two edges where the former edge leaves V1 & ends at V2,
& vice versa.
3.) Weighted
graph: - A graph is
called a weighted graph if a number representing information such cost or
weight is associated with the traversal of each edge. Directed & undirected
graphs may both be weighted.
4.) Multi
graph: - A
multi-graph has more than one edge between the same two vertices. Consider the
example of airline flights, where there may be multiple flights between two
cities. Similarly, there may be more than one edge between two vertices.
--------------------------------------------------------------------------------------------------------------------------
Q5.) Explain:
1.) Fixed
block storage allocation.
2.) Variable
block storage allocation
Ans.)
1.) Fixed block storage allocation:- First block
storage allocation is the simplest case of dynamic storage allocation. This is
the straight forward method in which, all the blocks are of identical in size.
The user can decide the size of the block. The operating system keeps a pointer
called AVAIL.
Procedure
GETNODE (NODE)
If
(AVAIL=NULL) then
Print “The
memory is insufficient”
Else
Ptr = AVAIL
AVAIL=AVAIL.LINK
Return (ptr)
Exit
Procedure
RETURNNODE (ptr)
Ptr1=AVAIL
While
(ptr1.LINK is not NULL)
Ptr1=ptr1.LINK
Ptr1.LINK=ptr
Ptr.LINK = NULL
Exit
2.) Variable block storage allocation:-
To overcome
the disadvantages of fixed block storage, blocks of variable sizes are used. Here
also linked lists play a vital for the management of memory blocks. The
procedures used for allocation and de-allocation of memory blocks from the
variable block storage are as follows.
Procedure
RETURNNODE (ptr)
Ptr1=AVAIL
While
(ptr1.SIZE < ptr. SIZE) and (ptr1.LINK ≠ NULL) do
Ptr2=ptr1
Ptr1 =
ptr.LINK
Endwhile
If (ptr.SIZE
<ptr1.SIZE) then
Ptr2.LINK =
ptr
Ptr.LINK =
ptr1
Else
Ptr1.LINK =
ptr
Ptr.LINK =
NULL
Endif
Exit
--------------------------------------------------------------------------------------------------------------------------
Q6.) What is the use of external Storage Devices?
Explain any two external storage devices.
Ans.) The capacity of main memory is limited by two factors, the
cost of main memory and the technical problem in developing a large capacity of
main memory. We discover that in some instances programs can also reside in
storage units which do not belong to main memory.
The two external
storage devices are: -
1.)
Magnetic tape: -
Magnetic
tape is an information storage medium consisting of a magnet sable coating on a
thin plastic strip. Nearly all recording tape is of this type, whether used for
video with a video cassette recorder, audio storage (reel-to-reel tape, compact
audio cassette, digital audio tape (DAT), digital linear tape (DLT) and other
formats including 8-track cartridges) or general purpose digital data storage
using a computer (specialized tape formats, as well as the above-mentioned compact audio
cassette, used with home computers of the 1980s, and DAT, used for backup in
workstation installations of the 1990s).
Modern
magnetic tape is
Magnetic drums:
- A magnetic drum, is a
direct-access or random-access storage device, also referred to as drum. It is
a metal cylinder coated with magnetic iron-oxide material on which data and
programs can be stored. Magnetic drums were once used as a primary storage
device but have since been implemented as auxiliary storage devices.
--------------------------------------------------------------------------------------------------------------------------
No comments:
Post a Comment