Scribd Logo
Upload

Welcome to Scribd!

  • 22 views

    Final-Term DSA V1

    Uploaded by

    Asadullah Tariq Tariq
    This document provides instructions for a data structures and algorithms exam, including 5 questions assessing algorithms for binary search trees, binary trees, AVL trees, min-heaps, graphs, hashing, and shortest path problems. Students are instructed to show their work step-by-step and only answer the parts asked. The exam is 120 minutes long and worth a total of 70 marks.

    Copyright:

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

    Final-Term DSA V1

    Uploaded by

    Asadullah Tariq Tariq
    22 views3 pages
    This document provides instructions for a data structures and algorithms exam, including 5 questions assessing algorithms for binary search trees, binary trees, AVL trees, min-heaps, graphs, hashing, and shortest path problems. Students are instructed to show their work step-by-step and only answer the parts asked. The exam is 120 minutes long and worth a total of 70 marks.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides instructions for a data structures and algorithms exam, including 5 questions assessing algorithms for binary search trees, binary trees, AVL trees, min-heaps, graphs, hashing, and shortest path problems. Students are instructed to show their work step-by-step and only answer the parts asked. The exam is 120 minutes long and worth a total of 70 marks.

    Copyright:

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

    Final-Term DSA V1

    Uploaded by

    Asadullah Tariq Tariq
    This document provides instructions for a data structures and algorithms exam, including 5 questions assessing algorithms for binary search trees, binary trees, AVL trees, min-heaps, graphs, hashing, and shortest path problems. Students are instructed to show their work step-by-step and only answer the parts asked. The exam is 120 minutes long and worth a total of 70 marks.

    Copyright:

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

    THE SUPERIOR UNIVERSITY LAHORE

    Faculty of Computer Science


    dd& Information Technology
    Final -Term, Fall 2021

    Faculty of Computing
    Subject: Data Structures & Algorithms Max Marks: 70
    Instructor: Asadullah Tariq QCH Signature: Dr Irfan ud Din

    Name: ___________________
    Instructions:
    Roll No: _________________
    1. The person sitting next to you is also in worries, so trust on your own logic.
    Date: ___________________
    2. Read the statement very carefully and write the only part you’re asked to answer.

    Time Allowed: 120 Min. 3. Keep an eye on your watch, no extra time will be given.
    Instructor: Muhammad Hassan Total Marks: 50

    Question 1: (6+6+6=18 Marks)

    (A) Write an algorithm to find minimum value in a Binary Search Tree (BST.

    Function int FindMin(Node *Root) will take a Root pointer as an


    argument and return the minimum value.

    (B) Write an algorithm of a function which will count total number of


    Nodes in a Binary Tree. (Hint: Binary Tree Traversing)

    (C) Write an algorithm to search the given value in AVL tree, function
    bool SearchinAVL(Node * root, int Key) will return true if key value
    is present in tree otherwise it will return false.

    Question 2: (6+6=12 Marks)

    (A) Insert the following values (from left to right) in an initially empty
    Min-Heap. You are required to draw every step by hand in your answer.

    45, 35, 8, 25, 11, 12, 24, 14

    (B) Insert the following values (left to right) in an initially empty AVL
    Tree, Do balancing where required, show your work step by step.

    15, 20, 24, 10, 13, 7, 30, 36


    Question 3: (6(2+2+2)+5+5=16 Marks)

    A. Traverse the tree given below according to the mentioned


    methods and write the sequence nodes.

    o In-Order Traversing
    o Pre-Order Traversing
    o Post-Order traversing

    B. Apply RemoveMin()on the following MinHeap, and draw each step by hand
    to fulfill the Min-Heap property.
    Note: RomoveMin() Function will remove the minimum value at once
    only.

    C. insert a new node 4 in the following heap and draw each step by hand
    to fulfill the Min-Heap property.
    Question 4: (3+3+8=14-Marks)

    A. Consider the following graphs given in figure (a) and (b) respectively.
    Your task is to represent these graphs using Adjacency matrix.

    (A) (B)

    B. Find the shortest path by using a shortest path algorithm (Dijikstra


    OR Prims OR ……….) for the following graph.

    Question 5: (5+5=10 Marks)

    Consider a list of elements given below, you are required to insert the
    elements in the given order (Left to right) in a hash table of size 10 using
    below mentioned methods, using the hash function h(x)=x mod N.

    List of Elements: 5, 6, 2, 16, 8, 19, 18, 26, 36, 3

    Methods to Perform:

    a) Separate Chaining
    b) Linear Probing

    You might also like