11:10 C 1310MIDTERMSTUDYGUIDE... V Done 1 of 3 Midterm Study Guide CSC1310 DATA STRUCTURES / ABSTRACT DATA TYPES What does ADT stand for? Abstract Data Type Data structures organize data True OBJECTS & CLASSES & TEMPLATES When using header files, what is an include guard and what does it look like? #ifndef Constructors 0 Return type? Doesn't have a return type 0 Name of constructor Rectangle (); 0 Can you have more than one? Yes, this would be called an Overloaded Constructor o What is default constructor A constructor which can be called with no arguments o Automatically called when? When an object is created . Destructor 0 Return type? Has no return type o Used often to deallocate memory True 0 The name is preceded by a tilde True 0 Automatically called when? When an object is destroyed Access specifiers 0 Private / public 0 Member function that only needs to be accessed by other member functions can be made private o Usually data (attributes) are private Encapsulation Inline member function is a function that is defined in the class declaration Access members of a class with what operator? Dereference an object pointer with what operator? Two questions ask what the output is of a program which contains a class. Syntax of defining a class member function outside of the class declaration Templates o what is a function template? A function definition having a special type parameter that may be used in place of types in the function o syntax of a function template RECURSION This study source was downloaded by 100000806476375 from CourseHero.com on 09-30-2023 11:02:53 GMT -05:00 https://www.coursehero.com/file/85362231/1310MIDTERMSTUDYGUIDEdocx/ A recursive function is a function that calls itself. Depth of recursion . When does recursive function terminate? Using recursive functions for math problems is common Given a program with a recursive function, what is the output? SEARCH / SORT ALGORITHMS What is ascending / descending Linear search is also called sequential search Which search algorithm is most efficient? Which search algorithm requires the list to be sorted? Given an algorithm function that describes the number of operations, give the simplified Big O notation (two questions like this) Given pseudocode. which algorithm? (at least 2 questions like this) Q A ...11:10 C 1310MIDTERMSTUDYGUIDE... V Done o what is a function template? A function definition having a special type parameter that may be ce of types in the function B 2 of 3 function template RECURSION This study source was downloaded by 100000806476375 from CourseHero.com on 09-30-2023 11:02:53 GMT -05:00 https://www.coursehero.com/file/85362231/1310MIDTERMSTUDYGUIDEdocx/ A recursive function is a function that calls itself. . Depth of recursion When does recursive function terminate? Using recursive functions for math problems is common Given a program with a recursive function, what is the output? SEARCH / SORT ALGORITHMS What is ascending / descending Linear search is also called sequential search Which search algorithm is most efficient? Which search algorithm requires the list to be sorted? Given an algorithm function that describes the number of operations, give the simplified Big O notation (two questions like this) Given pseudocode, which algorithm? (at least 2 questions like this) If you have an array with 20000 elements, how many comparisons ON AVERAGE will the linear search perform o What about maximum number of comparisons using binary search? Which algorithm runs in linear time? What is quadratic time? 0 Exponential time? o Logarithmic time? Which sort algorithm uses the least amount of space in memory to run? (Between insertion sort, merge sort, & quick sort?) Know efficiency class for best, average, worst case efficiency of: 0 Linear search 0 Binary search 0 Bubble sort Selection sort 0 Insertion sort o Quick sort 0 Merge sort What kind of functions does merge sort require? What kind of functions does quick sort require? How does radix sort work - does it use comparison? Does it use buckets? LINKED LIST what is a node, head, tail What is a singly linked list, doubly linked list . . . last node points to null common list operations - what they do, what they return (getLength, search This study source was downloaded by 100000806476375 from CourseHero.com on 09-30-2023 11:02:53 GMT -05:00 https://www.coursehero.com/file/85362231/1310MIDTERMSTUDYGUIDEdocx/ When traversing a list, how does a node pointer know when it reaches the end of the list? (encounters a null pointer) How does a linked list class take care of removing the dynamically allocated nodes? (destructor function) when new data needs added to the list, a node is dynamically allocated and inserted what does appending a node mean? how is it different then inserting a node? Q A ...11:10 C 1310MIDTERMSTUDYGUIDE... V Done 0 Insertion sort B 3 of 3 ions does merge sort require? What kind of functions does quick sort require? How does radix sort work - does it use comparison? Does it use buckets? LINKED LIST what is a node, head, tail What is a singly linked list, doubly linked list . . . last node points to null common list operations - what they do, what they return (getLength, search This study source was downloaded by 100000806476375 from CourseHero.com on 09-30-2023 11:02:53 GMT -05:00 https:/www.coursehero.com/file/85362231/1310MIDTERMSTUDYGUIDEdocx/ When traversing a list, how does a node pointer know when it reaches the end of the list? (encounters a null pointer) How does a linked list class take care of removing the dynamically allocated nodes? (destructor function) when new data needs added to the list, a node is dynamically allocated and inserted . . . what does appending a node mean? how is it different then inserting a node? what does it mean if the head pointer points to null? what is traversing? what is efficiency of search in a singly-linked linear list? (O(n)) STANDARD TEMPLATE LIBRARY vector class is part of STL List STL - push_front(), pop_front(), back(), front(), remove() - will remove all instances of that value STACK / QUEUE Stack: LIFO - last in first out - like stack of plates. insertions insert in top, deletions delete (pop) from top Queue: FIFO - first in first out - like line in grocery store. insertions insert (enqueue) in back (end), deletions delete (dequeue) from beginning / front / head given code that pushes & pops from stack, what is printed out to the screen? given code that enqueues & dequeues from the queue, what is printed out to the screen? queues that are implemented as arrays are static queues . . . . stacks that are implemented as arrays are static stacks queues that are implemented as linked lists are dynamic queues stacks that are implemented as linked lists are dynamic stacks This study source was downloaded by 100000806476375 from CourseHero.com on 09-30-2023 11:02:53 GMT -05:00 https:/www.coursehero.com/file/85362231/1310MIDTERMSTUDYGUIDEdocx/ Q A