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

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

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

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

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

1.ง่าย

แต่ละโหนดในลิงก์ลิสต์สองทิศทาง (doubly linked list) มีอะไร

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

ความลึก (depth) ของโหนดในต้นไม้คือ

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

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

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

รายการประชิดใช้หน่วยความจำเท่าใดสำหรับกราฟที่มี V จุดยอดและ E เส้นเชื่อม

  1. AO(V × E)
  2. BO(V + E)
  3. CO(V²)
  4. DO(E²)
5.ปานกลาง

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

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

คุณมีการอ้างอิงถึงโหนดกลางลิสต์ ในลิสต์ชนิดใดลบมันได้ใน O(1)

  1. Aอาร์เรย์เรียงลำดับ
  2. Bลิงก์ลิสต์เชิงเดี่ยว
  3. Cลิงก์ลิสต์สองทิศทาง
  4. Dอาร์เรย์พลวัต
7.ยาก

การแทรกคีย์ในต้นไม้ AVL ทำให้ต้นไม้ย่อยซ้ายของโหนดสูงเกินไป และคีย์ใหม่อยู่ในต้นไม้ย่อยซ้ายของลูกซ้าย (กรณีซ้าย–ซ้าย) ใช้วิธีแก้ใด

  1. Aหมุนซ้ายหนึ่งครั้งที่โหนดที่ไม่สมดุล
  2. Bเปลี่ยนสีโหนดและลูกของมัน
  3. Cหมุนซ้ายที่ลูก แล้วหมุนขวาที่โหนด
  4. Dหมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
8.ยาก

ข้อได้เปรียบหลักของ skip list เหนือลิงก์ลิสต์ที่เรียงลำดับคืออะไร

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

เฉลย

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

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