Data Structure IMP Q & Ans for [Link] -2nd sem.

By : [Link], CSE, NIST

MODULE-1
1. What is a structure in C?
Answer: A structure is a user-defined data type that groups variables of different types
under a single name.

2. How can a structure be passed to a function?

Answer: A structure can be passed to a function either by value (copying the structure) or
by reference (using a pointer).

3. What is a pointer to a structure?

Answer: A pointer to a structure stores the address of a structure variable and can be
used to access structure members using the arrow (->) operator.

4. Define dynamic memory allocation (DMA) in C.

Answer: DMA is the process of allocating memory during runtime using functions like
malloc(), calloc(), realloc(), and free().

5. How is DMA used with structures?

Answer: We can allocate memory for a structure dynamically using functions like malloc()
and access its members using a pointer.

6. What is a self-referential structure?

Answer: A self-referential structure is a structure that contains a pointer to another
structure of the same type.

7. Give an example of a self-referential structure.

Answer:
c
CopyEdit
struct Node {
int data;
struct Node *next;
};

8. Define data structure.

Answer: A data structure is a way of organizing and storing data to perform operations
efficiently.

9. What are the types of data structures?

Answer: Data structures are broadly classified into linear (arrays, lists) and non-linear
(trees, graphs).

10. What is an Abstract Data Type (ADT)?

Answer: An ADT is a model for data types where only the behavior is specified without
any implementation details.
1
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST

11. How is an ADT represented?

Answer: An ADT is represented through its operations (like push, pop for stack) and the
rules that define its behavior.

12. Define ADT of a Stack.

Answer: The ADT of a stack defines operations like push(), pop(), peek(), and checking if
the stack is empty or full, following LIFO principle.

13. Define ADT of a Queue.

Answer: The ADT of a queue defines operations like enqueue(), dequeue(), and checking
if the queue is empty or full, following FIFO principle.

14. What is a stack?

Answer: A stack is a linear data structure that follows Last In First Out (LIFO) principle for
insertion and deletion.

15. How can stack be used to reverse a string?

Answer: By pushing each character onto the stack and then popping characters back, the
string can be reversed.

16. How is infix expression converted to postfix using stack?

Answer: Stack is used to store operators; by following precedence and associativity rules,
infix expressions are converted to postfix.

17. How can a decimal number be converted to binary using a stack?

Answer: Divide the decimal number by 2 repeatedly, push remainders onto the stack,
then pop and display to get binary.

18. What is a linear queue?

Answer: A linear queue is a simple queue where elements are inserted at the rear and
deleted from the front in a sequential manner.

19. What is a circular queue?

Answer: A circular queue connects the end of the queue back to the front, forming a
circle, to utilize unused space.

20. What is a Deque?

Answer: A Deque (Double Ended Queue) is a linear data structure where elements can be
inserted or deleted from both front and rear ends.
[5 MARKS ]
1. Explain different ways of passing a structure to a function with examples.
Answer:
A structure can be passed:
 By Value: A copy of the structure is passed to the function.

2
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
void display(struct Student s);
 By Reference (Pointer): Only the address of the structure is passed, reducing
memory overhead.
void display(struct Student *s);
Example:
struct Student
{
int id;
char name[20];
};

void display(struct Student s) {

printf("%d %s", [Link], [Link]);
}

2. What is a pointer to a structure? Explain with an example.

Answer:
A pointer to a structure holds the address of a structure. Using the -> operator, we can
access structure members. Example:
struct Employee
{
int id;
float salary;
};

struct Employee e1 = {101, 50000};

struct Employee *ptr = &e1;

printf("%d %.2f", ptr->id, ptr->salary);

Pointers make it easier to pass large structures and dynamically allocated structures to
functions.

3. How is dynamic memory allocation (DMA) used with structures? Provide an example.
Answer:
Dynamic memory allocation allows creation of structure variables at runtime using
malloc() or calloc(). Example:
struct Student
{
int roll;
char name[20];
};

struct Student *ptr = (struct Student *)malloc(sizeof(struct Student));

ptr->roll = 1;
strcpy(ptr->name, "John");
3
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
printf("%d %s", ptr->roll, ptr->name);
free(ptr);
DMA is essential for creating flexible, scalable programs.

4. Define a self-referential structure. Write its uses with an example.

Answer:
A self-referential structure contains a pointer to the same type of structure. Example:

struct Node
{
int data;
struct Node *next;
};
Uses:
 Linked lists
 Trees
 Graphs
These structures allow dynamic creation of complex data types like linked lists where
nodes point to each other.

5. Define data structure. Explain its types with examples.

Answer:
A data structure is a format to store and organize data efficiently.
Types:
 Linear Data Structure: Data arranged sequentially (Array, Stack, Queue, Linked List)
 Non-Linear Data Structure: Data arranged hierarchically (Tree, Graph)
Examples:
 Array: Storing list of students
 Tree: Storing hierarchical data like file systems

6. What is Abstract Data Type (ADT)? Explain ADT of Stack.

Answer:
An ADT is a theoretical model that defines a data structure purely by its behavior
(operations), not its implementation. ADT of Stack:
Operations:
 push(x): Add x to the top
 pop(): Remove top element
 peek(): Return top element without removal
 isEmpty(): Check if stack is empty
 isFull(): Check if stack is full
It follows LIFO (Last In First Out) principle.

7. Explain the process of converting infix expression to postfix using stack.

