Copyright © 2005 Suradet Jitprapaikulsarn
สงวนลิขสิทธิ์ 2548 สุรเดช จิตประไพกุลศาล

Final Examination 2

6 ตุลาคม 2548 เวลา 08:00 - 11:00 น.

1. (400 คะแนน) สมมติว่าวิชาที่คุณเรียนมีการบ้านหลายชิ้นที่คุณจะต้องส่งเพื่อเก็บคะแนน โดยการบ้านแต่ละครั้งมีคะแนนเต็ม 100 คะแนน Solution.

1.1. (30 คะแนน) เขียน data definition ของการบ้านโดยเรียกข้อมูลชนิดนี้ว่า Homework

//--------------------------------------------------------------------------
// Data Definition
//-----------------
// A homework is either
//  - an empty list
// or a structure consisting of
//  - data as number
//  - rest as homework
//--------------------------------------------------------------------------

1.2. (20 คะแนน) เขียนคำสั่งภาษา C สำหรับ data definition ในข้อ 1.1

struct Homework
{
    double data;
    Homework *rest;
};

1.3. (30 คะแนน) เขียนตัวอย่างข้อมูล data example) ของ data definition ในข้อ 1.2

Homework *empty = 0;
Homework hw1 = { 84.3, empty };
Homework hw2 = { 95.4, &hw1 };
Homework hw3 = { -59.0, &hw2 };
Homework hw4 = { 23.3, &hw3 };

1.4. (20 คะแนน) เขียน code pattern ของภาษา C สำหรับ data definition ในข้อ 1.1

... F(Homework * H)
{
    if (H == 0)
    {
        ...
    }
    else
    {
        ... H->data ...
        ... F(H->rest) ...
    }
}

1.5. (100 คะแนน) จงเขียนฟังก์ชัน isValidScore เพื่อตรวจสอบดูว่าคะแนนของแต่ละการบ้านอยู่ในช่วงคะแนนที่ถูกต้องหรือไม่

//--------------------------------------------------------------------------
// @description Check whether the homework scores are valid
// @param H a homework
// @return true if every score is between 0 and 100 inclusively
// @contract isValidScore : Homework -> boolean
// @example isValidScore(empty) == true
// @example isValidScore(&hw1) == true
// @example isValidScore(&hw2) == false
// @example isValidScore(&hw3) == false
//--------------------------------------------------------------------------
bool isValidScore(Homework * H)
{
    if (H == 0)
    {
        return true;
    }
    else
    {
        return (0 <= H->data) && (H->data <= 100) && isValidScore(H->rest);
    }
}

สมมติว่าในวิชาที่คุณเรียนนี้คะแนนการบ้านเป็นเพียงส่วนหนึ่งของคะแนนทั้งหมด โดยมีการแบ่งสัดส่วนดังต่อไปนี้

อนึ่งในหนึ่งภาคการศึกษามีเพียงโครงงานเดียว สมมติว่าโดยการบ้านแต่ละชิ้น โครงงานแต่ละ โครงงาน หรือสอบแต่ละครั้งล้วนมีคะแนนเต็ม 100 คะแนน

1.6. (30 คะแนน) เขียน data definition ของผลการเรียน โดยจะเรียกข้อมูลแบบนี้ว่า ScoreCard

//--------------------------------------------------------------------------
// Data Definition
//-----------------
// A ScoreCard is a structure consisting of
//  - hw as Homework
//  - project as number
//  - midterm as number
//  - final as number
//-------------------------------------------------------------------------- 

1.7. (20 คะแนน) เขียนคำสั่งภาษา C สำหรับ data definition ในข้อ 1.5

struct ScoreCard
{
    Homework    *hw;
    double      project;
    double      midterm;
    double      final;
};

1.8. (30 คะแนน) เขียนตัวอย่างข้อมูล (data example) ของ data definition ในข้อ 1.5

ScoreCard s1 = { empty, 60.0, 70.0, 95.0 };
ScoreCard s2 = { &hw1, 84.7, 37.9, 58.4 };
ScoreCard s3 = { &hw2, 68.7, 78.2, 95.6 };

1.9. (20 คะแนน) เขียน code pattern ของภาษา C สำหรับ data definition ในข้อ 1.5

... G(ScoreCard S)
{
    ... F(S.hw) ...
    ... S.project ...
    ... S.midterm ...
    ... S.final ...
}

1.10. (100 คะแนน) จงเขียนฟังก์ชัน finalScore เพื่อคำนวณหาคะแนนทั้งหมดที่ได้หลังจาก การแบ่งสัดส่วน

