國立暨南國際大學 103 學年度第二學期小考試卷

1. (10%) Determine whether the following code is correct or not.  If it is correct, predict its output.  If it is incorrect, point out the mistake(s).
   
   // Dynamic Memory Allocation
   #include <iostream>
   using std::cin;
   using std::cout;
   using std::endl;
   
   struct ListElement
   {
           int value;              // value of an element
           ListElement* pNext;     // Pointer to a list element
   };
   
   ListElement* add(ListElement* pList, int v);
   
   void printList(ListElement* p);
   
   int main()
   {
       ListElement* pList = NULL;
       int a[] = {1, 3, 5, 7, 2, 4, 6, 0};
       int i, n;
       for (i=0; i < sizeof(a)/sizeof(a[0]); i++)
       {
           n = a[i];
           if (n > 0)
               pList = add(pList, n);
           else
               break;
       }
       printList(pList);
       return 0;
   }
   
   void printList(ListElement* p)
   {
       while (p != NULL)
       {
           std::cout << p->value;
           p = p->pNext;
       }
       cout << endl;
   }
   
   ListElement* add(ListElement* pList, int v)
   {
       ListElement* p = new ListElement;
       p->pNext = pList;
       p->value = v;
       return p;
   }
   
   
   
2. (10%) Determine whether the following code is correct or not.  If it is correct, predict its output.  If it is incorrect, point out the mistake(s).
   
   // Linked List
   #include <iostream>
   using std::cin;
   using std::cout;
   using std::endl;
   
   struct ListElement
   {
           int value;              // value of an element
           ListElement* pNext;     // Pointer to a list element
   };
   
   ListElement* add(ListElement* pList, int v);
   
   void printList(ListElement* p);
   
   int main()
   {
       ListElement* pList = NULL;
       int a[] = {1, 3, 5, 7, 2, 4, 6, 0};
       int i, n;
       for (i=0; i < sizeof(a)/sizeof(a[0]); i++)
       {
           n = a[i];
           if (n > 0)
               pList = add(pList, n);
           else
               break;
       }
       printList(pList);
       return 0;
   }
   
   void printList(ListElement* p)
   {
       while (p != NULL)
       {
           std::cout << p->value;
           p = p->pNext;
       }
       cout << endl;
   }
   
   ListElement* add(ListElement* pHead, int v)
   {
       ListElement* p = pHead;
       ListElement* original_pNext;
       if (pHead == NULL)
       {
           pHead = new ListElement;
           pHead->value = v;
           pHead->pNext = NULL;
       }
       else if (v < pHead->value)
       {
           pHead = new ListElement;
           pHead->value = v;
           pHead->pNext = p;
       }
       else
       {
           for (p=pHead; p->pNext != NULL && v > p->pNext->value; p=p->pNext)
               ;
           original_pNext = p->pNext;
           p->pNext = new ListElement;
           p->pNext->value = v;
           p->pNext->pNext = original_pNext;
       }
   
       return pHead;
   }
   
   
3. (10%) Determine whether the following code is correct or not.  If it is correct, predict its output.  If it is incorrect, point out the mistake(s).
   
   // Binary Tree
   #include <iostream>
   using std::cin;
   using std::cout;
   using std::endl;
   
   struct Node
   {
           int value;               // value of an element
           Node* pLeft;             // Pointer to the left child
           Node* pRight;            // Pointer to the right child
   };
   
   typedef Node* ptr;               // P.46
   
   Node* add(ptr& pNode, int n);
   void printTree(Node* p);
   
   int main()
   {
       Node* pTree = NULL;
       int a[] = {5, 7, 2, 4, 0};
       int i, n;
       for (i=0; i < sizeof(a)/sizeof(a[0]); i++)
       {
           n = a[i];
           if (n > 0)
               pTree = add(pTree, n);
           else
               break;
       }
       printTree(pTree);
       cout << endl;
       return 0;
   }
   
   void printTree(Node* pNode)
   {
       if (pNode->pLeft)
           printTree(pNode->pLeft);
       std::cout << pNode->value << ' ';
       if (pNode->pRight)
           printTree(pNode->pRight);
   }
   
   Node* add(ptr& pNode, int n)
   {
       int v;
       if (pNode == NULL)
       {
           pNode = new Node;
           pNode->value = n;
           pNode->pLeft = NULL;
           pNode->pRight = NULL;
       }
       else
       {
           v = pNode->value;
           if (v < n)
           {
               add(pNode->pRight, n);
           }
           else
               add(pNode->pLeft, n);
       }
   
   
       return pNode;  // TODO: changed to void
   }