Answer:
Steps:
4
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
1. Read the expression left to right.
2. If operand, add to output.
3. If operator, push onto stack after popping higher precedence operators.
4. If '(', push to stack.
5. If ')', pop and output until '(' is found.
6. At the end, pop all operators from stack.
Example:
Infix: (A+B)*C
Postfix: AB+C*

8. Write the algorithm for decimal to binary conversion using stack.

Answer:
Algorithm:
1. Push remainders of decimal number divided by 2 onto stack.
2. Divide number until it becomes 0.
3. Pop and display all elements to get binary equivalent.
Example:
Decimal: 10
Stack after push: 0, 1, 0, 1
Binary: 1010

9. Differentiate between linear queue and circular queue.

Answer:
Feature Linear Queue Circular Queue
Structure Straight line Circular connection
Wastage Memory wasted after deletions No wastage
End Condition rear == MAX-1 (rear+1)%MAX == front
Efficiency Less efficient More efficient
Example Ticket counter queue Round robin CPU scheduling

10. What is a Deque? Explain its types with examples.

Answer:
A Deque (Double Ended Queue) allows insertion and deletion at both front and rear ends.
Types:
 Input-Restricted Deque: Insertion at rear only, deletion at both ends.
 Output-Restricted Deque: Deletion at rear only, insertion at both ends.
Example:
Adding elements at both ends of a train compartment.
[LONG QUESTIONS]
1. Explain in detail how structures are passed to functions and how pointers to structures
are used. Provide examples.
Answer:
In C programming, structures can be passed to functions in two ways:

5
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
 Passing by Value: A copy of the structure is passed to the function. Changes inside
the function do not affect the original structure.
 Passing by Reference: A pointer to the structure is passed. Changes inside the
function affect the original structure.
Passing by Value Example:
struct Student
{
int id;
char name[20];
};

void display(struct Student s) {

printf("%d %s", [Link], [Link]);
}

int main() {
struct Student stu1 = {1, "John"};
display(stu1);
}
Passing by Reference Example:
void display(struct Student *s) {
printf("%d %s", s->id, s->name);
}

int main() {
struct Student stu1 = {1, "John"};
display(&stu1);
}
Pointers to Structure: Pointers are used to dynamically access structure members and
save memory. The arrow operator (->) is used with pointers to structures to access
members easily.
Usefulness:
 Saves memory.
 Efficient parameter passing.
 Required for dynamic memory allocation (DMA).

2. Define Data Structure. Explain types of Data Structures with examples.

Answer:
Definition:
A data structure is a way of organizing and storing data so that it can be accessed and
modified efficiently.
Types of Data Structures:
1. Linear Data Structures:
Elements are arranged sequentially.
 Array: Fixed-size list.

6
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
 Stack: Follows LIFO (Last In First Out).
 Queue: Follows FIFO (First In First Out).
 Linked List: Nodes connected using pointers.
2. Non-Linear Data Structures:
Elements are arranged hierarchically.
 Tree: Hierarchical structure with a root node.
 Graph: Nodes connected arbitrarily.
Examples:
 Array: List of student names.
 Stack: Undo operation in editors.
 Queue: Printer queue.
 Linked List: Playlist of songs.
 Tree: Family tree.
 Graph: Social media network.
Importance:
Efficient data structures help optimize storage and retrieval operations, impacting the
performance of algorithms.

3. Define Abstract Data Types (ADT). Explain ADT of Stack and Queue with representation.
Answer:
Definition of ADT:
An Abstract Data Type (ADT) is a theoretical concept where the data type is defined by its
behavior (operations) rather than its implementation.
ADT of Stack:
A stack is a collection of elements with two main operations:
 push(element): Add element at top.
 pop(): Remove top element.
Other operations:
 peek(): Get top element without removing.
 isEmpty(): Check if the stack is empty.
 isFull(): Check if the stack is full.
Representation:
 Can be implemented using arrays or linked lists.
 Follows LIFO principle.
ADT of Queue:
A queue is a collection where elements are inserted at rear and deleted from front:
 enqueue(element): Insert at rear.
 dequeue(): Remove from front.
Other operations:
 isEmpty(): Check if queue is empty.
 isFull(): Check if queue is full.
Representation:
 Can be implemented using arrays or linked lists.
 Follows FIFO principle.

7
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
Importance:
ADT defines what operations are to be performed but not how they are performed,
enabling abstraction and modularity.

4. Explain the applications of Stack with respect to reversing a string, infix to postfix
conversion, and decimal to binary conversion.
Answer:
1. Reversing a String Using Stack:
 Push all characters of the string onto a stack.
 Pop characters one by one and append to a new string.
Example Code:
char str[] = "hello";
Stack push all characters -> h,e,l,l,o
Pop -> o,l,l,e,h => reversed string
2. Infix to Postfix Conversion:
 Use stack to hold operators.
 Follow precedence and associativity rules.
 Output operands directly and operators based on precedence.
Example: Infix: (A+B)*C
Postfix: AB+C*
Steps:
 Read A -> Operand -> Output.
 Read + -> Operator -> Push to stack.
 Read B -> Operand -> Output.
 Read * -> Higher precedence -> Push after popping +.
 Read C -> Operand -> Output.
 Pop remaining operators.
3. Decimal to Binary Conversion:
 Divide the number by 2.
 Push remainders onto stack.
 Pop all elements to get binary number.
Example: Decimal 10 -> remainders: 0,1,0,1
Binary: 1010
Importance:
Stacks simplify these tasks by handling operations in a last-in-first-out manner, making
them suitable for parsing and conversions.

