Final Exam
Introduction to Computer Science
NCNU CSIE

Date: January 18th, 2013
Time: 08:10-10:00
Open book; turn off computer & mobile phone

1. (10%) What will be the output of the following program?
   
   // Two's Complement
   #include <iostream>
   
   int main()
   {
       signed short m = 1<<15 | 1<<7;
       std::cout << m << std::endl;
       return 0;
   }
   
   
   
   
2. (10%) What will be the output of the following program?
   
   #include <iostream>
   using std::endl;
   using std::cout;
   
   int k;    // Be aware of global variables
   
   void PrintNumber(int i)
   {    
       for (int j=1; j<=i; j++)
           cout << j;
   }
   
   void PrintStar(int i)
   {
       for (k=1; k<=i; k++)
           cout << '*';
   }
   
   int main()
   {
       for (k=0; k<3; k++)
           PrintNumber(3);
       cout << endl;
   
       for (k=0; k<3; k++)
           PrintStar(3);
       cout << endl;
   
       return 0;
   }

3. (10%) What will be the output of the following program?
   
   // Point to char
   #include <iostream>
   
   int main()
   {
       char* movie_star[] = {
           "Arnold Schwarzenegger",
           "Bruce Willis",
           "Jackie Chan",
           "Jet Li",
           "Steven Seagal",
           "Sylvester Stallone" };
       std::cout << sizeof(movie_star[3]) << std::endl;
       return 0;
   }
   
   
   
   
   
   
4. (10%) What will be the output of the following program?
   
   // Bubble sort
   #include <iostream>
   
   int bsort1(int A[], int n)
   {
       int i,j,temp;
       bool sorted;
       for (i=n-1; i>0 ; i--)
       {
           sorted = true;
           for (j=0 ; j<i ; j++)       
               if (A[j] > A[j+1])
               {
                   temp = A[j]; A[j] = A[j+1]; A[j+1] = temp;
                   sorted = false;
               }       
           if (sorted)
               return n-i;
       }
       return n-1;
   }
   
   int main()
   {
       int a[] = { 2, 4, 6, 7, 1, 3, 5 };   
       int size = sizeof(a) / sizeof(a[0]);
       int n = 0;
       n = bsort1(a, size);
       std::cout << "It takes " << n << " pass"
           << (n>1?"es":"") << " to sort the sequence.\n";   
       return 0;
   }
   
   
   
   
5. (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).
   
   // switch-case
   #include <iostream>
   
   int main()
   {
       char str[] = "The Bear and The Dragon";
       char c;
       int i, count(0);
       for (i=0; i < sizeof(str); i++)
       {
           c = str[i];
           switch (c)
           {
           case 'A'<=c && c <= 'Z':
               count++;
               break;
           }
       }
       std::cout << count << std::endl;
       return 0;
   }
   
   
   
6. (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).
   
   // Pass-by-reference
   #include <iostream>
   
   struct ListElement
   {
       int value;
       ListElement* pNext;
   };
   
   void Print(ListElement &p)
   {
       std::cout << p.value;
       if (p.pNext != NULL)
       {
           p = *p.pNext;
           Print(p);   
       }
       else
           std::cout << std::endl;
   }
   
   int main()
   {
       ListElement LE1 = { 3, NULL };
       ListElement LE2 = { 1, &LE1 };
       ListElement LE3 = { 0, &LE2 };
       ListElement LE4 = { 2, &LE3 };
   
       Print(LE4);
       Print(LE4);
       return 0;
   }
   
   
   
   
   
   

7. (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).
   
   // Recursive function
   #include <iostream>
   
   static int count = 0;    // static variable    
   
   int fibonacci(int n)
   {
       count++;
       if (n == 0) return 0;    
       else if (n == 1) return 1;
       else return fibonacci(n-1) + fibonacci(n-2);
       std::cout << "fibonacci() called" << std::endl;
   }
   
   int main()
   {
       std::cout << fibonacci(5) << std::endl;
       std::cout << "This recursive function has been called " 
                   << count << " times." << std::endl;    
       return 0;
   }
   
   
   

