COMP 410 Final Exam Prep Questions and Answers Graded 2024

List Data Structure - general ops: get k items, insert at k, delete at K Implementing as List ins O(1) rem O(1) Get O(n) Find O(n) Empty O(1) Size O(n) or O(1) Implementing as Array ins O(N) rem O(N) Get O(1) Find O(n) Empty O(1) Size O(1) Ordered List - can assist in list searching binary search O(logN) Stack - LIFO general ops: push, pop, top, empty, size keeps pointer to most recent slot, useful for reversing sequences top O(1) push O(1) pop O(1) Queue - FIFO General ops: add, remove, front, empty size keeps pointer to front slot and back slot, maintains order of arrival add: insert at slot front remove: delete slot from back add O(1) remove O(1), O(N) for array front O(1) Bubble Sort - O(N^2) time required to sort list of N items easy to program but very slow stable Binary Search Tree - Average: find O(logN) insert O(logN) remove O(logN) traversals O(N) Worst find O(N) insert O(N) remove O(N) traversals O(N) all nodes in left child subtree have smaller value than root, all nodes in right are greater Depth First - travel down paths towards leaves until forced to stop Breadth First - visit all children of a node before going down deeper paths PreOrder - Visit root, the recursively visit children L to R