ใบงาน โครงสร้างข้อมูล พร้อมเฉลย

ลักษณะเด่นของเซต (set) ในฐานะชนิดข้อมูลนามธรรมคืออะไร

1. Aเข้าถึงได้เฉพาะที่ปลายด้านเดียว
2. Bเก็บสมาชิกโดยไม่มีซ้ำ
3. Cเก็บสมาชิกเรียงลำดับ
4. Dเก็บคู่คีย์–ค่า

การท่องแบบ preorder ของต้นไม้ทวิภาคเยี่ยมโหนดตามลำดับใด

1. Aทีละระดับจากด้านบน
2. Bต้นไม้ย่อยซ้าย แล้วโหนด แล้วต้นไม้ย่อยขวา
3. Cโหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
4. Dต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด

โครงสร้างข้อมูลใดใช้ท่องต้นไม้แบบ level-order

1. Aสแตก
2. Bตารางแฮช
3. Cคิว
4. Dคิวลำดับความสำคัญ

ใน min-heap ทวิภาคที่เก็บในอาร์เรย์ (ดัชนีเริ่มที่ 0) ลูกของโหนดที่ดัชนี i อยู่ที่

1. Ai/2 และ i/2 + 1
2. Bi + 1 และ i + 2
3. C2i และ 2i + 1
4. D2i + 1 และ 2i + 2

อัลกอริทึมของ Dijkstra ใช้ชนิดข้อมูลนามธรรมใดเลือกจุดยอดถัดไปที่จะประมวลผล

1. Aสแตก
2. Bคิว FIFO
3. Cเซตที่ไม่มีลำดับ
4. Dคิวลำดับความสำคัญแบบค่าต่ำสุด (min-priority queue)

ต้นไม้ทวิภาคสมบูรณ์เต็ม (perfect binary tree) ที่มีความสูง h มีกี่โหนด เมื่อความสูงนับเป็นเส้นเชื่อม

1. A2h + 1
2. Bh²
3. C2^h
4. D2^h+1 − 1

ภายใต้การแฮชสม่ำเสมออย่างง่าย เวลาคาดหมายของการค้นหาในตารางแฮชแบบ chaining ที่มี n คีย์และ m ถังคือเท่าใด

1. AO(log n)
2. BO(m)
3. CO(1 + α) เมื่อ α = n / m
4. DO(n)

เพื่อให้ตารางแฮชทำงานถูกต้อง แฮชและความเท่ากันต้องเป็นไปตามกฎใด

1. Aค่าแฮชต้องเป็นจำนวนเฉพาะ
2. Bคีย์ที่เท่ากันต้องมีค่าแฮชเท่ากัน
3. Cคีย์ที่ต่างกันต้องมีค่าแฮชต่างกัน
4. Dค่าแฮชที่เท่ากันหมายถึงคีย์เท่ากัน