Skip to content
SmartFigureEdu

CS 3301 Data Structures question paper, April/May 2024

Download PDFRepeated questions and unit-wise bank

Question Paper Code : 50896

B.E./B.Tech. DEGREE EXAMINATIONS, APRIL/MAY 2024.

Third Semester

Computer Science and Engineering

CS 3301 — DATA STRUCTURES

(Common to : )

(Regulations 2021)

Time : Three hoursMaximum : 100 marks

Answer ALL questions.

PART A — (10 × 2 = 20 marks)

  1. 1.

    State the advantages of modularity in programming.

  2. 2.

    What are ADT? Give an example.

  3. 3.

    A circular queue has a size of 5 and has 3 elements 11, 30, 41 where F=1 and R=3. After inserting 50 and 60, what is the value of F and R. Trying to insert 33 at this stage what happens. Delete 2 elements from the queue and insert 71, 98. Show the sequence of steps for the above operations.

  4. 4.

    A letter means push and an asterisk means pop in the following sequence. Give the sequence of values returned by the pop operations, when this sequence of operations is performed on an initially empty LIFO stack. U S G * O * O L D * * * E V * * * Y * O * *

  5. 5.

    What are the properties of AVL trees?

  6. 6.

    A binary tree T has 9 nodes. The inorder and postorder traversals of T yield the following: Inorder traversal (I): E A C K F H D B G Postorder traversal (Po): E C K A H B G D F Draw the binary tree.

  7. 7.

    Define Euler's circuits.

  8. 8.

    Give the topological order for the DAG in Figure 1. [Figure 1: DAG with vertices 1 to 7 and edges 1->3, 1->4, 2->4, 2->5, 4->3, 5->4, 3->6, 4->6, 4->7, 5->7]

  9. 9.

    What are the different hash functions?

  10. 10.

    The keys 22, 28, 23, 12, 13, 3, 25 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and apply linear probing for resolving the collision. What is the resultant hash table?

PART B — (5 × 13 = 65 marks)

  1. 11.
    (a)
    • (i)What are the different ways the list can be implemented? State and explain list ADT.(6)
    • (ii)Write the function to add two polynomial given as a linked list. Input: p1 = 13x^8 + 7x^5 + 32x^2 + 54, p2 = 3x^12 + 17x^5 + 3x^3 + 98(7)
  2. Or
  3. (b)
    • (i)Distinguish between singly, doubly and circular linked list with an example.(6)
    • (ii)Write a C function to insert a node in the middle of the linked list and count the number of nodes in the circular linked list.(7)
  4. 12.
    (a)
    • (i)What is circular queue? Explain with suitable example.(6)
    • (ii)State the application of Queue and explain any one application with an example.(7)
  5. Or
  6. (b)

    Write a C function for the following conversions.

    • (i)Infix to postfix expression
    • (ii)Evaluate the postfix expression

    (6+7)

  7. 13.
    (a)
    • (i)Distinguish between Binary tree, general tree and binary search tree and also give an example.(6)
    • (ii)Given the AVL Tree in Figure 2. Draw the resulting balanced tree step by step after 5 is removed. Label each node with balance factor. [Figure 2: AVL tree with root 5; 5 has children 3 and 10; 3 has children 2 and 4; 2 has left child 1; 10 has children 7 and 11; 7 has children 6 and 9; 9 has left child 8; 11 has right child 12](7)
  8. Or
  9. (b)

    Write a C function for the following in the Binary search tree:

    • (i)To find the height of a tree.
    • (ii)To Find minimum and maximum
    • (iii)Pre order traversals.

    (5+5+3)

  10. 14.
    (a)

    Distinguish between Prims and Kruskal's? Using Prims algorithm starting with vertex "A", list the vertices of the graph given in Figure 3. in the order they are added to maximum spanning tree. [Figure 3: undirected weighted graph with vertices A to J and edges A-B = 2, B-C = 3, A-D = 15, B-D = 5, B-E = 17, C-E = 12, C-F = 18, D-E = 4, E-F = 13, A-I = 9, D-G = 6, E-G = 11, E-H = 7, F-H = 14, G-H = 19, G-I = 8, G-J = 10, H-J = 16, I-J = 1]

  11. Or
  12. (b)
    • (i)What is B Tree and B+ Tree? Explain with example.(6)
    • (ii)Distinguish between BFS and DFS with the usage of stack and queue.(7)
  13. 15.
    (a)
    • (i)Distinguish between linear search and binary search.(6)
    • (ii)What is extendible hashing? State and explain with example.(7)
  14. Or
  15. (b)

    Sort the sequence 4, 6, 8, 2, 9, 5, 1, 7 and 3 using the following

    • (i)Merge sort
    • (ii)Quicksort (picking the first element as the pivot).

    (6+7)

PART C — (1 × 15 = 15 marks)

  1. 16.
    (a)

    What are the basic heap operations? Show how heap sort processes the input 142, 543, 123, 65, 453, 879, 572, 434, 111, 242, 811, 102.

  2. Or
  3. (b)

    Write the functions for the following operations on doubly linked list.

    • -Sum up the values stored in the nodes of a list.(5)
    • -Count the even numbers in the list.(5)
    • -Delete the node with an element X.(5)

Other CS3301 papers