科目名稱： 程式設計
 期末考 開課系所：資工系 考試日期 2018.6.21
系所別：
 年級：
 學號：
 姓名：
 考試時間 08:10-10:00
Open book; turn off computer & mobile phone
1
2



3



4
5
6
7
8


9




10



11


  1. (10%) In Berkeley Engineering Graduate Commencement, Tsai-Chu Yeh mentioned that what they learned in Berkeley are not only tools to complete missions, but also some soft skills. Can you name some of them?

  2. (10%) Determine whether the following code has syntax errors or not.  If it is correct, predict its output.  If it is incorrect, point out the mistake(s).
    // Overflow
    #include <iostream>
    using std::cin;
    using std::cout;
    using std::endl;

    int main()
    {
        unsigned short n = 11;
        unsigned short a = 7;
        for (unsigned short i = 1; i<n; i++)
        {
            a = a * i;
            if (i >= 7) cout << a << endl;
        }
        return 0;
    }

  3. (10%) Determine whether the following code has syntax errors or not.  If it is correct, predict its output.  If it is incorrect, point out the mistake(s).

    // Pointer to Character
    #include <iostream>
    using std::cout;
    using std::endl;

    int main()
    {
        char name[] = "Catherine Zeta-Jones";
        char* p = name;
        std::cout << name[10] << std::endl;
        std::cout << p+10 << std::endl;
        std::cout << *(p+10) << std::endl;
        return 0;
    }

  4. (10%) Determine whether the following code has syntax errors or not.  If it is correct, predict its output.  If it is incorrect, point out the mistake(s).

    // Default Value of a Parameter
    #include <iostream>
    using std::cout;
    using std::endl;

    int f(int a, int b=8, int c)
    { return a+b+c; }

    int main()
    {
        cout << f(7,9) << endl;
        return 0;
    }

  5. (10%) Determine whether the following code has syntax errors or not.  If it is correct, predict its output.  If it is incorrect, point out the mistake(s).

    // Pointer to Class, Array of Objects, Initialization List
    #include <iostream>
    #include <cstring>

    class Node
    {
    public:
        char ch;
        Node* next;

        Node(char c=' ', Node* p=NULL): ch(c), next(p) {}

        void Print()
        {
            for (Node* p=this; p!=NULL; p=p->next)
                std::cout << p->ch;
            std::cout << std::endl;
        }
    };

    int main()
    {
        char msg[] = "FOOTBALL";
        const int n = strlen(msg);
        Node m[8];
        m[0] = Node(msg[0], NULL);
        for (int i=1; i<n-1; i++)
        {
            m[i].ch = msg[i];
            m[i].next = &m[i-1];
        }
        m[5].Print();
        return 0;
    }
  6. (10%) What will be the output of the following program?

    // Tree height
    #include <iostream>
    struct TREE
    {
        TREE* left;
        char ch;
        TREE* right;
    };

    unsigned min(unsigned a, unsigned b)
    { return (a>b)?b:a; }

    unsigned h(TREE* p)
    {
        if (p == NULL)
            return 0;
        else
            return min(h(p->left), h(p->right)) + 1;
    }
    TREE* createTree()
    {
           TREE* f = new TREE; f->left = NULL; f->ch='F'; f->right = NULL;
       TREE* e = new TREE; e->left = NULL; e->ch='E'; e->right = f;
       TREE* d = new TREE; d->left = e; d->ch='D'; d->right = NULL;
       TREE* b = new TREE; b->left = d; b->ch='B'; b->right = NULL;
       TREE* c = new TREE; c->left = NULL; c->ch='C'; c->right = NULL;
       TREE* a = new TREE; a->left = b; a->ch='A'; a->right = c;
       return a;
    }

    int main()
    {
        TREE* p = NULL;
        p = createTree();
        std::cout << h(p) << std::endl;
        return 0;
    }

  7. (10%) What will be the output of the following program?

    // swap()
    #include <iostream>

    class CNumber
    {
    public:
        int value;

        CNumber(int n) { value = n; }

        void print() { std::cout << value << std::endl; }
        void swap(CNumber N)
        {
            int temp = N.value;
            N.value = value;
            value = temp;
        }
    };

    int main()
    {
        CNumber a(20);
        CNumber b(18);
        a.swap(b);
        a.print();
        b.print();
        return 0;
    }


  8. (10%) If you compile and run the following run on a x86 host, what will be the output?

    // Binary files
    #include <iostream>
    #include  <fstream>
    using std::ifstream;
    using std::ofstream;

    int main()
    {
        short a, b;
        ofstream outfile("a.dat", std::ios::binary);
        for (char c='A'; c<='D'; c++)       // 'A' == 65
            outfile.write(&c, 1);
        outfile.close();

        ifstream infile("a.dat", std::ios::binary);
        infile.read(reinterpret_cast<char *>(&a), 2);
        infile.read(reinterpret_cast<char *>(&b), 2);
        std::cout << a << '\t' << b << '\n';
        return 0;
    }

  9. (10%) Determine whether the following code has syntax erros or not.  If it is correct, predict its output.  If it is incorrect, point out the mistake(s).

    // STL vector
    #include <iostream>
    #include <vector>
    using std::cout;
    using std::endl;
    using std::vector;

    int main()
    {
        int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        vector<int> mydata(data+1, data+7);
        vector<int> hisdata(mydata.begin()+1, mydata.end()-1);
        for (int i=0; i<hisdata.size(); i++)
            cout << hisdata.at(i);
        cout << endl;
        return 0;
    }

  10. (10%) Determine whether the following code has syntax erros or not.  If it is correct, predict its output.  If it is incorrect, point out the mistake(s).

    // STL map
    #include <iostream>
    #include <map>
    #include <string>
    using std::cout;
    using std::endl;
    using std::map;
    using std::string;
    using std::pair;

    int main()
    {
        map<char, short> count;
        string vowels = "AEIOU";
        string movie = "CATHERINE ZETA-JONES";
        char c;
        for (int i=0; i<vowels.length(); i++)
            count.insert( pair<char, short>(vowels[i], 0) );
        for (int i=0; i<movie.length(); i++) {
            c = movie[i];
            if (count.find(c) != count.end())
                count[c]++;
        }

        for (map<char, short>::iterator i = count.begin();
                 i != count.end(); i++)
            cout << i->first << '\t' << i->second << endl;

        return 0;
    }

  11. (10%) Determine whether the following code has syntax erros or not.  If it is correct, predict its output.  If it is incorrect, point out the mistake(s).

    /*
     * This class generates prime numbers up to a user specified
     * maximum.  The algorithm used is the Sieve of Eratosthenes.
     * Given an array of integers starting at 2:
     * Find the first uncrossed integer, then cross out all its
     * multiples.  Repeat until there are no more multiples
     * in the array.
     */

    #include <iostream>
    #include <cmath>
    #include <vector>

    using std::cout;
    using std::endl;
    using std::vector;

    class PrimeGenerator
    {
    private:
        vector<bool> crossedOut;
        vector<int>  result;

    public:
        vector<int> generatePrimes(int maxValue)
        {
            if (maxValue > 2)
            {
                uncrossIntegersUpTo(maxValue);
                crossOutMultiples();
                putUncrossedIntegersIntoResult();
            }
            return result;
        }

        int show()
        {
            for (int i=0; i<result.size(); i++)
                cout << result.at(i)
                     << (i==result.size()-1?'\n':' ');
            return result.size();
        }

    private:
        void uncrossIntegersUpTo(int maxValue)
        {
            crossedOut.clear();     // If I remark this line
            for (int i=0; i<maxValue+1; i++)
                crossedOut.push_back(false);
        }

        void crossOutMultiples()
        {
            int limit = determineIterationLimit();
            for (int i=2; i<=limit; i++)
                if (notCrossed(i))
                    crossOutMultiplesOf(i);
        }

        int determineIterationLimit()
        {
            // Every multiple in the array has a prime factor that
            // is less than or equal to the root of the array size,
            // so we don't have to cross out multiples of numbers
            // larger than that root.

            double iterationLimit = sqrt(crossedOut.size() );
            return static_cast<int>( iterationLimit );
        }

        void crossOutMultiplesOf(int i)
        {
            for (int multiple = 2*i; multiple < crossedOut.size(); multiple += i)
                crossedOut.at(multiple) = true;
        }

        bool notCrossed(int i)
        {
            return crossedOut.at(i) == false;
        }

        void putUncrossedIntegersIntoResult()
        {
            result.resize( numberOfUncrossedIntegers() );
            for (int j=0, i=2; i<crossedOut.size(); i++)
                if ( notCrossed(i) )
                    result.at(j++) = i;
        }

        int numberOfUncrossedIntegers()
        {
            int count = 0;
            for (int i=2; i<crossedOut.size(); i++)
                if ( notCrossed(i) )
                    count++;

            return count;

        }
    };

    int main()
    {
        PrimeGenerator p, q;
        p.generatePrimes(15);
        p.show();
        q.generatePrimes(20);
        q.show();
        p.generatePrimes(25);
        p.show();

        return 0;
    }