Data Structure Quiz #10 Search & Hash

ข้อใดจริงเกี่ยวกับโครงสร้างข้อมูล Hash

• เป็นโครงสร้างข้อมูลแบบไม่เชิงเส้น

• ตำแหน่งในการเก็บข้อมูลสัมพันธ์กับลำดับการเข้าของข้อมูล

• Hash function จะระบุตำแหน่งที่เก็บข้อมูล

• ใช้เวลาในการค้นหาข้อมูลอย่างน้อย O(log n)

Operator/Function ที่นิยมใช้ใน hash function คืออะไร

• Integer Division

• Modulo

• Ceiling

• Floor

กำหนดโครงสร้างข้อมูล Hash ที่มี Hash table ขนาด 10 ช่องและมี Hash function คือ H(x, i) = (x+ 2i)mod 10

(แก้ collision แบบ linear probing, i แทนจำนวนการชน)

ถ้ามีการใส่ข้อมูลที่มีค่าคีย์ = 24 เป็นข้อมูลแรก

ข้อมูลนี้จะถูกเก็บในช่อง index เท่าใด

กำหนดโครงสร้างข้อมูล Hash ที่มี Hash table ขนาด 10 ช่องและมี Hash function คือ H(x, i) = (x+ 2i)mod 10

(แก้ collision แบบ linear probing, i แทนจำนวนการชน)

ดังรูป

ถ้ามีการใส่ข้อมูลที่มีค่าคีย์ = 24 เป็นลำดับถัดไป

ข้อมูลนี้จะถูกเก็บในช่อง index เท่าใด

เมื่อกำหนดให้ Hash function คือ H(x)=(x+2i)mod 7 เมื่อ i แทนจำนวนการชน การใส่ข้อมูล "TUM" โดยมีการ weighting ลงใน hash table นี้ จะถูกเก็บในข้อมูลอินเด็กซ์หมายเลขอะไร

ข้อใดจริงเกี่ยวกับการค้นหาเชิงเส้น

• 
  ใช้กับข้อมูลที่ไม่เรียงลำดับได้

• เวลาใน best case คือ O(log n)

• 
  ถ้าเรียงลำดับข้อมูลก่อน จะลดเวลาสุทธิในการค้นหา worst case ได้

• 
  ใช้ในโครงสร้างข้อมูลเชิงเส้นทั่วไป

ข้อใดจริงเกี่ยวกับ Binary Search

• ใช้ค้นหาในข้อมูลที่ไม่เรียงลำดับได้เลย

• 
  ค้นหาโดยการเปรียบเทียบกับ mean ของข้อมูล

• ใช้เวลาค้นหากรณีแย่สุดเป็น O(log n)

• มีข้อมูล 4 ตำแหน่งที่จะหาพบในการเปรียบเทียบ 3 ครั้ง

ข้อใดถูกต้อง เกี่ยวกับ ขั้นตอนวิธี Binary Search ในอาร์เรย์ A

• 
  ถ้า Start <= End จะหยุดการทำงาน

• ถ้า key < A[mid] จะอัปเดท end = mid - 1

• ถ้า key > A[mid] จะอัปเดท start = mid - 1

• ถ้า key = mid จะสรุปว่าค้นหาพบ found = True

การค้นหา "80" ด้วย Interp. search ในข้อมูล 10 ตัว ที่มีค่า A[0]= 10 และ A[9]=90 จะได้ mid = ?

เงื่อนไขใดต่อไปนี้ ทำให้การค้นหา ของ interpolation search หยุดดำเนินการ

• 
  start > end

• A[start] ≤ key

• 
  key > A[end]

• found == True