EECS2011_Sample_Exam

pdf

School

Toronto Metropolitan University *

*We aren’t endorsed by this school

Course

2011

Subject

Electrical Engineering

Date

Jan 9, 2024

Type

pdf

Pages

Uploaded by CommodoreFlag12225

YORK UNIVERSITY Lassonde School of Engineering Department of Electrical Engineering & Computer Science SAMPLE FINAL EXAM EECS 2011 Fundamentals of Data Structures Instructor: Larry Yueli Zhang 180 minutes Aids Allowed : one 8.5”x11”, double -sided aid sheet Student Number: First Name: ______________________________ Last Name: ______________________________ Do NOT turn this page until you have received the signal to start. In the meantime, please fill out the identification section above. Read the instructions below carefully. General Instructions: • This is a sample exam for the purpose of practicing the exam format. Its difficulty does NOT represent the difficulty of the real exam. • This exam consists of a total of 72 marks on 18 pages (including this one). When you receive the signal to start, please make sure that your copy is complete. • Make sure your ID is on your desk during the exam. • Keep your eyes on your own work. We will move your seat and mark your paper for a 10% penalty each time we notice otherwise. • You may not leave within the first or last 10 minutes of the exam. • For all questions, provide your answer on the exam paper. • This exam includes a few blank pages that are for rough work only. If you write an answer on one of the blank pages, you must indicate clearly what you want to be marked. • Do NOT detach any page from the exam. • You must submit the aid-sheet at the end of the exam. Version Z

EECS 2011 Sample Exam Page 2 of 18 Question 1: Multiple Choices and Short Answers [2 marks x 17 = 34 marks] For ALL multiple-choice questions, select EXACTLY ONE choice. Selecting more than one choice will result in a mark of 0 (zero). 1. True or False: Big-Oh is for describing the worst-case runtime; big-Omega is for describing the best-case runtime. A. True B. False 2. Consider a nearly complete binary tree T, which of the following conditions is sufficient for concluding that “T is a max heap”? Choose one. A. Every leaf node is smaller than all its ancestors. B. The root of the tree is larger than all its descendants. C. Every non-root node is smaller than all its ancestors. D. The inorder traversal of the tree yields a sorted array in descending order. 3. True or False: When an undirected graph is very sparse , its adjacency list uses roughly the same amount of space as its adjacency matrix. A. True B. False 4. Consider the increase key and decrease key operations on a max or min heap, which of the following involves the BUBBLE-DOWN operation? Choose one. A. Increase key on a max heap B. Increase key on a min heap C. Decrease key on a max heap D. Decrease key on a min heap E. A and B F. B and C G. A and D

EECS 2011 Sample Exam Page 3 of 18 5. Which of the following data structures achieves the best performance for implementing a priority queue on which we ONLY do INSERT? Choose one. A. Sorted array B. Sorted linked list C. Unsorted linked list D. Binary min-heap 6. True or False: In a BST, the predecessor of a node x must be in the left subtree of x. Choose one. A. True B. False 7. We know that a non-empty binary tree T with distinct keys is both a valid binary min-heap and a valid binary search tree. Which of the following is TRUE about T? Choose one. A. The size of T must be 1. B. The size of T must be 2. C. The size of T may be greater than 2 D. It is impossible to have such a T. 8. Which of the following is TRUE about the load factor of a hash table? Choose one. A. With chaining, the load factor must be less than or equal to 1. B. With chaining, the load factor can be greater than one. C. With open addressing, the load factor can be greater than one. D. None of the above is true. 9. Which of the following is FALSE about loop invariant? Choose one. A. The loop invariant must be true before entering the loop. B. The loop invariant being true does not guarantee the termination of the loop. C. The loop invariant and the loop guard cannot be both true. D. The loop invariant may not be true in the middle of an iteration.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

EECS 2011 Sample Exam Page 4 of 18 10. What is the minimum possible number of nodes in an AVL-tree of height 4? Write a number in the blank below. Recall that the height of a tree is defined as the number of edges in the longest root-to-leaf path. Answer: _______________ 11. Consider inserting the sequence 1, 2, 3, . . . , 255 (i.e., 255 values in total) into an initially empty AVL- tree, what is the height of the resulting AVL-tree? Write a number in the blank below. Answer: _______________ 12. Consider the DFS tree generated by a DFS on a connected graph. Write below the necessary and sufficient condition for a node v to be a leaf node of the DFS tree. The condition must be in terms of v’s discovery time d[v] and finishing time f[v]. Answer: _____________________________ 13. How many leaf nodes are there in a binary heap with 263 nodes? Write a number in the blank below. Answer: _______________ 14. Trace the following pseudocode of a recursive function Mystery. What does Mystery(4) print? Write your answer in the blank. Assume that the print method prints without the newline character, so all printed numbers are on the same line. Answer: ______________________ void Mystery (int n) { if (n > 1) { Mystery(n-1); print(n); Mystery(n-2); } }

