Monday, 27 November 2017

Short Answer type Questions on Data Structure

1. What is the difference between an array and a linked list?
The size of an array is fixed whereas size of linked list is variable. In array the data elements are stored in continuous memory locations but in linked list it is non continuous memory locations. Addition, removal of data is easy in linked list whereas in arrays it is complicated.

2. What is a node?
The data element of a linked list is called a node.

3. What does node consist of?
Node consists of two fields: data field to store the element and link field to store the address of the next node.

4. Write the syntax of node creation?
Syntax of node creation:
struct node
{
data type ;
struct node *ptr; 
}
temp;

5. Write the syntax for pointing to next node?
Syntax for pointing to next node:
node->link=node1;

6. What is sorting?
Sorting is the process of arranging elements in some logical order.Sorting methods are classified into the following categories: External sorting: This deals with sorting of data stored in external files. This method is used when the volume of data is very large and cannot be held in a computer’s RAM . Internal sorting: This deals with sorting of data held in the RAM of a computer.

7. What is insertion sort?
This algorithm is very popular with bridge players when they sort their cards. In this procedure, we pick up a particular value and then insert it at the appropriate place in the sorted sub list.

8. What is the complexity of insertion sort?
Ans : The worst-case performance occurs when the elements of the input array are in descending order. In the worst-case, the first pass will require one comparison, the second pass will require 2 comparisons, and so on until the last pass which will require (n-1) comparisons. In general, the kth pass will require k-1 comparisons. Therefore the total number of comparisons is:
F(n)=1+2+3+…..+(n-k)+….+(n-3)+(n-2)+(n-1)
=n(n-1)/2
=O(n2)

9. What is merge sort?
Ans: Merging means combining elements of two arrays to form a new array. The simplest way of merging two arrays is to first copy all the elements of one array into a new array and then append all the elements of the second array to the new array. If you want the resultant array to be sorted, you can sort it by any of the sorting techniques. If the arrays are originally in sorted order, they can be merged in such a way as to ensure that the combined array is also sorted. This technique is known as merge sort.

10. What is selection sort?
Ans: Selection sort requires (n-1) passes to sort an array. In the first pass, we find the smallest element from a[0], a[1], a[2], … a[n-1] and swap it with the first element, i.e. a[0]. In the second pass, we find the smallest element from a[1], a[2], a[3]….a[n-1] and swap it with a[1] and so on.


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput