ชุดที่ 4 โครงสร้างข้อมูล การค้นหา และการเรียงลำดับ

ชุดนี้ครอบคลุมอาร์เรย์ รายการโยง สแตก คิว ฮีป ต้นไม้ ต้นไม้ค้นหาแบบทวิภาค กราฟ ตารางแฮช การค้นหาแบบลำดับและแบบทวิภาค และอัลกอริทึมการเรียงลำดับ เน้นการไล่ขั้นตอนและการเลือกใช้ให้เหมาะกับงาน

ซีรีส์ตะลุยข้อสอบครูผู้ช่วย เอกคอมพิวเตอร์ 2569 • exammvp.com

สรุปก่อนทำข้อสอบ

อาร์เรย์และรายการโยง

• อาร์เรย์: หน่วยความจำต่อเนื่อง · เข้าถึงด้วยดัชนี O(1) · แทรก/ลบกลางต้องเลื่อนข้อมูล O(n)
• ที่อยู่ A[i] = base + i × size · สองมิติแบบ Row-major: A[i][j] = base + (i × จำนวนคอลัมน์ + j) × size
• รายการโยง: โหนด = ข้อมูล + ตัวชี้ · แทรก/ลบเมื่อรู้ตำแหน่ง O(1) · เข้าถึงตัวที่ k ต้องไล่ O(n) · ลบโหนดถัดจาก p: p.next = p.next.next · รายการโยงคู่เดินย้อนกลับได้

สแตกและคิว

• คิววงกลม: rear = (rear + 1) mod n นำช่องว่างกลับมาใช้ · Min-Heap รากมีค่าน้อยสุด ใช้ทำคิวลำดับความสำคัญ
• Infix (A + B) × C − D → Postfix A B + C × D −

ต้นไม้ (Tree)

• ราก · ใบ (ไม่มีลูก) · ความสูง = จำนวนเส้นเชื่อมจากรากถึงใบที่ลึกที่สุด · ต้นไม้ n โหนดมี n − 1 เส้นเชื่อม
• ต้นไม้ทวิภาคสูง h มีโหนดได้มากสุด 2^(h+1) − 1 · ชั้นที่ k มีได้มากสุด 2^k โหนด
• Preorder (ราก–ซ้าย–ขวา) · Inorder (ซ้าย–ราก–ขวา, BST ได้ข้อมูลเรียง) · Postorder (ซ้าย–ขวา–ราก, ต้นไม้นิพจน์ได้ Postfix)
• BST: ซ้ายน้อยกว่า ขวามากกว่า · สมดุลค้นหา O(log n) · ใส่ข้อมูลที่เรียงแล้วกลายเป็นเส้นตรง O(n) → แก้ด้วย AVL / Red-Black Tree

กราฟ (Graph)

• ผลรวมดีกรี = 2 × จำนวนเส้นเชื่อม · Adjacency Matrix O(V²) เหมาะกราฟหนาแน่น · Adjacency List O(V + E) เหมาะกราฟเบาบาง
• BFS ใช้คิว ได้เส้นทางที่ผ่านจุดน้อยที่สุด · DFS ใช้สแตก/เวียนเกิด · Dijkstra หาเส้นทางสั้นสุดเมื่อน้ำหนักไม่ติดลบ · MST มี V − 1 เส้น (Kruskal, Prim)

แฮช การค้นหา และการเรียงลำดับ

• ตารางแฮช: h(k) = k mod m · การชนแก้ด้วย Linear Probing หรือ Chaining · ค้นหาเฉลี่ย O(1)
• Binary Search ต้องเรียงข้อมูลก่อน · ข้อมูล n ตัวเปรียบเทียบไม่เกิน ⌈log₂(n + 1)⌉ ครั้ง (1 ล้านตัว → 20 ครั้ง)