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

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

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

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

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

1.ง่าย

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

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

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

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

สมาชิกของอาร์เรย์ถูกเก็บในหน่วยความจำอย่างไร

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

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

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

โครงสร้างข้อมูลใดใช้ตรวจว่าวงเล็บใน "{[()]}" สมดุลหรือไม่

  1. Aตารางแฮช
  2. Bคิว
  3. Cสแตก
  4. Dbinary search tree
6.ปานกลาง

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

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

ในบัฟเฟอร์วงกลม front == rear อาจหมายถึงว่างหรือเต็ม วิธีทั่วไปในการแยกสองกรณีคืออะไร

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

การแฮชซ้อน (double hashing) ลดปัญหาใดของ linear probing เป็นหลัก

  1. Aต้นทุน O(n) ในการอ่านค่าของคีย์
  2. Bความจำเป็นต้องเก็บคีย์ในตาราง
  3. Cการจับกลุ่มปฐมภูมิ (primary clustering) ซึ่งช่องที่ถูกใช้ต่อกันเป็นสายยาว
  4. Dความจำเป็นต้องมีฟังก์ชันแฮช

เฉลย

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

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