1.ง่าย
ความสูงของต้นไม้มักถูกนิยามว่า
- Aจำนวนเส้นเชื่อมบนเส้นทางที่ยาวที่สุดจากรากไปยังใบ
- Bจำนวนโหนดทั้งหมดในต้นไม้ นับทั้งรากและใบทุกใบ
- Cจำนวนใบในต้นไม้
- Dจำนวนลูกของราก
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ในกราฟไม่มีทิศทาง ดีกรี (degree) ของจุดยอดคืออะไร
- Aจำนวนจุดยอดในกราฟ
- Bความยาวของเส้นทางที่ยาวที่สุดจากมัน
- Cตำแหน่งของมันในรายการประชิด
- Dจำนวนเส้นเชื่อมที่ต่ออยู่กับมัน
3.ง่าย
ลักษณะเด่นของเซต (set) ในฐานะชนิดข้อมูลนามธรรมคืออะไร
- Aเก็บสมาชิกโดยไม่มีซ้ำ
- Bเข้าถึงได้เฉพาะที่ปลายด้านเดียว
- Cเก็บคู่คีย์–ค่า
- Dเก็บสมาชิกเรียงลำดับ
4.ปานกลาง
ความซับซ้อนเชิงเวลาของการค้นหาคีย์ใน binary search tree ที่สมดุลคือเท่าใด
- AO(1)
- BO(n log n)
- CO(log n)
- DO(n)
5.ปานกลาง
วิธีแก้การชนกันแบบใดเก็บคีย์ที่ชนกันไว้ในลิสต์ที่ถังเดียวกัน
- Aการตรวจสอบกำลังสอง (quadratic probing)
- Bการตรวจสอบเชิงเส้น (linear probing)
- Cการแฮชซ้อน (double hashing)
- Dการเชื่อมโซ่แยก (separate chaining)
6.ปานกลาง
ต้นไม้ AVL และต้นไม้แดง–ดำ (red-black) รับประกัน
- Aไม่มีโหนดใดมีลูกสองตัว
- Bคีย์ถูกเก็บตามลำดับการแทรก
- Cการค้นหาในเวลาคงที่ทุกกรณี
- Dความสูง O(log n) ผ่านการปรับสมดุลใหม่
7.ยาก
คู่การท่องใดกำหนดต้นไม้ทวิภาคที่มีคีย์ไม่ซ้ำได้เพียงแบบเดียวเสมอ
- Apreorder และ inorder
- Blevel-order เพียงอย่างเดียว
- Cpreorder เพียงอย่างเดียว
- Dpreorder และ postorder
8.ยาก
ในบัฟเฟอร์วงกลม front == rear อาจหมายถึงว่างหรือเต็ม วิธีทั่วไปในการแยกสองกรณีคืออะไร
- Aเก็บจำนวนสมาชิกแยกต่างหาก หรือเว้นหนึ่งช่องไว้เสมอ
- Bล้างบัฟเฟอร์ทุกครั้งที่ front เท่ากับ rear ดังนั้นสถานะจึงเป็นว่าง
- Cเก็บ front และ rear ในตัวแปรเดียวกัน
- Dทำให้ขนาดบัฟเฟอร์เป็นเลขกำลังสอง
เฉลย
- 1. A · จำนวนเส้นเชื่อมบนเส้นทางที่ยาวที่สุดจากรากไปยังใบ
- 2. D · จำนวนเส้นเชื่อมที่ต่ออยู่กับมัน
- 3. A · เก็บสมาชิกโดยไม่มีซ้ำ
- 4. C · O(log n)
- 5. D · การเชื่อมโซ่แยก (separate chaining)
- 6. D · ความสูง O(log n) ผ่านการปรับสมดุลใหม่
- 7. A · preorder และ inorder
- 8. A · เก็บจำนวนสมาชิกแยกต่างหาก หรือเว้นหนึ่งช่องไว้เสมอ
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com