Data Structures and Algorithms - B.Tech 3rd Semester Special Exam., 2020

2020•Semester 3•Civil-CA•End Semester
Bihar Engineering University, Patna
B.Tech 3rd Semester Special Exam., 2020

Data Structures and Algorithms

Time: 03 HoursCode: PCC-IT-302 (100304)Full Marks: 70

Instructions:

  1. The marks are indicated in the right-hand margin.
  2. There are NINE questions in this paper.
  3. Attempt FIVE questions in all.
  4. Question No. 1 is compulsory.
Q.1 Choose the correct answer of the following (any seven):[14]

  1. If the number of records to be sorted is small, then ______ sorting can be efficient.

    1. merge
    2. heap
    3. selection
    4. bubble

  2. Which of the following is not a limitation of binary search algorithm?

    1. Must be a sorted array
    2. Requirement of sorted array is expensive when a lot of insertions and deletions are needed
    3. There must be a mechanism to access middle element directly
    4. Binary search algorithm is not efficient when the data elements are more than 1500

  3. The complexity of the merge sort is

    1. \( O(n) \)
    2. \( O(\log n) \)
    3. \( O(n^2) \)
    4. \( O(n\log n) \)

  4. Which of the following is a hash function?

    1. A function has allocated memory to keys
    2. A function that computes the location of the key in the array
    3. A function that creates an array
    4. A function that computes the location of the values in the array

  5. In simple hashing, what is the search complexity?

    1. \( O(n) \)
    2. \( O(\log n) \)
    3. \( O(n\log n) \)
    4. \( O(1) \)

  6. In simple chaining, what data structure is appropriate?

    1. Singly linked list
    2. Doubly linked list
    3. Circular linked list
    4. Binary tree

  7. Which is not true about insertion sort?

    1. Exhibits the worst case performance when the initial array is sorted in reverse order
    2. Worst case and average case performance is \( O(n^2) \)
    3. Can be compared to the way a card player arranges his card from a card deck
    4. None of the above

  8. Which of the below mentioned sorting algorithms is not stable?

    1. Selection sort
    2. Bubble sort
    3. Merge sort
    4. Insertion sort

  9. A pivot element to partition unsorted list is used in

    1. merge sort
    2. bubble sort
    3. selection sort
    4. insertion sort

  10. Which one of the following is divide and conquer approach?

    1. Insertion sort
    2. Merge sort
    3. Shell sort
    4. Heapsort
Q.2 Solve this question :[14]

  1. Write down breadth-first traversal and depth-first traversal of given graph taking 1 as source vertex.

    Question Diagram
Q.3 Solve this question :[14]

  1. Construct a B-tree with minimum degree t as 3 and a sequence of integers 10, 20, 30, 40, 50, 60, 70, 80 and 90 in an initially empty B-tree. Show each step.

Q.4 Solve this question :[14]

  1. Write a function to perform merge sort on array of element mentioned. Also write recurrence relation for time complexity of algorithm.

Q.5 Solve this question :[14]

  1. What is AVL tree? Describe deletion operation in AVL tree with example.

Q.6 Solve this question :[14]

  1. Apply bubble sort on given array of integers: 26, 45, 13, 23, 12, 7, 38, 42. Show the content of array after every pass.

Q.7 Solve this question :[14]

  1. Write the algorithm to count leaf node in binary tree and check whether the tree is balanced or not.

Q.8 Solve both questions :[14]

  1. What is hash table? How can we use this structure to find all anagrams in a dictionary?

  2. Write a function that inserts a given element in a binary search tree. If the element is already present, throw an exception 'duplicate value'.

Q.9 Write short notes on the following:[14]

  1. Linear and non-linear data structures

  2. How to implement stack using queue

  3. Heapsort

  4. C++ STL