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

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

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

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

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

1.ง่าย

deque (double-ended queue) คืออะไร

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

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

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

แมป (map หรือ dictionary) เก็บอะไร

  1. Aคู่ของคีย์ที่เท่ากัน
  2. Bค่าที่เรียงตามขนาด
  3. Cค่าตามลำดับการแทรกเท่านั้น
  4. Dคู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
4.ปานกลาง

อัลกอริทึมของ Dijkstra ใช้ชนิดข้อมูลนามธรรมใดเลือกจุดยอดถัดไปที่จะประมวลผล

  1. Aสแตก
  2. Bคิว FIFO
  3. Cคิวลำดับความสำคัญแบบค่าต่ำสุด (min-priority queue)
  4. Dเซตที่ไม่มีลำดับ
5.ปานกลาง

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

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

วิธีแก้การชนกันแบบใดเก็บคีย์ที่ชนกันไว้ในลิสต์ที่ถังเดียวกัน

  1. Aการเชื่อมโซ่แยก (separate chaining)
  2. Bการแฮชซ้อน (double hashing)
  3. Cการตรวจสอบเชิงเส้น (linear probing)
  4. Dการตรวจสอบกำลังสอง (quadratic probing)
7.ยาก

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

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

อาร์เรย์พลวัตเพิ่มเป็นสองเท่าเมื่อเต็ม เหตุใดหลายการสร้างจึงหดมันเมื่อเหลือเพียงหนึ่งในสี่เท่านั้น ไม่ใช่ครึ่งหนึ่ง

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

เฉลย

  1. 1. C · โครงสร้างที่อนุญาตให้แทรกและเอาออกที่ทั้งสองปลาย
  2. 2. A · การแทรกที่จุดเริ่มต้น
  3. 3. D · คู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
  4. 4. C · คิวลำดับความสำคัญแบบค่าต่ำสุด (min-priority queue)
  5. 5. B · สมาชิกของอาร์เรย์ต่อเนื่องกัน จึงใช้แคชของ CPU ได้ดี
  6. 6. A · การเชื่อมโซ่แยก (separate chaining)
  7. 7. B · หมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
  8. 8. B · เพื่อหลีกเลี่ยงการปรับขนาดซ้ำเมื่อ push และ pop สลับกันใกล้ขอบเขต

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