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

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

ใบงานใหม่ฝึกออนไลน์พร้อมคำใบ้

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

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

1.ง่าย

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

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

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

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

ข้อแตกต่างหลักระหว่างอาร์เรย์สถิตกับอาร์เรย์พลวัตคืออะไร

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

โหนดใน binary search tree มีต้นไม้ย่อยขวา in-order successor ของมันอยู่ที่ใด

  1. Aแม่ของมันเสมอ
  2. Bลูกขวาของมันเสมอ
  3. Cโหนดขวาสุดของต้นไม้ย่อยซ้าย
  4. Dโหนดซ้ายสุดของต้นไม้ย่อยขวา
5.ปานกลาง

ในฮีปทวิภาคที่เก็บในอาร์เรย์เริ่มที่ดัชนี 0 แม่ของโหนดที่ดัชนี i อยู่ที่ใด

  1. Aที่ดัชนี 2i + 1
  2. Bที่ดัชนี ⌊(i − 1) / 2⌋
  3. Cที่ดัชนี i − 1
  4. Dที่ดัชนี ⌊i / 2⌋ + 1
6.ปานกลาง

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

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

โครงสร้าง union-find (เซตไม่เชื่อมกัน) ที่ใช้ union by rank และ path compression มีต้นทุนกระจายต่อการดำเนินการเป็น

  1. AO(n)
  2. BO(log n) พอดี
  3. CO(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
  4. DO(n²)
8.ยาก

คุณสมบัติใดทำให้ B-tree ทุกต้นสมดุลอย่างสมบูรณ์

  1. Aทุกโหนดมีลูกสองตัวพอดี
  2. Bคีย์ถูกเก็บเฉพาะที่ราก
  3. Cใบทั้งหมดอยู่ที่ความลึกเดียวกัน
  4. Dแต่ละโหนดเก็บหนึ่งคีย์

เฉลย

  1. 1. C · โหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
  2. 2. D · กราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
  3. 3. B · อาร์เรย์พลวัตขยายได้โดยย้ายไปยังบล็อกหน่วยความจำที่ใหญ่กว่า
  4. 4. D · โหนดซ้ายสุดของต้นไม้ย่อยขวา
  5. 5. B · ที่ดัชนี ⌊(i − 1) / 2⌋
  6. 6. B · คิวขนาดคงที่
  7. 7. C · O(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
  8. 8. C · ใบทั้งหมดอยู่ที่ความลึกเดียวกัน

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