E-Content
Program
: Computer Technology Program Code : CM-3-K
Name
Course Title : Data Structure Using ‘C’ (DSU) Course Code : 313301
Semester : III
CO1 : Perform basic operations on Arrays.
CO2 : Apply different Searching and Sorting methods.
CO3 : Implement basic operations on Linked List.
Q. No.
UNIT I. Introduction to DS
1. Explain following terms:
i) Time complexity ii) Space Complexity.
Ans. ) Time Complexity:
The amount of time is required to execute an algorithm or program is called as Time Complexity.
It is expressed using Big O notation, such as:
O(1) – Constant time (independent of input size)
O(n) – Linear time
O(n^2) – Quadratic time
O(log n) – Logarithmic time
ii) Space Complexity:
The amount of space or memory is required to execute and store an algorithm or program is called as
Space Complexity.
It includes memory for variables, data structures, function calls, etc.
Also expressed in Big O notation, like:
O(1) – Constant space
O(n) – Space grows linearly with input
O(n^2) – Space grows quadratically
2. List the operations performed on Data Structures?
Ans. 1. Inserting: Adding a new data in the data structure is referred as insertion.
2. Deleting: Removing a data from the data structure is referred as deletion.
3. Sorting: Arranging the data in some logical order (ascending or descending, numerically or
alphabetically).
4. Searching: Finding the location of data within the data structure which satisfy the searching
condition.
5. Traversing: Accessing each data exactly once in the data structure so that each data item is traversed
or visited.
6. Merging: Combining the data of two different sorted files into a single sorted file.
7. Copying: Copying the contents of one data structure to another.
8. Concatenation: Combining the data from two or more data structure.
3. Classify Data Structures?
Ans.
4. Differentiate between linear and non-linear data structures on any two parameters.
Ans. Sr.
No. Linear data structure Non-linear data structure
1 A data structure in which all data elements are A data structure in which all data elements are
stored in a sequence is known as linear data not stored in a sequence is known as non-linear
structure. data structure.
2 All elements are stored in contiguous memory All elements may stored in non-contiguous
locations inside memory. memory locations inside memory.
3 Example:- stack, queue Example:- tree, graph
5. Write C program for performing following operations on array: insertion, display.
Ans. #include<stdio.h>
#include<conio.h>
void main()
{
int a[10], x, i, n, pos;
clrscr();
printf(“Enter the number of array element\n”);
scanf(“%d”,&n);
printf(“Enter the array with %d element\n”, n);
for(i=0;i<n;i++)
{
scanf(“%d”,&a[i]);
}
printf(“Enter the key value and its position\n”);
scanf(“%d%d” ,&x,&pos);
for(i=n; i >= pos; i--)
{
a[i]=a[i-1];
}
a[pos-1]=x;
printf(“Array elements are:\n “);
for(i=0;i<n+1;i++)
{
printf(“%d\t”,a[i]);
}
getch();
}
Q. No.
UNIT II. Searching and Sorting
1. Find the position of element 29 using Binary Search method in an array ‘A’ as given below :
A = {11, 5, 21, 3, 29, 17, 2, 43}
Ans. An array which is given A[ ]= {11,5,21,3,29,17,2,43} is not in sorted manner, first we need to sort
them in order;
So an array will be A[ ]={2,3,5,11,17,21,29,43} and the value to be searched is VAL =29.
The binary search algorithm will proceed in the following manner.
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
2 3 5 11 17 21 29 43
Iteration 1:
LOW = 0, HIGH = 7,
So, MID = LOW+HIGH/2
= (0 + 7) / 2 = 3
Now, VAL = 29 and A[MID] = A[3] =11
i.e, 29!=17 and 29 > 11
Therefore, we now search for the value in the second half of the array.
So, we need to change the values of LOW as LOW=MID+1.
Iteration 2:
Now,
LOW = MID + 1= 3+1= 4,
HIGH = 7,
So, MID = (4 + 7)/2 =11/2 = 5;
VAL = 29 and A [MID] =A [5] = 21
i.e 29!=21 and 29>21
Therefore, we now search for the value in the second half of the array.
So, again we need to change the values of LOW as LOW= MID +1.
Iteration 3:
Now,
LOW = MID + 1 = 5+1= 6,
HIGH = 7,
So MID = (6 + 7)/2 = 6
Now, VAL = 29 and A [MID] =A [6]=29
i.e 29=29
So, Element 29 is found after 3 comparisons and at 6th position in given array.
2. Differentiate between binary search and sequential search (linear search).
Ans. Sr. Binary Search Sequential Search / Linear Search
No.
1 Input data needs to be sorted in Binary Search Input data need not to be sorted in Linear Search.
2 In contrast, binary search compares key value A linear search scans one item at a time, without
with the middle element of an array and if jumping to any item.
comparison is unsuccessful then cuts down
search to half.
3 Binary search implements divide and conquer Linear search uses sequential approach.
approach.
4 In binary search the worst case Complexity is In linear search, the worst case Complexity is
O(log n)comparisons. O(n) comparisons.
5 Binary search is efficient for the larger array. Linear search is efficient for the smaller array.
3. Define Sorting and list its methods?
Ans. Sorting is the process of arranging elements in a specific order, usually in ascending or descending order.
It is commonly applied to arrays, lists, or any collection of data.
Sorting helps in searching, report generation, and data analysis.
Sorting Methods:
1. Bubble Sort 2. Selection Sort 3. Insertion Sort 4. Merge Sort
5. Quick Sort 6. Radix Sort
4. Write a program to search a particular data from the given array using Linear Search.
Ans. #include <stdio.h> /* Linear search begins */
void main() for (i = 0; i < n ; i++)
{ {
int array[10]; if (key = = array[i] )
int i, n, key, found = 0; {
found = 1;
printf("Enter the number of elements "); break;
scanf("%d", &n); }
}
printf("Enter the %d elements in an array:”,n); if (found == 1)
for (i = 0; i < n; i++) {
{ printf("Element is present in the array at position
scanf("%d", &array[i]); %d", i+1);
} }
printf("Enter the element to be searched "); else
scanf("%d", &key); {
printf("Element is not present in the array");
}
getch( );
}
5. Sort the following array in ascending order using Bubble Sort Method:
A: 348, 14, 614, 5381, 47.
Ans. Array before Sorting is: { 348 14 614 5381 47 }
Pass 1: 348 14 614 5381 47
14 348 614 5381 47
14 348 614 5381 47
14 348 614 5381 47
After Pass 1: 14 348 614 47 5381
Pass 2: 14 348 614 47 5381
14 348 614 47 5381
14 348 614 47 5381
After Pass 2: 14 348 47 614 5381
Pass 3: 14 348 47 614 5381
14 348 47 614 5381
After Pass 3: 14 47 348 614 5381
Sorted Array after '3' passes is
A = { 14 47 348 614 5381 }
Q. No.
UNIT III. Linked List
1. Create a singly linked list using data fields 10, 20, 30, 40, 50. Search a node 40 from the SLL and
show procedure step-by-step with the help of diagram from start to end.
Ans. To Search a data field in singly linked list, need to start searching the data field from first node of singly
linked list.
ORIGINAL LIST:
SEARCHING A NODE 40
STEP 1:
40
Compare 40 with first node i.e. 10
But 40!=10
So, move to next node.
STEP 2:
40
Compare 40 with second node i.e. 20
But 40!=20
So, move to next node.
STEP 3:
40
Compare 40 with third node i.e. 30
But 40!=30
So, move to next node.
STEP 4:
40
Compare 40 with fourth node i.e. 40
here 40 = 40
So, Searching is successful i.e node 40 is found at 4th location.
2. Write an algorithm to insert a new node at the beginning of the singly circular linked list.
Ans. Algorithm
Step 1: Start
Step 2: Create a new node with the given data.
Step 3: If the circular linked list is empty (head is None):
• Set the new node as the head.
• Make the new node point to itself: newnode->next = newnode
Step 4: Else (circular linked list is not empty):
• Find the last node in the circular linked list.
• Set the new node as the new head:
a. Set newnode->next = head->next
b. Update the head pointer: head = newnode
• Make the last node point to the new head to maintain the circular structure:
a. Traverse the list to find the last node.
b. Set the lastnode->next = head
Step 5: Stop
3. Compare Linked List and Array (any 4 points).
Ans.
Array Linked list
An array is a collection of elements of a similar A linked list is a collection of objects known as a
data type. node where node consists of two parts, i.e., data
and address.
Array elements store in a contiguous memory Linked list elements can be stored anywhere in
location. the memory or randomly stored.
Array works with a static memory. Here static The Linked list works with dynamic memory.
memory means that the memory size is fixed and Here, dynamic memory means that the memory
cannot be changed at the run time. size can be changed at the run time according to
our requirements.
Array elements are independent of each other. Linked list elements are dependent on each
other. As each node contains the address of the
next node so to access the next node, we need to
access its previous node.
Array takes more time while performing any Linked list takes less time while performing any
operation like insertion, deletion, etc. operation like insertion, deletion, etc.
Accessing any element in an array is faster as the Accessing an element in a linked list is slower as
element in an array can be directly accessed it starts traversing from the first element of the
through the index. linked list.
In the case of an array, memory is allocated at In the case of a linked list, memory is allocated
compile-time. at run time.
Memory utilization is inefficient in the array. For Memory utilization is efficient in the case of a
example, if the size of the array is 6, and array linked list as the memory can be allocated or
consists of 3 elements only then the rest of the deallocated at the run time according to our
space will be unused. requirement.
4. Define the terms: 1) Data Field 2) Next Pointer
Ans.
Data Next
Node
1) Data: The data field is the part of a data structure (like a node in a linked list) that stores the
actual data or value.
2) Next Pointer or Reference: The next pointer (or link field) is the part of a node that stores the
address (or reference) of the next node in the structure.
5. Write an algorithm to count number of nodes in Singly Linked List?
Ans. Function to count number of nodes in a given singly linked list.
For example, the function should return 5 for linked list 1->3->1->2->1.
Algorithm: Using Iterative Solution
1) Start
2) Initialize count as 0
3) Initialize a node pointer, current = head.
4) Do following while current is not NULL
a) current = current -> next
b) count++;
5) Return count
6) Stop
6. Write a structure of Singly Linked List and Doubly Linked List?
Ans. SLL:
struct node
{
int data;
struct node *next;
};
DLL:
struct node
{
int data;
struct node *next;
struct node *prev;
};
Following are the important terms to understand the concept of Singly and Doubly linked list.
Link − Each link of a linked list can store a data called an element.
Next − Each link of a linked list contains a link to the next link called Next.
Prev − Each link of a linked list contains a link to the previous link called Prev.
