# CSE SOLUTION SITE

Data Structure Question List | Solve

### (15).Algorithm: (Deleting From a Linear Array) DELETE (LA, N, K, ITEM) Here LA is a linear array with N elements and K is a positive integer such that K < N. This algorithms Deletes an element ITEM into the Kth Element LA.

Data Structure Question List | Solve

# What is Data Structures?

Data Structure:
Data may be organized on many different ways; The logical or mathematical model of a particular organization of data is called a data structure.

# What is mean Stack?

Stack:
A Stack, also called a last-in-first-out(LIFO) system, is a linear list in which insertions and deletions can take place only at one end, called the top.

#### What is Queue?

Queue:
A queue, also called a first-in first-out(FIFO) system, is a linear list in which deletions can take place only at one end of the list, the "front" of the list, and insertions can take place only at the other end of the list, the "rear" of the list.

#### The following four operations play a major role in this text:

1.Traversing:
Accessing each record exactly once so that certain items in the record may be processed.

2.Searching:
Finding the location of the record with a given key value, or finding the locations of all records which satisfy one or more conditions.
3.Inserting:
Adding a new record of the structure.

4.Deleting:
Removing a record from the structure.

# QINSERT(QUEUE, N, FRONT, REAR, ITEM) This procedure inserts an elements ITEM into a queue.

If FRONT = 1 and REAR = N, or if FRONT = REAR + 1, then:
Write: OVERFLOW, and Return.

2.             [Find new value of REAR.]

If  FRONT : = NULL, then : [Queue initially empty.]
Set FRONT : = 1 and REAR : = 1

Else :
Set REAR : = REAR + 1 .

[End of  If structure]

3.  Set QUEUE[REAR] : = ITEM.     [This inserts new element]

4. Return

# Algorithm 2.1: (Largest Element in Array) A nonempty array DATA with N numerical values is given.This algorithm finds the location LOC and the value MAX of the largest element of DATA.The variable K is used as a counter.

Step 1.  [Initialize] Set K: = 1, LOC: = 1 and MAX : = DATA[1].

Step 2.  [Increment Counter]. Set K : = K+1.

Step 3. [test counter.] If K > N, then:
Write: LOC,  MAX, and Exit.

Step 4. [Compare and Update.] If MAX < DATA[K], then:
Set LOC: = K and MAX : = DATA[K].

Step 5. [Repeat Loop.] Go to the Step 2.

# There are two case for describing in the complexity of algorithms:

(1) Worst Case:
The Maximum value of f(n) for any possible input.

(2) Average Case:
The expected value of f(n) Sometimes we also consider the minimum possible value of f(n), called the best case. Suppose, The numbers of n1, n2, ......, nk occur with respective probabilities p1,p2, ........., pk. Then the expectation of average value E is given by E = n1 p1 + n2 p2 + ................... + nk pk

# Algorithm 2.4: (Linear Search) A Linear Array DATA with N elements and a specific ITEM of information are given. This algorithm finds the location LOC of ITEM in the array DATA or sets LOC = 0.

1.  [Initialize] Set K: = 1 and LOC : = 0.
2.  Repeat Steps 3 and 4 while LOC = 0 and K < N.
3. It ITEM = DATA[K], then: Set LOC: = K.
4. Set K : = K+1. [increments Counter.]
[End of Step 2 Loop.]
5. [Successful?]
If LOC = 0, then:
Write: ITEM is not in the array DATA.
Else :
Write: LOC is the location of ITEM.
[End of If structure.]
6. Exit.

# The Operation one normally performs on any linear structure.

(a) Traversal:
Processing each element in the list.

(b) Search:
Finding the location of the element with a given value or the record with a given key.

(c) Insertion:
Adding a new element to the list

