Introduction to Data Structure and Array - AD ICT/AP/AME/

1.       What is Data Structure?

Answer: Data structure is the logical or mathematical model of a particular

organization of data. 

2.       Write classification of Data Structure?

Answer: Data structures can be classified in to two categories. They are,

a.     Primitive Data Structure: int, float, double etc.

b.    Non –primitive data structure: It can be divided in to two categories. They are,

(1) Linear Data Structure: Data elements are arranged in a sequential or linear manner and each element is attached with previous and next element.

(a)  Static data structure

-        Static data structures are fixed in memory size

(b) Dynamic data structure

-        Dynamic data structures are not fixed in memory size.

-        We can randomly increase or decrease the size of the data structure in run time.

(2) Non-linear Data Structure: Data elements are not arranged in a sequential manner. We can’t traverse all elements at a time.

3.       Operations of Data Structure?

Answer: The major operations that can be performed by a data structure is written below,

a.     Insertion: A new element can be inserted in the data structure

b.    Deletion: An element can be removed from the data structure

c.     Updating: An element’s value can be updated

d.    Sorting: All elements of an array can be sorted in ascending or descending order.

e.     Searching: A element can be searched from all the elements of a data structure.

4.       Advantages of Data Structure?

Answer: The advantages of data structure is written below,

a.     Efficiency: If the choice of a Data Structure for implementing a particular ADT is proper it makes the program very efficient in terms of time and space complexity.

b.    Reusability: The data structure provides reusability means that multiple client programs can use the data structure.

c.     Abstraction: The data structure specified by the ADT also provides the level of abstraction. The client can’t see the internal working of data structure so it doesn’t have to worry about the implementation part. The client can only see the interface.

5.       What is an array? Write properties of an array?

Answer: Array is a collection of similar type of data stored in a contagious memory location. The properties of an array are written below,

a.     Each elements of an array are of same data type and carries the same size that is 4 bytes.

b.    Elements in the array are stored at contiguous memory locations from which the first element is stored at the smallest memory location.

c.     Elements in the array can be accessed randomly since we can calculate the address of each element of the array with the given base address and size of the data elements.

6.       Explain traversal operation in an array.

Answer: here LA is a linear array with lower bound LB and upper bound UB. This algorithm traverses LA applying an operation PROCESS to each element of LA.

a.     [Initialize counter.] Set K:= LB.

a.     Repeat Steps 3 and 4 while K ≤ UB.

b.            [Visit element.] Apply PROCESS to LA[K].

c.             [Increase counter.] Set K:= K+ 1.

[End of Step 2 loop.]

d.    Exit

7.       Explain Insertion operation of an array?

Answer: Here LA is a liner array with N elements and K is a positive integer such that K≤N. This algorithm inserts an element ITEM into the Kth position in LA.

a.     [Initialize counter.] Set J:=N.

b.    Repeat Steps 3 and 4 while J≥K.

c.         [Move Jth element downward] Set LA[J+1] := LA[J]

d.        [Decrease counter.] Set J := J-1.

[End of Step 2 loop]

e.     [Insert element.] Set LA[K] :=ITEM.

f.      [Reset N.] Set N:=N+1.

g.    Exit.

8.       Explain Deletion operation of an array.

Answer: Here LA is a linear array with N elements and Ki s a positive integer such that K≤N. This algorithm deletes the kth element from LA.

a.     Set ITEM := LA[K]

b.    Repeat for J = K to N-1:

      [Move J+ 1st element upward] Set LA[J] :=LA[J+1]

[End of loop.]

c.     [Reset the number N of elements in LA.] Set N:=N-1

d.    Exit

9.       Explain Linear Search operation of in an array

Answer: Here DATA is a linear array with N elements, and ITEM is a given item of information. This algorithm finds the location LOC of IEM in DATA, or sets LOC:=0 if the search is unsuccessful.

a.     [Insert ITEM at the end of DATA] Set DATA[N+1] := ITEM

