Scribd Logo
Upload

Welcome to Scribd!

  • 18 views

    2020-Dec CS-306 57

    Uploaded by

    Anu Gau
    The document contains instructions for an exam on data structures. It provides 4 questions, each with 2 parts, testing knowledge of linked lists, binary search trees, sorting algorithms, graphs, heaps, and hashing.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    2020-Dec CS-306 57

    Uploaded by

    Anu Gau
    18 views2 pages
    The document contains instructions for an exam on data structures. It provides 4 questions, each with 2 parts, testing knowledge of linked lists, binary search trees, sorting algorithms, graphs, heaps, and hashing.

    Original Title

    2020-Dec_CS-306_57

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document contains instructions for an exam on data structures. It provides 4 questions, each with 2 parts, testing knowledge of linked lists, binary search trees, sorting algorithms, graphs, heaps, and hashing.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    18 views2 pages

    2020-Dec CS-306 57

    Uploaded by

    Anu Gau
    The document contains instructions for an exam on data structures. It provides 4 questions, each with 2 parts, testing knowledge of linked lists, binary search trees, sorting algorithms, graphs, heaps, and hashing.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    NATIONAL INSTITUTE OF TECHNOLOGY, HAMIRPUR

    Computer Science & Engineering Department


    End Semester Exam-October 2020

    Course: Open Elective-I Semester: 5th


    Subject Code: CS-306 Duration: 2 Hours
    Subject Name: Data Structure Max Marks: 50
    Date: 17/12/2020 Time: 10:00 AM–12:00 PM
    Note: All questions are compulsory

    Instructions:
     Each Student is required to write his/her Name, Roll No, Subject Name, Subject Code,
    Programme, Semester, Department, Date of Exam and Number of pages on top of the
    first sheet and put the Signature with date at the bottom of each sheet of the answer booklet.
     Please make one complete pdf of your scanned answer sheet and save it with the name as
    rollnosubjectcode.pdf only and then upload it.
     After the exam time is over, students may take extra 15 minutes to scan and upload their answer
    booklet on Google Classroom. Further, delay in submission by a student may lead to
    deduction in marks or rejection of whole answer booklet.

    Q.1 a) Given a linked list whose typical node consists of an INFO and LINK field. [5]
    Formulate an algorithm which will count the number of nodes in the list which
    contain the value greater than 10.

    b) How stack can be used to recognize strings aca, bcb, abcba, bacab, abbcbba? Show
    [5]
    the trace of contents of stack for recognizing the string abcba.

    Q.2 a) The Preorder traversal of the tree is: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10


    The inorder traversal of the tree is: [5]
    0, 1,2,3,4,5,6,7,8,9,10
    What is the postorder traversal?

    b) In the following binary search tree, first insert 10 and then insert 33. After these [5]
    insertions, delete 26 and, delete 14 and then delete 17. Draw the tree after each
    operation.

    Q.3 a) Rewrite the QUICK-SORT procedure to sort the numbers into nonincreasing instead [5]
    of nondecreasing order.

    b) Discuss the best case and worst case complexity of Insertion sort. [5]
    Q.4 a) Find the minimum spanning tree of the graph given below using Kruskal Algorithm. [5]

    b) Demonstrate Dijkstra algorithm on graph shown above where the source vertex is B. [5]

    Q.5 a) What are the minimum and maximum numbers of elements in a heap of height h? [2]

    b) Is the sequence 23, 17, 14, 6, 13, 10, 1, 5, 7, 12 a max-heap? Where in a max-heap [2]
    might the smallest element reside, assuming that all elements are distinct?

    c) Write pseudocode for the procedure MINHEAPIFY(A, i), which performs the [3]
    corresponding manipulation on a min-heap.

    d) Demonstrate the insertion of the keys 5, 28, 19, 15, 20, 33, 12, 17, 10 into a hash [3]
    table with collisions resolved by chaining. Let the table have 9 slots, and let the hash
    function be h(k) = k mod 9.

    You might also like