CSCA48 Test #9
• You will have 30 minutes to answer 2 questions
• Please ensure that your hands, head, and desktop are visible in your
webcam
• Turn your camera, microphone, and speakers on, leave your volume at a low level
• Once the test has begun, you may not touch or approach your computer unless told to do so, you must remain in view of the camera at all times
• If you have a question, raise your hand and you will be moved to a breakout room where you can talk to an invigilator
• All answers must be legible and clearly labeled, no marks will be given for unclear or unreadable answers
• If any question is under-specified, you will not be penalized for making a reasonable assumption
• The questions in this test refer to the following Graph. Please copy it down carefully
Question 1
Draw the graph represented as:
a) An adjacency matrix
b) An adjacency list
Use indexes 0 through 4, starting with A at index 0
Question 2
Consider the algorithm below being run on a directed graph with V nodes and E edges. Provide the worst-case big-O complexity of the algorithm if the graph is implemented as:
a) An adjacency matrix
b) An adjacency list
for(int i=0; i