1.ง่าย
ในกราฟไม่มีทิศทาง ดีกรี (degree) ของจุดยอดคืออะไร
- Aความยาวของเส้นทางที่ยาวที่สุดจากมัน
- Bจำนวนจุดยอดในกราฟ
- Cจำนวนเส้นเชื่อมที่ต่ออยู่กับมัน
- Dตำแหน่งของมันในรายการประชิด
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ลักษณะเด่นของเซต (set) ในฐานะชนิดข้อมูลนามธรรมคืออะไร
- Aเก็บคู่คีย์–ค่า
- Bเก็บสมาชิกเรียงลำดับ
- Cเข้าถึงได้เฉพาะที่ปลายด้านเดียว
- Dเก็บสมาชิกโดยไม่มีซ้ำ
3.ง่าย
ในลิงก์ลิสต์เชิงเดี่ยว ตัวชี้ next ของโหนดสุดท้ายมีค่าเป็น
- Aที่อยู่ของโหนดแรก
- BNull (ไม่มีโหนด)
- Cที่อยู่ของโหนดก่อนหน้า
- Dจำนวนโหนดในลิสต์
4.ปานกลาง
หาคีย์ที่น้อยที่สุดใน binary search tree ได้อย่างไร
- Aตามลูกขวาจากรากจนไม่มีลูกขวา
- Bเยี่ยมทุกใบและเปรียบเทียบกัน
- Cดูเฉพาะราก
- Dตามลูกซ้ายจากรากจนไม่มีลูกซ้าย
5.ปานกลาง
วิธีแก้การชนกันแบบใดเก็บคีย์ที่ชนกันไว้ในลิสต์ที่ถังเดียวกัน
- Aการตรวจสอบเชิงเส้น (linear probing)
- Bการเชื่อมโซ่แยก (separate chaining)
- Cการแฮชซ้อน (double hashing)
- Dการตรวจสอบกำลังสอง (quadratic probing)
6.ปานกลาง
คิวถูกสร้างด้วยสแตกสองตัว: push ลงสแตก "in" และ pop จากสแตก "out" โดยเติมจาก "in" เมื่อว่าง ต้นทุนกระจายต่อการดำเนินการคือเท่าใด
- AO(1)
- BO(log n)
- CO(n²)
- DO(n)
7.ยาก
เวลาทำงานของการค้นหาในแนวกว้างบนกราฟที่มี V จุดยอดที่เก็บเป็นเมทริกซ์ประชิดคือเท่าใด
- AO(V)
- BO(V + E)
- CO(E log V)
- DO(V²)
8.ยาก
อัลกอริทึมของ Kahn สำหรับการเรียงทอพอโลยีลบจุดยอดที่มี in-degree 0 ซ้ำ ๆ โครงสร้างใดเก็บจุดยอดเหล่านั้น
- Aสแตกของเส้นเชื่อมที่เยี่ยมทั้งหมด
- Bเมทริกซ์ประชิดที่บันทึกว่าจุดยอดใดถูกลบไปแล้ว
- Cคิว (หรือคอลเล็กชันใดก็ได้) ของจุดยอดที่มี in-degree เป็น 0
- Dmax-heap เรียงตาม out-degree
เฉลย
- 1. C · จำนวนเส้นเชื่อมที่ต่ออยู่กับมัน
- 2. D · เก็บสมาชิกโดยไม่มีซ้ำ
- 3. B · Null (ไม่มีโหนด)
- 4. D · ตามลูกซ้ายจากรากจนไม่มีลูกซ้าย
- 5. B · การเชื่อมโซ่แยก (separate chaining)
- 6. A · O(1)
- 7. D · O(V²)
- 8. C · คิว (หรือคอลเล็กชันใดก็ได้) ของจุดยอดที่มี in-degree เป็น 0
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com