5. Define Queue. Differentiate between Linear Queue, Circular Queue and Deque with
suitable examples.
Answer:
Definition:
A queue is a linear data structure that follows FIFO (First In First Out) principle.
Operations:
 enqueue(element): Insert at rear.
 dequeue(): Remove from front.

8
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST

Linear Queue:
 Straight line structure.
 After several deletions, space at front is wasted.
Example: Queue after enqueue 1,2,3: [1,2,3]
After dequeue 1: [X,2,3] (wasted space at front)

Circular Queue:
 Last position connected back to first.
 Better memory utilization.
 When rear reaches end, it wraps around.
Example: Queue positions: [2,3, , ,1] after wrap-around.

Deque (Double Ended Queue):

 Elements can be inserted and removed from both front and rear.
 Two types:
o Input-Restricted Deque: Insertion at rear only.
o Output-Restricted Deque: Deletion at rear only.
Example: Deque operations:
 Insert at front: 1
 Insert at rear: 2
 Delete from front: 1
 Delete from rear: 2
Comparison Table:
Feature Linear Queue Circular Queue Deque
Insertions Rear Rear, wraps around Front and Rear
Deletions Front Front Front and Rear
Wastage Yes No No
Flexibility Less More Most
MODULE-2
SORT QUESTIONS-
1. What is a linked list?
Answer: A linked list is a linear data structure where each element (node) contains data
and a pointer to the next node.
2. What is a self-referential structure?
Answer: A self-referential structure is a structure that contains a pointer to a structure of
the same type.
3. Write the structure of a node in a singly linked list.
Answer:
struct Node {
int data;
struct Node *next;
};

9
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
4. What is the head of a linked list?
Answer: The head is a pointer that points to the first node of a linked list.
5. Define traversal in a linked list.
Answer: Traversal is the process of visiting each node of a linked list exactly once to
perform some operation.
6. What are the basic operations on a singly linked list?
Answer: Insertion, Deletion, Traversal, and Search are the basic operations.
7. How is insertion done at the beginning of a singly linked list?
Answer: A new node is created, its next pointer is set to the current head, and then the
head is updated to the new node.
8. How is deletion done at the beginning of a singly linked list?
Answer: The head node is removed by updating the head pointer to the next node, and
the old head is freed.
9. What is a circular linked list?
Answer: In a circular linked list, the last node points back to the first node instead of
NULL.
10. What is a doubly linked list?
Answer: A doubly linked list is a linked list where each node contains a pointer to both the
next and the previous node.
11. Write the structure definition for a doubly linked list node.
Answer:
struct DNode
{
int data;
struct DNode *prev, *next;
};
12. How does a circular linked list differ from a singly linked list?
Answer: In a circular linked list, the last node points to the first node, whereas in a singly
linked list, the last node points to NULL.
13. Name two real-world applications of linked lists.
Answer: Memory management and dynamic data structures like stacks, queues.
14. How is stack implemented using a linked list?
Answer: Stack is implemented by inserting and deleting nodes only at the head (top) of
the linked list.
15. How is queue implemented using a linked list?
Answer: Queue is implemented by inserting at the rear and deleting from the front of the
linked list.
16. What is the advantage of a linked list over an array?
Answer: Linked lists are dynamic in size and allow efficient insertions and deletions
compared to arrays.
17. What is insertion sort using a linked list?
Answer: In insertion sort, elements are inserted into their correct position within the linked
list to maintain a sorted order.

10
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
18. How is polynomial addition done using linked lists?
Answer: Two polynomials represented by linked lists are traversed and like terms are
added node by node to form a resultant linked list.
19. What are the two pointers maintained in a doubly linked list?
Answer: Each node maintains a pointer to the next node and a pointer to the previous
node.
20. What happens if the next pointer of a node is NULL in a singly linked list?
Answer: It indicates that the node is the last node in the singly linked list.

[LONG QUESTIONS]
1. Define and explain the concept of a singly linked list with a diagram.
Answer:
A singly linked list is a collection of nodes where each node contains:
 Data part
 Next pointer to the next node
The last node points to NULL.
Diagram:
[Data|Next] -> [Data|Next] -> [Data|NULL]
2. Write the algorithm to insert a node at the end of a singly linked list.
Answer:
 Create a new node.
 Set its next pointer to NULL.
 Traverse to the last node.
 Set last node’s next to point to the new node.
3. Differentiate between singly linked list and doubly linked list.
Answer:
Feature Singly Linked List Doubly Linked List
Pointer One (next) Two (prev and next)
Traversal Forward only Forward and backward
Memory Less More (extra pointer)
4. What are the advantages of using circular linked lists?
Answer:
 No NULL at end, so easy to move circularly.
 Useful in applications like round-robin scheduling.
 Efficient queue implementations.
5. Explain traversal of a circular linked list.
Answer:
 Start at any node.
 Continue moving to next node.
 Stop when the starting node is encountered again.
6. Explain the basic operations of a doubly linked list.
Answer:
Operations:

11
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
 Insertion (at front, middle, end)
 Deletion (at front, middle, end)
 Traversal (forward and backward) Each operation uses prev and next pointers
carefully.
7. Explain how stack can be implemented using linked list.
Answer:
 Push: Insert at the head.
 Pop: Delete from the head.
 Top of stack is head node.
8. Explain how queue can be implemented using linked list.
Answer:
 Maintain front and rear pointers.
 Enqueue: Insert at rear.
 Dequeue: Delete from front.
9. Write the structure and traversal algorithm of a doubly linked list.
Answer:
Structure:
truct DNode
{
int data;
struct DNode *prev, *next;
};
Traversal:
 Start from head.
 Move using next until NULL.
