Data Structures IMP
UNIT I
LINEAR DATA STRUCTURES-LIST
Abstract Data Type (ADT) - List ADT- Arrays based Implementation-linked
list implementation-singly linked lists-circularly linked lists-doubly linked
list-Application of list-polynomial manipulation-all operations (insertion,
deletion, merge, traversal).
|
S. No. |
Question |
|
1 |
What is a
data structure? ● A data structure is a method
for organizing and storing data which would allow
efficient data retrieval and usage. ● A data
structure is a way of organizing data that considers not only the items stored, but also their relationships to each other. |
|
2 |
Why do we
need data structures? ● Data structures allow us to achieve an important goal: component reuse. ● Once data
structure has been implemented, it can be used again and again in various applications. |
|
3 |
List some
common data structures. ● Stacks ● Queues ● Lists ● Trees ● Graphs ● Tables |
|
4 |
How data
structures are classified? Data structures are classified into two categories based
on how the data items are operated: i. Primitive data structure ii. Non-Primitive data structure |
|
|
a. Linear data structure b. Non-linear data structure |
||||||||||||
|
5 |
Differentiate
linear and non-linear data structure.
|
||||||||||||
|
6 |
Define ADT (Abstract Data Type) An abstract data type (ADT) is a set of operations
and mathematical abstractions , which can be viewed as how the set of operations is implemented.
Objects like lists, sets and graphs, along with their operation, can be
viewed as abstract data types, just as integers, real numbers and Booleans. |
||||||||||||
|
7 |
Mention the
features of ADT. a. Modularity i. Divide program into small functions ii. Easy to debug and maintain iii. Easy to modify b. Reuse i. Define some operations only once and reuse them
in future c. Easy to change the implementation |
||||||||||||
|
8 |
Define List ADT A list is a sequence of zero or more elements of a given type. The list is
represented as sequence of elements separated by comma. A1, A2,
A3…..AN Where
N>0 and A is of type element |
||||||||||||
|
9 |
What are the
ways of implementing linked list? The list can be implemented in the following ways: i. Array implementation ii. Linked-list implementation |
|
|
|
iii. Cursor
implementation |
|
10 |
What are the
types of linked lists? There are three types i. Singly linked list ii. Doubly linked list iii. Circularly linked list |
|
11 |
How the singly linked
lists can be represented?  Each node has two elements i. Data ii. Next |
|
12 |
How the doubly linked list
can be represented? 
backward link. Each node has three fields: 1. Address of previous node 2. Data 3. Address of next node. |
|
13 |
What are
benefits of ADT? a. Code is easier to understand b. Implementation of ADT can be changed
without requiring changes to
the program that uses the ADT |
|
14 |
When singly linked list can be represented as
circular linked list? In a singly linked list,
all the nodes
are connected with forward links to the next nodes in the list. The
last node has
a next field,
NULL. In order
to implement
the circularly linked |
|
|
lists from singly linked
lists, the last node’s next field is connected to the first node.
 |
