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

อะไรคือนิยามของต้นไม้ทวิภาค (binary tree)

1. Aทุกโหนดเก็บเลขฐานสอง
2. Bทุกโหนดมีลูกไม่เกินสองตัว
3. Cต้นไม้มีสองระดับพอดี
4. Dทุกโหนดมีลูกสองตัวพอดี

สมาชิกของอาร์เรย์ถูกเก็บในหน่วยความจำอย่างไร

1. Aในบล็อกต่อเนื่องเดียว ต่อกันทีละตัว
2. Bกระจัดกระจาย เชื่อมด้วยตัวชี้
3. Cในตำแหน่งสุ่มที่เลือกด้วยแฮช
4. Dในต้นไม้ของหน้าหน่วยความจำ

ความสูงของต้นไม้มักถูกนิยามว่า

1. Aจำนวนใบในต้นไม้
2. Bจำนวนโหนดทั้งหมดในต้นไม้ นับทั้งรากและใบทุกใบ
3. Cจำนวนเส้นเชื่อมบนเส้นทางที่ยาวที่สุดจากรากไปยังใบ
4. Dจำนวนลูกของราก

แทรกคีย์ 50, 30, 70, 20, 40 ตามลำดับนี้ลงใน binary search tree ว่าง ลูกซ้ายของ 30 คืออะไร

1. A40
2. B50
3. C70
4. D20

แอปพลิเคชันต้องการค้นหาเร็ว และต้องแสดงรายการคีย์เรียงลำดับและตอบคำถามช่วง โครงสร้างใดเหมาะที่สุด

1. Aลิงก์ลิสต์ที่ไม่เรียงลำดับ
2. Bตารางแฮช
3. Cสแตก
4. Dbinary search tree แบบสมดุล

ตารางแฮชขนาด 7 ใช้ h(k) = k mod 7 และ linear probing หลังแทรก 10 แล้ว 17 ถูกเก็บที่ใด

1. Aดัชนี 6
2. Bดัชนี 3
3. Cดัชนี 0
4. Dดัชนี 4

segment tree มักใช้เพื่อ

1. Aตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
2. Bเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน
3. Cเก็บเส้นเชื่อมของกราฟ
4. Dสร้างสแตก

อาร์เรย์พลวัตเพิ่มเป็นสองเท่าเมื่อเต็ม เหตุใดหลายการสร้างจึงหดมันเมื่อเหลือเพียงหนึ่งในสี่เท่านั้น ไม่ใช่ครึ่งหนึ่ง

1. Aเพราะการหดที่ครึ่งหนึ่งทำให้สมาชิกหาย
2. Bเพื่อให้อาร์เรย์เรียงลำดับ
3. Cเพื่อหลีกเลี่ยงการปรับขนาดซ้ำเมื่อ push และ pop สลับกันใกล้ขอบเขต
4. Dเพราะตัวจัดสรรหน่วยความจำคืนหน่วยความจำได้เฉพาะเป็นหนึ่งในสี่ของบล็อกเท่านั้น