私立中原大學八十八學年度研究所招生考試命題紙

所組別 :資訊工程學系 科目 :計算機概論 考試時間 : 05月01日第 3節


注意事項： 程式必須加上適當註解,未加適當註解均扣分或不給分.
  1. [15 pts.]

    1. Let p be a pointer to an integer in the C program. Which expression is different from the others?
      2. (a) *p + = 1;
      (b) *p = *p + 1;
      (c) ++*p;
      (d) *p++;

    2. Which function declaration is not correct for the function definition in C++.

      3. void f(int j, float k)

      {

        // . . .

      }
      (a)void f(int, float);
      (b)void f(int k, float j);
      (c)void f(float k, int j);
      (d)void f(int j, float k);

    3. Which function declaration is invalid in C++ when we consider default arguments?
      4. (a)f(int x, int y);
      (b)f(int x=0, int y);
      (c)f(int x, int y=0);
      (d)f(int x=0, int y=0);

    4. What is the result of the C program?

      5. int f(int x, int y, int z)

      {

        int p;

        p = (x < y) ? x : y;

        return (p < z) ? p : z;

      }

      void main()

      {

        int j = f(1, 2, 3);

      }
      (a)j = 1
      (b)j = 2
      (c)j = 3
      (d)j = 6

    5. What is the value of x after executing the C program segment?

      6. int x, *y, z[4] = {0, 2, 4, 6};

      y = z;

      x = *(y + 2);
      (a)x = 0
      (b)x = 2
      (c)x = 4
      (d)x = 6

  2. [85 pts.]
    1. A Fibonacci function is defined as follows:

      1. [2 pts.] What is the value of Fib(6)? You must show detailed steps to get credits.
      2. [4 pts.] Write a function in C or C++ using recursion for the calculation of Fibonacci function, which takes one integer as input and returns the value of Fibonacci function.
      3. [4 pts.] Write a function in C or C++ using for-loop for the calculation of Fibonacci function, which takes one integer as input and returns the value of Fibonacci function.
      4. [3 pts.] What are the advantage and disadvantage of the recursive version compared to the for-loop version when we consider 1) efficiency, 2) memory usage, and 3) debugging?

      1. [4 pts.] Write a function with pointer parameters in C or C++ to exchange (swap) the values of two integers.
      2. [4 pts.] Write a function with reference parameters in C++ to exchange (swap) the values of two integers.

    3. An integer number is said to be a perfect number if its factors, including 1 (but not the number itself), sum to the number. For example, 6 is a perfect number because 6 = 1+2+3. Write a C or C++ function which takes one integer as input and

      1. [4 pts.] determines whether the input integer is a perfect number (using modulus operator %) and
      2. [4 pts.] prints the factors of the input integer when it is indeed perfect.

    4. [4 pts.] Please modify and complete the following Student class definition in C++ in order to keep track of the number of existing Student objects. You can save the number into an unsigned long number called “count” which is a data member of class Student.

      5. class Student {

         public:

            Student ( );

            ~Student ( );

          private:

            unsigned long id;

      }
    5. [10 pts.] Please explain the meaning of the following declaration. (For example, int *p is a pointer to an integer.)

      6. int **p;

      int *p[];

      int *p( );

      int (*p) ( );

      int (*(*p( ))[ ]) ( );

      　

    6. [4 pts.] What is the output of the following C program:

      7. void main()

      {

           int x=1, y=1;

           f(&x,y);

           f(&x,y);

           printf("x is %d; y is %d", x, y);

      }

      void f(int *p, int q)

      {

           static int r = 1;

           *p += r;

           q += r;

           printf("r is %d; ", r++);

      }

      　

      1. [2 pts.] Draw the binary tree after inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty binary tree.
      2. [3 pts.] What are the outputs by printing out all the numbers in the tree above via i) preorder, ii) inorder, and iii) postorder tree walk.
      3. [5 pts.] Write a nonrecursive function in C or C++ to search for a node with a given key in a binary tree. Given a pointer p to the root of the tree and a key k, the function should return a pointer to a node with key k if one exists; otherwise it should return NULL.

    8. Use big-O notation to determine the time complexity of the following codes. Assume that time complexity is measured by the number of assignments and comparison performed.
      1. [4 pts.]

        2.    for(i = 0; i < n; i++)

              for (j = 1, total = a[0]; j <= i; j++)

                total + = a[j];

      2. [4 pts.]

        3.    for(i = 4; i < n; i++)

              for (j = i - 3, total = a[i-4]; j <= i; j++)

                total + = a[j];

    9. The bubble sort is an algorithm for sorting a set of numbers.
      1. [4 pts.] Write a pseudo code for the bubble sort.
      2. [4 pts.] How many comparisons are used in the bubble sort?

    10. Hash functions are used to directly access data in a table.
      1. [4 pts.]What is hash collision when we use a hash function?
      2. [4 pts.]What is a perfect hash function?
      3. [4 pts.]Determine whether the following hash function h(K) is a perfect hash

        4. function:

        h(K) = (K mod p) mod Tsize for some prime number p > Tsize,

        where Tsize is the size of the table.

        　
        --- END---