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

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

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

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

1.ง่าย

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

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

2.ง่าย

การดำเนินการใดช้าในอาร์เรย์แต่เร็วที่ส่วนหัวของลิงก์ลิสต์

Aการเข้าถึงสมาชิกตัวที่ 5
Bการอ่านสมาชิกตัวสุดท้ายด้วยดัชนี
Cการหาความยาวของอาร์เรย์ขนาดคงที่
Dการแทรกที่จุดเริ่มต้น

3.ง่าย

กราฟมีน้ำหนัก (weighted graph) คืออะไร

Aกราฟที่เก็บบนดิสก์
Bกราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
Cกราฟที่จุดยอดบางจุดหนักกว่าจุดอื่นเพราะมีเส้นเชื่อมมากกว่า
Dกราฟที่มีเส้นเชื่อมมากกว่าจุดยอด

4.ปานกลาง

นิพจน์ postfix 3 4 + 2 * มีค่าเท่าใด

5.ปานกลาง

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

6.ปานกลาง

บัฟเฟอร์วงกลม (circular buffer หรือ ring buffer) มักใช้สร้าง

Aคิวขนาดคงที่
Bฟังก์ชันแฮช
Cต้นไม้ค้นหาแบบทวิภาค
Dการท่องกราฟ

7.ยาก

ข้อใดเกี่ยวกับ heapsort ถูกต้อง

Aเรียงในที่เดิมใน O(n log n) กรณีเลวร้ายที่สุด แต่ไม่เสถียร
Bเสถียรและต้องใช้หน่วยความจำเพิ่ม O(n)
Cทำงานใน O(n) กับอินพุตใด ๆ
Dต้องใช้ binary search tree เป็นที่เก็บเพิ่มเติม จึงใช้หน่วยความจำเพิ่ม O(n)

8.ยาก

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

เฉลย

1. B · โหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
2. D · การแทรกที่จุดเริ่มต้น
3. B · กราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
4. D · 14
5. C · 20
6. A · คิวขนาดคงที่
7. A · เรียงในที่เดิมใน O(n log n) กรณีเลวร้ายที่สุด แต่ไม่เสถียร
8. C · 60

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