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

ใบงาน โครงสร้างข้อมูล ฟรีสำหรับพิมพ์: 8 ข้อ ตั้งแต่ระดับง่ายถึงระดับข้อสอบจริง พร้อมเฉลย พิมพ์หรือบันทึกเป็น PDF ได้

สำหรับผู้สอน: พิมพ์ ทำสำเนา และใช้ในชั้นเรียนได้ฟรี ใบงานใหม่แต่ละชุดมีค่าตัวเลขใหม่และเฉลยของตัวเอง หากใส่ลิงก์ไปยัง ExamProblems ในหน้ารายวิชาของคุณ เราจะขอบคุณมาก

ชื่อ: ____________________ วันที่: ____________

1.ง่าย

สมาชิกที่เล็กที่สุดของ min-heap ทวิภาคอยู่ที่ใด

Aในตำแหน่งสุดท้ายของอาร์เรย์
Bในใบซ้ายสุด
Cที่ราก
Dในใบใดก็ได้ ซึ่งต้องค้นหา

2.ง่าย

กราฟมีทิศทาง (directed graph) คืออะไร

Aกราฟที่ไม่มีวงจร
Bกราฟที่เส้นเชื่อมทุกเส้นมีน้ำหนัก
Cกราฟที่ทุกคู่ของจุดยอดที่ต่างกันเชื่อมกันด้วยเส้นเชื่อม
Dกราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง

3.ง่าย

ตัวประกอบการโหลด (load factor) ของตารางแฮชคืออะไร

Aจำนวนถังหารด้วยความยาวเฉลี่ยของคีย์ที่เก็บ
Bจำนวนการชนกันจนถึงตอนนี้
Cจำนวนสมาชิกที่เก็บหารด้วยจำนวนถัง
Dเวลาที่ใช้โหลดตารางจากดิสก์

4.ปานกลาง

เมทริกซ์ประชิด (adjacency matrix) ของกราฟที่มี V จุดยอดใช้หน่วยความจำเท่าใด

AO(V + E)
BO(E)
CO(V²)
DO(log V)

5.ปานกลาง

ความซับซ้อนเชิงเวลาของการค้นหาคีย์ใน binary search tree ที่สมดุลคือเท่าใด

AO(1)
BO(log n)
CO(n)
DO(n log n)

6.ปานกลาง

การค้นหาคำความยาว L ใน trie ที่มีตัวอักษรคงที่ใช้เวลาเท่าใด

AO(L × n)
BO(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
CO(n) เมื่อ n คือจำนวนคำ
DO(log n) เมื่อ n คือจำนวนคำ

7.ยาก

ใน BST ที่มีราก 50 ต้นไม้ย่อยซ้าย 30 (ลูก 20, 40) และต้นไม้ย่อยขวา 70 (ลูก 60, 80) ลบรากโดยใช้ in-order successor คีย์ใดกลายเป็นรากใหม่

8.ยาก

กฎของต้นไม้แดง–ดำรับประกันอะไรเกี่ยวกับความสูงของต้นไม้ที่มี n คีย์

Aความสูงไม่เกิน n / 2
Bความสูงไม่เกิน log₂ n + 1
Cความสูงเท่ากับ log₂ n พอดี
Dความสูงไม่เกิน 2 log₂(n + 1)

เฉลย

1. C · ที่ราก
2. D · กราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
3. C · จำนวนสมาชิกที่เก็บหารด้วยจำนวนถัง
4. C · O(V²)
5. B · O(log n)
6. B · O(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
7. D · 60
8. D · ความสูงไม่เกิน 2 log₂(n + 1)

เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com