สอบย่อยวิชา DS เทอม 1/2567

Time Cost หรือ Big O Notation ของ AVL Tree ในการค้นหา เพิ่ม ลบ คือเท่าไร ?

• O(n)

• O(log n)

• O(n log n)

• O(1)

ข้อใดต่อไปนี้เป็นอัลกอริทึมที่ใช้หาค่าทางสั้นที่สุด (Shortest Path) ระหว่างสองโหนดใน Weighted Graph ?

• Depth-First Search (DFS)

• Breadth-First Search (BFS)

• Dijkstra's Algorithm

• Kruskal's Algorithm

Minimum Spanning Tree ถูกนำไปใช้ในสถานการณ์ใดได้บ้าง?

• การออกแบบเครือข่ายคอมพิวเตอร์ให้ใช้สายเคเบิลน้อยที่สุด
  

• การกำหนดเส้นทางการเดินรถเพื่อให้ถึงจุดหมายเร็วที่สุด
  

• การหาตำแหน่งที่ดีที่สุดสำหรับสร้างสถานีไฟฟ้า
  

• การจัดลำดับการดำเนินงานของกระบวนการในคอมพิวเตอร์

ข้อใดต่อไปนี้เป็นอัลกอริทึมการจัดเรียงที่มีความซับซ้อนของเวลาเฉลี่ยดีที่สุด และให้เวลา cost เท่าไร

• Selection Sort, O(N*N)

• Bubble Sort, O(N)

• Merge Sort, O(N*LogN)

• Merge Sort, O(LogN)

ความซับซ้อนของเวลา หรือ Big O ของ Bubble Sort คือเท่าใด ?

• O(n log n)

• O(n*n)

• O(n)

• O(log n)

ความซับซ้อนของเวลา หรือ Big O ของ Binary Search ใน sorted array คือเท่าใด ?

• O(log n)

• O(1)

• O(n)

• O(n * log n)

ข้อใดต่อไปนี้ ไม่ใช่ วิธีการแก้ปัญหาการชนกัน (Collision) ใน Hash Tables?

• Linear Probing

• Rehashing

• Double Hashing

• Depth-First Probing

ข้อใดกล่าวผิดเกี่ยวกับ Linear Probing ใน Hash Tables ?

• อาจเกิดปัญหา Primary Clustering ได้

• ต้องใช้เวลาค้นหานานขึ้นเมื่อ Hash Table เริ่มเต็ม

• ใช้การค้นหาตำแหน่งว่างถัดไปอย่างเป็นลำดับ (Sequential Search)

• ไม่สามารถจัดเก็บข้อมูลที่มีค่า Hash ซ้ำกันได้

ข้อใดกล่าวผิดเกี่ยวกับ Double Hashing

• แก้ปัญหา Primary Clustering

• ใช้ฟังก์ชัน Hash 2 อันเพื่อคำนวณที่อยู่ในการจัดเก็บ Key เพื่อลดการชน

• ช่วยให้ Hash Table มีโอกาสเต็มช้าลง

• ใช้เวลาเร็วในการคำนวณฟังก์ชกันเพื่อหาตำแหน่งที่อยู่ของ Key

Rehashing มักถูกทำเพื่ออะไร?

• เพิ่มขนาดของ Hash Table

• ลดขนาดของ Hash Table

• ลบคีย์ที่ซ้ำกัน

• ปรับปรุงประสิทธิภาพการจัดเรียง