Copyright © 2005 Suradet Jitprapaikulsarn
สงวนลิขสิทธิ์ 2548 สุรเดช จิตประไพกุลศาล

Mid-term Examination 25 กรกฎาคม 2548 เวลา 18:00 - 21:00 น.

2.1             (50 คะแนน) Write the data definition for this data structure.

Data Definition
---------------
A SetOfNumber is either
 - an empty set
 - or a structure consisting of
     - member as number
     - subset as SetOfNumber

  2.2             (50 คะแนน) Write the C++ code for the above data definition.

struct SetOfNumber
{
    int         member;
    SetOfNumber *subset;
};

2.3             (50 คะแนน) Write the data examples using the digits from your student ID.  Note that there can NOT be any duplicate members in a set; therefore, if you student ID is 123424 then your last set contains 4 digits.  In other word, you will have 5 sets including the empty set.

2.4             (50 คะแนน) Write the code pattern for this data structure.

 ... F(SetOfNumber *S)
{
    if (S == 0)
    {

        ...
    }
    else
    {
        ... S->member ...
        ... F( S->subset ) ...
    }
}

2.5             (100 คะแนน) Write the function, isMember, to check whether a digit is in a set.

//--------------------------------------------------------------------------
// @description Check whether a digit is a member of a SetOfNumber
// @param x the number to check
// @param S a set of number
// @return true if x is in S, false otherwise
// @contract isMember: int SetOfNumber -> boolean
// @example isMember(5, set1) == false
// @example isMember(6, set3) == true
// @example isMember(8, set5) == true
//--------------------------------------------------------------------------
bool isMember(int x, SetOfNumber *S)
{
    if (S == 0)
    {
        return false;
    }
    else
    {
        if (x == S->member)
            return true;
        else
            return isMember(x, S->subset);
    }
}

2.6             (100 คะแนน) Write the function, isSubset, to check whether the first set is a subset of the second set.  Note that for set A to be a subset of set B, every member of A must be a member of B.

//--------------------------------------------------------------------------
// @description Check whether a SetOfNumber is a subset of another SetOfNumber
// @param S1 a set of number
// @param S2 a set of number
// @return true if S1 is a subset of S2, false otherwise
// @contract isSubset: SetOfNumber SetOfNumber -> boolean
// @example isSubset(empty, set1) == true
// @example isSubset(set1, empty) == false
// @example isSubset(set3, set5)  == true
//--------------------------------------------------------------------------
bool isSubset(SetOfNumber *S1, SetOfNumber *S2)
{
    if (S1 == 0)
    {
        return true;
    }
    else
    {
        if ( isMember(S1->member, S2) )
            return isSubset(S1->subset, S2);
        else
            return false;
    }
}

2.7             (100 คะแนน) Write the function, isEquivalent, to check whether two sets are equivalent.  Note that set A and set B are equal if A is a subset of B and B is also a subset of A