10. Write short notes on polynomial addition using linked list.
Answer:
 Each term (coefficient and exponent) is a node.
 Compare exponents of two polynomials.
 Add coefficients if exponents match.
 Otherwise, insert node with higher exponent first.
[LANG ]
1. Explain different types of linked lists with their structure and differences.
1. Singly Linked List
 Definition:
In a singly linked list, each node contains two parts:
o Data (the value)
o Next Pointer (address of the next node)
 Structure:
struct Node {
int data;
struct Node* next;
};
 Important Points:
o Traversal is only in one direction (forward).

12
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
o The last node’s next points to NULL.
o Insertion and deletion operations are simple and efficient at the beginning.
2. Circular Linked List
 Definition:
In a circular linked list, the last node points back to the first node instead of NULL.
 Structure:
struct Node
{
int data;
struct Node* next;
};
(Same as singly, but the next of the last node points to head.)
 Important Points:
o No NULL at the end; the list becomes circular.
o Useful for applications that require continuous looping (e.g., round-robin
scheduling).
o Traversal continues indefinitely unless carefully managed.
3. Doubly Linked List
 Definition:
Each node in a doubly linked list contains three parts:
o Data (the value)
o Previous Pointer (address of previous node)
o Next Pointer (address of next node)
 Structure:
struct DNode
{
int data;
struct DNode* prev;
struct DNode* next;
};
 Important Points:
o Allows traversal in both directions (forward and backward).
o Requires extra memory for storing prev pointers.
o More complex insertion and deletion, but more flexible.
4. Circular Doubly Linked List
 Definition:
A circular doubly linked list connects the last node’s next pointer to the first node,
and the first node’s prev pointer to the last node.
 Structure:
struct DNode
{
int data;
struct DNode* prev;
struct DNode* next;
};
13
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
(Same as doubly, but both ends connect.)
 Important Points:
o Traversal can start at any node and move circularly in both directions.
o Used where both infinite forward and backward traversal is required.
Comparison Table
Singly Linked Circular Linked Circular Doubly Linked
Feature Doubly Linked List
List List List
Pointer per
1 (next) 1 (next) 2 (prev, next) 2 (prev, next)
node
Forward Forward and Forward and
Traversal Forward only
(circular) Backward Backward (circular)
Head and Tail
Last Node Points to NULL Points to head Points to NULL
connected
Memory
Less Less More (extra pointer) More
usage
Scheduling Music players,
Applications Simple lists Navigation systems
systems complex navigations
2. Discuss all operations (Insertion, Deletion, Traversal) in singly linked list with
algorithms.
Ans: 1. Insertion Operations
Insertion can happen in three ways:
 At the beginning
 At the end
 After a specific node (in between)
A. Insertion at the Beginning
Algorithm:
1. Create a new node.
2. Set newNode->next = head.
3. Update head = newNode.
Diagram:
New Node -> Old Head -> ...
B. Insertion at the End
Algorithm:
1. Create a new node.
2. Set newNode->next = NULL.
3. If the list is empty, set head = newNode.
4. Else, traverse to the last node.
5. Set lastNode->next = newNode.
Diagram:
Head -> Node -> ... -> Last Node -> New Node (NULL)
C. Insertion After a Specific Node
14
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
Algorithm:
1. Find the node prevNode after which you want to insert.
2. Create a new node.
3. Set newNode->next = prevNode->next.
4. Set prevNode->next = newNode.
Diagram:
... -> prevNode -> newNode -> nextNode -> ...
2. Deletion Operations
Deletion can happen in three ways:
 At the beginning
 At the end
 At a specific position
A. Deletion at the Beginning
Algorithm:
1. Check if the list is empty.
2. Create a temporary pointer temp = head.
3. Update head = head->next.
4. Free temp.
Diagram:
Old Head -> becomes -> head->next
B. Deletion at the End
Algorithm:
1. Check if the list is empty.
2. If there is only one node, free it and set head to NULL.
3. Otherwise, traverse to the second-last node.
4. Free its next node and set secondLastNode->next = NULL.
C. Deletion at a Specific Position
Algorithm:
1. Find the previous node of the node to be deleted.
2. Update prevNode->next = nodeToDelete->next.
3. Free nodeToDelete.
3. Traversal Operation
Traversal is visiting each node exactly once.
Algorithm for Traversal
1. Start with temp = head.
2. While temp != NULL:
o Print or process temp->data.
o Move to the next node (temp = temp->next).
Summary Table
Operation Steps
Insertion at Beginning Create node → Point to head → Update head
Insertion at End Create node → Traverse to end → Link new node

15
 Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
Operation Steps
Insertion After a Node Create node → Link after given node
Deletion at Beginning Free head → Update head
Deletion at End Traverse to second-last → Free last node
Deletion at Position Find previous node → Update links → Free node
Traversal Visit each node till NULL

3. How to implement a stack and a queue using linked list? Explain with diagrams and
pseudo-code.
Ans:
A. Stack Using Linked List
Concept of Stack:
 Stack follows LIFO (Last In First Out) principle.
 Operations:
o Push (Insert at the top)
o Pop (Remove from the top)
Structure of Node:
struct Node
{
int data;
struct Node* next;
};
 data: Value of the stack element.
 next: Pointer to the next node.
Diagram:
Top --> [data|next] -> [data|next] -> [data|next] -> NULL
Pseudo-code for Operations:
Push Operation (Insert at the beginning):
PUSH(stack, value)
1. Create a new node.
2. Set newNode->data = value.
3. Set newNode->next = stack (current top).
4. Update stack = newNode.
Pop Operation (Delete from the beginning):
POP(stack)
1. If stack is empty, Underflow error.
2. Create temp = stack.
3. Update stack = stack->next.
4. Free temp.
Top Element:

