Consider the student records for UBC students which contain

Consider the student records for UBC students, which contain courses, grades (including GPA), year of study, and major. Students can be added (new registration or transfer) and deleted (graduated, dropped out, or transferred). Select all the data structure(s) that give the lowest asymptotic complexity (worst-case, expected, or amortized) to return all the students with GPA between 75% and 85%? (Do not worry about insertion time.)

Queue

Unsorted List

Unsorted Array

AVL tree

Red-Black Tree

Skip List

Stack

Heap

Hash Table

Solution

AVL tree, Red-Black tree and Skip List will give lowest expected complexity of O( klogn )

where k = number of students with GPA between 75% and 85%

    and n = total number of students