Data Structures and Algorithms question bank PDF

Preview

Summary

Dara structures and algorithms notes for computer science programming Sorting algorithms Searching Algorithms Time Complexities of searching and sorting algorithms...

Description

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 ArrayInsert(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 ArrayDelete(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 tak 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 < n Accordingly this function finds L=log2 n Q. No. -22. Suppose Fibonacci number F11 = 89 and F12 = 144 are given a) Should one use recursion or iteration to obtain F16? Find16. b) Write an iterative procedure to obtain first N elements Sol. a) Fibonacci numbers should be evaluated by using iteratuion( bottom up) rather than by using recursion(Top to Bottom) Hence F16 377+610=987 b)

FIBONACCI(F,N)

1. Set F[1]:=1 and F[2]:=1 2. Repeat for L=3 to N: Set F[L]:=F[L-1]+F[L-2]. 3. Return. Q. No. -23.Consider a deque maintained by a circular arrayw with N memory cells. a) Suppose a element is added to the deque. How is LEFT or RIGHT changed? b) Suppose an element is deleted. How is LEFT or RIGHT changed? Sol. a) If the element is added on left, then LEFT is decreased by 1(mod N). if added on right, right is increased by 1(mod N).

b) If deleted from left then LEFT is increased by 1(mod N).if deleted from right, RIGHT is decreased by 1(mod N). in the case LEFT=RIGHT before deletion both LEFT & RIGHT are assigned NULL to indicate deque is empty. Q. No.-24. Suppose S is the following list of 14 alphabetic characters: DA TAS TR U C TU R E S Use Quicksort algorithm to find final position of first character D. Follow Algorithm 1. CATAS T R U D TU R E S 2. CADAS T R UTT U R E S 3. CAA D ST R UTT U R E S 4. C AA D S T R U T T U R E S

Sol. a) Since order in which subsets are sorted does not matter, LOWER and UPPER can be implemented as queues or even deques rather the stacks Q. No. -25. Suppose S consists of the following n=5 letters: A B C D E Find no. of comparisons to sort S using Quicksort. Draw general Conclusion. Beginning with E it takes n-1=4 comparisons to recognize that A is already in its correct position. Sorting S is now reduced to sorting the following sublist with n-1=4 letters. A B C D E Beginning with Eit takes n-2 = 3 comparisons to recognize that B in sublist is already in its correct position. Sorting is now reduced to sorting the following sublist with n-2=3 letters: A B C D E Consequently we have 4 + 3 + 2 + 1 =10 So using Quicksort it takes C=(n-1) + (n-2) + )n-3) + …. + 2 + 1 = n(n-1)/2 = O(n2) Q. No. -26. Consider Quick sort Algo. a) Can arrays LOWER and UPPER be implemented as queues rather than stacks? b) what is space complexity? . Sol. b) Quick sort Algorithm is an in-space algorithm that is elements remain in their places except for interchanges. The extra space required mainly for stacks LOWER and UPPER. On the average extra space required for algo is proportional to log n, n is no. of element t be sorted.

Q27)Explain Basic terminology of Data Structure. Ans.Basic Terminology:Data - values or set of values Data Item /datum – single unit of value Group item – which are divided into sub items like employee name may be divided into sub items like first name, middle name, last name Elementary data item – that can’t be divided into subparts Entity – something that has certain attributes. Attributes- are properties that can be assigned some values. Entity set – Entities with similar attributes. Information- meaningful or processed data Q28)What is Data structure and also Criteria that must be taken into consideration while chosing a Data Structur Ans: Study of data structure includes 1)Logical or mathematical model description of the structure 2) Implementation of the structure on a computer 3)Quantitative analysis of the structure which includes determining the amount of memory needed to store the structure and the time required to process the structure.

In subject data structure and algorithm, data in primary memory are considered while DBMS deals with data in secondary memory

Data Structure – Logical or mathematical model of a Particular organization of data is called data structure. Criteria that must be taken into consideration while chosing a Data Structure- The choice of a Particular data structure depends on following considerations. 1. First it must be rich enough in structure to mirror the actual relationships of the data in real world. 2. Structure should be simple enough that one can effectively process the data when necessary.