16
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
cpp
CopyEdit
TOP(stack)
1. If stack is not empty
2. Return stack->data
Advantages:
 No fixed size (dynamic memory allocation).
 Push and Pop operations are O(1) time.
B. Queue Using Linked List
Concept of Queue:
 Queue follows FIFO (First In First Out) principle.
 Operations:
o Enqueue (Insert at rear)
o Dequeue (Remove from front)
Structure of Node:
struct Node {
int data;
struct Node* next;
};
We need two pointers:
 front (first element)
 rear (last element)
Diagram:

Front --> [data|next] -> [data|next] -> [data|next] -> NULL <-- Rear
Pseudo-code for Operations:
Enqueue Operation (Insert at the end):
ENQUEUE(queue, value)
1. Create a new node.
2. Set newNode->data = value.
3. Set newNode->next = NULL.
4. If queue is empty:
- front = rear = newNode.
5. Else:
- rear->next = newNode.
- rear = newNode.
Dequeue Operation (Delete from the front):
markdown
CopyEdit
DEQUEUE(queue)
1. If queue is empty, Underflow error.
2. Create temp = front.
3. Update front = front->next.
4. If front == NULL:

17
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
- rear = NULL.
5. Free temp.
Peek Front Element:
pgsql
CopyEdit
FRONT(queue)
1. If front is not NULL
2. Return front->data
Advantages:
 No overflow unless memory full.
 Efficient O(1) time for Enqueue and Dequeue.
Summary Table
Structure Stack (Linked List) Queue (Linked List)
Main pointers Top Front and Rear
Insert at Top (Head) Rear (Tail)
Remove from Top (Head) Front (Head)
Principle LIFO FIFO
4. Write a C program to implement insertion and deletion in a doubly linked list. Explain
the logic.
Answer: Logic Explanation
 A doubly linked list has each node pointing both to the next node and the previous
node.
 In Insertion:
o We create a new node and adjust the prev and next pointers carefully.
 In Deletion:
o We find the node to delete and adjust its neighbors’ pointers before freeing
it.
 Careful handling of pointers is very important to avoid memory leaks or
segmentation faults.
Structure of Node
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* prev;
struct Node* next;
};
Program
#include <stdio.h>
#include <stdlib.h>

// Define Node structure

18
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
struct Node {
int data;
struct Node* prev;
struct Node* next;
};

// Head pointer for the list

struct Node* head = NULL;

// Function to create a new node

struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}

// Insertion at the beginning

void insertAtBeginning(int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
head = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
}

// Insertion at the end

void insertAtEnd(int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
head = newNode;
} else {
struct Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}

19
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
// Deletion at the beginning
void deleteAtBeginning() {
if (head == NULL) {
printf("List is empty. Nothing to delete.\n");
return;
}
struct Node* temp = head;
head = head->next;
if (head != NULL) {
head->prev = NULL;
}
free(temp);
}

// Deletion at the end

void deleteAtEnd() {
if (head == NULL) {
printf("List is empty. Nothing to delete.\n");
return;
}
struct Node* temp = head;
if (temp->next == NULL) { // Only one node
free(temp);
head = NULL;
return;
}
while (temp->next != NULL) {
temp = temp->next;
}
temp->prev->next = NULL;
free(temp);
}

// Function to display the list

void displayList() {
struct Node* temp = head;
if (temp == NULL) {
printf("List is empty.\n");
return;
}
printf("Doubly Linked List: ");
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
20
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
printf("NULL\n");
}

// Main function
int main() {
insertAtBeginning(10);
insertAtBeginning(20);
insertAtEnd(5);
displayList(); // 20 <-> 10 <-> 5 <-> NULL

deleteAtBeginning();
displayList(); // 10 <-> 5 <-> NULL

deleteAtEnd();
displayList(); // 10 <-> NULL

return 0;
}
Logic Recap:
 Insertion at Beginning:
New node's next → old head,
Old head's prev → new node,
Update head.
 Insertion at End:
Traverse to last node,
Last node's next → new node,
New node's prev → last node.
 Deletion at Beginning:
Update head to next node,
Set new head's prev → NULL,
Free the old head.
 Deletion at End:
Traverse to last node,
Last node’s previous node’s next → NULL,
Free the last node.
5. Explain polynomial addition using linked lists with example.
Ans: Concept
 In polynomial addition, we add coefficients of terms having the same power of x.
 A linked list is a great way to represent polynomials because:
o Each node can store a coefficient and an exponent.
o The nodes are kept in decreasing order of exponents for easier addition.
Structure of Node
struct Node
{
int coeff; // Coefficient
21
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
int expo; // Exponent
struct Node* next;
};
Each node stores:
 coeff: the coefficient of the term
 expo: the exponent of x
 next: pointer to the next term
Example
Let’s add two polynomials:
Polynomial 1:
5x3+4x2+25x^3 + 4x^2 + 25x3+4x2+2
Polynomial 2:
3x3+x+63x^3 + x + 63x3+x+6
Representation using Linked Lists:
Polynomial 1 Polynomial 2
5→4→2 3→1→6
(x³) (x²) (x⁰) (x³) (x¹) (x⁰)
Each arrow represents a pointer to the next node.
Addition Logic
1. Compare the exponents.
2. If exponents are equal:
o Add their coefficients.
o Store the sum in the result list.
3. If one exponent is greater:
o Copy that term directly to the result.
4. Move to the next term accordingly.
5. Continue till both polynomials are completely traversed.
Step-by-Step Addition
Step Action
Compare 5x³ and 3x³ Exponents equal → Add coefficients: 5+3=8 → Term: 8x³
Compare 4x² and x¹ 2 > 1 → Take 4x² into result
Compare 2x⁰ and x¹ 0 < 1 → Take x¹ into result
Compare 2x⁰ and 6x⁰ 0 = 0 → Add coefficients: 2+6=8 → Term: 8x⁰

