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

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

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

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

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

1.ง่าย

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

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

ลักษณะเด่นของเซต (set) ในฐานะชนิดข้อมูลนามธรรมคืออะไร

  1. Aเก็บสมาชิกโดยไม่มีซ้ำ
  2. Bเข้าถึงได้เฉพาะที่ปลายด้านเดียว
  3. Cเก็บคู่คีย์–ค่า
  4. Dเก็บสมาชิกเรียงลำดับ
3.ง่าย

ในต้นไม้ โหนดพี่น้อง (sibling) คืออะไร

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

แอปพลิเคชันต้องการค้นหาเร็ว และต้องแสดงรายการคีย์เรียงลำดับและตอบคำถามช่วง โครงสร้างใดเหมาะที่สุด

  1. Abinary search tree แบบสมดุล
  2. Bสแตก
  3. Cลิงก์ลิสต์ที่ไม่เรียงลำดับ
  4. Dตารางแฮช
5.ปานกลาง

extract-min ใน min-heap ทวิภาคทำงานอย่างไร

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

สมาชิกใหม่ถูกแทรกลงในฮีปทวิภาคอย่างไร

  1. Aแทรกที่ตำแหน่งตามลำดับโดยเลื่อนสมาชิกที่ใหญ่กว่าทั้งหมดไปทางขวาหนึ่งตำแหน่ง
  2. Bวางที่รากและเลื่อนลง
  3. Cสร้างฮีปใหม่ทั้งหมดตั้งแต่ต้น
  4. Dวางที่ท้ายอาร์เรย์และเลื่อนขึ้น (sift up) ตราบที่ยังละเมิดคุณสมบัติฮีป
7.ยาก

วัตถุถูกเก็บเป็นคีย์ใน hash map จากนั้นฟิลด์ที่ฟังก์ชันแฮชใช้ถูกเปลี่ยน ผลลัพธ์ที่น่าจะเกิดคืออะไร

  1. Aการค้นหาวัตถุอาจล้มเหลว เพราะมันอยู่ในถังของแฮชเก่า
  2. Bไม่มีอะไรเปลี่ยน เพราะแฮชของคีย์คำนวณเพียงครั้งเดียวตอนโปรแกรมเริ่มทำงาน
  3. Cmap ย้ายคีย์ไปถังใหม่โดยอัตโนมัติ
  4. Dmap โยนข้อผิดพลาดทันทีที่ฟิลด์เปลี่ยน
8.ยาก

ภายใต้การแฮชสม่ำเสมออย่างง่าย เวลาคาดหมายของการค้นหาในตารางแฮชแบบ chaining ที่มี n คีย์และ m ถังคือเท่าใด

  1. AO(n)
  2. BO(log n)
  3. CO(1 + α) เมื่อ α = n / m
  4. DO(m)

เฉลย

  1. 1. D · คิว (queue)
  2. 2. A · เก็บสมาชิกโดยไม่มีซ้ำ
  3. 3. C · โหนดที่มีแม่เดียวกัน
  4. 4. A · binary search tree แบบสมดุล
  5. 5. C · ย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
  6. 6. D · วางที่ท้ายอาร์เรย์และเลื่อนขึ้น (sift up) ตราบที่ยังละเมิดคุณสมบัติฮีป
  7. 7. A · การค้นหาวัตถุอาจล้มเหลว เพราะมันอยู่ในถังของแฮชเก่า
  8. 8. C · O(1 + α) เมื่อ α = n / m

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