//--------------------------------------------------------------------------
// @description determine the final score according to the following ratio
//              homework    20%
//              project     15%
//              midterm     30%
//              final       35%
// @param S a score card
// @return the weighted sum of all scores
// @contract finalScore : ScoreCard -> double
// @example finalScore(S1) == 63.25
// @example finalScore(S2) == 61.375
// @example finalScore(S3) == 85.195
//--------------------------------------------------------------------------
double finalScore(ScoreCard S)
{
    return averageScore(S.hw) * 0.20 +
           S.project * 0.15 +
           S.midterm * 0.30 +
           S.final * 0.35;
}

2. (200 คะแนน) Binary Search Tree (BST) คือ binary tree ที่มีคุณสมบัติว่า ค่าที่อยู่ใน  subtree ทางซ้ายจะน้อยกว่าค่าที่อยู่ใน node และค่าที่อยู่ใน subtree ทางขวา จะมากกว่าค่าที่อยู่ใน node.  Solution.

2.1. (100 คะแนน) จงเขียนฟังก์ชัน contain? ในภาษา Scheme เพื่อตรวจดูว่า มีค่าที่สนใจใน BST หรือไม่

;----------------------------------------------------------------------------
; @description check whether a number is in a Binary Search Tree
; @param n the number to be checked
; @param T a binary search tree
; @return true if n is in T, false otherwise
; @contract contain? : number BT -> boolean
; @example (contain? 5 empty) = false
; @example (contain? 5 bt1) = true
; @example (contain? 5 bt2) = false
; @example (contain? 5 bt3) = true
;----------------------------------------------------------------------------
(define (contain? n T)
  (cond
    [(empty? T) false]
    [else (or (eq? n (BT-data T))
              (contain? n (BT-left T))
              (contain? n (BT-right T)))]))

2.2. (100 คะแนน) จงเขียนฟังก์ชัน insertBST เพื่อใส่ค่าเข้าไปใน BST

;----------------------------------------------------------------------------
; @description insert a number into a binary search tree
; @param n the number to be checked
; @param T a binary search tree
; @return a new binary with n inside
; @contract insertBST : number BST -> BST
; @example (insertBST 6 empty) = (make-BT 6 empty empty)
; @example (insertBST 6 bt1) = (make-BT 5 empty (make-BT 6 empty empty))
; @example (insertBST 6 bt2) = (make-BT 10 (make-BT 6 empty empty) empty)
; @example (insertBST 6 bt3) = (make-BT 8 (make-BT 5 empty (make-BT 6 empty empty)) (make-BT 10 empty empty))
;----------------------------------------------------------------------------
(define (insertBST n T)
  (cond
    [(empty? T) (make-BT n empty empty)]
    [(eq? n (BT-data T)) T]
    [(< n (BT-data T)) (make-BT (BT-data T)
                                (insertBST n (BT-left T))
                                (BT-right T))]
    [else (make-BT (BT-data T)
                   (BT-left T)
                   (insertBST n (BT-right T)))]))

3. (100 คะแนน) (Accumulating Knowledge) จงเขียนฟังก์ชัน list2num ในภาษา C เพื่อแปลง list ของตัวเลขให้กลายเป็นจำนวนเต็ม ตัวอย่างเช่น

list1 = { 1, empty };

list2 = { 4, &list1 };

list3 = { 7, & list2 };

list2num(&list3) == 147.

Hint: 147 = (((1x10) + 4) x 10) + 7

Solution.


//--------------------------------------------------------------------------
// @description convert a list of digits to a number
// @param L a list of digits
// @return the corresponding number
// @contract list2num : ListOfDigit -> number
// @example list2num(empty) == 0
// @example list2num(L1) == 1
// @example list2num(L2) == 14
// @example list2num(L3) == 147
//--------------------------------------------------------------------------
int list2num(ListOfDigit * L)
{
    if (L == 0)
    {
        return 0;
    }
    else
    {
        return list2num_A(L->rest, 10, L->first);
    }
}
//--------------------------------------------------------------------------
// @description convert a list of digits to a number
// @param L a list of digits
// @param multiplier the current multiplier
// @param acc the accumulated number so far
// @return the corresponding number
// @contract list2num_A : ListOfDigit number number -> number
// @example list2num_A(empty, 10, 2) == 2
// @example list2num_A(L1, 10, 9) == 19
// @example list2num_A(L2, 10, 7) == 147
//--------------------------------------------------------------------------
int list2num_A(ListOfDigit * L, int multiplier, int acc)
{
    if (L == 0)
    {
        return acc;
    }
    else
    {
        return list2num_A(L->rest, multiplier*10, L->first * multiplier + acc);
    }
}

Last update 6 October 2005, 22:23
Copyright © 2005 Suradet Jitprapaikulsarn
สงวนลิขสิทธิ์ 2548 สุรเดช จิตประไพกุลศาล