d) Deletion:
( Removing an element from the list.

(e) Sorting:
Arranging the elements in some type of order.

(f) Merging:
Combing two lists into a single list.

# Algorithm 4.1: (Traversing a Linear Array) 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.

1. [Initialize counter.] Set K : = LB.
2. Repeat Steps 3 and 4 while K < UB.
3. [Visit Element] Apply Process to LA[K].
4.  [Increase counter] Set K : = K +1.    // K = LB + 1
[End of Step 2 Loop]
5. Exit.

# (a) Suppose ITEM = 40. The search for ITEM in the array DATA is pictured in fig. 4.6, Where the values of DATA[BEG] and DATA[END] in each stage of the algorithm are indicated by circles and the value of DATA[MID] by a square.Specifically, BEG, END and MID will have the following succesive values:

1. Initially, BEG = 1 and END = 13. Hence
MID = INT[(1 + 13/2)] = 7 and so DATA[MID] = 55

2. Since 40 < 55, End has its value changed by END = MID - 1 = 6. Hence
MID = INT[(1+6/2)] = 3 and so DATA[MID] = 30

3. Since 40 > 30, BEG has its value changes by BEG = MID + 1 = 4. Hence
MID = INT[(4+6)/2] = 5  and so  DATA[MID] =  40

We have found ITEM in location LOC = MID = 5.

11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99
11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99
11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99  [Successful]

# (b) Suppose ITEM = 85. The Binary search for ITEM in the array DATA is pictured in fig. 4.6, Where the values of DATA[BEG] and DATA[END] in each stage of the algorithm are indicated by circles and the value of DATA[MID] by a square.Specifically, BEG, END and MID will have the following succesive values:

1. Initially, BEG = 1 and END = 13. Hence
MID = INT[(1 + 12)/2] = 7 and so DATA[MID] = 55

2. Since 85 > 55, End has its value changed by END = MID + 1 = 8. Hence
MID = INT[(8 + 13)/2] = 10 and so DATA[MID] =77

3. Since 85 > 77, BEG has its value changes by BEG = MID + 1 = 11. Hence
MID = INT[(11 + 13)/2] = 12  and so  DATA[MID] =  88.

4. Since 85 < 88, END has its value changes by END = MID - 1 = 11. Hence
MID = INT[(11 + 11)/2] = 11  and so  DATA[MID] =  80

11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99
11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99
11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99
11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99 [Unsuccessful]

# Algorithm 4.6: (Binary Search) BINARY(DATA, LB, UB, ITEM, LOC) Here DATA ia a sorted array with lower bound LB and upper bound 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 location LOC of ITEM in DATA or sets LOC = NULL.

1.  [Initialize segment variables.]
Set BEG : = LB, END  : = UB and MID = INT((BEG+END)/2).

2.  Repeat Steps 3 and 4 while BEG < END and DATA[MID] != ITEM

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

Set END : = MID - 1.

Else:
Set BEG : = MID + 1.
[End of Structure.]

4. Set MID : = INT((BEG + END)/2).
[End of Step 2 Loop.]

5. If DATA[MID] = ITEM, then:
Set LOC : = MID.

Else:
Set LOC : = NULL.
[End of If Structure.]

6. Exit.

# Algorithm: (Inserting into a Linear Array) INSERT (LA, N, K, ITEM) Here LA is a linear array with N elements and K is a positive integer such that K < N. This algorithms inserts an element ITEM into the Kth position in LA.

1.    [Initialize Counter.]  Set J : = N.

2. Repeat Steps 3 and 4 while J > K.

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

4.     [Decrease Counter.]  Set J = J-1.
[End of Step 2 loop]

5.    [Insert Element.]   Set LA[K] : = ITEM.

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

7.   Exit.

# Algorithm: (Deleting From a Linear Array) DELETE (LA, N, K, ITEM) Here LA is a linear array with N elements and K is a positive integer such that K < N. This algorithms Deletes an element ITEM into the Kth Element LA.

1.  Set ITEM : = LA[K].

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

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

[End of Loop].

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

4. Exit.