b.    [Initialize counter.] Set LOC:=1

c.     [Search for ITEM]

Repeat while DATA[LOC] ≠ ITEM

   Set LOC := LOC+1

[End of loop]

d.    [Successful?] If LOC = N+1then: Set LOC:=0

e.     Exit

10.   Explain Binary Search.

Answer: Here DATA is a sorted array with lower bound LB, upper bond UB and ITEM is a given item of information. The variables BEG, END and MID denote, respectively, the beginning, end and middle locations of a segment of elements of DATA. This algorithm finds the locations LOC of ITEM in DATA or set LOC = NULL.

a.     [Initialize segment variables.]

Set BEG:=LB,END:=UB and MID:=INT((BEG+END)/2)

b.    Repeat Steps 3 and 4 while BEG≤END and DATA[MID]≠ITEM

c.                If ITEM<DATA[MID],then:

             Set END: = MID – 1.

          Else:

             Set BEG := MID+1.

d.              Set MID:=INT((BEG+END)/2).

e.     If DATA[MID] = ITEM, then:

   Set LOC:=MID

Else:

  Set LOC:=NULL

f.      Exit          

11.   What is sorting? Explain Bubble sort.

Answer: Sorting refers to the operation of rearranging the elements of an array so they are in increasing or decreasing order.

Here Data is an array with N elements. This algorithm sorts the elements in DATA.

a.     Repeat Step 2 and 3 for K= 1 to N-1.

b.         Set PTR := 1.[Initialize pass pointer PTR]

c.          Repeat while PTR≤N-K: [Execute pass]

(1) If DATA[PTR] > DATA[PTR+1], then:

Interchange DATA[PTR] and DATA[PTR+1].

(2) Set PTR:=PTR+1.

  [End of inner loop.]

[End of Step 1 outer loop.]

d.    Exit

12.   Explain time complexity of Bubble sort.

Answer: Traditionally, the time for a sorting algorithm is measured in terms of the number of comparison. The number f(n) of comparisons in the bubble sort is easy to computed. Specially there are n-1 comparisons during the first pass, which places the largest element in the last position; there are n-2 comparisons in the second step, which places the second largest element in the next-to-last position; and so on. Thus,

f(n) = (n-1)+(n-2)+…+2+1= -  + O(n) = O(n²)

In other words, the time required to execute the bubble sort algorithm is proportional to n² where n is the number of items.

13.   Explain time complexity of different array operations

Answer: The time complexity of an array is given below,

Operation	Average Case	Worst Case
Access	O(1)	O(1)
Search	O(n)	O(n)
Insertion	O(n)	O(n)
Deletion	O(n)	O(n)

Space Complexity

In array, space complexity for worst case is O(n).

14.   Difference between Linear and Binary Search.

Answer: Difference of Linear and Binary Search is written below,

Linear Search	Binary Search
a.     In linear search input data need not to be in sorted.	a.     In binary search input data need to be in sorted order.
b.    It is also called sequential search.	b.    It is also called half-interval search.
c.     The time complexity of linear search O(n).	c.     The time complexity of binary search O(log n).
d.    Multidimensional array can be used.	d.    Only single dimensional array is used.
e.     Linear search performs equality comparisons	e.     Binary search performs ordering comparisons
f.      It is less complex.	f.      It is more complex.
g.    It is very slow process.	g.    It is very fast process.

 

 

Points to Remember – For the Hardest part of Question

1.       We can’t traverse all elements of a non-linear data structure at a time.

2.       Each elements of an array are of same data type and carries the same size that is 4 bytes

3.       Each element in the array can be accessed via its index

4.       Sorting and searching a value in an array is easier

5.       Arrays are best to process multiple values quickly and easily

6.       Arrays are good for storing multiple values in a single variable

7.       Byte address of element A[i] = base address + size * ( i - first index)

8.       If many insertion and deletion are to be made in a collection of data elements then linear array may not be the most efficient way of storing the data.

 

 

Important Math

1.    Address calculation for an array element.