EECS2011A_F22_Midterm_Solution

pdf

School

York University *

*We aren’t endorsed by this school

Course

2011 , 310

Subject

Electrical Engineering

Date

Jan 9, 2024

Type

pdf

Pages

Uploaded by DrNeutron12857

YORK UNIVERSITY Lassonde School of Engineering Department of Electrical Engineering & Computer Science Midterm Test - Fall 2022 EECS 2011 A Fundamentals of Data Structures Instructor: Larry Yueli Zhang 80 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 midterm consists of a total of 32 marks on 10 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. Just Be Yourself! Version B

EECS 2011 A Fall 2022 Midterm Test Page 2 of 10 Question 1: Multiple Choices and Short Answers [2 marks x 10 = 20 marks] For multiple-choice questions, one mark will be deducted for each missing choice or wrong choice . 1. Which of the following is TRUE? Circle ONE. A. The nodes of a linked list are allocated contiguously next to each other in memory. B. A working linked list class must have a “size” attribute. C. Inserting a new node to a linked list may require copying all existing nodes in the list to a new memory location. D. None of the above is true. 2. Consider a circular, singly linked list with “ next ” and with both head and tail references. Which of the following operations would have a Θ(n) worse-case runtime? Circle ALL that apply. A. Insert at the head B. Insert at the tail C. Delete at the head D. Delete at the tail E. None of the above 3. Immediately after exiting a loop, which of the following are TRUE? Circle ALL that apply. A. negation of loop guard B. precondition C. loop guard D. loop invariant 4. Which of the following functions grows the most slowly ? Choose ONE. A. log(n 0.5 ) B. log(n)*log(n) C. (log(n)) 0.5 D. n 0.5

EECS 2011 A Fall 2022 Midterm Test Page 3 of 10 5. What is the worst-case runtime of the following pseudocode? Choose ONE. A. Θ(n log n) B. Θ( n 2 (log n) 3 ) C. Θ(n 5 ) D. Θ(n 2 log n) E. None of the above int Program(int n) { int r = 1; int i = 1; while (i < n * n) { j = 1; while (j < n * n * n) { j = j * 3; r = r + j + i; } i = i + 2; } return r; } 6. Consider of the following piece of pseudocode. Which of the following is a valid invariant of the loop? Circle ALL that apply. A. x > 0 B. x >= b C. x + b*y = a D. x + b*y = b E. y + a*x = a F. y + a*x = b G. y <= b // Precondition: a >= 0 and b > 0 Mystery(a, b) { x = a; y = 0; while (x >= b) { x = x - b ; y = y + 1; } return x; } 7. Consider a binary tree T, which of the following condition(s) are sufficient for concluding that “T is a binary search tree ”? Circle ALL that apply. A. Every node is larger than its left child and smaller than its right child, if the child exists. B. Every non-leaf node has only left child (no right child) and is larger than its left child. C. The root is larger than all nodes in its left subtree and smaller than all nodes in its right subtree. D. The inorder traversal of the tree yields a sorted array in ascending order.

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 A Fall 2022 Midterm Test Page 4 of 10 8. Trace the following pseudocode of a recursive function Mystery. What is the value of Mystery(5) ? Write your answer in the blank. Answer: __________________ int Mystery(int n) { if (n <= 1) { return 2; } if (n mod 3 == 0) { return Mystery(n-1) + 1; } return 2 * Mystery(n-1) - Mystery(n-2) + 1; } 9. Trace the following pseudocode of a recursive function Mystery. What does Mystery(2) 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 > 0) { print(n); Mystery(n-1); print(n-1); Mystery(n-1); } } 10. Consider inserting a sequence of 7 values, in the following order, into an initially empty binary search tree . One of the values is hidden. 43, 21, 32, HIDDEN, 42, 40, 35 We know that the hidden value is an integer that is different from all other values in the sequence, and we know that the resulting BST has a height of 6, i.e., the maximum possible height with 7 nodes. In the blank below, write down ALL possible values of the hidden value. If no possible value exists, write "impossible" as the answer. If infinitely many values are possible, write "infinite" as the answer. Answer: ____________________________________

EECS 2011 A Fall 2022 Midterm Test Page 5 of 10 Question 2: Linked List [6 marks] We would like to implement a method named " Delete23in123() " for a singly linked list . That is, whenever there is a consecutive sequence of nodes with values 1, 2, 3, we delete the 2 and 3. For example, Before: 1 -> 2 -> 3 After: 1 Before: 7 -> 1 -> 2 -> 3 -> 9 -> 2 -> 3 After: 7 -> 1 -> 9 -> 2 -> 3 Before: 7 -> 1 -> 2 -> 3 -> 2 -> 3 -> 2 -> 3 -> 9 After: 7 -> 1 -> 9 Note from the above example that, after deleting one instance of 23, there may be new instances of 123 formed. You must delete ALL of them. Below is the partially completed pseudocode with three blanks missing. Fill in the three blanks so that the pseudocode works correctly according to the above specification. Do NOT use recursion in this question. Delete23in123(L): cur = L.head; while ( ______________________________________________________ ) { //BLANK 1 if (cur.value == 1 and cur.next.value == 2 and cur.next.next.value == 3) { ______________________________________________________; //BLANK 2 } else { ______________________________________________________; //BLANK 3 } } Return;

EECS 2011 A Fall 2022 Midterm Test Page 6 of 10 Question 3: Recursion and Stack [6 marks] We would like to implement a SortedPush (stack, item) method which, given a stack whose elements are sorted in non-decreasing order from top to bottom, inserts a new item into the stack to the right location, so that the elements in the stack remain sorted. We will develop this method using recursion . Below is the partially completed pseudocode with three blanks missing. Fill in the three blanks so that the pseudocode works correctly according to the above specification. You are allowed to use the following stack methods: Push() , Pop() , IsEmpty() , and Peek() . /* * Precondition : The elements in <stack> are sorted in non-decreasing * order from top to bottom, i.e., the smallest element is at the top. * Postcondition : Insert <item> to <stack> and the elements in <stack> * remain sorted. */ SortedPush(stack, item): if (_________________________________________) { // BLANK 1, base case stack.Push(item); } else { // recursive case x = stack.Pop(); _____________________________________________; // BLANK 2 _____________________________________________; // BLANK 3 } Return;

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 A Fall 2022 Midterm Test Page 7 of 10 BLA N K PAGE You may use the space on this page for rough work. This page will NOT be marked.

EECS 2011 A Fall 2022 Midterm Test Page 8 of 10 BLA N K PAGE You may use the space on this page for rough work. This page will NOT be marked.

EECS 2011 A Fall 2022 Midterm Test Page 9 of 10 BLA N K 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 A Fall 2022 Midterm Test Page 10 of 10 FOR GRADING USE ONLY Q1: _________ Q2: _________ Q3: _________ TOTAL: _____________

Related Documents

Week 3 Assignment Gough.docx

ECE210 - Lab 3 - LTSpice and Nodal analysis.pdf

ECE210 - Lab 4 - Soldering and Thevenin.pdf

SOFE3650Guidelines.docx

ELD-3110 wa2.docx

Discussion Board_ Assistive Technology.docx

HW7sol.pdf

Week 2 Lab Assignment_UJT Operation (OL).docx

Week 1 Lab_Comparator_On_Off_Control (OL).docx

COMM_onesInvoice.docx

LANG_heSpreadsheet.docx

SITXMGT004-MIA-Event-planning.xlsx.v1.0.xlsx