Solutions for: assignment_3_4_2024_25_DSU[1].pdf Source file: uploaded PDF.

Citation:
■filecite■turn1file0■

Q.1 Draw the diagram of a circular queue with front and rear pointers.
Answer (diagram + explanation): 1) A circular queue is a linear data structure that uses a single,
fixed-size buffer as if it were connected end-to-end (circularly). Two pointers (indices) are used:
FRONT (index of the front element) and REAR (index of the last element).
ASCII diagram (array indexed 0..n-1): Index: 0 1 2 3 4
[A]--->[B]--->[C]--->[D]--->[E]
When REAR reaches the last index, next position is 0 if there is free space. Operations: - Enqueue:
REAR = (REAR + 1) % SIZE; insert at REAR. - Dequeue: remove at FRONT; FRONT = (FRONT + 1) % SIZE.
Empty condition: FRONT == -1 (or FRONT == REAR + 1 depending on implementation). Full condition:
(REAR + 1) % SIZE == FRONT.
--------------------------------------------------------------------------------
Q.2 Describe the working of the Bubble sort method with an example.
Answer: Bubble sort repeatedly steps through the list, compares adjacent elements and swaps them if
they are in the wrong order. Each pass moves the largest unsorted element to its final position.
Algorithm (ascending): 1. For i from 0 to n-2: For j from 0 to n-2-i: If A[j] > A[j+1],
swap A[j] and A[j+1]
Example: Sort [5, 1, 4, 2, 8] Pass 1: [1, 4, 2, 5, 8] (5 bubbled to position 3) Pass 2: [1, 2, 4, 5,
8] Pass 3: [1, 2, 4, 5, 8] (no swaps => sorted)
Time complexity: O(n^2) worst and average; O(n) best (optimized with a swap flag).
--------------------------------------------------------------------------------
Q.3 Write an algorithm to traverse a linked list.
Answer (pseudocode): 1. Set PTR = head 2. While PTR != NULL: a) Process PTR->data (print or use
it) b) PTR = PTR->next 3. End
This visits each node exactly once. Time complexity: O(n).
--------------------------------------------------------------------------------
Q.4 Explain Queue overflow and underflow conditions with examples.
Answer: - Overflow: occurs when attempting to enqueue into a full queue (no free space). Example:
Array-based queue with size 5 and 5 elements already; calling enqueue causes overflow.
- Underflow: occurs when attempting to dequeue from an empty queue. Example: calling dequeue on a
queue with FRONT == -1 or FRONT > REAR (empty condition).
--------------------------------------------------------------------------------
Q.5 Describe time and space complexity with examples of each.
Answer: - Time complexity measures how running time grows with input size (n). Expressed using
Big-O. Examples: Linear search O(n), Binary search O(log n), Insertion sort O(n^2), Quick sort O(n
log n) average.
- Space complexity measures extra memory used (excluding input). Examples: Iterative reversing of
array uses O(1) extra space; Merge sort requires O(n) extra space.
Always state best/average/worst cases when relevant.
--------------------------------------------------------------------------------
Q.6 Describe the working of radix sort with an example.
Answer: Radix sort sorts numbers by processing individual digits. LSD (least significant digit)
radix sort uses a stable sort (like counting sort) by digit from least significant to most.
Example: Sort [170, 45, 75, 90, 802, 24, 2, 66] using base 10 (LSD radix): - Sort by units digit:
[170, 90, 802, 2, 24, 45, 75, 66] - Sort by tens digit: [802, 2, 24, 45, 66, 170, 75, 90] - Sort by
hundreds digit: [2, 24, 45, 66, 75, 90, 170, 802]
Time complexity: O(d*(n + b)) where d=#digits and b=base. For fixed digit size, O(n).
--------------------------------------------------------------------------------
Q.7 Write an algorithm to insert a new node at the beginning and end of the singly linked list.
Answer: Insert at beginning: 1. Create newNode. 2. newNode->data = value 3. newNode->next = head 4.
head = newNode Insert at end: 1. Create newNode with next = NULL 2. If head == NULL: head = newNode;
return 3. PTR = head 4. While PTR->next != NULL: PTR = PTR->next 5. PTR->next = newNode
Time: O(1) for insert-at-beginning, O(n) for insert-at-end (without tail pointer).
--------------------------------------------------------------------------------
Q.8 Write a ‘C’ program to calculate the factorial of a number using recursion.
Answer (C code):
```c #include <stdio.h> long factorial(int n) { if (n <= 1) return 1; return n *
factorial(n-1); } int main(){ int n; printf("Enter n: "); scanf("%d", &n); if (n<0)
printf("Factorial not defined for negative numbers\n"); else printf("%ld\n", factorial(n));
return 0; } ```
--------------------------------------------------------------------------------
Q.9 Write a ‘C’ program to generate a Fibonacci series of numbers using recursion.
Answer (C code):
```c #include <stdio.h> int fib(int n){ if(n==0) return 0; if(n==1) return 1; return
fib(n-1) + fib(n-2); } int main(){ int i, n; printf("Enter number of terms: ");
scanf("%d", &n); for(i=0;i<n;i++) printf("%d ", fib(i)); printf("\n"); return 0; } ```
Note: Recursive Fibonacci is exponential time; use iterative DP for large n.
--------------------------------------------------------------------------------
Q.10 Write a ‘C’ program to calculate GCD of two numbers using recursion.
Answer (C code using Euclid's algorithm):
```c #include <stdio.h> int gcd(int a, int b){ if(b==0) return a; return gcd(b, a % b); }
int main(){ int a,b; printf("Enter two numbers: "); scanf("%d %d", &a, &b);
printf("GCD = %d\n", gcd(a,b)); return 0; } ```
--------------------------------------------------------------------------------
Q.11 Describe a circular linked list with a suitable diagram. Also state advantage of circular
linked list over linear linked list.
Answer: A circular linked list is a list where the last node points back to the first node (no NULL
at end). ASCII diagram: Head -> [A] -> [B] -> [C] ^ |
|--------------| Advantages: - Can traverse the entire list starting at any node and come back to
it. - Useful for round-robin scheduling and buffering. - No need to check for NULL when looping (but
must stop after full cycle).
--------------------------------------------------------------------------------
Q.12 Write a program to implement a stack with push, pop and display operations.
Answer (C code - array implementation):
```c #include <stdio.h> #define MAX 100 int stack[MAX], top = -1; void push(int x){
if(top==MAX-1){ printf("Stack Overflow\n"); return; } stack[++top] = x; } int pop(){
if(top==-1){ printf("Stack Underflow\n"); return -1; } return stack[top--]; } void display(){
if(top==-1){ printf("Empty\n"); return; } for(int i=top;i>=0;i--) printf("%d ", stack[i]);
printf("\n"); } int main(){ int choice,x; while(1){ printf("[Link] [Link] [Link]
[Link]\n"); scanf("%d", &choice); if(choice==1){ scanf("%d", &x); push(x);}
else if(choice==2) printf("Popped: %d\n", pop()); else if(choice==3) display(); else
break; } return 0; } ```
--------------------------------------------------------------------------------
Q.13 Write an algorithm to search an element in a linked list.
Answer (pseudocode): 1. PTR = head 2. While PTR != NULL: if PTR->data == key: return PTR (or
index) PTR = PTR->next 3. Return NOT FOUND
Time: O(n)
--------------------------------------------------------------------------------
Q.14 Describe selection sort method. Also sort input list using selection sort: 50, 24, 5, 12, 30
Answer: Selection sort repeatedly selects the minimum (for ascending) from the unsorted portion and
swaps it into place.
Steps on [50,24,5,12,30]: Pass1: min=5 -> swap 50 & 5 => [5,24,50,12,30] Pass2: min among
[24,50,12,30] is 12 -> swap 24 & 12 => [5,12,50,24,30] Pass3: min among [50,24,30] is 24 -> swap 50
& 24 => [5,12,24,50,30] Pass4: min among [50,30] is 30 -> swap => [5,12,24,30,50] Sorted.
Time: O(n^2).
--------------------------------------------------------------------------------
Q.15 Write an algorithm to delete a node at the beginning from a singly Linked List.
Answer: 1. If head == NULL: list empty, return 2. temp = head 3. head = head->next 4. free(temp)
Time: O(1)
--------------------------------------------------------------------------------
Q.16 Implement a C program to insert an element in an array.
Answer (C code - insert at position):
```c #include <stdio.h> int main(){ int arr[100], n, pos, val, i; printf("Enter n: ");
scanf("%d", &n); for(i=0;i<n;i++) scanf("%d", &arr[i]); printf("Enter position (0-based) and
value: "); scanf("%d %d", &pos, &val); if(pos<0 || pos>n){ printf("Invalid position\n"); return
0; } for(i=n; i>pos; i--) arr[i] = arr[i-1]; arr[pos] = val; n++; printf("Array after
insertion: "); for(i=0;i<n;i++) printf("%d ", arr[i]); printf("\n"); return 0; } ```
--------------------------------------------------------------------------------
Q.17 Write an algorithm to delete an intermediate node in a singly linked list.
Answer (delete node with given key): 1. If head==NULL: return 2. If head->data == key: delete at
beginning (see Q15) 3. PTR = head While PTR->next != NULL and PTR->next->data != key: PTR
= PTR->next 4. If PTR->next == NULL: key not found Else: temp = PTR->next; PTR->next =
temp->next; free(temp)
Time: O(n)
--------------------------------------------------------------------------------
Q.18 Explain the concept of circular Queue along with its need.
Answer: A circular queue treats the array as circular, reusing freed positions at the start when
REAR reaches the end. Need: to utilize array space efficiently when multiple enqueues/dequeues
occur; avoids shifting.
Enqueue: if (REAR+1)%SIZE == FRONT -> full. Dequeue: FRONT = (FRONT+1)%SIZE.
--------------------------------------------------------------------------------
Q.19 Define the terms ‘overflow’ and ‘underflow’ with respect to stack.
Answer: - Stack overflow: trying to push into a full stack (top == MAX-1 for array-based). - Stack
underflow: trying to pop from an empty stack (top == -1).
--------------------------------------------------------------------------------
Q.20 Implement a C program to search a particular data from the given array using Linear Search.
Answer (C code):
```c #include <stdio.h> int main(){ int n, arr[100], i, key, found=0; scanf("%d", &n);
for(i=0;i<n;i++) scanf("%d", &arr[i]); scanf("%d", &key); for(i=0;i<n;i++){
if(arr[i]==key){ printf("Found at index %d\n", i); found=1; break; } } if(!found)
printf("Not Found\n"); return 0; } ```
--------------------------------------------------------------------------------
Q.21 Compare Linked List and Array.
Answer: - Arrays: contiguous memory, random access O(1), fixed size, insertion/deletion costly O(n)
(shifting). - Linked List: nodes scattered, sequential access O(n), dynamic size, easy O(1)
insertion/deletion at known location (no shifting), extra memory for pointers.
--------------------------------------------------------------------------------
Q.22 Implement a C program to insert element into the queue and delete the element from the Queue.
Answer (C code - circular queue using array):
```c #include <stdio.h> #define SIZE 5 int q[SIZE], front=-1, rear=-1; void enqueue(int x){
if((rear+1)%SIZE==front){ printf("Queue Overflow\n"); return; } if(front==-1) front=0; rear
= (rear+1)%SIZE; q[rear]=x; } int dequeue(){ if(front==-1){ printf("Queue Underflow\n"); return
-1; } int val = q[front]; if(front==rear) front=rear=-1; else front=(front+1)%SIZE;
return val; } int main(){ enqueue(10); enqueue(20); enqueue(30); printf("Dequeued: %d\n",
dequeue()); return 0; } ```
--------------------------------------------------------------------------------
Q.23 Explain the concept of recursion using stack.
Answer: Each recursive call is pushed onto the call stack with its local variables and return
address. When the function returns, its stack frame is popped. Example: computing factorial(4) will
push frames for 4,3,2,1; return unwinds.
--------------------------------------------------------------------------------
Q.24 Show with suitable diagrams how to delete a node from singly linked list at the beginning, in
between and at the end of the list.
Answer: - Delete at beginning: head -> A -> B -> C. Remove A: head = head->next. - Delete in between
(node X): adjust previous->next = X->next; free X. - Delete at end: traverse to node before last
(prev), prev->next = NULL; free last. (ASCII diagrams omitted for brevity; same pointer updates as
described.)
--------------------------------------------------------------------------------
Q.25 Write algorithm for preorder traversal of binary tree.
Answer (recursive): Preorder(node): if node == NULL: return visit(node) Preorder(node->left)
Preorder(node->right)
Example: For tree root with left and right children, preorder visits root, left-subtree, right-
subtree.
--------------------------------------------------------------------------------
Q.6 Describe the working of radix sort with an example.
Answer: Radix sort sorts numbers by processing individual digits. LSD (least significant digit)
radix sort uses a stable sort (like counting sort) by digit from least significant to most.
Example: Sort [170, 45, 75, 90, 802, 24, 2, 66] using base 10 (LSD radix): - Sort by units digit:
[170, 90, 802, 2, 24, 45, 75, 66] - Sort by tens digit: [802, 2, 24, 45, 66, 170, 75, 90] - Sort by
hundreds digit: [2, 24, 45, 66, 75, 90, 170, 802]
Time complexity: O(d*(n + b)) where d=#digits and b=base. For fixed digit size, O(n).
--------------------------------------------------------------------------------
Q.27 Differentiate between Stack and Queue (any four points)
Answer: 1. Order: Stack = LIFO (last-in-first-out); Queue = FIFO (first-in-first-out) 2. Operations:
Stack uses push/pop; Queue uses enqueue/dequeue 3. Typical use: Stack -> recursion, expression
evaluation; Queue -> scheduling, buffering 4. Access: Stack top only; Queue both ends for
enqueue/dequeue (front and rear)
--------------------------------------------------------------------------------
Q.28 Explain node structure for single linked list. Also write advantages of singly list over array.
Answer: Node structure typically: struct Node { int data; struct Node *next; }; Advantages over
array: dynamic size, efficient insertion/deletion (O(1) if position known), no contiguous memory
requirement.
--------------------------------------------------------------------------------
Q.29 With a neat sketch explaining the working of the priority queue.
Answer: A priority queue is an abstract data type where each element has a priority. Dequeue removes
element with highest (or lowest) priority. Representation: often implemented with a binary heap.
Example (max-priority): insert items with priorities and extract max.

--------------------------------------------------------------------------------
Q.30 Explain Binary Search Tree (BST) with an example.
Answer: A BST is a binary tree where for each node, left subtree keys < node key < right subtree
keys. Example (insert 50,30,70,20,40,60,80): 50 / \ 30 70 / \ / \ 20 40
60 80 Search, insert, delete operations use this property. Average time O(log n) for balanced tree.
--------------------------------------------------------------------------------
Q.31 Describe working of linear search with an example.
Answer: Linear search checks each element sequentially until a match is found or end reached.
Example: Search 12 in [5,12,7,9] -> compare 5 (no), compare 12 (yes) -> found at index 1. Time:
O(n).
--------------------------------------------------------------------------------
Q.32 Compare linear list with circular list.
Answer: - Linear list: last node points to NULL; circular list: last node points to first node. -
Traversal of linear list ends at NULL; circular list can loop infinitely if no stop condition. -
Circular lists are useful for round-robin; linear lists are simpler for one-pass processing.
--------------------------------------------------------------------------------
Q.33 Differentiate between linear and non-linear data structure.
Answer: - Linear DS: elements arranged sequentially (arrays, lists, stacks, queues); each element
has single predecessor/successor (except ends). - Non-linear DS: elements related in hierarchical
fashion (trees, graphs); elements can have multiple relationships.
--------------------------------------------------------------------------------
Q.34 Write a ‘C’ program for insert and delete operations to be performed on queue.
Answer: Same as Q.22 (circular queue implementation). See code provided in Q.22.
--------------------------------------------------------------------------------
Q.35 Write a ‘C’ program for insertion sort. Sort array: 30 10 40 5
Answer (explain + code): Insertion sort builds a sorted subarray by inserting each element into its
correct position. Steps on [30,10,40,5]: - i=1 (key=10): shift 30 -> [10,30,40,5] - i=2 (key=40): no
shift -> [10,30,40,5] - i=3 (key=5): shift 40,30,10 -> [5,10,30,40]
C code: ```c #include <stdio.h> void insertionSort(int a[], int n){ for(int i=1;i<n;i++){
int key=a[i], j=i-1; while(j>=0 && a[j]>key){ a[j+1]=a[j]; j--; } a[j+1]=key; }
} int main(){ int a[]={30,10,40,5}, n=4; insertionSort(a,n); for(int i=0;i<n;i++) printf("%d ",
a[i]);} ```
--------------------------------------------------------------------------------
Q.36 Write a menu driven C program to implement stack using array (push,pop,display,exit).
Answer: See code in Q.12 (same array-based stack). That code is menu-driven.
--------------------------------------------------------------------------------
Q.37 Write the C function for (i) searching a node in singly linked list (ii) counting number of
nodes.
Answer (C functions):
```c // (i) search struct Node* search(struct Node* head, int key){ struct Node* p = head;
while(p){ if(p->data==key) return p; p=p->next; } return NULL; } // (ii) count nodes int
countNodes(struct Node* head){ int c=0; struct Node* p=head; while(p){ c++; p=p->next; }
return c; } ```
--------------------------------------------------------------------------------
Q.38 State any two differences between linear search and binary search.
Answer: 1. Linear search works on unsorted lists; binary search requires sorted list. 2. Linear
search time O(n); binary search time O(log n).
--------------------------------------------------------------------------------
Q.39 Define term pointer and null pointer.
Answer: - Pointer: a variable that stores memory address of another variable (e.g., int *p;). - Null
pointer: a special pointer value that points to nothing (NULL). Used to indicate end or 'no object'.
--------------------------------------------------------------------------------
Q.11 Describe a circular linked list with a suitable diagram. Also state advantage of circular
linked list over linear linked list.
Answer: A circular linked list is a list where the last node points back to the first node (no NULL
at end). ASCII diagram: Head -> [A] -> [B] -> [C] ^ |
|--------------| Advantages: - Can traverse the entire list starting at any node and come back to
it. - Useful for round-robin scheduling and buffering. - No need to check for NULL when looping (but
must stop after full cycle).
--------------------------------------------------------------------------------
Q.41 Implement a ‘C’ program to insert an element into the queue and delete the element from the
queue.
Answer: See queue implementation in Q.22. (Circular queue code provided earlier.)
--------------------------------------------------------------------------------