SJSU CS 146 - Final Exam (3 pages)

Previewing page 1 of 3 page document View the full content.
View Full Document

Final Exam



Previewing page 1 of actual document.

View the full content.
View Full Document
View Full Document

Final Exam

283 views

Exam


Pages:
3
School:
San Jose State University
Course:
Cs 146 - Data Structures and Algorithms
Data Structures and Algorithms Documents

Unformatted text preview:

2003 Spring Final Exam Note Please bring 882E scantron For 11 30 am section Thursday May 15 9 45am to 12 00pm For 12 30 pm section Monday May 19 12 15am to 14 00pm Final Exam Topics 40 of the final exam will cover topics we covered before the first and second midterm exams and 60 of the final exam will cover topics we taught after the 2 nd midterm Here is a list of topics in the latter category Running Time Simplified model of computation Counting operations to estimate running time examples o linear search o binary search Big Oh big Theta big Omega little Oh Big Oh classes linear logarithmic etc Example of running time using recursion efficient exponentiation Stack ADT o Stack operations Array and linked list implementations Running times o Applications Balancing symbols Evaluating postfix expressions Implementing recursion problems with recursion Trees Definitions o Parent child leaf root o Path length of path height of node tree depth of node tree Implementation of general tree Binary Trees o Inorder postorder preorder traversal o Example expression trees Infix postfix prefix notation Construction of expression tree from postfix expression Binary Search Trees o Ordering property o Example of induction full binary tree of height h has 2 h 1 1 nodes o Operations and running times In class find findMin findMax insert remove In homework findKth findSuccessor AVL Trees o Balance condition o Rebalancing after insertion single and double rotations Priority Queues Heaps Operations insert deleteMin Binary heap implementation o Heap order property o Structure property o Implementation of insert and deleteMin operations o Running times for insert and deleteMin operations Other heap operations o buildHeap proof of O N running time o Hash Heap data structure to efficiently implement extra operations decreaseKey p delta increaseKey p delta delete p where p is position and delta is a positive amount Selection algorithms using heaps finding kth smallest number in a list of N



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Final Exam and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Final Exam and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?