UNIT I
PART-A
1. Define data structure.
The data structure can be defined as the collection of elements and all the possible
operations which are required for those set of elements. Formally data structure can be defined as
a data structure is a set of domains D, a set of domains F and a set of axioms A. this triple
(D,F,A) denotes the data structure d.
2. What do you mean by non-linear data structure? Give example.
The non-linear data structure is the kind of data structure in which the data may be
arranged in hierarchical fashion. For example- Trees and graphs.
3. What do you linear data structure? Give example.
The linear data structure is the kind of data structure in which the data is linearly
arranged. For example- stacks, queues, linked list.
4. What is abstract data type? What are all not concerned in an ADT?(NOV/DEC 2019)
The abstract data type is a triple of D i.e. set of axioms, F-set of functions and A-Axioms
in which only what is to be done is mentioned but how is to be done is not mentioned. Thus ADT
is not concerned with implementation details.
5. What is a linked list?(NOV/DEC 2019)
A linked list is a set of nodes where each node has two fields ‘data’ and ‘link’. The data
field is used to store actual piece of information and link field is used to store address of next
node.
6. Define doubly linked list.
Doubly linked list is a kind of linked list in which each node has two link fields. One link
field stores the address of previous node and the other link field stores the address of the next
node.
7. State the advantages of circular lists over doubly linked list.
In circular list the next pointer of last node points to head node, whereas in doubly linked
list each node has two pointers: one previous pointer and another is next pointer. The main
advantage of circular list over doubly linked list is that with the help of single pointer field we
can access head node quickly. Hence some amount of memory get saved because in circular list
,only one pointer is reserved.
8. What are the advantages of doubly linked list over singly linked list?
The doubly linked list has two pointer fields. One field is previous link field and another
is next link field. Because of these two pointer fields we can access any node efficiently whereas
in singly linked list only one pointer field is there which stores forward pointer.
9. What is the circular linked list?(NOV/DEC 2018)
The circular linked list is a kind of linked list in which the last node is connected to
the first node or head node of the linked list.
This node is useful for getting the starting address of the linked list.
10. What is the advantage of an ADT?(NOV/DEC 2018)
➢ Change: the implementation of the ADT can be changed without making changes in
the client program that uses the ADT.
➢ Understandability: ADT specifies what is to be done and does not specify the
implementation details. Hence code becomes easy to understand due to ADT.
➢ Reusability: the ADT can be reused by some program in future.
PART-B
1. Explain the insertion operation in linked list. How nodes are inserted after a specified
node.(NOV/DEC 2019)
2. Write an algorithm to perform add, delete and display operation using LIST ADT?
(NOV/DEC 2018)
3. Discuss deletion operation in circular linked lists.(NOV/DEC 2018)
4. Discuss the insertion operation for a doubly linked list.
5. How to perform deletion operation using linked list?
6. How polynomial expression can be represented using linked list for addition? (NOV/DEC
2018,NOV/DEC 2019)
7. Discuss the deletion operation for doubly linked list.
, UNIT II
PART-A
1. Define Stack
A Stack is an ordered list in which all insertions (Push operation) and deletion (Pop
operation) are made at one end, called the top. The topmost element is pointed by top. The top is
initialized to -1 when the stack is created that is when the stack is empty. In a stack S = (a1,an),
a1 is the bottom most element and element a is on top of element ai-1. Stack is also referred as
Last In First Out (LIFO) list.
2. What are the various Operations performed on the Stack?
The various operations that are performed on the stack are
CREATE(S) – Creates S as an empty stack.
PUSH(S,X) – Adds the element X to the top of the stack.
POP(S) – Deletes the top most elements from the stack.
TOP(S) – returns the value of top element from the stack.
ISEMTPTY(S) – returns true if Stack is empty else false.
ISFULL(S) - returns true if Stack is full else false.
3. 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
4. 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 function.
5. Define Queue.
A Queue is an ordered list in which all insertions take place at one end called the rear, while
all deletions take place at the other end called the front. Rear is initialized to -1 and front is
initialized to 0. Queue is also referred as First In First Out (FIFO) list.
6. What are the various operations performed on the Queue?
The various operations performed on the queue are
CREATE(Q) – Creates Q as an empty Queue.
Enqueue(Q,X) – Adds the element X to the Queue.
Dequeue(Q) – Deletes a element from the Queue.
ISEMTPTY(Q) – returns true if Queue is empty else false.
ISFULL(Q) - returns true if Queue is full else false.
, 7. How do you test for an empty Queue?
The condition for testing an empty queue is rear=front-1. In linked list implementation of
queue the condition for an empty queue is the header node link field is NULL.
8.Define Dequeue.(NOV/DEC 2019)
Dequeue stands for Double ended queue. It is a linear list in which insertions and
deletion are made from either end of the queue structure.
9.Define Circular Queue.
Another representation of a queue, which prevents an excessive use of memory by
arranging elements/ nodes Q1,Q2,…Qn in a circular fashion. That is, it is the queue, which wraps
around upon reaching the end of the queue
10.List any four applications of stack.(NOV/DEC 2018,NOV/DEC 2019)
Parsing context free languages
Evaluating arithmetic expressions
Function call
Traversing trees and graph
Tower of Hanoi
PART-B
1. Write an algorithm for Push and Pop operations on Stack using Linked list.(NOV/DEC
2019)
2. Explain the array implementation of stack ADT in detail?
3. Explain in detail about circular queue.
4. Write the algorithm for converting infix expression to postfix (polish)
expression?(NOV/DEC 2019)
5. Explain in detail about priority queue ADT in detail?
6. What is Queue? Explain its operation and implement it using array.(NOV/DEC 2019)
7. Explain linked list implementation of queue ADT in detail?