test 2 review

Card Set Information

test 2 review
2015-11-11 16:20:01
cs240 test2
Diane cs240 test2 review
Show Answers:

  1. Templates
  2. An operator that has different meanings with different data types is said to be ____________.
  3. In C++, >> is used as a _______________ operator and a _______________ operator.
    stream extraction, right shift
  4. Any function that overloads an operator is called _________________.
    an operator function
  5. The syntax of the heading of the operator function is:
    returnType operator operatorSymbol(parameters) i.e. bool operator > (const char&, const char&)
  6. In C++, operator is a __________________.
    reserved word
  7. Operator functions are ________________ functions.
  8. Except for the assignment operator and the member selection operator, to use an operator on class objects the operator must be ____________.
  9. The assignment operator, when used on a class object, performs a _________________ copy.
    default member-wise or shallow
  10. For classes with pointer member variables, the assignment operator must be ___________________.
    explicitly overloaded
  11. One benefit of operator overloading is _________________.
    concise notation, such as that available for built-in data types
  12. What are the things you cannot change when you overload an operator?
    • precedence
    • associativity
    • number of parameters it takes
    • the meaning of how it works with built-in data types
    • also - no default parameters
  13. Can you create new operators?
    No. Only existing operators can be overloaded.
  14. ______ C++ operators can be overloaded.
  15. The operators that cannot be overloaded are :
    • . (dot)
    • .*
    • ::
    • ?:
    • and sizeof
  16. What does the pointer 'this' refer to?
    the object as a whole
  17. The operator functions that overload the operators (),[],-> or = for a class must _________________.
    be members of that class
  18. A _________ function is a nonmember of a class.
  19. The heading of the prototype of a friend function is preceded by ______________.
    the word friend
  20. In C++, friend is a _________________.
    reserved word
  21. If an operator function is a member of a class, the ________________ operand of the operator must be a class object of that operator's class.
    far left
  22. The binary operator function as a member of a class has only one parameter, as a nonmember of a class, it has _______________.
    two parameters
  23. The operator functions that overload the stream insertion operator (<<) and the stream extraction operator (>>) for a class must _______________.
    be a friend function of that class.
  24. To overload the pre-increment (++) or pre-decrement (--)operator for a class if the operator function is a member of that class it must have ___ parameters.
  25. To overload the post-increment (++) or post-decrement (--) operator for a class if the operator function is a member of that class it must have _____________.
    one parameter, of type int - the user does not specify a value for the parameter - it is only used to distinguish pre- and post-increment operators
  26. A conversion constructor is a _______________ function.
    single parameter
  27. A _________________________ converts its argument to an object of the constructor's class. The compiler implicitly calls such constructors.
    conversion constructor
  28. Classes with pointer member variables must _________________________. (rule of three)
    overload the assignment operator, include copy constructor and destructor
  29. In C++, a function name can be ________________.
  30. In C++, template is _______________.
    a reserved word
  31. Using function templates allows you to ________________.
    write a single code segment for a set of related functions.
  32. Using class templates allows you to ____________________.
    write a single code segment for a set of related classes.
  33. The syntax of a template is:
    • template
    • declaration;
    • in which Type is a user-defined identifier which is used to pass data types as parameters, and declaration is either a function or a class.
    • In the declaration, class refers to any user-defined data type or built-in data type.
  34. ____________________ are called parameterized types.
    Class templates
  35. In a class template, the parameter Type __________________________________.
    specifies how a generic class template is to be customized to form a specific template class.
  36. The parameter ___________ is mentioned in every class header and member function definition.
  37. If cType is a class template, and func is a member function of cType, give the syntax for the function definition of func.
    • template
    • returnType cType::func(parameters)
  38. If cType is a class template and can take int as a parameter, how would you declare an object called x of type cType?
    cType x;
  39. Templates allow for class specifications to be created __________________.
    from a single source template.
  40. What is a quirk about implementing templates?
    The class definition and its use must be in the same file.
  41. What is the purpose of a function template?
    • A function template allows you to write one function definition that can be used to create an actual function definition to be created for each data type it can accept.
    • Each time the function template is called with a different data type, a new function definition is created to handle that data type.
  42. There are 3 ways to create the file(s) that create a class template. List and briefly describe them.
    • 1) class template declaration #includes the .cpp file at the end of the header file (right before #endif)
    • 2) Both the class template declaration and definition are in the .h file (both inside #ifndef ... #endif)
    • 3) The class template is defined and declared inline. Remember, the point of header files is convenience for the programmer because the compiler compiles top-down.
  43. What is 'boxing'?
    Making a generic data type more specific. For example, you could declare a currency object and convert integer values for dollars and cents to a currency object. This is boxing.
  44. What is 'unboxing'?
    Unboxing is converting an object back to its non-user defined data types. For example, if a currency object stored integers for dollars and cents, unboxing would return the double that represented the dollars and cents in it.
  45. What is the purpose of a conversion constructor?
    A conversion constructor receives input in one format and creates an object to store the equivalent value in a differnt format. For example, one could use a conversion constructor to create an object that stores an angle in polar coordinates when it is passed an angle in rectangular coordinates.
  46. One can write a __________________ to convert an object of one type to another type.
    typecast operator
  47. What is the syntax for declaring a typecast operator that will convert a Polar type object to a Rect type object?
    • Polar::operator Rect() {
    • code to convert;
    • return Rect(x,y);} //a Rect object has two members, x and you
  48. What is the syntax for declaring a conversion constructor that will convert a Rect object to a Polar object?
    • Rect::Rect(const Polar& pol) {
    • code to perform conversion and set data members;}
  49. When both a conversion constructor and a typecast operator exist, and you attempt to set an object equal to another object type, which will be used by the compiler?
    The typecast operator.
  50. Recursion
  51. Recursion is _____________.
    the process of solving a problem by reducing it to smaller versions of itself.
  52. A recursive definition defines a problem _________________.
    in terms of smaller versions of itself
  53. Every recursive definition has one or more ________________.
    base cases.
  54. A recursive algorithm solves a problem by ___________________________.
    reducing it to smaller versions of itself
  55. Every recursive algorithm has one or more ___________________.
    base cases
  56. The solution to the problem _____________________ is obtained directly.
    in a base case. In other cases, the function calls itself until it reaches a base case.
  57. A function is called recursive it __________________.
    it calls itself
  58. Recursive algorithms are implemented using ___________________.
    recursive functions
  59. Every recursive function has one or more _________________.
    base cases
  60. The general solution breaks the problem into __________________.
    smaller versions of itself
  61. The _________________ must eventually be retuced to a base case.
    general case
  62. The ________________ stops recursion.
    base case
  63. Every call to a recursive function has ___________________.
    its own code and its own set of parameters and local variables
  64. When a particular retursive call is completed, what happens?
    Control goes back to the calling environment, which is the previous recursive call. The code immediately following the recursive call is executed until the code is completely executed. Then, control is again returned to the calling environment (which may be another recursive call).
  65. A function is _________________ if it calls itself.
    directly recursive
  66. A function is said to be _______________ if it calls another function and eventually results in a call to the original function.
    indirectly recursive
  67. What is a tail recursive function?
    A function in which the last statement executed is the recursive call.
  68. What are the four requirements to design a recursive function?
    • 1) How can you define the problem in terms of a smaller problem of the same type?
    • 2) How does each recursive call diminish the size of the problem?
    • 3) What instance(s) of the problem can serve as the base case(s)?
    • 4) As the problem size diminishes, will you reach this base case?
  69. How is recursion stopped?
    A recursive function must allow for communication between its "versions" to stop the recursion. This can be done with parameters.
  70. If you are given a set of n objects and you must make sets of k objects from it, what is the general formula for how many sets of k can be made from n objects?
    • int nCr(n, r) {
    • if (r == 0 || r == n) return 1; // stop recursion, we know the answer.
    • return nCr(n-1, r-1) + nCr(n-1, r); // the answer is made of the sum of two "easier" ones
    • }
    • or, n choose r = (n-1 Choose r-1) + (n-1 Choose r)
  71. If you are given a set of n objects and you must make sets of k objects from it, what are the base cases?
    • 1) n == k => you can make 1 set
    • 2) n < k => you can make 0 sets (not enough for a set of k elements)
    • 3) k == 1 => you can make n sets because you are making sets of 1 object
  72. When should you use recursion rather than iteration?
    When a straightforward iterative solution cannot be found.
  73. What is a danger when using a recursive algorithm?
    stack overflow - running out of memory
  74. Linked Lists
  75. A linked list is a list of
    items called nodes, in which the order of the nodes is determined by the address, called a link(or next), stored in each node.
  76. The pointer to a linked list - that is, the pointer to the first node in the list - is stored in a separate location called __________.
    the head
  77. A linked list is a ____________.
    dynamic data structure
  78. The length of a linked list is __________________.
    the number of nodes in the list
  79. Item insertion and deletion from a linked list do not require _______________, only ________________.
    data movement, the pointers are adjusted
  80. A single linked list is traversed ____________.
    only in one direction
  81. The search on a linked list is ____________.
  82. The __________ of a linked list is always fixed, pointing to the __________ node in the list.
    head, first
  83. To traverse a linked list, the program must use ________________.
    a pointer different than the head pointer of the list, initialized to the first node in the list
  84. In a doubly linked list, each node has ____________________.
    two links, one points to the next node and one points to the previous node.
  85. A doubly linked list can be traversed ___________________.
    in either direction
  86. In a doubly linked list, item insertion and deletion require the adjustment of ________________.
    two pointers in the node
  87. In a circular linked list, the ________________________.
    last node points to the previous node.
  88. Stacks and Queues
  89. A stack is a data structure in which the items are added to and deleted from _________________.
    one end only
  90. A stack is a ___________ data structure.
  91. What are the basic operations on a stack?
    • Push an item onto the stack
    • Pop an item off of the stack
    • retrieve the top element of the stack
    • initialize the stack
    • check whether the stack is empty
    • check whether the stack is full
  92. A stack can be implemented as __________________ or ___________________.
    an array or a linked list
  93. The middle elements of a stack should/should not be accessed directly.
    should not
  94. Stacks are ____________ versions of arrays and linked lists.
  95. ___________________ does not require the use of parentheses to enforce operator precedence.
    Postfix notation
  96. In postfix notation, the operators ____________________.
    are written after the operands
  97. Postfix expressions are evaluated according to the following rules:
    • a) scan the expression from left to right.
    • b) if an operator is found, back up to get the required number of operands, evaluate the operator, and continue.
  98. A queue is a data structure in which items ____________________.
    are added to one end and removed from the other
  99. A queue is a _______ data structure.
  100. What are the basic operations on a queue?
    • add an item to the queue
    • remove an item from the queue
    • retrieve the first element of the queue
    • retrieve the last element of the queue
    • initialize the queue
    • check whether the queue is empty
    • check whether the queue is full
  101. A queue can be implemented as __________________ or ___________________.
    an array or a linked list
  102. The middle elements of a queue should/should not be accessed directly.
    should not
  103. Queues are _____________ versions of arrays and linked lists.
  104. Searching and Sorting Algorithms
  105. Describe how the sequential sorting algorithm works.
    The sequential sorting algorithm searches the list for a given item, starting with the first element in the list. It continues to compare the search item with the elements in the list until either the item is found of no more elements are left in the list with which it can be compared.
  106. On average, sequential search algorithm searches __________ (how much of the list).
    half the list
  107. For a list of length n, in a successful search, on average, the sequential search makes ____________ comparisons.
    (n+1)/2 = O(n)
  108. A sequential search is ________________ for large lists.
    not efficient
  109. A binary search is much ___________ than a sequential search.
  110. A binary search requires the list elements to be __________________.
    in order (sorted)
  111. To search for an item in a list of length 1024, a binary search requires no more than ______ iterations of the loop, and so no more than 22 comparisons.
    • 11, 22
    • 1024/2=512 (1) 512/2=256 (2) 256/2=128 (3) 128/2=64 (4) 64/2=32 (5) 32/2=16 (6) 16/2=8 (7) 8/2=4 (8) 4/2=2 (9) at most 2 more options to evaluate => (10), (11)
    • In each iteration of the loop, the midpoint is tested for equality to sought value. If it is not equal, it we test to see if it is greater than the sought value. If not, we can assume the midpoint is less than the sought value and throw out the lower half of the list.
  112. For a list of length n, in a successful search, on average the binary search makes ______________ comparisons.
    2 log(base 2) n - 32
  113. Let f be a function of n. By the term ________________, we mean the study of the function f as n becomes larger and larger without bound.
  114. The selection sort algorithm sorts a list by _________________.
    finding the smallest element in the unsorted portion of the list then moving it to the end of the sorted portion of the list (aka the beginning of the unsorted list).