DSA 2019 Makeup

4th semester

Group A

  1. Big Theta notation (Θ) :
    The equation simply means there exist positive constants C 1 and C 2 such that f(n) is sandwich between C 2 g(n) and C 1 g(n
  2. FIFO stands for First In – First Out, which simply means the request which has come first will be dealt first. As this is the case with a QUEUE data structure, we simply call an ordinary queue as a FIFO queue.
  3. A drawback of linked lists is that access time is linear (and difficult to pipeline). Faster access, such as random access, is not feasible. Arrays have better cache locality compared to linked lists.
  4. The tail recursion is better than non-tail recursion. As there is no task left after the recursive call, it will be easier for the compiler to optimize the code. So if it is tail recursion, then storing addresses into stack is not needed. We can use factorial using recursion, but the function is not tail recursive.
  5. Splaying an element, is the process of bringing it to the root position by performing suitable rotation operations. In a splay tree, splaying an element rearranges all the elements in the tree so that splayed element is placed at the root of the tree.
  6. A heap is a tree-based data structure in which all the nodes of the tree are in a specific order. specific order with respect to the value of and the same order will be followed across the tree.
  7. A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
  8. A directed graph (or digraph) is a set of vertices and a collection of directed edges that each connects an ordered pair of vertices. … We use the names 0 through V-1 for the vertices in a V-vertex graph.
  9. Data sorting is any process that involves arranging the data into some meaningful order to make it easier to understand, analyze or visualize. When working with research data, sorting is a common method used for visualizing data in a form that makes it easier to comprehend the story the data is telling.
  10. Different collision resolution techniques in Hashing
  • Open Hashing (Separate chaining)
  • Closed Hashing (Open Addressing) Liner Probing. Quadratic probing. Double hashing.


Group B

Q.No 11.



Q.no 12

Q.n0 13

Q.no 14

Q.no 15

Leave a Reply

Your email address will not be published.