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

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

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

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

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

1.ง่าย

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

  1. Aต้นไม้ทวิภาค (binary tree)
  2. Bฮีป (heap)
  3. Cคิว (queue)
  4. Dสแตก (stack)
2.ง่าย

คุณสมบัติ max-heap คืออะไร

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

ตารางแฮชเก็บข้อมูลเป็น

  1. Aคู่คีย์–ค่าที่หาตำแหน่งด้วยฟังก์ชันแฮช
  2. Bรายการที่เรียงลำดับเท่านั้น
  3. Cต้นไม้ที่คีย์เรียงลำดับ
  4. Dสตริงความยาวคงที่
4.ปานกลาง

การค้นหาคำความยาว L ใน trie ที่มีตัวอักษรคงที่ใช้เวลาเท่าใด

  1. AO(L × n)
  2. BO(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
  3. CO(n) เมื่อ n คือจำนวนคำ
  4. DO(log n) เมื่อ n คือจำนวนคำ
5.ปานกลาง

การตรวจว่ามีเส้นเชื่อม (u, v) หรือไม่ด้วยเมทริกซ์ประชิดใช้เวลาเท่าใด

  1. AO(log V)
  2. BO(E)
  3. CO(1)
  4. DO(V)
6.ปานกลาง

เหตุใดฮีปทวิภาคจึงเก็บในอาร์เรย์ได้โดยไม่ต้องใช้ตัวชี้

  1. Aเป็นต้นไม้ทวิภาคสมบูรณ์ ตำแหน่งจึงเป็นไปตามสูตรดัชนีง่าย ๆ
  2. Bฮีปมีสมาชิกไม่เกิน 100 ตัวเสมอ
  3. Cอาร์เรย์เก็บคีย์ให้เรียงลำดับโดยอัตโนมัติ จึงไม่ต้องใช้ตัวชี้
  4. Dคีย์ทั้งหมดในฮีปเท่ากัน
7.ยาก

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

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

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

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

เฉลย

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

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