EECS 2011 Sample Exam Page 5 of 18 15. The array H below stores a binary max-heap. 9 7 4 2 5 3 In the space below , write the content of the resulting array after calling ExtractMax(H) . H after ExtractMax: ______ ______ ______ ______ ______ 16. We are given a “ manipulated ” binary search tree where two nodes in the tree have swapped their keys. Below is the inorder traversal of this tree. 8, 9, 10, 18, 14, 15, 11, 21 In the two blanks below, write the two keys that were swapped. Swapped keys: ________ and _________ 17. Below are the postorder and inorder traversals of a binary tree. Reconstruct the tree and draw the tree in the space below. Postorder traversal: 2, 5, 8, 4, 7, 3 Inorder traversal: 5, 2, 8, 3, 4, 7 Draw the tree here:

EECS 2011 Sample Exam Page 6 of 18 Question 2: Hash Table [4 marks] Consider a hash table with collisions resolved by chaining . The hash table has 5 buckets, and it uses hash function h(k) = k mod 5 . Perform the following sequence of INSERT operations and draw the final resulting hash table in the figure below. The final position of key 15 is drawn for you. INSERT: 15, 23, 39, 38, 42, 33, 14

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

EECS 2011 Sample Exam Page 7 of 18 Question 3: Binary Search Tree [4 marks] We want to check whether a BST is broken (“broken” means not all nodes in the tree satisfy the BST property). The tool we have is that we can perform a SEARCH operation on the BST and get the sequence of nodes that are visited during the search. So, we performed SEARCH(42) and got the following visiting sequence: 80 (root), 75, 51, 55, 48, 41, 42 (found) Can you tell for sure whether the BST is broken from the above sequence? First circle Yes, No, or Not Sure below, then justify your answer. Be concise. Circle one: Yes No Not Sure Justification:

EECS 2011 Sample Exam Page 8 of 18 Question 4: Queue and Recursion [6 marks] Below is an attempt to implement a ReverseAndRemoveOdds(Q) operation on a queue Q. The method is supposed to reverse the order of the items in the queue as well as removing all the odd numbers. However, the pseudocode is buggy. Below is an example of a queue Q before and after ReverseAndRemoveOdds(Q) if the method worked correctly. BEFORE : (front) 3, 1, 4, 1, 5, 2, 6 (back) AFTER : (front) 6, 2, 4 (back) Read the code (including the documentation) and answer the questions on the following page. Continued on the next page… /* Assume the following behaviour of the Queue methods. - Enqueue(item): enqueue at the back of the queue - Dequeue(): dequeue at the front. Raise an exception if the queue is empty. - IsEmpty(): returns whether the queue is empty. */ void ReverseAndRemoveOdds(Q) { x = Q.Dequeue(); Helper(Q, x); return; } void Helper(Q, item) { if (Q.isEmpty()) { return; } x = Q.Dequeue(); Helper(Q, x); if (item is even) { Enqueue(item); } return; }

EECS 2011 Sample Exam Page 9 of 18 (a) Below, write the content of a non-empty queue Q by filling in the following blank (with a list of integers) such that calling ReverseAndRemoveOdds (Q) gives a WRONG result without raising any exception. The size of the queue must be less than or equal to 5. If such an input does not exist, write “IMPOSSIBLE” in the blank. Q : (front) ______________________________________ (back) (b) Below, write the content of a non-empty queue Q by filling in the following blank (with a list of integers) such that calling ReverseAndRemoveOdds (Q) gives a CORRECT result without raising any exception. The size of the queue must be less than or equal to 5. If such an input does not exist, write “IMPOSSIBLE” in the blank. Q : (front) ______________________________________ (back) (c) Below, write the content of a non-empty queue Q by filling in the following blank (with a list of integers) such that calling ReverseAndRemoveOdds (Q) will result in a “maximum level s of recursion exceeded” error. The size of the queue must be less than or equal to 5. If such an input does not exist, write “IMPOSSIBLE” in the blank. Q : (front) ______________________________________ (back)

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

