BioJuncture - Home



Question Bank with solution-Data Structure and Algorithm

Q.No. – 1. Write an an algorithm for insertion in linear Array.

Q.No.-2. Write an algorithm for deletion in linear Array.

Sol. 1.

Insertion in Array-

Insert(A,N,k,Value)(Inserting at kth location)

1. Set j:=N

2. Repeat steps 3 & 4 while j >=k

3. Set A[j+1]=A[j].

4. Set j:=j-1

5. Set A[k]:= value

6. Set N:=N+1

7. Exit.

Sol. 2.

Deletion in Array-

Delete(A,N,k,Value)(deletion at kth location)

1. Set value:= A[k].

2. Set j:=k.

3. Repeat 3 & 4 while j

Else If Front=N then:

Set Front:=1.

Else:

Set Front:=Front+1.

4. Exit.

Q.No. -15, what is Deque.

Deques:- Also called doubly ended queues. Elements can be inserted and deleted at both ends but not in middle of queues. End pointers are denoted by LEFT and RIGHT. In Input restricted deques insertion can take place at one end from RIGHT(Rear) but deletions can take place at both ends. In output restricted deques deletion can take place at only one end called LEFT(Front) but insertion can take place at both ends.

Example:- Consider following deque of characters where DEQUE ius a circular array which isallocated six memory cells.

LEFT:2, RIGHT:4 DEQUUE: __, A, C, D, __ __

Describe the deque while following operations take place.

a) F is added on right

LEFT =2, RIGHT=5 DEQUE:__, A, C, D, F,__

b) Two elements are deleted from right

LEFT=2, RIGHT=3 DEQUE: __ A, C, __, __, __

c) K,L,M are added on left

LEFT=5, RIGHT=3 DEQUE: K, A, C, __, M, L

d) M is deleted

LEFT=6, RIGHT=3 DEQUE: K, A, C, __, __, L

e) R is added on left

LEFT=5, RIGHT=3 DEQUE: K, A, C, __, R, L

f) S is added on right

LEFT=5, RIGHT=4, DEQUE: K, A, C, S, R, L

g) T is added to right

Since LEFT=RIGHT + 1, DEQUE is full, T cannot be added. OVERFLOW Condition.

Question:16Suppose each data structure is stored in a circular array with N memory cells.

a) Find no. of elements NUM in a queue in terms of FRONT and REAR.

b) Find the no. of elements NUM in deque in terms of LEFT & RIGHT.

c) When will the array be filled?

Sol.

a) If FRONT 1

a)_ Find L(25)

b) What does this function do?

Sol.

a) L(25)=L(12)+1

=[L(6)+1]+1=L(6)+2=[L(3)+1]+2=L(3)+3

=[L(1)+1]+3=L(1)+4

0+4=4

b) Each time n is divided by 2 the value of L is increased by 1. Hence L is greatest integer such that 2 L ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download