Bachelor Computer Application (BCA)
Data Structure
Most important question banks
Unit : 1
1.Difference between primitive and non-primitive data structure:
Primitive data structure | Non primitive data structure |
1) Primitive data structure is a kind of data structure that stores the data of only one type. | Non-primitive data structure is a type of data structure that can Store the data of more than one type. |
2) Example of primitive data structure are integer, character, float, etc.. | Example of non- primitive data Structures are Array, Linked list, Stack, Queue. |
3)It Starts with a lowercase character. | It Starts with an uppercase character. |
4)Primitive data structure will contain some value. (it can’t be null) | Non primitive data structure can consist of a null value. |
5) Size depends on the type of the Data structure. | In case of non-primitive data Structure size is not fixed. |
2.Explain Advantages of Data Structure:
• Data structure helps in efficient storage of data in the storage device.
• Data structure usage provides convenience while retrieving the data from storage device.
• Data structure provides effective and efficient processing of small as well as large amount of data.
• Usage of proper data structure can help programmer save lots of time or processing time while operations such as storage, retrieval or processing of data.
• Manipulation of large amount of data can be carried out easily with the use of good data structure approach.
• Most of the well-organized data structures like Array, stack, queues, graph, tree, linked list has well-built and pre-planned approach for operations like storage, addition, retrieval, manipulation, deletion, etc. While using them, programmer can be completely rely on these data structures.
• Data structure usage can simply encourage reusability in long run as well.
3.Explain Dataflow of an Algorithm, and why we need
algorithms.
Problem: A problem can be a real-world problem or any instance from the real-world problem for which we need to create a program or the set of instructions. The set of instructions is known as an algorithm.
• Algorithm: An algorithm will be designed for a problem which is a step-by-step procedure.
• Input: After designing an algorithm, the required and the desired inputs are provided to the algorithm
• Processing unit: The input will be given to the processing unit, and the processing unit will produce the desired output.
• Output: The output is the outcome or the result of the program. We need algorithms because of the following reasons: -
• Scalability: It helps us to understand the scalability. When we have a big real-world problem, we need to scale it down into small-small steps to easily analyze the problem.
• Performance: The real-world is not easily broken down into smaller steps. If the problem, can be easily broken into smaller steps means that the problem is feasible.
4.Explain space and time complexity of an algorithms.
Suppose X is treated as an algorithm and N is treated as the size of input data, the time and space implemented by the Algorithm X are the two main factors which determine the efficiency of X.
• Time Factor − The time is calculated or measured by counting the number of key operations such as comparisons in sorting algorithm.
• Space Factor − The space is calculated or measured by counting the maximum memory space required by the algorithm.
• The complexity of an algorithm f(N) provides the running time and / or storage space needed by the algorithm with respect of N as the size of input data.
• Space Complexity
• Space complexity of an algorithm represents the amount of memory space needed the algorithm in its life cycle.
• Space needed by an algorithm is equal to the sum of the following two components: -
-> Fixed part
-> Variable part
• A fixed part that is a space required to store certain data and variables (i.e. simple variables and constants, program size etc.), that are not dependent of the size of the problem.
• A variable part is a space required by variables, whose size is totally dependent on the size of the problem. For example, recursion stack space, dynamic memory allocation etc.
• Space complexity S(p) of any algorithm p is S(p) = A + Sp(I) Where A is treated as the fixed part and S(I) is treated as the variable part of the algorithm which depends on instance characteristic I. Following is a simple example that tries to explain the concept.
Unit :2
5. What is Array? Explain in detail .
∙ Array is a container which can hold a fix number of items and these items should be of the same type.
∙ An array is a collection of homogeneous (same type) data items stored in contiguous memory locations.
∙ Element − Each item stored in an array is called an element.
∙ Index − Each location of an element in an array has a numerical index, which is used to identify the element.
Why we need an array?
Array is particularly useful when we are dealing with lot of variables of the same type. For example, let’s say I need to store the marks in math subject of 100 students. To solve this particular problem, either I have to create the 100 variables of int type or create an array of int type with the size 100.
Obviously the second option is best, because keeping track of all the 100 different variables is a tedious task. On the other hand, dealing with array is simple and easy, all 100 values can be stored in the same array at different indexes (0 to 99).
6.What is Stack ? Explain Stack in detail.
∙ A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has one end.
∙ It contains only one pointer top pointer pointing to the topmost element of the stack. ∙ Whenever an element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack.
∙ In other words, a stack can be defined as a container in which insertion and deletion can be done from the one end known as the top of the stack.
Working of Stack
∙ Stack works on the LIFO pattern. As we can observe in the below figure there are five memory blocks in the stack; therefore, the size of the stack is 5.
∙ Suppose we want to store the elements in a stack and let's assume that stack is empty. We have taken the stack of size 5 as shown below in which we are pushing the elements one by one until the stack becomes full.
∙ The following are some common operations implemented on the stack:
∙ push(): When we insert an element in a stack then the operation is known as a push. If the stack is full then the overflow condition occurs.
∙ pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no element exists in the stack, this state is known as an underflow state.
∙ is Empty(): It determines whether the stack is empty or not.
∙ is Full(): It determines whether the stack is full or not.'
∙ peek(): It returns the element at the given position.
∙ count(): It returns the total number of elements available in a stack.
∙ change(): It changes the element at the given position.
∙ display(): It prints all the elements available in the stack.
7. Explain in detail : Representation of an Array.
Arrays can be declared in various ways in different languages. For illustration, let's take C array declaration.
As per the above illustration, following are the important points to be considered.
● Index starts with 0.
● Array length is 10 which means it can store 10 elements.
● Each element can be accessed via its index. For example, we can fetch an element at index 6 as 27.
Basic Operations :
Following are the basic operations supported by an array.
● Traverse − print all the array elements one by one.
● Insertion − Adds an element at the given index.
● Deletion − Deletes an element at the given index.
● Search − Searches an element using the given index or by the value.
● Update − Updates an element at the given index.
8.write Advantages and Dis-advantages of an array.
Advantages:
● A convenient way to store large amounts of similar data.
● It is used to represent multiple items of similar nature using a single name.
● It allows us to store data in multi-dimensional arrays. ( We will learn about them in a later section.)
● It is used to create other data structures like heaps, linked lists, etc.
● You need not access elements sequentially, random access is allowed.
● Since elements are stored in consecutive blocks hence they are useful to use in iterations.
● Since the size of the array is known during compile-time, there is no chance of memory run out for arrays.
Dis-Advantages:
● Since it is a static data structure that is has a fixed size we should
know or determine array size at compile time itself. No
modifications can be done to array size during runtime.
● Inserting and deleting elements from an array is a tedious task,
as it would involve shifting of some or all the elements of the
array which would also involve managing memory space for it
as well.
● Since we declare array at compile time itself with a particular
size, it is possible that a lot of memory space might get wasted if
only some address space is used and occupied.
● Operations like insertion, deletion are time-consuming tasks on
arrays.
9.convert following infix notations to prefix notations and postfix notations.
1. a + b +ab ab+
2. (a + b) ∗ c *+abc ab+c*
3. a ∗ (b + c)
4. a / b + c / d
5. ((a + b) ∗ c) – d
10.Explain push and pop operation with algorithm:
PUSH operation:
The steps involved in the PUSH operation is given below:
● Before inserting an element in a stack, we check whether the stack is full.
● If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.
● When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
● When the new element is pushed in a stack, first, the value of the top gets incremented, i.e., top=top+1, and the element will be placed at the new position of the top.
● The elements will be inserted until we reach the max size of the stack.
● The process of putting a new data element onto stack is known as a Push Operation. Push operation involves a series of steps −
● Step 1 − Checks if the stack is full.
● Step 2 − If the stack is full, produces an error and exit.
● Step 3 − If the stack is not full, increments top to point next empty space.
● Step 4 − Adds data element to the stack location, where top is pointing.
● Step 5 − Returns success.
POP operation:
The steps involved in the POP operation is given below:
● Before deleting the element from the stack, we check whether the stack is empty.
● If we try to delete the element from the empty stack, then the underflow condition occurs.
● If the stack is not empty, we first access the element which is pointed by the top
● Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.
● A Pop operation may involve the following steps
● Step 1 − Checks if the stack is empty.
● Step 2 − If the stack is empty, produces an error and exit.
● Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
● Step 4 − Decreases the value of top by 1.
● Step 5 − Returns success.
Unit :- 3
11. What is queue? Explain basic operations of queue.
A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).
▪ In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.
▪ Queue is exactly how queue system works in real world. If you go to a ticket counter to buy movie tickets, and are first in the queue, then you will be the first one to get the tickets.
▪ The process to add an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.
Basic Operations of Queue :-
▪ enqueue() − add (store) an item to the queue.
▪ dequeue() − remove (access) an item from the queue.
▪ Few more functions are required to make the above-mentioned
queue operation efficient. These are −
▪ peek() − Gets the element at the front of the queue without
removing it.
▪ isfull() − Checks if the queue is full.
▪ isempty() − Checks if the queue is empty.
12. Write down the basic steps for enqueue() and dequeue()
operation of queue. Explain with Example.
Enqueue Operation:
1.check if the queue is full
2.for the first element, set the value of FRONT to 0
3.increase the REAR index by 1
4.add the new element in the position pointed to by REAR
Dequeue Operation:
1.check if the queue is empty
2.return the value pointed by FRONT
3.increase the FRONT index by 1
4.for the last element, reset the values of FRONT and REAR to1
Example:
Front: Get the front item from queue. Require mostly when deleting item.
Rear: Get the last item from queue. Require mostly when adding item.
Adding Element : -
13. Explain circular queue in detail.
A circular queue is a linear data structure in which the operations are performed based on FIFO(First In First Out) principle and the last position is connected back to the first position to make a circle.
▪ It is also known as a Ring Buffer.
Why we use circular queue?
▪ If the rear reaches to the end position of the Queue then there might be possibility that some vacant spaces are left in the beginning which cannot be utilized.
▪ So, to overcome such limitations, the concept of the circular queue was introduced.
▪ There is one solution to avoid such wastage of memory space by shifting both the elements at the left and adjust the front and rear end accordingly.
▪ It is not a practically good approach because shifting all the elements will consume lots of time.
▪ The efficient approach to avoid the wastage of the memory is to use the circular queue data structure.
14. Implement circular queue using one example.
Insert 5,Insert 10,Insert 15,Insert 20,Insert 25,Insert
30,Delete,Delete,Insert 35,Insert 40
15. What is link list? Explain Insertion of Link list with example.
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations.
▪ Linked List can be defined as collection of objects called nodes that are randomly stored in the memory.
▪ A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory.
▪ The last node of the list contains pointer to the null. Insertion in Singly link list :-
▪ The insertion into a singly linked list can be performed at different positions.
▪ Based on the position of the new node being inserted, the insertion is categorized into the
following categories:-
1.Insertion at beginning of the list
2.Insertion at end of the list
3.Insertion after specified node Insertion at beginning of the list :
Steps:-
➢Allocate memory for new node
➢Store data
➢Change next of new node to point to head
➢Change head to point to recently created node
Insertion at end of the list :
Steps:-
➢Allocate memory for new node
➢Store data
➢Traverse to last node
➢Change next of last node to recently created node
Insert at the Middle
➢Allocate memory and store data for new node
➢Traverse to node just before the required position of new node
➢Change next pointers to include new node in between
Unit :4
16. Define Tree Explain Binary Tree in Detail.
Ans:- Trees represent a special case of more general structures known as graphs. In a graph, there is no restrictions on the number of links that can enter or leave a node, and cycles may be present in the graph.
The figure 5.1.1 shows a tree and a non-tree.
In a tree data structure, there is no distinction between the various children of a node i.e., none is the "first child" or "last child". A tree in which such distinctions are made is called an ordered tree, and data structures built on them are called ordered tree data structures. Ordered trees are by far the commonest form of tree data structure.
BINARY TREE:
In general, tree nodes can have any number of children. In a binary tree, each node can have at most two children. A binary tree is either empty or consists of a node called the root together with two binary trees called the left subtree and the right subtree. A tree with no nodes is called as a null tree. A binary tree is shown in
figure 5.2.1.
Binary trees are easy to implement because they have a small, fixed
number of child links. Because of this characteristic, binary trees are
the most common types of trees and form the basis of many important
data structures.
17. Explain In order and Pre-order Traversal.
Inorder Traversal:
In the case of inorder traversal, the root of each subtree is visited after its left subtree has been traversed but before the traversal of its right subtree begins. The steps for traversing a binary tree in inorder traversal are:
1. Visit the left subtree, using inorder.
2. Visit the root.
3. Visit the right subtree, using inorder.
The algorithm for inorder traversal is as follows: void in order(node *root)
{
if(root != NULL)
{ in order(root->lchild);
Print root -> data; inorder(root->rchild);
} }
Preorder Traversal:
In a preorder traversal, each root node is visited before its left and
right subtrees are traversed. Preorder search is also called
backtracking. The steps for traversing a binarytree in preorder
traversal are:
1. Visittheroot.
2. Visittheleftsubtree, usingpreorder.
3. Visittherightsubtree, usingpreorder. The algorithm for preorder
traversal is
as follows:void preorder(node *root)
{ if( root != NULL )
{
print root -> data;
preorder (root -> lchild);preorder (root -> rchild);
}
}
18. Convert a Following Tree into in-order and pre-order
Traverse.
Traverse the following binary tree in pre, post, inorder and level order.
19. Explain Depth first search in Detail.
In Depth first search, we begin with root as a start state, then some successor of the start state, then some successor of that state, then some successor of that and so on, trying to reach a goal state. One simple way to implement depth first search is to use astack data structure consisting of root node as a start state.
If depth first search reaches a state S without successors, or if all the successors of a state S have been chosen (visited) and a goal state has not get been found, then it “backs up” that means it goes to the immediately previous state or predecessor formally, the state whose successor was ‘S’ originally.
To illustrate this let us consider the tree shown below.
Suppose S is the start and G is the only goal state. Depth first search will first visit S, then A, then D. But D has no successors, so we must back up to A and try its second successor, E. But this doesn’t have any successors either, so we back up to A again. But now we have tried all the successors of A and haven’t found the goal state G so we must back to ‘S’. Now ‘S’ has a second successor, B. But B has no
successors, so we back up to S again and choose its third successor, C. C has one successor, F. The first successor of F is H, and the first of H is J. J doesn’t have any successors, so we back upto H and try its second successor. And that’s G, the only goal state.
So the solution path to the goal is S, C, F, H and G and the states
considered were in order S, A, D, E, B, C, F, H, J, G.
Disadvantages:
1. It works very fine when search graphs are trees or lattices, but can get struck in an infinite loop on graphs. This is because depth first search can travel around a cycle in the graph forever. To eliminate this keep a list of states previously visited, and never permit search to return to any of them.
2. We cannot come up with shortest solution to the problem.
20. Explain Breadth first search in Detail.
BFS stands for Breadth First Search. It is also known as level order traversal. The Queue data structure is used for the Breadth First Search traversal. When we use the BFS algorithm for the traversal in a graph, we can consider any node as a root node.
Let's consider the below graph for the breadth first search traversal.
Suppose we consider node 0 as a root node. Therefore, the traversing
would be started from node 0.
Once node 0 is removed from the Queue, it gets printed and marked as a visited node.
Once node 0 gets removed from the Queue, then the adjacent nodes of node
0 would be inserted in a Queue as shown below:
Now the node 1 will be removed from the Queue; it gets printed and marked as a visited node
Once node 1 gets removed from the Queue, then all the adjacent nodes of a node 1 will be added in a Queue. The adjacent nodes of node 1 are 0, 3,
2, 6, and 5. But we have to insert only unvisited nodes in a Queue.
Since nodes 3, 2, 6, and 5 are unvisited; therefore, these nodes will be
added in a Queue as shown below:
The next node is 3 in a Queue. So, node 3 will be removed from the
Queue,
it gets printed and marked as visited as shown below:
Once node 3 gets removed from the Queue, then all the adjacent nodes of node 3 except the visited nodes will be added in a Queue. The adjacent nodes of node 3 are 0, 1, 2, and 4. Since nodes 0, 1 are already visited, and node 2 is present in a Queue; therefore, we need to insert only node 4 in a Queue.
Now, the next node in the Queue is 2. So, 2 would be deleted from the Queue. It gets printed and marked as visited as shown below:
Once node 2 gets removed from the Queue, then all the adjacent nodes of node 2 except the visited nodes will be added in a Queue. The adjacent nodes of node 2 are 1, 3, 5, 6, and 4. Since the nodes 1 and 3 have already been visited, and 4, 5, 6 are already added in the Queue; therefore, we do not need to insert any node in the Queue.
The next element is 5. So, 5 would be deleted from the Queue. It gets
printed and marked as visited as shown below:
Once node 5 gets removed from the Queue, then all the adjacent nodes of node 5 except the visited nodes will be added in the Queue. The adjacent nodes of node 5 are 1 and 2. Since both the nodes have already been visited; therefore, there is no vertex to be inserted in a Queue.
The next node is 6. So, 6 would be deleted from the Queue. It gets
printed and marked as visited as shown below:
Once the node 6 gets removed from the Queue, then all the adjacent nodes of node 6 except the visited nodes will be added in the Queue. The adjacent
nodes of node 6 are 1 and 4. Since the node 1 has already been visited and node 4 is already added in the Queue; therefore, there is not vertex to be inserted in the Queue.
The next element in the Queue is 4. So, 4 would be deleted from the
Queue. It gets printed and marked as visited.
Once the node 4 gets removed from the Queue, then all the adjacent nodes of node 4 except the visited nodes will be added in the Queue. The adjacent nodes of node 4 are 3, 2, and 6. Since all the adjacent nodes have already been visited; so, there is no vertex to be inserted in the Queue.
Unit:5
21. What is hashing explain with example:
Hashing is an important data structure designed to solve the problem of efficiently finding and storing data in an array. For example, if you have a list of 20000 numbers, and you have given a number to search in that list- you will scan each number in the list until you find a match.
It requires a significant amount of your time to search in the entire list and locate that specific number. This manual process of scanning is not only time consuming but inefficient too. With hashing in the data structure, you can narrow down the search and find the number within seconds.
Hashing in a data structure is a two-step process.
1. The hash function converts the item into a small integer or hash value. This integer is used as an index to store the original data.
2. It stores the data in a hash table. You can use a hash key to locate data quickly.
Examples of Hashing in Data Structure:
The following are real-life examples of hashing –
👉In schools, the teacher assigns a unique roll number to each student. Later, the teacher uses that roll number to retrieve information about that student.
👉A library has an infinite number of books. The librarian assigns a unique number to each book. This unique number helps in identifying the position of the books on the bookshelf.
22. What is Hash Function?
The hash function in a data structure maps arbitrary size of data to fixed-sized data. It returns the following values: a small integer value (also known as hash value), hash codes, and hash sums.
hash = hashfunc(key)
index = hash % array size
The has function must satisfy the following requirements:
👉 A good hash function is easy to compute.
👉 A good hash function never gets stuck in clustering and distributes keys evenly across the hash table.
👉 A good hash function avoids collision when two elements or items get assigned to the same hash value.
23. Collision Resolution Techniques:
Hashing falls into a collision if two keys are assigned the same index number in the hash table. The collision creates a problem because each index in a hash table is supposed to store only one value. Hashing in data structure uses several collision resolution techniques to manage the performance of a hash table.
24.What is linear probing:
Hashing results in an array index that is already occupied to store a value. In such a case, hashing performs a search operation and probes linearly for the next empty cell.
Linear Probing Example Imagine you have been asked to store some items inside a hash table of size 30. The items are already sorted in a key-value pair format. The values given are: (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99).
The hash(n) is the index computed using a hash function and T is the table size. If slot index = ( hash(n) % T) is full, then we look for the next slot index by adding 1 ((hash(n) + 1) % T). If (hash(n) + 1) % T is also full, then we try (hash(n) + 2) % T. If (hash(n) + 2) % T is also full, then we try (hash(n) + 3) % T. The hash table will look like the following:
25. Explain Advantages and disadvantages of hashing:
Advantages :
👉 Main advantage is synchronization.
👉 In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software’s, particularly for associative arrays, database indexing, caches and sets.
Disadvantages :
👉Hash collisions are practically unavoidable. when hashing a random subset of a large set of possible keys.
👉 Hash tables become quite inefficient when there are many collisions.
👉 Hash table does not allow null values, like hash map.
Unit 6
26.Explain sorting in detail:
● Sorting is the process of arranging the elements of an array so that they can be placed either in ascending or descending order.
● For example, consider an array A = {A1, A2, A3, A4, …., An }, the array is called to be in ascending order if element of A are arranged like A1 > A2 > A3 > A4 > A5 > ? > An Consider an array;
int A[10] = { 5, 4, 10, 2, 30, 45, 34, 14, 18, 9 }
● The Array sorted in ascending order will be given as:-
A[] = { 2, 4, 5, 9, 10, 14, 18, 30, 34, 45 }
45,34,30,18,14,10,9,5,4,2
● There are many techniques by using which, sorting can be performed.
1. Bubble Sort
2. Bucket Sort
3. Comb Sort
4. Counting Sort
5. Heap Sort
6. Insertion Sort
7. Merge Sort
8. Quick Sort
9. Radix Sort
10. Selection Sort
11. Shell Sort
27.Explain Bubble sort with algorithm :
In Bubble sort, Each element of the array is compared with its adjacent element.
● The algorithm processes the list in passes. A list with n elements requires n-1 passes for sorting.
● Consider an array A of n elements whose elements are to be sorted by using Bubble sort.
The algorithm processes like following:-
● In Pass 1, A[0] is compared with A[1], A[1] is compared with
A[2], A[2] is compared with A[3] and so on. At the end of pass
1, the largest element of the list is placed at the highest index of
the list.
● In Pass 2, A[0] is compared with A[1], A[1] is compared with
A[2] and so on. At the end of Pass 2 the second largest element
of the list is placed at the second highest index of the list.
● In pass n-1, A[0] is compared with A[1], A[1] is compared with
A[2] and so on. At the end of this pass. The smallest element of
the list is placed at the first index of the list.
Algorithm :
Step 1: Repeat Step 2 For i = 0 to N-1
Step 2: Repeat For J = i + 1 to N - I
Step 3: IF A[J] > A[i]
SWAP A[J] and A[i]
[END OF INNER LOOP]
[END OF OUTER LOOP
Step 4: EXIT
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Bubble sort, also referred to as comparison sort, is a simple sorting algorithm that repeatedly goes through the list, compares adjacent elements and swaps them if they are in the wrong order.
This is the most simplest algorithm and inefficient at the same time. Yet, it is very much necessary to learn about it as it represents the basic foundations of sorting.
28.Explain selection sort in detail:
In selection sort, the smallest value among the unsorted elements of the array is selected in every pass and inserted to its appropriate position into the array.
First, find the smallest element of the array and place it on the first position. Then, find the second smallest element of the array and place it on the second position. The process continues until we get the sorted array.
The array with n elements is sorted by using n-1 pass of selection sort algorithm.
The idea behind this algorithm is pretty simple.
We divide the array into two parts: sorted and unsorted.
The left part is sorted subarray and the right part is unsorted subarray.
Initially, sorted subarray is empty and unsorted array is the
complete given array.
We perform the steps given below until the unsorted subarray becomes empty:
Pick the minimum element from the unsorted subarray. Swap it with the leftmost element of the unsorted subarray.
Now the leftmost element of unsorted subarray becomes a part
(rightmost) of sorted subarray and will not be a part of unsorted
subarray.
A selection sort works as follows:
Part of unsorted array
Part of sorted array
Leftmost element in unsorted array
Minimum element in unsorted array
This is our initial array A = [5, 2, 6, 7, 2, 1, 0, 3]
Leftmost element of unsorted part = A[0]
Minimum element of unsorted part = A[6]
We will swap A[0] and A[6] then, make A[0] part of sorted subarray.
Leftmost element of unsorted part = A[1]
Minimum element of unsorted part = A[5]
We will swap A[1] and A[5] then, make A[1] part of sorted subarray.
Leftmost element of unsorted part = A[2]
Minimum element of unsorted part = A[4]
We will swap A[2] and A[4] then, make A[2] part of sorted subarray.
Leftmost element of unsorted part = A[3]
Minimum element of unsorted part = A[5]
We will swap A[3] and A[5] then, make A[3] part of sorted subarray.
Leftmost element of unsorted part = A[4]
Minimum element of unsorted part = A[7]
We will swap A[4] and A[7] then, make A[4] part of sorted subarray.
Leftmost element of unsorted part = A[5]
Minimum element of unsorted part = A[6]
We will swap A[5] and A[6] then, make A[5] part of sorted subarray.
Leftmost element of unsorted part = A[6]
Minimum element of unsorted part = A[7]
We will swap A[6] and A[7] then, make A[6] part of sorted subarray.
29.Explain insertion sort with first Iteration:
Insertion sort is the sorting mechanism where the sorted array is built having one item at a time.
The array elements are compared with each other sequentially and then arranged simultaneously in some particular order.
The analogy can be understood from the style we arrange a deck of cards.
This sort works on the principle of inserting an element at a particular position, hence the name Insertion Sort.
Insertion Sort works as follows:
The first step involves the comparison of the element in question with its adjacent element.
And if at every comparison reveals that the element in question can be inserted at a particular position, then space is created for it by shifting the other elements one position to the right and inserting the element at the suitable position.
The above procedure is repeated until all the element in the array is at their apt position.
let us now understand working with the following example:
Consider the following array: 25, 17, 31, 13, 2
First Iteration: Compare 25 with 17. The comparison shows 17< 25.
Hence swap 17 and 25.
The array now looks like:
17, 25, 31, 13, 2
30.Explain searching and one of its method in detail.
Searching in data structure refers to the process of finding the required information from a collection of items stored as elements in the computer memory. These sets of items are in different forms, such as an array, linked list, graph, or tree. Another way to define searching in the data structures is by locating the desired element of specific characteristics in a collection of items.
There are different kind of searching method here we discuss about linear search….
Linear Search
The linear search algorithm iteratively searches all elements of the array. It has the best execution time of one and the worst execution time of n, where n is the total number of items in the search array.
It is the simplest search algorithm in data structure and checks each item in the set of elements until it matches the searched element till the end of data collection. When the given data is unsorted, a linear search algorithm is preferred over other search algorithms.
Complexities in linear search are given below:
Space Complexity:
Since linear search uses no extra space, its space complexity is O(n),
where n is the number of elements in an array.
Time Complexity:
● Best-case complexity = O(1) occurs when the searched item is present at the first element in the search array.
● Worst-case complexity = O(n) occurs when the required element is at the tail of the array or not present at all.
● Average- case complexity = average case occurs when the item to be searched is in somewhere middle of the Array.
Pseudocode for the linear search algorithm
procedure linear_search (list, value)
for each item in the list
if match item == value
return the item's location
end if
end for
end procedure
Example,
Let’s take the following array of elements:
45, 78, 15, 67, 08, 29, 39, 40, 12, 99
To find ‘29’ in an array of 10 elements given above, as we know
linear search algorithm
Comments