B.TECH - Semester 3 data structures and algorithms Question Paper 2020 (may)
Practice authentic previous year university questions for better exam preparation.
Sample Questions
- Differentiate between abstract and concrete data structure.
- What is stepwise refinement?
- Let LIST be the singly linked list. Write an algorithm to find the number of times a given data item ITEM occurs in the LIST.
- Check whether the given expression is properly parenthesized using stack $$ \left(A+\left[\frac{(B * C)}{D-E}\right]-F\right) $$
- Explain structured approach to programming
- What is the best sorting technique to sort almost sorted list? Justify your answer.
- Write a pseudo code to find the smallest and largest elements in a binary search tree.
- Is garbage collection essential? Justify your answer.
- Compare linear search and binary search.
- Explain buddy system. Answer any one full question from each Module, 20 marks each.
- (a) Explain in detail about the structure and operations of Doubly Linked List.
- (b) Explain about the use and representation of header node in linked list.
- (c) Compare vectors and arrays in detail.
- (a) Explain the application of vectors.
- (b) Design an efficient algorithm to calculate $x^{n}$ with a running time no longer than $O(\log n)$.
- (c) Write down the algorithms for operations in a circular linked list.
- (a) Write an algorithm for conversion of infix expression to postfix form. Convert the expression $$ (A * B / C-E)+F $$
- (b) List out the properties of binary search trees.
- (c) Write an algorithm to insert an element in a binary search tree.
- (a) Give any two representations of graphs.
- (b) Write an algorithm to check a particular sub string is present in a given string or not? If found print its location.
- (c) Give the algorithm for BFS graph traversal.
- (a) List major issues memory management.
- (b) Compare internal and external fragmentation.
- (c) Compare the different memory allocation strategies.
- (a) Given memory partitions of $100 \mathrm{~K}, 200 \mathrm{~K}, 50 \mathrm{~K}, 250 \mathrm{~K}$ and 400 K in order. How would each of the first fit, worst fit and best fit strategies process request for $112 \mathrm{~K}, 47 \mathrm{~K}, 340 \mathr...
- (b) Explain compaction.
- (c) Illustrate the process of memory management using boundary tag method using suitable example.
- (a) Write an algorithm to do the partition of a list using quick sort and then use insertion sort for sorting sub lists. Explain it with example.
- (b) Define hashing. List out the properties of a good hash function. With the necessary examples. Explain different hashing functions.
- (a) Write an algorithm to sort a list of elements using merge sort. Apply merge sort on the list: $3,4,20,6,7,5,2,16$
- (b) Define collision. What is linear probing? The following keys • $10,16,11,1,3,4,23,15$ are inserted into an initially empty table of length 8 using open addressing using the hash function $h(k)=k \bmod 8$ and linear probing. What is the resultant ...