Resulting Polynomial:
8x3+4x2+x+88x^3 + 4x^2 + x + 88x3+4x2+x+8
Or represented as linked list:
8x^3 -> 4x^2 -> 1x^1 -> 8x^0 -> NULL
Pseudo-code for Polynomial Addition
ADD(poly1, poly2)

22
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
1. Initialize result list as empty.
2. While both poly1 and poly2 are not NULL:
a. If poly1->expo == poly2->expo:
- Sum the coefficients.
- Create new node with sum and same exponent.
- Move both poly1 and poly2 to next.
b. Else if poly1->expo > poly2->expo:
- Copy poly1's node to result.
- Move poly1 to next.
c. Else:
- Copy poly2's node to result.
- Move poly2 to next.
3. If any list remains, attach it directly to result.
4. Return the result list.
Diagram
Poly1: 5x³ -> 4x² -> 2x⁰ -> NULL
Poly2: 3x³ -> 1x¹ -> 6x⁰ -> NULL

Result: 8x³ -> 4x² -> 1x¹ -> 8x⁰ -> NULL
Polynomial addition using linked lists involves:
 Comparing exponents,
 Adding coefficients if exponents match,
 Otherwise carrying over the larger exponent term,
 Using a linked list structure for dynamic, efficient storage.

MODUL-3
[SORT QUESTION AND ANSWER]

1.Q: Define a tree in data structures.

A: A tree is a non-linear hierarchical data structure consisting of nodes connected by
edges, where one node is the root and every node has zero or more child nodes.

2. Q: What is the root of a tree?

A: The root is the topmost node of a tree and is the only node without a parent.

3. Q: Define leaf node and internal node.

A: A leaf node is a node with no children. An internal node is any node that has at least
one child.

4. Q: What is the height of a tree?

A: The height of a tree is the length of the longest path from the root to any leaf node.

5. Q: What is a subtree?
A: A subtree is any node in a tree along with all of its descendants.

23
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
6. Q: Define parent and child nodes in a tree.
A: In a tree, a node A is the parent of node B if B is directly connected to A one level
below; B is then called the child of A.

7. Q: What is a binary tree?

A: A binary tree is a tree in which each node has at most two children, referred to as the
left and right child.

8. Q: What is an M-way tree?

A: An M-way tree is a generalization of a binary tree where each node can have up to M
children.

9. Q: Name the three common types of binary tree traversals.

A: The three types are Inorder (LNR), Preorder (NLR), and Postorder (LRN) traversals.

10. Q: What is inorder traversal of a binary tree?

A: In inorder traversal, nodes are visited in the order: left subtree, root, right subtree.

11. Q: What is preorder traversal of a binary tree?

A: In preorder traversal, nodes are visited in the order: root, left subtree, right subtree.

12. Q: What is postorder traversal of a binary tree?

A: In postorder traversal, nodes are visited in the order: left subtree, right subtree, root.

13. Q: Which two traversals are needed to reconstruct a unique binary tree?
A: Inorder traversal combined with either preorder or postorder traversal is needed to
reconstruct a unique binary tree.

14. Q: Can a binary tree be reconstructed using only preorder and postorder? Why or why
not?
A: No, because without the inorder sequence, the left and right subtrees cannot be
uniquely identified.

15. Q: What is a Binary Search Tree (BST)?

A: A BST is a binary tree where each node's left subtree contains values less than the
node and the right subtree contains values greater than the node.

16. Q: What is the time complexity of searching in a BST?

A: The average time complexity is O(log n); in the worst case (unbalanced tree), it is
O(n).

17. Q: What are the basic operations in a BST?

A: The basic operations are insertion, deletion, and search.

24
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
18. Q: What is an AVL tree?
A: An AVL tree is a self-balancing binary search tree where the difference in height
between left and right subtrees (balance factor) is at most 1 for all nodes.
19. Q: What is the balance factor in an AVL tree?
A: The balance factor of a node is the height of its left subtree minus the height of
its right subtree.
20. Q: What is a B-Tree and where is it used?
A: A B-Tree is a self-balancing M-way search tree optimized for systems that read
and write large blocks of data, such as databases and file systems.

[LONG QUESTIONS WITH ANS]

1. Q: Explain the key terminologies used in tree data structures with suitable diagrams.

A:

 Root: The topmost node in a tree.

 Parent: A node with children.
 Child: A node descended from another node.
 Leaf: A node with no children.
 Internal Node: A node with at least one child.
 Subtree: A portion of the tree that includes a node and its descendants.
 Height: The length of the longest path from the root to a leaf.
Each term defines the hierarchical relationships and structure of the tree.

2. Q: Differentiate between binary trees and M-way trees with examples.

A:

 Binary Tree: Each node has at most two children (left and right). Example:

markdown
CopyEdit
10
/ \
5 15

 M-way Tree: Each node can have up to M children. Commonly used in B-Trees.
Example (3-way tree):

csharp
CopyEdit
[10 | 20]
/ | \
<10 10-20 >20

