CS1027FinalApril07Master.doc

12 Pages
157 Views
Unlock Document

Department
Computer Science
Course
Computer Science 1026A/B
Professor
Eric Schost
Semester
Winter

Description
Questions from the Computer Science 027b Final Exam April 2007With SolutionsThis is not the entire 3hour exam since there were topics on the exam that are not relevant this termThe marks for each individual question are given Allow approximately 1 minute per mark on averageNote that theStackADT QueueADT Iterator ListADT UnorderedListADT OrderedListADT BinaryTreeADT and BinarySearchTreeADT interfaces were provided at the back of the exam paper as well as the code for LinearNodejava and BinaryTreeNodejava19 marks For each of the following give the time complexity usingBigO notation Assume an input of size n in each caseaforint in i0i Answer On2forint j1 jn jSystemoutprintlnj ifor int kn k1 kk2Systemoutprintlnk ibfor int k1 kn kAnswer On log n jnwhile j 0Systemoutprintlnjjj2 cfor int i1 i5 i Answer Onfor int j1 jn j for int k1 k3 kSystemoutprintlni ji jk127 marksFor each of the following algorithms or methods from the collection classes used in this course suppose that the container in question contains n elements Using BigO notation give the worstcase time complexity for eachaThe method pushT element from class ArrayStackOn bThe method dequeue from class CircularArrayQueue O1 cThe method findT targetElement from class LinkedBinaryTreeOn dThe algorithm to search for a specific element in a binary search treeOneThe algorithm to search for a specific element in a binary search tree if the binary search tree is known to be balancedOlog n fThe Selection Sort algorithm from the course notes that is implemented using Queues to sort a queue of n data itemsOn2gThe Insertion Sort algorithm from the course notes that is implemented using Stacks to sort a queue of n data items On22
More Less

Related notes for Computer Science 1026A/B

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit