CS 225: Data Structures FINAL EXAM
PRACTICE QUESTIONS AND ANSWERS
2025 University of Illinois Urbana-
Champaign
Correct
101
, 1 of 101
Term
In a heap how to access the right child of a node indexed at
i?
A. i+1
B.2i+1
C. 2i
D.3i+1
E. 3i
Give this one a try later!
B C
E A
Don't know?
2 of 101
Term
in implementing Queue ADT, using which of the following
data structure gives best asymptotic runtime for enqueue
and dequeue? (Assume best possible implementation for
queue using provided data structure)
A. Singly linked list with head and tail pointer.
B.Exactly two of the other options are correct.
, C. Singly linked list with head pointer only.
D.Doubly linked list with head and tail pointer.
E. Doubly linked list with head pointer only.
Give this one a try later!
E B
A C
Don't know?
3 of 101
Term
graph implemented using edge list
incidentEdges runtime?
A. O(1)
B.O(n)
C. O(m)
D.O(n^2)
E.O(logn)
F.O(deg(v))
G. O(min(deg(v), deg(u))
Give this one a try later!
, D E
C B
Don't know?
4 of 101
Term
Priority queue using a sorted singly
linked list. What is the runtime of find,
remove, and insert
A. find O(n), remove O(n), insert O(n)
B.find O(n), remove O(1), insert O(n)
C. find O(logn), remove O(logn), insert O(1)
D.find O(1), remove O(1), insert O(n)
E. find O(1), remove O(1), insert O(logn)
F.find O(n/2), remove O(1), insert O(n/2)
Give this one a try later!
B C
E D
Don't know?
PRACTICE QUESTIONS AND ANSWERS
2025 University of Illinois Urbana-
Champaign
Correct
101
, 1 of 101
Term
In a heap how to access the right child of a node indexed at
i?
A. i+1
B.2i+1
C. 2i
D.3i+1
E. 3i
Give this one a try later!
B C
E A
Don't know?
2 of 101
Term
in implementing Queue ADT, using which of the following
data structure gives best asymptotic runtime for enqueue
and dequeue? (Assume best possible implementation for
queue using provided data structure)
A. Singly linked list with head and tail pointer.
B.Exactly two of the other options are correct.
, C. Singly linked list with head pointer only.
D.Doubly linked list with head and tail pointer.
E. Doubly linked list with head pointer only.
Give this one a try later!
E B
A C
Don't know?
3 of 101
Term
graph implemented using edge list
incidentEdges runtime?
A. O(1)
B.O(n)
C. O(m)
D.O(n^2)
E.O(logn)
F.O(deg(v))
G. O(min(deg(v), deg(u))
Give this one a try later!
, D E
C B
Don't know?
4 of 101
Term
Priority queue using a sorted singly
linked list. What is the runtime of find,
remove, and insert
A. find O(n), remove O(n), insert O(n)
B.find O(n), remove O(1), insert O(n)
C. find O(logn), remove O(logn), insert O(1)
D.find O(1), remove O(1), insert O(n)
E. find O(1), remove O(1), insert O(logn)
F.find O(n/2), remove O(1), insert O(n/2)
Give this one a try later!
B C
E D
Don't know?
