ข้อสอบเก่ามิดเทอม Data structure 2566/1

• CPU จาก Sun enterpise มีการทำงานแบบ single process โดยจัดระดับของ process แบบ First-In-First-Out จากตารางที่ process เข้ามา (Arrived time) และ Computation time จงเขียนว่าแต่ละ process เริ่มทำงานตอนไหน

• จงออกแบบ Data structure ของ Light weight Process, โดยที่แต่ละ Light weight process จะมี lwp_id, priory, และ stack ของมันโดยไม่จำเป็นต้องเขียนโค้ดในแต่ละ methods

class Stack {
    // Code here
};
class LWP {
    // Code here
};

• ผลลัพท์ของโค้ดนี้เป็นไง

int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for(int i = 0; i < 10; i += 2) {
    cout << arr[i] << "_";
}

• ผลลัพท์ของโค้ดนี้เป็นไง

int arr[] = {7, 8, 4, 4, 7, 2, -1, 1, 6, 9};
for(int i = 0; i < 10; i++) {
    for(int j = 0; j < 9; j++) {
        if(arr[j] > arr[j + 1]) {
            int t = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = t;
        }
    }
}

for(int i = 0; i < 10; i++) {
    cout << arr[i] << "_";
}

• หาอยากได้ผลลัพท์ออกมาดังนี้ -7-9--2-3--5-8-2-0-5- ต้องให้ A, B, C เป็นอะไร

int arr[3][3] = {{-7, 3, 2}, {9, -5, 0}, {-2, 8, 5}};
for(int i = 0; A; i++) {
    for(int j = 0; B; j++) {
        cout << C << "-";
    }
}

• จะเติมข้อมูล $11, 15, 24, 28, 9, 109, 21$ ลงใน การเก็บข้อมูลของ Open Address Hash table ใน Array t[7] โดยมี hash function ดังนี้

  $$H(x, i) = (x + x * i)$$

  • โดยที่ $x$ เป็น key และ $i$ เป็นจำนวนครั้งที่ถูก Collision

    $i$	0	1	2	3	4	5	6
    $t[i]$

• จะเติมข้อมูล $11, 15, 24, 28, 9, 109, 21$ ลงใน การเก็บข้อมูลของ Open Address Hash table ใน Array t[7] โดยมี hash function ดังนี้

  $$H(x, i) = (x + i)$$

  • โดยที่ $x$ เป็น key และ $i$ เป็นจำนวนครั้งที่ถูก Collision

    $i$	0	1	2	3	4	5	6
    $t[i]$

• ให้เขียนโค้ดสร้าง Linklist อันที่ 1, 2, และ 3 จาก Class ดังนี้ โดยมี head เป็น pointer ของ Class Node มีความหมายว่าเป็นสมาชิกตัวแรก

class Node {
    public:
        char c;
        Node *next;
};

• ให้เขียนโค้ดสร้าง Linlist อันที่ 1, 2, และ 3 จาก Class ดังนี้โดยมี head เป็น pointer ของ Class Node มีความหมายว่าเป็นสมาชิกตัวแรก จากนั้นให้เพิ่มสมาชิกตัวที่ 4 ระหว่างตัวที่ 2 และ 3

class Node {
    public:
        char c;
        Node *next;
}

• จงวาดรูปการเชื่อมต่อของ Linked lists โดยมี Operations ดังนี้ ถ้าหากมี index อยู่ใน Linked lists ให้ทำ หากอยู่นอก Linked lists ให้ไม่สนใจ

  
  1. Insert B after idx ที่ 0
  2. Insert C after idx ที่ 1
  3. Insert D before idx ที่ 0
  4. ...

• ให้เขียนโค้ดการ push เข้า stack จากตัวแปรดังนี้ โดยที่มี arr[10] เป็น stack และมี top เป็น index ไว้เก็บด้านบนสุดของ stack. ให้ top มีค่าเริ่มต้นเป็น 0

int arr[10];
int top = 0;

• ให้เขียนโค้ดการ pop ออกจาก stack จากตัวแปรดังนี้ โดยที่มี arr[10] เป็น stack และมี top เป็น index ไว้เก็บด้านบนสุดของ stack. ให้ top มีค่าเริ่มต้นเป็น 0

int arr[10];
int top = 0;

• จงแปลง Postfix expression $\lrArr$ Infix expression (อย่างละ 2 ข้อ)

  • a b c / - a d / e - * $\rArr \space?$
  • a + b * (c + d) / f + d * e $\rArr \space?$

• Application แบบไหนเหมาะสม Data structure แบบ Stack หรือ แบบ Queue โดยใส่ $x$ ลงในช่อง

  Application	Stack	Queue
  Reverse Polish
  Downloading web contents
  Function calls
  Signal Transportation
  Assembly language
  Process Management
  Image Rendering

• ให้เขียนขั้นตอนการ enqueue และ dequeue จาก Linked Lists โดยที่มีตัวแปร head เป็น pointer ของ Class Node มีความหมายว่าเป็นตัวแรกของ Linked Lists และ tail เป็น pointer ของ Class Node มีความหมายว่าเป็นตัวสุดท้ายของ Linked lists

• ให้ออกแบบ Data structure จาก Array, Linked list, Queue, Stacks และ Hash table โดยที่มีข้อมูลดังนี้

  • โดยอาจารย์ที่สอนในแต่ละวิชาจะกรอกคะแนนนักศึกษาที่สอน โดยจะมีรหัสวิชา ชื่อ วิชา คะแนนเต็ม และตามด้วยคะแนนของนศศแต่ละคน
  • เมื่อกรอกคะแนนครบหมดแล้วอาจารย์ต้องสามารถกรอกเลขรหหัสนักศึกษาเพื่อ ดูคะแนนของแต่ละวิชาได้
  • เงื่อนไข
    • โดยต้องใส่คะแนนเป็น Input ได้
    • สามารถดูคะแนนของทุกวิชาของนักศึกษาแต่ละคนได้

course_id course_name total_score
std_id std_name score
std_id std_name score
std_id std_name score
...

เช่น

1. 040613205 Data structure 50
670406261235 ABC 45
670406261234 DEF 48
1. 040613123 Tonkaewmetics 100
680406266789 TKL 5
670406261234 DEF 99

แล้วดูคะแนนของนศศ 670406261234 จะได้

040613123
040613205 Data structure 48
040613123 Tonkaewmetics 99