Scribd Logo
Upload

Welcome to Scribd!

  • 19 views

    Question Bank1

    Uploaded by

    Rahul Sonawane

    Copyright:

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

    Question Bank1

    Uploaded by

    Rahul Sonawane
    19 views8 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

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

    Question Bank1

    Uploaded by

    Rahul Sonawane

    Copyright:

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

    B.Sc. (C.S.

    ) Question Paper format for the Examination


    April / May 2022
    Instructions:
    1. Questions: Number of Questions are: 5.
    2. Total Marks Assigned: 35.
    3. Time assigned: 2 Hours.

    Q1. Attempt any EIGHT of the following (Out of TEN). [ 1 X 8 = 8]


    Q2. Attempt any FOUR of the following (Out of FIVE). [ 2 X 4 = 8 ]
    Q3. Attempt any TWO of the following (Out of THREE). [ 4 X 2 = 8]
    Q4. Attempt any TWO of the following (Out of THREE). [ 4 X 2 = 8]
    Q5. Attempt any ONE of the following (Out of TWO). [ 3 X 1= 3]
    Chapter 1
    Tree
    A. Short Answer Questions: [1 or 2 Marks]
    a) Define tree?
    b) Define Height of tree?
    c) Define left skewed binary tree.
    d) What are the two methods of binary tree implementation?
    e) Define tree– traversal and mention the type of traversals?
    f) What is a binary tree?
    g) What are complete trees?
    h) List any two applications of Tree Data Structure.
    i) Which traversal will be used to display elements of Binary Search tree in ascending
    order?
    j) In binary tree construction which is the most efficient data structure used?
    k) There are 8, 15, 13, 14 nodes were there in 4 different trees. Which of them could have
    formed a full binary tree?
    l) Write preorder of following Binary Search Tree.

    B. Short Answer Questions: [3 or 4 Marks]


    a) Write a recursive ‘C’ function to search an element in a Binary Search Tree of integers.
    b) Write a recursive ‘C’ function to insert an element in a Binary Search Tree of integers.
    c) Write a ‘C’ function to compare two BST.
    d) Show the steps of creating a Binary search tree for the following data:
    15, 30, 20, 5, 10, 2, 7.
    e) Construct binary search tree for following data. Show the tree at each step
    34, 91, 30, 31, 80, 85, 138.
    f) 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.
    g) Construct binary search tree for following data. Show the tree at each step
    13, 4,25,3,21,20,7.
    h) Write a ‘C’ function to find minimum and maximum element from leaf nodes of a Binary
    tree.
    i) Write a ‘C’ function to find maximum element from Binary Search Tree.
    j) Sort the following data using Heap Sort procedure
    30, 55, 48, 37, 10, 91, 84, 2.
    k) Traverse the following binary tree using preorder, postorder, inorder traversal techniques.
    Chapter 2
    Efficient Search Trees
    A. Short Answer Questions: [1 or 2 Marks]
    a) What is an m-way search tree?
    b) What is ‘B’ Tree?
    c) Write the difference between Binary search tree and AVL Tree.
    d) What is the special property of red-black trees and what root should always be?
    e) True or false: Red-Black trees are an example of a self-balancing binary search tree. That
    is, they reorganize themselves when you insert nodes, so no global rebalancing is ever
    necessary.
    f) What are the Properties of Red Black Trees?
    g) What are the properties of B tree?

    B. Short Answer Questions: [3 or 4 Marks]


    a) Explain the AVL tree insertion and deletion with suitable example
    b) Write a short note on types of rotations on AVL tree.
    c) Describe the algorithms used to perform single and double rotation on AVL tree.
    d) Explain about B-Tree with suitable example.
    e) What is a balance factor in AVL trees?
    f) Write a short note on Splay Tree
    g) Explain the Insertion Operation in B-Tree with example.
    h) Construct the AVL Tree for the following data
    Chaitra, Magh, Vaishakh, Kartik, Falgun, Aashadh
    i) Construct an AVL tree for the following data:
    SRI, IND, AUS, FRA, CAN, DEN
    j) Construct an AVL tree for the following data:
    Mon., Wed., Tue., Sat., Sun., Thu.
    k) Construct an AVL tree for the following data:
    COMP, MATH, STAT, GEOG, ELEC, CHEM.
    Chapter 3
    Graph
    A. Short Answer Questions: [1 or 2 Marks]
    a) Define Graph?
    b) List any two methods of representing graphs.
    c) State any two applications of Graph.
    d) State the purpose of topological sort.
    e) What is a directed graph?
    f) Define indegree and out degree of a graph?
    g) Define path in a graph?
    h) What is the use of BFS?
    i) What is meant by strongly connected in a graph?
    j) State any one application of graph.
    k) Does the minimum spanning tree of a graph give the shortest distance between any 2
    specified nodes?
    l) Define AVL trees
    m) What is a heap?
    n) What is a spanning Tree?
    o) Name the data structure used for:
    a. BFS of graph
    b. DFS of graph.

    B. Short Answer Questions: [3 or 4 Marks]


    a) Consider the following graph:
    i) Draw the adjacency list.
    ii) Write the BFS and DFS traversals.
    iii) Which vertices have maximum indegree ?

    b) Define topological sorting. What will be the topological order of activities for the AOV
    network given below?
    c) Explain Breadth First Search algorithm with example?
    d) Explain Depth first and breadth first traversal?
    e) What is topological sort? Write an algorithm to perform topological sort?
    f) Consider the following graph:

    Write:
    (i) Adjacency matrix
    (ii) Adjacency list
    (iii) DFS and BFS (source vertex a).

    g) Consider the following graph:

    (i) Adjacency matrix


    (ii) Adjacency list
    (iii) DFS and BFS (source vertex V1).
    h) Explain Prim's algorithm with an example?
    i) Define topological sort? Explain with an example?
    j) Explain graph representation using adjacency multilist with example.
    k) Define the following terms:
    (a) Acyclic graph
    (b) Multigraph
    (c) Spanning Trees
    (d) Degree of vertex
    l) Write a Program that implements depth first search algorithm.
    m) Consider the following specification of a graph G:
    V(G) = {1, 2, 3, 4}
    E(G) = {(1, 2),(1, 3),(3, 3),(3, 4),(4, 1)}
    (i) Draw a picture of the undirected graph.
    (ii) Draw adjacency matrix of its.
    n) Consider the following adjacency matrix
    1000
    0001
    0010
    0100
    i) Draw the Graph
    ii) Draw the Adjacency list
    iii) Draw the Inverse Adjacency List.
    o) Write an algorithm for BFS traversal of a Graph.
    p) Explain Djiksatras algorithm
    q) What is a minimum spanning tree?
    r) What does Kruskals’s algorithm do? Explain with example.
    s) Consider the following graph.
    Write:
    i) Adjacency Matrix.
    ii) Adjacency List.
    iii) DFS and BFS (Start vertex V1)

    t)
    Chapter 4
    Hash Table

    You might also like