Scribd Logo
Upload

Welcome to Scribd!

  • 17 views

    Data Structure Assignment - Answers-2013

    Uploaded by

    Julian Ssonko

    Copyright:

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

    Data Structure Assignment - Answers-2013

    Uploaded by

    Julian Ssonko
    17 views11 pages

    Original Title

    Data Structure Assignment_Answers-2013

    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
    17 views11 pages

    Data Structure Assignment - Answers-2013

    Uploaded by

    Julian Ssonko

    Copyright:

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

    DFS Assignment Answers - 2013

    Q. Define Data Structure and explain its types.

    Data Structure:
    Data Structure is a way/method to store data so that various processes
    (searching, filtering etc.) can be applied on the data and Information from
    that stored data can be accessed quickly and efficiently.

    OR

    Data Structure is a triplet consisting of D, F, A where:


    D: Data that can be stored in the structure.
    F: Functions/Operations that can be done on the stored data.
    A: Axioms (Rules) to be applied on the data.

    Types of Data Structure:


    Non-Primitive / Classic Data Structures

    Linear Non-Linear

    Array Linked List Stack Queue Trees Graphs Tables Sets


    Q. State difference between linear and non-linear data structure with
    examples.

    Linear Data Structure Non-Linear Data Structure

    Data structure that stores the Data structure that stores the
    elements in a linear fashion. elements in a non-linear fashion.

    Elements are distributed over a plane


    Elements are stored in a
    where there is no particular
    line/sequence.
    sequence.

    Example: Stack, Queue Example: Tree, Graph


    Q. Explain row major order and column major order. OR Explain storage
    mechanisms for a 2-dimensional array.

    A 2-D array can be stored in 2 ways in memory:


    1) Row-major order.
    2) Column-major order.

    Row-major order:
    Elements are stored row-by-row / row-wise.
    First row, Second row and so on.

    Column-major order:
    Elements are stored column-by-column / column-wise.
    First column, Second column and so on.

    Example:

    A11 A11
    A11 A12
    A12 A21

    A21 A22 A21 A12


    A22 A22
    Row-major Column-major
    order order
    Q. Write an algorithm to delete a node from a singly linked list at any
    position.

    KEY = 45
    Header ptr1 ptr ptr2
    X 25 15 45 35 5 X

    Algorithm:
    DeleteAny_SL
    Input:
    Header: Pointer to the starting node of the linked list.
    KEY: Data of the node to be deleted.
    Output:
    Node with data KEY deleted from the linked list or message on
    failure.
    Data Structure:
    Single linked list whose address of starting node is known from
    Header.

    Steps:
    ptr = Header
    While(ptr->Link != NULL) AND (ptr->Data != KEY), do
    ptr1 = ptr
    ptr = ptr->Link
    EndWhile

    If(ptr->Data == KEY), then


    ptr2 = ptr->Link
    ptr1->Link = ptr2
    ReturnNode(ptr)
    Else
    print “KEY not found. Deletion not possible.”
    EndIf
    Stop
    Q. Define (with diagram/example) ‘Sibling’ and ‘Height of Tree’.

    Sibling:
    Nodes which have common or same parent are called Siblings.

    In the above tree, nodes B, C and D are siblings as their parent is same, node
    A.

    Height of Tree:
    Number of nodes in the longest path starting from root to leaf is called
    Height of Tree.
    Relationship between height and maximum level is: h = lmax + 1

    Height of the above mentioned tree is 3.


    Q. What is Sparse Matrix? Explain in brief. OR Define Sparse Matrix with
    example.

    Sparse Matrix:
    A sparse matrix is a 2-dimensional array where majority of the elements are
    NULL.

    As a result, there is a lot of memory wastage.

    Example of Sparse Matrix:

    5 - -

    - - 9

    - - -

    1 - -
    Q. Convert the following expressions to prefix and postfix.

    1) ( ( ( A + B ) * C ) – D ) / F

    Postfix:

    Step-1: Fully parenthesize the expression.

    Step-2: Move the operators to the corresponding right parenthesis.

    Step-3: Remove all the parentheses.

    A B + C * D – F / [Postfix Expression]

    Prefix:

    Step-1: Fully parenthesize the expression.

    Step-2: Move the operators to the corresponding left parenthesis.

    Step-3: Remove all the parentheses.

    / - * + A B C D F [Prefix Expression]
    Q. Convert the following expressions to prefix and postfix.

    2) ( ( P + ( ( Q ^ R ) – S ) ) * ( U – ( P / R ) ) )

    Postfix:
    Step-1: Fully parenthesize the expression.

    Step-2: Move the operators to the corresponding right parenthesis.

    Step-3: Remove all the parentheses.


    P Q R ^ S - + U P R / - * [Postfix Expression]

    Prefix:
    Step-1: Fully parenthesize the expression.

    Step-2: Move the operators to the corresponding left parenthesis.

    Step-3: Remove all the parentheses.


    * + P - ^ Q R S – U / P R [Prefix Expression]
    Q. Convert the following expression into POSTFIX using algorithm method:
    ((A*B+C)+D–E)/(G+H)–(I*J/K)

    Infix expression enclosed in brackets:


    (((A*B+C)+D–E)/(G+H)–(I*J/K))

    Step Symbol Stack O/P (Postfix)


    1 ( ( -
    2 ( (( -
    3 ( ((( -
    4 A ((( A
    5 * (((* A
    6 B (((* AB
    7 + (((+ AB*
    8 C (((+ AB*C
    9 ) (( AB*C+
    10 + ((+ AB*C+
    11 D ((+ AB*C+D
    12 - ((- AB*C+D+
    13 E ((- AB*C+D+E
    14 ) ( AB*C+D+E-
    15 / (/ AB*C+D+E-
    16 ( (/( AB*C+D+E-
    17 G (/( AB*C+D+E-G
    18 + (/(+ AB*C+D+E-G
    19 H (/(+ AB*C+D+E–GH
    20 ) (/ AB*C+D+E–GH+
    21 - (- AB*C+D+E–GH+/
    22 ( (-( AB*C+D+E–GH+/
    23 I (-( AB*C+D+E–GH+/I
    24 * (-(* AB*C+D+E–GH+/I
    25 J (-(* AB*C+D+E–GH+/IJ
    26 / (-(/ AB*C+D+E–GH+/IJ*
    27 K (-(/ AB*C+D+E–GH+/IJ*K
    28 ) (- AB*C+D+E–GH+/IJ*K/
    29 ) AB*C+D+E–GH+/IJ*K/-
    Q. Convert the following expression into POSTFIX using algorithm method:
    (A*C+D)–(E–F+G/H)+J

    Infix expression enclosed in brackets:


    ((A*C+D)–(E–F+G/H)+J)

    Step Symbol Stack O/P (Postfix)


    1 ( ( -
    2 ( (( -
    3 A (( A
    4 * ((* A
    5 C ((* AC
    6 + ((+ AC*
    7 D ((+ AC*D
    8 ) ( AC*D+
    9 - (- AC*D+
    10 ( (-( AC*D+
    11 E (-( AC*D+E
    12 - (-(- AC*D+E
    13 F (-(- AC*D+EF
    14 + (-(+ AC*D+EF-
    15 G (-(+ AC*D+EF-G
    16 / (-(+/ AC*D+EF-G
    17 H (-(+/ AC*D+EF–GH
    18 ) (- AC*D+EF–GH/+
    19 + (+ AC*D+EF–GH/+-
    20 J (+ AC*D+EF–GH/+-J
    21 ) AC*D+EF–GH/+-J+
    Q. Consider the following expression and evaluate: 15, 3, -, 2, *, 6, 6, /, -

    Step Symbol Stack Operation


    1 15 15 Push(15)
    2 3 15, 3 Push(3)
    y = Pop() // 3
    x = Pop() // 15
    3 - 12
    result = x – y = 15 – 3 = 12
    Push(result)
    4 2 12, 2 Push(2)
    y = Pop() // 2
    x = Pop() // 12
    5 * 24
    result = x * y = 12 * 2 = 24
    Push(result)
    6 6 24, 6 Push(6)
    7 6 24, 6, 6 Push(6)
    y = Pop() // 6
    x = Pop() // 6
    8 / 24, 1
    result = x / y = 6 / 6 = 1
    Push(result)
    y = Pop() // 1
    x = Pop() // 24
    9 - 23
    result = x - y = 24 - 1 = 23
    Push(result)

    Value of the given expression is 23.

    You might also like