EECS 2011 Sample Exam Page 10 of 18 Question 5: Spreading the Gossip [10 marks] In a large university like the YorkU, every student knows many other students. However, friendship relations are kept with only a few of them, to whom gossips are told. Suppose that whenever a student knows of a piece of gossip, she tells it to all her friends on the following day. So, on the first day, the source of the gossip tells it to her friends; on the second day, the source’s friends tell it to their friends; on the third day, the friends of the source’s friends tell it to their friends; and so on. As the YorkU Gossip Administrator, you have access to the list of friendship relations between all students. Your job is to choose a student to be the source of a given piece of gossip. In order to do this job properly, you need compute the following two quantities given a source of gossip. • The Maximum Daily Boom Size (MDBS) , which is the largest number of students that, on a single day, hear the piece of gossip for the first time; and • The First Boom Day (FBD) , which is the first day on which the maximum daily boom size occurs. Devise an algorithm that, given the friendship relations between the students and one student who is the source of gossip, computes the MDBS and the FBD of that gossip spreading process. Answer the following questions. (a) How to model this problem using a graph? Answer this by completing the following. [3 marks]. The graph is: directed / undirected (circle the one you choose) A vertex in the graph represents _________________________________ An edge in the graph represents _________________________________ (b) Which graph operation (that we learned from this course) do you run on this graph? Write down the operation’s name and the parameters you pass to the operation. [3 marks] This question continues on the next page …

EECS 2011 Sample Exam Page 11 of 18 (c) After running the above operation. How do you get the MDBS? [2 marks] (d) After running the above operation. How do you get the FBD? [2 marks]

EECS 2011 Sample Exam Page 12 of 18 Question 6: Word Ladder [14 marks] A word ladder is a sequence of valid English words where two adjacent words differ by only one letter. For example , the following is a word ladder from “COLD” to “WARM”: COLD → CORD → CARD → WARD → WARM You are given the two words “PHYSICS” and “GEOLOGY”, and you must design an algorithm that computes a word ladder between the two words, with the shortest possible sequence of words. Input : The two words “PHYSICS” and “GEOLOGY”, and an unsorted list of 7-letter English words. Assume that there are N such words in the list, and that all words consist of only the 26 English alphabet letters (A to Z). Output : A word ladder sequence from “PHYSICS” to “GEOLOGY” that contains the smallest possible number of words. If such a word ladder is impossible, return NULL. Requirement : The runtime (either worst-case or average-case) of the algorithm must be in O(N) . Answer the following questions. (a) How to model this problem using a graph? Answer this by completing the following. [3 marks]. The graph is: directed / undirected (circle the one you choose) A vertex in the graph represents _________________________________ An edge in the graph represents _________________________________ (b) How many vertices are there in the graph? [1 mark] Continued on the next page…

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

EECS 2011 Sample Exam Page 13 of 18 (c) How many edges are there in the graph? Describe it in big-Oh notation and provide a brief justification. [2 marks] (d) Should we use the adjacency matrix or the adjacency list to store the graph? Circle your choice below. No need for justification. [1 mark] adjacency matrix adjacency list (e) In addition to the graph, what other data structure is needed in order to satisfy the requirement? Write below the name of the data structure, and briefly justify why it is necessary. [2 marks] Continued on the next page…

EECS 2011 Sample Exam Page 14 of 18 (f) Concisely describe the graph construction process , i.e., the procedure to populate the data structure storing the graph. Briefly justify its runtime. [3 marks] (f) Once the graph is constructed, which graph operation (that we learned from this course) do you run on this graph? Write down the operation’s name and the parameters you pass to the operation. [2 marks]

EECS 2011 Sample Exam Page 15 of 18 BLANK PAGE You may use the space on this page for rough work. This page will NOT be marked.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

EECS 2011 Sample Exam Page 16 of 18 BLANK PAGE You may use the space on this page for rough work. This page will NOT be marked.

EECS 2011 Sample Exam Page 17 of 18 BLANK PAGE You may use the space on this page for rough work. This page will NOT be marked.

EECS 2011 Sample Exam Page 18 of 18 FOR GRADING USE ONLY Q1: _________ /34 Q2: _________ / 4 Q3: _________ / 4 Q4: _________ / 6 Q5: _________ /10 Q6: _________ /14 TOTAL: _____________ /72

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version