8. (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).

   // Representing a polynomial with a linked-list
   #include <iostream>
   
   struct ListElement
   {
       int value;
       ListElement* pNext;
   };
   
   void Print(ListElement* p)
   {
       int i;
       for (i = 0; p != NULL; p = p->pNext, i++)
       {
           std::cout << "+" << p->value;
           if (i > 0)
           {
               std::cout << "X";
               if (i > 1)
                   std::cout << "^" << i;
           }
       }
       std::cout << std::endl;
   }
   
   int main()
   {
       ListElement LE4 = { 1, NULL };
       ListElement LE3 = { 2, &LE4 };
       ListElement LE2 = { 0, &LE3 };
       ListElement LE1 = { 3, &LE2 };
   
       Print(&LE1);
       return 0;
   }
   
   

9. (10%) The above Print() function does not handle negative coefficients beautifully.  For example, the polynomial "X^3-X^2-3" will be output as "+-3+0X+-1X^2+1X^3".  If we want it to print "-3-X^2+X^3", what expression should you supply in the following blank?
   

   // Representing a polynomial with a linked-list
   #include <iostream>
   using std::cout;
   
   struct ListElement
   {
       int value;
       ListElement* pNext;
   };
   
   void Print(ListElement* p)
   {
       int i;
       for (i = 0; p != NULL; p = p->pNext, i++)
       {
   	if (p->value == 0) continue;	// Skip this term
           if (p->value == -1) cout << '-';
           if (p->value > 0) cout << "+";
   	if (    (1)   p->value != 1) cout << p->value;
           if (i > 0)
           {
               cout << "X";
               if (i > 1)
                   cout << "^" << i;
           }
       }
       cout << std::endl;
   }
   
   int main()
   {
       ListElement LE4 = { 1, NULL };
       ListElement LE3 = { -1, &LE4 };
       ListElement LE2 = { 0, &LE3 };
       ListElement LE1 = { -3, &LE2 };
   
       Print(&LE1);
       return 0;
   }
   
   

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

    // Adding two polynomials
    #include <iostream>
    
    struct Polynomial
    {
        int coefficient;
        Polynomial* pNext;
    };
    
    void Print(Polynomial* p)
    {
        int i;
        for (i = 0; p != NULL; p = p->pNext, i++)
        {
            std::cout << "+" << p->coefficient;
            if (i > 0)
            {
                std::cout << "X";
                if (i > 1)
                    std::cout << "^" << i;
            }
        }
        std::cout << std::endl;
    }
    
    Polynomial* Add(Polynomial* p1, Polynomial* p2)
    {
    	int n;
    	Polynomial* pSum = NULL;
    	Polynomial* pHead = NULL;
    	Polynomial* pPrevious = NULL;
    	for (n=0; p1 || p2; n++)
    	{
    		pSum = new Polynomial;
    		if (!pHead) pHead = pSum;
    		if (pPrevious) pPrevious->pNext = pSum;
    		if (p1 == NULL)
    		{
    			pSum->coefficient = p2->coefficient;
    			p2 = p2->pNext;
    		}
    		else if (p2 == NULL)
    		{
    			pSum->coefficient = p1->coefficient;
    			p1 = p1->pNext;
    		}
    		else	// Neither p1 nor p2 are NULL
    		{
    			pSum->coefficient = p1->coefficient + p2->coefficient;
    			p1 = p1->pNext;
    			p2 = p2->pNext;
    		}
    		pPrevious = pSum;
    	}
    	pSum->pNext = NULL;
    	return pHead;
    }
    
    
    int main()
    {
    	Polynomial a2 = { 1, NULL };
    	Polynomial a1 = { 2, &a2 };
    	Polynomial a0 = { 1, &a1 };	// 1 + 2X + X^2
    
    	Polynomial b2 = { 4, NULL };
    	Polynomial b1 = { 4, &b2 };
    	Polynomial b0 = { 1, &b1 };	// 1 + 4X + 4X^2
    
    	Polynomial* ps = Add( &a0, &b0 );
    	Print(ps);
    	return 0;
    }