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

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

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

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

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

1.ง่าย

โครงสร้างข้อมูลใดทำงานตามหลักการ "เข้าหลังออกก่อน" (last in, first out)

  1. Aสแตก (stack)
  2. Bคิว (queue)
  3. Cตารางแฮช (hash table)
  4. Dลิงก์ลิสต์ (linked list)
2.ง่าย

กราฟประกอบด้วย

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

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

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

หาคีย์ที่น้อยที่สุดใน binary search tree ได้อย่างไร

  1. Aตามลูกขวาจากรากจนไม่มีลูกขวา
  2. Bเยี่ยมทุกใบและเปรียบเทียบกัน
  3. Cดูเฉพาะราก
  4. Dตามลูกซ้ายจากรากจนไม่มีลูกซ้าย
5.ปานกลาง

ต้นไม้ AVL รักษาเงื่อนไขสมดุลใดที่ทุกโหนด

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

เหตุใดการท่องอาร์เรย์จึงเร็วกว่าการท่องลิงก์ลิสต์ที่ยาวเท่ากันมากในทางปฏิบัติ

  1. Aสมาชิกของอาร์เรย์ต่อเนื่องกัน จึงใช้แคชของ CPU ได้ดี
  2. Bอาร์เรย์ใช้คำสั่งน้อยกว่าในการเปรียบเทียบค่า
  3. Cลิงก์ลิสต์เก็บสมาชิกบนดิสก์เสมอ
  4. Dการท่องอาร์เรย์เป็น O(1) โดยรวม ส่วนการท่องลิงก์ลิสต์เป็น O(n)
7.ยาก

Fenwick tree (binary indexed tree) บนอาร์เรย์ที่มีตัวเลข n ตัว รองรับการดำเนินการใดใน O(log n)

  1. Aการหามัธยฐานใน O(1)
  2. Bการแทรกสมาชิกที่ตำแหน่งใดก็ได้
  3. Cคำถามผลรวมคำนำหน้าและการอัปเดตสมาชิกเดียว
  4. Dการเรียงอาร์เรย์และการค้นหาแบบทวิภาค
8.ยาก

หากไม่มี union by rank หรือ path compression ต้นทุนในกรณีเลวร้ายที่สุดของ find หนึ่งครั้งในโครงสร้าง union-find ที่มี n สมาชิกคือเท่าใด

  1. AO(1)
  2. BO(n)
  3. CO(log n)
  4. DO(α(n))

เฉลย

  1. 1. A · สแตก (stack)
  2. 2. A · จุดยอด (โหนด) ที่เชื่อมต่อกันด้วยเส้นเชื่อม
  3. 3. D · จำนวนเส้นเชื่อมบนเส้นทางที่ยาวที่สุดจากรากไปยังใบ
  4. 4. D · ตามลูกซ้ายจากรากจนไม่มีลูกซ้าย
  5. 5. B · ความสูงของต้นไม้ย่อยซ้ายและขวาต่างกันไม่เกิน 1
  6. 6. A · สมาชิกของอาร์เรย์ต่อเนื่องกัน จึงใช้แคชของ CPU ได้ดี
  7. 7. C · คำถามผลรวมคำนำหน้าและการอัปเดตสมาชิกเดียว
  8. 8. B · O(n)

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