25
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
Binary trees are simpler but less space-efficient compared to M-way trees in disk-based
systems.

3. Q: Describe the three depth-first traversals of a binary tree with an example.

A:
Given a binary tree:

mathematica
CopyEdit
A
/\
B C
/\
D E

 Inorder (LNR): D B E A C
 Preorder (NLR): A B D E C
 Postorder (LRN): D E B C A
Each traversal visits nodes in a specific order and is useful for different tree-
processing scenarios.

4. Q: How can a binary tree be reconstructed from inorder and preorder traversals? Explain
with an example.

A:
Given:

 Inorder: D B E A C
 Preorder: A B D E C
Steps:

1. The first node in preorder is the root (A).

2. Find A in inorder → Left: D B E, Right: C.
3. Repeat the process for left and right subtrees.
Final tree:

mathematica
CopyEdit
A
/\
B C
/\
D E

26
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
5. Q: Explain the operations of insertion and search in a Binary Search Tree (BST) with an
example.

A:
Insertion Example (insert 50, 30, 70, 20):

 50 becomes root.
 30 goes left of 50.
 70 goes right of 50.
 20 goes left of 30.
Search:
To search 20: Start at 50 → 30 → 20 (found).
BST maintains sorted order, enabling efficient operations (average O(log n)).

6. Q: What is an AVL tree? Describe the different rotation techniques used for balancing.

A:
An AVL tree is a height-balanced binary search tree where the balance factor of every
node is between -1 and +1.
Rotations:

 LL Rotation: Single right rotation.

 RR Rotation: Single left rotation.
 LR Rotation: Left then right.
 RL Rotation: Right then left.
These rotations restore balance after insertions or deletions.

7. Q: Explain the structure and properties of a B-Tree. How is it different from a BST?

A:

 A B-Tree is a balanced M-way search tree with multiple keys and children in each
node.
 Used in databases and file systems for large-scale data.
 Properties:
o All leaves at same level.
o Node can contain multiple keys.
o Insertion and deletion maintain balance without rotations.
Difference from BST:
 BST is binary, B-Tree is multi-way.
 B-Trees are optimized for disk storage.

8. Q: Describe the insertion process in an AVL tree with example and balancing steps.

A:
Insert: 30, 20, 10

27
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
 Insert 30 → Root
 Insert 20 → Left of 30
 Insert 10 → Left of 20 → LL imbalance
 Apply Right Rotation on 30
Balanced tree:

markdown
CopyEdit
20
/ \
10 30

Balance is restored using LL rotation.

9. Q: What is the difference between height and depth in trees? Explain with examples.

A:

 Height: Longest path from node to a leaf.

 Depth: Path from root to the node.
Example:

css
CopyEdit
A (depth 0)
/
B (depth 1)
/
C (depth 2, height 0)

C’s depth is 2, height is 0. A’s height is 2.

10. Q: Explain postorder traversal using recursion. Write an algorithm for it.

A:
Postorder (LRN) visits the left subtree, right subtree, then root.

Algorithm:

scss
CopyEdit
POSTORDER(node):
if node ≠ NULL:
POSTORDER([Link])

28
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
POSTORDER([Link])
visit(node)

Example Tree:

css
CopyEdit
A
/\
B C

Output: B C A

MODULE-4

[SORT QUESTIONS WITH ANSWERES]

1. Q: What is bubble sort?

A: Bubble sort is a simple comparison-based sorting algorithm that repeatedly
swaps adjacent elements if they are in the wrong order.
2. Q: What is the time complexity of bubble sort in the worst case?
A: The worst-case time complexity of bubble sort is O(n²).
3. Q: What is selection sort?
A: Selection sort is a sorting algorithm that repeatedly finds the minimum element
from the unsorted part and puts it at the beginning.
4. Q: What is the main difference between bubble sort and selection sort?
A: Bubble sort swaps elements multiple times per pass, while selection sort
performs only one swap per pass after finding the minimum.
5. Q: What is quick sort?
A: Quick sort is a divide-and-conquer algorithm that partitions the array around a
pivot and recursively sorts the subarrays.
6. Q: What is the average case time complexity of quick sort?
A: The average time complexity of quick sort is O(n log n).
7. Q: What is merge sort?
A: Merge sort is a divide-and-conquer algorithm that divides the array into halves,
recursively sorts them, and merges the sorted halves.
8. Q: Why is merge sort preferred for linked lists?
A: Merge sort is preferred for linked lists because it does not require random
access and works efficiently using pointers.

29
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
9. : What is linear search?
A: Linear search scans each element of a list one by one until the desired element
is found or the list ends.

9. Q: What is the time complexity of linear search?

A: The time complexity is O(n) in the worst and average cases.
10. Q: What is binary search?
A: Binary search is an efficient algorithm for finding a target in a sorted array by
repeatedly dividing the search interval in half.
11. Q: When can binary search be used?
A: Binary search can be used only on sorted arrays or lists.
12. Q: What is the time complexity of binary search?
A: The time complexity is O(log n).

14. Q: What is a graph?

A: A graph is a collection of vertices (nodes) connected by edges, which can be
directed or undirected.
15. Q: What are adjacent vertices?
A: Two vertices are adjacent if they are connected by an edge.
16. Q: What is the degree of a vertex in a graph?
A: The degree of a vertex is the number of edges connected to it. In a directed
graph, it includes in-degree and out-degree.
17. Q: What is a cycle in a graph?
A: A cycle is a path that starts and ends at the same vertex with no repetition of
edges or vertices (except the start/end).

18. Q: What is an adjacency matrix?

