Consider the student records for UBC students, which contain courses, grades (in

Question

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

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects