Final Exam
Introduction to Computer Science
NCNU CSIE

Date: January 13th 2010
Time: 14:10-17:00
Open book; turn off computer & mobile phone

1. What will be the output of the following program?

   // Simple loop
   #include <iostream>
   using std::cout;
   
   int main()
   {
       const int K=4;
       int i, j;
       for (i=1; i<=4; i++)
       {
           for (j=0; j<K-i; j++)
   	    cout << " ";
   	for (j=0; j<2*i-1; j++)
   	    cout << "*";
   	cout << "\n";
       }
       return 0;
   }
   

2. Check whether the following program has any syntax mistake. If yes, point out the mistakes and correct them; if no, predict the output of the program.

   // Pointer to char
   #include <iostream>
   #include <string.h>
   using std::cout;
   using std::endl;
   
   int main()
   {
       char s[] = "The Stars, Like Dust";
       char *p1, *p2;
       char c;
   
       cout << s << endl;
   
       for (p2=s; *p2 != '\0'; p2++);
       p2--;
       p1=s;
       while (p1 < p2)
       {
           c = *p1; *p1 = *p2; *p2 = c;
           p1++; p2--;
       }
   
       cout << s << endl;
   	
       return 0;
   }

3. What will be the output of the following program?

   // Stack
   #include <iostream>
   using std::cout;
   using std::endl;
   
   int stack[10];
   int i=0;
   
   void push(int n)
   { stack[i++] = n;
   }
   
   int pop(void)
   {
       if (i>0)
          return stack[--i];
       else
       {
          cout << "Enpty stack!" << endl;
          return -1;
       }
   }
   
   int main()
   {
       int j;
       for (j=1; j<8; j++)
           push(j);
       for (j=0; j<7; j++)
           cout << pop();
       cout << endl;
   
       push(j=1); cout << pop();
       push(++j); push(++j); cout << pop();
       push(++j); push(++j); cout << pop();
       push(++j); push(++j); cout << pop();
       cout << pop(); cout << pop(); cout << pop();
       cout << endl;
       return 0;
   }
   

4. Wha will be the output of the following program?
   
   // Sort a program
   #include <iostream>
   using std::cout;
   
   int main()
   {
       const int MAX_LINE=10;
       const int STATEMENT_WIDTH=80;
       int numbers[MAX_LINE]={ 0 };        // Line number
       int next[MAX_LINE] = { 0 };         // Index of the next line
       char statements[MAX_LINE][STATEMENT_WIDTH];
       int nLines = 0;     // how many lines are kept in memory
       int temp = 0;
   
           strcpy(statements[nLines], "A=10"); numbers[nLines++] = 10;
           strcpy(statements[nLines], "C=A+B"); numbers[nLines++] = 30;
           strcpy(statements[nLines], "B=20"); numbers[nLines++] = 20;
   
       // Sort_program
       for (int i=nLines-1; i>=0; i--)
           for (int j=0; j<i; j++)
               if (numbers[j]>numbers[j+1])    // exchange
           {
               temp = numbers[j];
               numbers[j] = numbers[j+1];
               numbers[j+1] = temp;
           }
          
           // List_program
           for (int i=0; i<nLines; i++)
           {
                   cout << numbers[i] << " ";
                   cout << statements[i] << "\n";
           }
   
           return 0;
   }
   
   
   
   
5. Check whether the following program has any syntax mistake. If yes, point out the mistakes and correct them; if no, predict the output of the program.
   
   // Linked-list
   #include <iostream>
   
   using std::cout;
   using std::endl;
   
   struct LINE
   {
           short number;
           char statement[80];
           LINE* next;
   };
   
   
   LINE* pHead = NULL;     // Pointer to a line
   
   int insert_line(int n, char* s);
   void list_program(LINE*);
   
   
   int main()
   {
           insert_line(10, "A=10");
           insert_line(35, "PRINT C");
           insert_line(20, "C=A+B");
           insert_line(15, "B=20");
   
           list_program(pHead);
   
           return 0;
   }
   
   void list_program(LINE* p)
   {
           while (p != NULL)
           {
                   cout << p->number << " "
                           << p->statement << endl;
                   p = p->next;
           }
           return;
   }
   
   int insert_line(int n, char* s)
   {
           LINE* pLINE = new LINE; // Dynamic Memory Allocation (P.194)
           LINE* p;
   
           pLINE->number = n;
           strcpy(pLINE->statement, s);
           pLINE->next = NULL;
   
           if (pHead == NULL)
               pHead = pLINE;
           else
           {
               p = pHead;
               while (p->next != NULL)
                   p = p->next;
               p->next = pLINE;
           }
           return 0;
   }
   
   
   