|
15 |
When doubly linked list can be represented as circular linked list? In a doubly linked list,
all nodes are connected with forward
and backward links to the next and previous nodes
respectively. In order
to implement circular linked lists from doubly
linked lists, the first node’s previous field is connected to the last node
and the last node’s next field is connected to the first node.
|
|
16 |
Where cursor
implementation can be used? The cursor implementation of lists is used by many
languages such as BASIC and FORTRAN that do not support pointers. The two important features of the cursor implementation of linked are as follows: ● The data are stored
in a collection of structures. Each structure contains data and a index to the next structure. ● A new
structure can be obtained from the system’s global memory by a call to cursorSpace array. |
|
17 |
List down
the applications of List. a. Representation of
polynomial ADT b. Used in radix and bubble sorting c. In a FAT
file system, the metadata of a large file is organized as a linked list of
FAT entries. d. Simple memory
allocators use a free list of unused memory regions, basically
a linked list with the list pointer inside the free
memory itself. |
|
18 |
What are the
advantages of linked list? a. Save memory space and easy
to maintain b. It is possible to retrieve
the element at a particular index c. It is possible to traverse
the list in the order of increasing index. |
|
|
d. It is possible to change the element at a particular index to a different value,without affecting any other elements |
|||
|
19 |
Mention the
demerits of linked list a. It is not possible to go
backwards through the list b. Unable to jump to the
beginning of list from the end. |
|||
|
20 |
The polynomial equation can be represented with
linked list as follows:
struct polynomial { int coefficient;int exponent;struct polynomial *next; }; |
|||
|
21 |
What are the
operations performed in list? The following operations can be performed on a list i. Insertion a. Insert at beginning b. Insert at end c. Insert after specific node d. Insert before specific node ii. Deletion a. Delete at beginning b. Delete at end c. Delete after specific node d. Delete before specific node iii. Merging iv. Traversal |
|||
|
22 |
What are the merits and demerits of array implementation of lists? Merits ● Fast, random access of elements ● Memory efficient – very less amount of memory is required Demerits ● Insertion
and deletion operations are very slow since the elements should be moved. ● Redundant memory space – difficult to estimate
the size of array. |
|||
|
23 |
What is a
circular linked list? A circular linked
list is a special type of linked
list that supports
traversing from the end of the list to the beginning by making the last node point back to the head of
the list. |
|
|
|
|
|
24 |
What are the
advantages in the array implementation of list? a. Print list operation can
be carried out at the linear time b. Find Kth operation takes a
constant time |
|
25 |
What is the
need for the header? Header of the linked list is the first element
in the list and
it stores the number of elements in the list. It points to the first data
element of the list. |
|
26 |
List three
examples that uses linked list? a. Polynomial ADT b. Radix sort c. Multi lists |
|
27 |
List out the
different ways to implement the list? 1. Array Based Implementation 2. Linked list Implementation i. Singly linked list ii. Doubly linked list iii. Cursor based linked list |
|
28 |
Write the
routine for insertion operation of singly linked list. Void Insert (ElementType X, List L, Position P) {Position
TmpCell; TmpCell=malloc(sizeof(struct Node));
if(TmpCell==NULL) FatalError(“Out of space!!!”); TmpCell->Element =X; TmpCell->Next=P->Next; P->Next=TmpCell; } |
|
29 |
Advantages
of Array over Linked List. 1. Array has a specific address for each element stored
in it and thus we can access
any memory directly. 2. As we know the position of the middle
element and other elements are easily accessible too, we can
easily perform BINARY
SEARCH in array. |
|
30 |
Disadvantages
of Array over Linked List. 1. Total
number of elements need to be mentioned or the memory allocation needs to be done at the time of array
creation 2. The size
of array, once
mentioned, cannot be increased in the program. If number of elements
entered exceeds the size of the array ARRAY OVERFLOW EXCEPTION occurs. |
|
|
|
|
31 |
Advantages
of Linked List over Array. 1. Size of the list doesn't need to be mentioned at the
beginning of the program. 2. As the linked list doesn't have a size limit, we can go on
adding new nodes (elements) and increasing the size of the list to any
extent. |
|
32 |
Disadvantages
of Linked List over Array. 1. Nodes do not have their own address. Only the address
of the first node
is stored and
in order to reach any
node, we need to traverse
the whole list from beginning to the desired node. 2. As all
Nodes don't have
their particular address, BINARY SEARCH cannot be performed |
|
1 |
Explain the various operations of the list ADT
with examples |
|
2 |
Write the program for array implementation of lists |
|
3 |
Write a C program for linked list implementation
of list. |
|
4 |
Explain the operations of singly linked lists |
|
5 |
Explain the operations of doubly linked lists |
|
6 |
Explain the operations of circularly linked lists |
|
7 |
How polynomial manipulations are performed with lists? Explain the operations |
|
8 |
Explain the steps involved in insertion and deletion into a singly and doubly linked list. |
UNIT II
LINEAR DATA STRUCTURES-STACKS,QUEUES
Stack ADT-Operations-applications-Evaluating arithmetic expressions-conversion of infix to postfix expressions-queue
ADT-Operations-circular queue-priority queue-dequeue-applications of queues.
|
S. No. |
Question |
|
1 |
Define Stack. A stack is an ordered
list in which
all insertions and deletions are made at one end,
called the top. It is an abstract data type and based on
the principle of LIFO (Last
In First Out). |
|
2 |
What are the
operations of the stack? a. CreateStack/
InitStack(Stack) – creates an empty stack b. Push(Item) – pushes an
item on the top of the stack c. Pop(Item) – removes the
top most element from the stack d. Top(Stack) – returns the
first element from the stack e. IsEmpty(Stack) – returns
true if the stack is empty |
|
3 |
Write the
routine to push a element into a stack. Push(Element X, Stack S) { if(IsFull(S) { Error(“Full Stack”); } else S→Array[++S→TopOfStack]=X; } |
|
4 |
How the operations performed on linked
list implementation of
stack? a. Push and pop operations at
the head of the list. b. New nodes
should be inserted at the front
of the list,
so that they become the top
of the stack. c. Nodes are removed from the
front(top) of the stack. |
|
5 |
What are the
applications of stack? The following are the applications of stacks • Evaluating arithmetic expressions • Balancing the parenthesis • Towers of Hanoi • Function calls Tree traversal |
|
6 |
What are the
methods to implement stack in C? The methods to implement stacks are: ● Array based ● Linked list based |
|
7 |
How the
stack is implemented by linked list? It involves dynamically allocating memory space
at run time while performing
stack operations. Since it consumes only that much amount of space is required
for holding its data elements , it prevents wastage of memory
space. struct stack { |
|
|
int element; struct stack *next; }*top; |
|
8 |
Write the
routine to pop a element from a stack. int pop() { if(top==NULL) { printf(“\n Stack is empty.\n”);getch();exit(1);} else {int temp; temp=top→element;
top=top→next; return temp; }} |
|
9 |
Define queue. It is a linear data structure that maintains a list of elements such that insertion happens
at rear end and deletion happens at front end. FIFO –
First In First Out principle |
|
10 |
What are the
operations of a queue? The operations of a queue are ● isEmpty() ● isFull() ● insert() ● delete() ● display() |
|
11 |
Write the
routine to insert a element onto a queue. void insert(int element) { if(front==-1 ) { front =
rear = front +1; queue[front] = element; return; } if(rear==99) { printf(“Queue is full”);
getch(); return; } rear =
rear +1; queue[rear]=element; } |
|
12 |
What are the
types of queue? The following are the types of queue: ● Double ended queue ● Circular queue ● Priority queue |
|
13 |
Define
double ended queue ● It is a special
type of queue
that allows insertion and deletion of elements at both |
|
|
Ends. ● It is also termed as DEQUE.
 |
|
14 |
What are the
methods to implement queue in C? The methods to implement queues are: ● Array based ● Linked list based |
|
15 |
How the
queue is implemented by linked list? • It is based on the dynamic memory management techniques which allow allocation and De-allocation of memory space at runtime. Insert operation It involves the following subtasks: 1. Reserving memory
space of the
size of a queue element in memory 2. Storing the added value at
the new location 3. Linking the new element
with existing queue 4. Updating the rear pointer Delete operation It involves the following subtasks: 1. Checking whether queue is empty 2. Retrieving the front most
element of the queue 3. Updating the front pointer 4. Returning the retrieved value |
|
16 |
Write the
routine to delete a element from a queue int del() {int i; if(front == NULL) /*checking whether the queue is empty*/ {return(-9999);} else {i = front→element;front = front→next;return i;} } |
|
17 |
What are the
applications of queue? The following are the areas in which queues are applicable a. Simulation b. Batch processing in an
operating systems c. Multiprogramming platform systems d. Queuing theory e. Printer server routines f. Scheduling algorithms like
disk scheduling , CPU scheduling g. I/O buffer requests |
|
18 |
Define
circular queue A Circular queue is a queue whose
start and end locations are logically connected with each other.
That means the start location comes after the end
location.
 |
|||
|
19 |
What are
push and pop operations? • Push – adding an element
to the top of stack • Pop – removing or deleting
an element from the top of stack |
|||
|
20 |
What are
enqueue and dequeue operations? • Enqueue - adding an element to the queue at the rear end If the queue
is not full,
this function adds an element
to the back of the queue, else it prints “OverFlow”. void enqueue(int queue[], int
element, int& rear,
int arraySize) { if(rear == arraySize) // Queue is full printf(“OverFlow\n”); else{ queue[rear] = element; // Add
the element to the back rear++; } } • Dequeue – removing or deleting an element from the queue
at the front end If the queue is not empty, this function removes the element from the front
of the queue,
else it prints
“UnderFlow”. void
dequeue(int queue[], int& front, int rear) { if(front == rear) // Queue is empty printf(“UnderFlow\n”); else { queue[front] = 0; // Delete
the front element front++; } } |
|||
|
21 |
Distinguish
between stack and queue. |
|||
|
|
STACK |
QUEUE |
|
|
|
Insertion and deletion are made
at one end. |
Insertion at one end rear and deletion at other end front. |
|||
|
|
|
The element
inserted last would be removed first. So LIFO structure. |
The
element inserted first would be removed
first. So FIFO structure. |
|
|
Full stack
condition: If(top==Maxsize) Physically and
Logically full stack |
Full stack
condition: If(rear = = Maxsize) Logically full.
Physically may or may not be full. |
|||
|
|
||||
|
22 |
Convert the infix
(a+b)*(c+d)/f into postfix
& prefix expression Postfix : a b + c d + * f / Prefix : / * + a b + c d f |
|||
|
23 |
Write
postfix from of the expression –A+B-C+D? A-B+C-D+ |
|||
|
24 |
How do you
test for an empty queue? To test for an empty
queue, we have to check whether READ=HEAD where REAR is a pointer pointing to
the last node in a queue and HEAD is a pointer that pointer to the dummy header.
In the case of array
implementation of queue,
the condition to be checked for an empty queue is READ<FRONT. |
|||
|
25 |
What are the
postfix and prefix forms of the expression? A+B*(C-D)/(P-R) Postfix form:
ABCD-*PR-/+ Prefix form: +A/*B-CD-PR |
|||
|
26 |
Explain the usage
of stack in recursive algorithm implementation? In recursive algorithms, stack data structures is used to
store the return address when a recursive call is encountered and also to store the values of all the parameters essential
to the current state of the procedure. |
|||
|
27 |
Define
priority queue with diagram and give the operations. Priority queue is a data structure that allows at least the following two operations. 1. Insert-inserts an element
at the end of the list called the rear. 2. DeleteMin-Finds, returns and removes the
minimum element in the
priority Queue. |
|||
|
|
Operations: Insert, DeleteMin |
|
28 |
Give the
applications of priority queues. There are three applications of priority queues 1. External sorting. 2. Greedy algorithm implementation. 3. Discrete even simulation. 4. Operating systems. |
|
29 |
How do you
test for an empty stack? To check if the stack
is empty, we only need to check whether top and bottom are the
same number. bool stack_empty(stack S) //@requires is_stack(S); { return
S->top == S->bottom; } |
|
30 |
What are the
features of stacks? ●
Dynamic data structures ●
Do not have a fixed size ●
Do not consume a fixed amount of memory ●
Size of stack changes with each push() and pop() operation. Each push()
and pop() operation increases and decreases the size of the stack by 1,
respectively. |
|
31 |
Write a
routine for IsEmpty condition of queue. If a queue is empty, this function returns
'true', else it returns
'false'. bool isEmpty(int front,
int rear) { return (front == rear); } |
|
1 |
Explain Stack ADT and its operations |
|
2 |
Explain array based implementation of stacks |
|
3 |
Explain linked list implementation of stacks |
|
4 |
Explain the applications of Stacks |
|
5 |
Explain how to evaluate arithmetic expressions
using stacks |
|
6 |
Explain queue ADT |
|
7 |
Explain array based implementation of queues |
|
8 |
Explain linked list implementation of queues |
Comments
Post a Comment