Skip to content
SmartFigureEdu

CD 3291 Data Structures and Algorithms question paper, November/December 2023

Download PDFRepeated questions and unit-wise bank

Question Paper Code : 20446

B.E./B.Tech. DEGREE EXAMINATIONS, NOVEMBER/DECEMBER 2023.

Second/Third Semester

Computer Science and Design

CD 3291 — DATA STRUCTURES AND ALGORITHMS

(Common to : Computer Science and Engineering (Artificial Intelligence and Machine Learning)/Computer Science and Engineering (Cyber Security)/Computer and Communication Engineering/Information Technology)

(Regulations 2021)

Time : Three hoursMaximum : 100 marks

Answer ALL questions.

PART A — (10 × 2 = 20 marks)

  1. 1.

    Identify how you will measure input size of an algorithm.

  2. 2.

    Define Accessors method in python.

  3. 3.

    Name any two applications where dequeue can be used.

  4. 4.

    Specify the time complexity of Insertion operation in circular linked list, how it is arrived.

  5. 5.

    Define collision in hashing.

  6. 6.

    State the algorithmic technique used in merge sort.

  7. 7.

    Difference between Binary Tree and Binary search Tree.

  8. 8.

    Give the worst, best average case complexities of Linear Search.

  9. 9.

    State Greedy algorithm.

  10. 10.

    List the three operations that can be performed on a graph.

PART B — (5 × 13 = 65 marks)

  1. 11.
    (a)
    • (i)Differentiate Data Types, Data Structures and Abstract Data Types.(5)
    • (ii)List the four factors that are dependent by the running time of a program.(4)
    • (iii)Assume an algorithm A, that solves problems by dividing them into 5 sub-problems of half the size. Then, recursively solving each sub-problem and combining the solution in linear time O(n). What is the recurrence relation of the algorithm A?(4)
  2. Or
  3. (b)
    • (i)With an example describe the two types of looping constructs used in Python.(4)
    • (ii)Describe the three steps involved in divide-and-conquer paradigm and how it is applied in merge sort algorithm.(5)
    • (iii)What are the various criteria used to improve the effectiveness of the algorithm?(4)
  4. 12.
    (a)
    • (i)Implement the operations Insert, Delete and Locate on List using Array-based implementation.(6)
    • (ii)List the disadvantages of queue data structure.(4)
    • (iii)Recall the advantages of linked list over arrays.(3)
  5. Or
  6. (b)
    • (i)Define Stack ADT and list the five operations that can be performed on it.(4)
    • (ii)There are two stacks in a single array, one grows from position 1 of the array, and the other grows from the last position. Write a procedure PUSH(x, S) that pushes element x onto stack S, where S is one or the other of these two stacks.(5)
    • (iii)Write an algorithm to insert a node before a given node in a linked list.(4)
  7. 13.
    (a)
    • (i)State and explain the algorithm of Quick Sort.(4)
    • (ii)Explain the working method of merge sort with the following data 10,15,0,17,20,30,70,6.(5)
    • (iii)Describe Linear search with an example.(4)
  8. Or
  9. (b)
    • (i)Differentiate Internal Sorting and External Sorting.(6)
    • (ii)What is insertion sort, explain its procedure by sorting the following elements 12, 11, 13, 5, 6, 3, 2.(7)
  10. 14.
    (a)

    Insert the following elements in sequence into an empty AVL Tree 43, 7, 15, 24, 12, 85, 74, 53.

  11. Or
  12. (b)

    Create a Binary search tree using the following data elements 40, 35, 53, 15, 73, 31, 5, 85, 51, 63, 79.

  13. 15.
    (a)
    • (i)Prove that the number of odd edge vertices in a connected graph should be even.(4)
    • (ii)Use Dijkstra'a Algorithm to find the shortest path. [Figure: weighted directed graph with edges A->B 7, A->C 12, B->C 2, B->D 9, C->E 10, E->D 4, D->F 1, E->F 5](6)
    • (iii)Compare and Contrast between Floyd's and Dijkstra's algorithms.(3)
  14. Or
  15. (b)
    • (i)Define Topological sort and write the procedure to do the same.(5)
    • (ii)Let G be a graph whose vertices are the integers 1 through 8, and let the adjacent vertices of each vertex be given by the table. Assume that, in a traversal of G, the adjacent vertices of a given vertex are returned in the same order as they are listed in the table below. [Table: vertex - adjacent vertices: 1 - (2, 3, 4); 2 - (1, 3, 4); 3 - (1, 2, 4); 4 - (1, 2, 3, 6); 5 - (6, 7, 8); 6 - (4, 5, 7); 7 - (5, 6, 8); 8 - (5, 7)] (1) Draw G (2) Order the vertices as they are visited in a DFS traversal starting at vertex 1. (3) Order the vertices as they are visited in a BFS traversal starting at vertex 1.(5)
    • (iii)Discuss the advantages of Depth-First Search.(3)

PART C — (1 × 15 = 15 marks)

  1. 16.
    (a)
    • (i)Define Selection sort and give its time and space complexity of the same for sorting the following elements 64, 25, 12, 22, 11.(8)
    • (ii)Create a binary search tree for the following numbers start from an empty binary search tree. 45, 26, 10, 60, 70, 30, 40 Delete keys 10, 60 and 45 one after the other and show the trees at each stage.(7)
  2. Or
  3. (b)

    Given Input {4371, 1323, 6173, 4199, 4344, 9679, 1989}, and a hash function h(x)=x mod 10. Do the following

    • (i)Open hash table(3)
    • (ii)Linear probing(4)
    • (iii)Quadratic probing(4)
    • (iv)Double hasing with h2(x) = 7 - (x mod 7)(4)

Other CD3291 papers