6. Check whether the following program has any syntax mistake. If yes, point out the mistakes and correct them; if no, predict the output of the program.

   // Linked-list
   #include <iostream>
   
   using std::cout;
   using std::endl;
   
   struct LINE
   {
           short number;
           char statement[80];
           LINE* next;
   };
   
   
   LINE* pHead = NULL;     // Pointer to a line
   
   int insert_line(int n, char* s);
   void list_program(LINE*);
   
   
   int main()
   {
           insert_line(10, "A=10");
           insert_line(35, "PRINT C");
           insert_line(20, "C=A+B");
           insert_line(15, "B=20");
   
           list_program(pHead);
   
           return 0;
   }
   
   void list_program(LINE* p)
   {
           while (p != NULL)
           {
                   cout << p->number << " "
                           << p->statement << endl;
                   p = p->next;
           }
           return;
   }
   
   int insert_line(int n, char* s)
   {
           LINE* pLINE = new LINE; // Dynamic Memory Allocation (P.194)
           LINE* p;
   
           pLINE->number = n;
           strcpy(pLINE->statement, s);
   		pLINE->next = NULL;
   
           if (pHead == NULL)
               pHead = pLINE;
           else
           {
   			p = pHead;
               while (p->next != NULL && p->next->number < n)
                   p = p->next;
               if (p->next == NULL)
   				p->next = pLINE;
   			else
   			{
   				pLINE->next = p->next;
   				p->next = pLINE;
   			}
           }
           return 0;
   }
   
   
   

7. What will be the output of the following program?

   // Pascal's triangle
   #include <iostream>
   #include <string.h>
   using std::cout;
   using std::endl;
   
   int C(int n, int m)
   {
   	if (m==0 || n==m)
   		return 1;
   	else 
   		return C(n-1, m-1) + C(n-1, m);
   }
   
   int main()
   {
       int i, j;
   	for (i=0; i<6; i++)
   	{
   		for (j=0; j<=i; j++)
   			cout << C(i,j) << " ";
   		cout << "\n";
   	}
       return 0;
   }
   
   
   

8. What will be the output of the following program?

   // Pythagoras Theorem
   #include <iostream>
   #include <string.h>
   using std::cout;
   using std::endl;
   
   int main()
   {
   	int a, b, c;
   	for (c=3; c<20; c++)
   		for (b=3; b<c; b++)
   			for (a=3; a<b; a++)
   				if (a*a + b*b == c*c)
   					cout << a << "\t" << b << "\t" << c << "\n";
   	return 0;
   }
   
   
   
   

9. The following code is a little different from Ex6_09, so you can expect that its behavior is also different.Predict its output.
   

   // Pass by reference
   #include <iostream>
   using std::cout;
   
   void test1(int, int);
   void test2(int&, int&);
   void test3(int&, int);
   
   int main()
   {
       int i = 2, j = 1;
       test1(i,j); cout << i << j << "\n";
       test2(i,j); cout << i << j << "\n";
       test3(i,j); cout << i << j << "\n";
       return 0;
   }
   
   void test1(int i, int j)
   { i++; j++; }
   
   void test2(int& i, int& j)
   { i++; j++; }
   
   void test3(int& i, int j)
   { i++; j++; }
   
   

10. The following code is slightly different from the above one.  Predict its output.
    
    // Structure array
    #include <iostream>
    using std::cout;
    
    struct POINT
    {
        int x;
        int y;
    }
    
    int Area(POINT p1, POINT p2)
    { return (p2.x - p1.x) * (p2.y - p1.y);
    }
    
    int main()
    {
        POINT p[2] = { { 30, 40 } , { 50, 60 } };   
        cout << Area(p[0], p[1]) << "\n";
        return 0;
    }