3. Sometimes the choice of data structure involves a time-space tradeoff: i.e. by increasing the amount of space for storing the data, one may be able to reduce the time needed for processing the data or vice versa. 4. Choice of data structure also depends upon relative frequency with which various operations are applied. Q29) what is complexity and explain Big O notation. Ans. Complexity:- An algorithm is a well defined list of steps for solving a Particular problem. The complexity of an algorithm is the function which gives running time and/or space in terms of input size. Big O Notation- Suppose M is an algorithm and n is the size of the input data. Clearly the complexity f(n) of M increases as n increases. It is rate of increase of f(n) that we want to examine. This is usually done by comparing f(n) with some standard function such as Log2 n, n, n log 2 n, n2, n3, 2n One way to compare the function f(n) with these standard function is to use the functional O notation. Such that Complexity linear search(O(n) Binary search O(log n) Bubble Sort O(n2) Merge Sort O(n log n) Other Asymptotic notation for complexity of algorithmOmega Notation(Ω) The Omega notation is used when function g(n) defines a lower bound for the function f(n) Theta notation(θ)- This is used when the function(n) is bounded both from above and below by the function g(n) Little Oh notation(o)- f of n is little oh of g of n iff f(n) = O(g(n)) and f(n) Ωg(n)) Q30) Explain various string operation. Ans: String OperationsSubstringSUBSTRING(‘TO BE OR NOT TO BE’,4,7)= BE OR N IndexingSuppose T contains the text: ‘HIS FATHER IS THE PROFESSOR’ Then INDEX(T, ‘THE’), INDEX(T, ‘THEN’) and INDEX(T. ‘ THE ‘) have the values 7,0,14 respectively. ConcatenationSuppose S1 = ‘MARK’ and S2= ‘TWAIN’, then: S1//S2=’MARKTWAIN’ But S1// ‘ ‘ // S2=’MARKTWAIN’. LengthLENGTH(‘COMPUTER’)=8 Insert-

INSERT(‘ABCDEFG’, 3, ‘XYZ’)=’ABXYZCDEFG’ DeletionDELETE(‘ABCDEFG’, 4,2)=’ABCFG’ ReplacementREPLACE(‘XABYABZ’, ‘AB’, ‘C’)=’XCYABZ’ Question31- Discuss how strings are stored and various operations that are applied on strings. Sol. Refer Lipschutz page 3.2-3.12

Q32.what is array. Array SOLU: Data structure(DS) are classified as linear or non linear. A DS is said to be linear If its elements form a sequence or linear list or they are at same level like Arrays, Queues, Linked List. A DS is said to be non linear when its elements do not form a sequence or when they are at different levels like Trees and Graphs. One way to represent linear relationship through sequential memory Locations other way by means of pointer. Various Operations that are applied on any data structurea)Traversal- Visiting each element exactly once. b) Search-Finding the Location of element with a given value or the record with a given key. c)Insertion- Adding a new element to the list. Various conditions may be associated with it. d) Deletion- Removing an element from the list. Various conditions may be associated with it. e)Sorting-Arranging elements in some order. f) Merging-Combining two lists into a single list.

Linear Array :Linear Array is a list of finite number n of homogeneous data elements. such that a)Elements are referenced respectively by an index set consisting of consecutive numbers. b) Elements are stored respectively in successive memory Locations. Length = UB-LB+1 Linear Array are called one dimensional arrays because here each element is referenced by single subscript. Sixe(3*5) is read as 3 by 5

Representation of Array in MemoryElements are stored in successive memory Locations in memory

Computer Memory Address calculation for single dimensional arrayLOC(A[k]) = Base(A) + w(k-LB) where w is number of memory cell per element, Base(A) is base address i.e. address of first element of Array, LB is smallest index used in Array. For ex. If Base address is 1000 and each element occupies 4 memory cells then address of 4th element is 1000+4(4-1)=1012. Note:- A collection A of elements is said to be indexed If any element of A, which we will cal A[k] can be Located and processed in a time that is independent of K. Linear Array can be indexed. Linked List doesn’t have this property.

Q33.Write an algorithm for traversing of Linear Array. Ans Traversing Linear ArrayTraverse(A,LB,UB) 1.Set k:=LB. 2.Repeat steps 3 & 4 while k =k 10. Set A[j+1]=A[j]. 11. Set j:=j-1 12. Set A[k]:= value 13. Set N:=N+1 14. Exit. Deletion in ArrayDelete(A,N,k,Value)(deletion at kth Location) 6.Set value:= A[k]. 7.Set j:=k. 8.Repeat 3 & 4 while j...