A: An adjacency matrix is a 2D array used to represent a graph where matrix[i][j]
= 1 indicates an edge between vertices i and j.
19. Q: What is an adjacency list?
A: An adjacency list represents a graph using an array or list where each index
stores a list of its neighboring vertices.

20. Q: What is the difference between DFS and BFS?

A: DFS (Depth First Search) explores as far as possible along each branch before
backtracking; BFS (Breadth First Search) explores all neighbors at the current depth
before going deeper.

[LONG QUESTIONS ]

1. Q: Explain the working of Bubble Sort with an example. What is its time complexity?

A:
Bubble sort repeatedly compares and swaps adjacent elements if they are in the wrong
order.
Example (Array: [5, 3, 4, 1]):
30
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
 Pass 1: [3, 4, 1, 5]
 Pass 2: [3, 1, 4, 5]
 Pass 3: [1, 3, 4, 5]
Time Complexity:
 Best: O(n)
 Average/Worst: O(n²)
It is inefficient for large datasets.

2. Q: Describe the Selection Sort algorithm and provide a dry run example.

A:
Selection sort finds the minimum element and swaps it with the beginning element.
Example (Array: [64, 25, 12, 22, 11]):

 Pass 1: [11, 25, 12, 22, 64]

 Pass 2: [11, 12, 25, 22, 64]
 Pass 3: [11, 12, 22, 25, 64]
 Pass 4: [11, 12, 22, 25, 64]
Time Complexity: O(n²) in all cases.

3. Q: Write and explain the steps of the Quick Sort algorithm. Include partitioning logic.

A:
Quick sort uses a pivot to partition the array into two halves and recursively sorts them.
Steps:

1. Choose a pivot (e.g., last element).

2. Rearrange elements so those < pivot come before, and > pivot come after.
3. Recursively apply to subarrays.
Partition Example:
Array: [8, 4, 7, 3]

 Pivot = 3 → Partitioned: [3, 4, 7, 8]

Time Complexity:
 Best/Average: O(n log n)
 Worst (unbalanced): O(n²)

4. Q: Explain Merge Sort with an example. Why is it more efficient than bubble or selection
sort?

A:
Merge sort divides the array into halves, sorts them, and merges them.
Example (Array: [5, 3, 8, 4]):

1. Divide: [5,3] and [8,4] → [5],[3] and [8],[4]

2. Merge: [3,5] and [4,8]

31
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
3. Merge final: [3,4,5,8]
Time Complexity: O(n log n) for all cases.
It is more efficient due to guaranteed divide-and-conquer strategy.

5. Q: Compare Linear Search and Binary Search. Provide their algorithmic steps.

A:

Feature Linear Search Binary Search

Array Type Unsorted/Sorted Sorted only
Time Complexity O(n) O(log n)

Linear Search Steps:

 Traverse from start to end; compare each element.

Binary Search Steps:

1. Find mid.
2. If mid = key, return.
3. If key < mid, search left half; else right.
Repeat until found or exhausted.

6. Q: Explain adjacency matrix and adjacency list representations of a graph with

examples.

A:
Adjacency Matrix:

 2D array where G[i][j] = 1 means edge exists.

 For undirected graph: symmetric matrix.

Example:
Vertices: A, B, C
Edges: A-B, B-C

css
CopyEdit
ABC
A [0 1 0]
B [1 0 1]
C [0 1 0]

Adjacency List:

 Each vertex stores a list of adjacent vertices.

32
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
makefile
CopyEdit
A: B
B: A, C
C: B

7. Q: What is Depth First Search (DFS)? Write its algorithm and give a sample traversal.

A:
DFS explores as far as possible along each branch before backtracking.
Algorithm (Recursive):

scss
CopyEdit
DFS(vertex):
mark vertex visited
for each neighbor:
if not visited:
DFS(neighbor)

Example Graph:
A-B-C
DFS from A → A, B, C
Uses a stack or recursion.

8. Q: Explain Breadth First Search (BFS) with its algorithm and example.

A:
BFS visits all vertices level by level using a queue.
Algorithm:

1. Enqueue starting vertex and mark as visited.

2. While queue not empty:
o Dequeue vertex.
o Visit unvisited neighbors and enqueue them.

Example Graph:
A-B-C
BFS from A → A, B, C
Uses queue data structure.

9. Q: List and explain five important graph terminologies with examples.

33
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST
A:

1. Vertex (Node): A point in a graph.

2. Edge: A line connecting two vertices.
3. Degree: Number of edges incident on a vertex.
4. Path: A sequence of vertices connected by edges.
5. Cycle: A path where the start and end vertex are the same.

Example:
In a triangle graph (A-B-C-A), each vertex has degree 2 and the cycle is A → B → C →
A.

10. Q: Discuss the differences between DFS and BFS with respect to traversal strategy and
use-cases.

A:

Feature DFS BFS

Depth-first
Strategy Level-order (queue)
(stack/recursion)
Memory Low (for sparse graphs) High (stores more neighbors)
Use-case Topological sort, puzzles Shortest path in unweighted graphs
Traversal Goes deep first Explores neighbors first

Both are fundamental graph traversal algorithms with distinct strengths.

[ LONG QUESTION’S ANSWER READ FROM BOOK FOR DETAIL EXPLINATION]

Here are a few important questions from Data Structures to help you prepare for the upcoming exams. Be sincere
in your studies and take care of your health.
– Bhabani Prasad Mishra

34
Data Structure IMP Q & Ans for [Link] -2nd sem.
By : [Link], CSE, NIST

35