final review

Home > Preview

The flashcards below were created by user dimeng on FreezingBlue Flashcards.


  1. You are given a template sorting function. You use it to sort an array of ints and an array of doubles, but it wont compile when you give it an array of Jedi. Why won't it work?
    Because Jedi are objects, the compiler does not know when one Jedi is greater than or less than another unless the Jedi class contains overloaded greater than and less than (comparison) operators.
  2. (T/F) A recursive function cannot ever call any function other than itself.
    False
  3. (T/F) If a recursive function's base case is never met, the function will recurse infinitely.
    False, the system will run out of memory causeing a stack overflow error.
  4. A ________ variable will stay in memory even after the function that declared it is removed from the stack.
    static
  5. When deleting from a standard linked list, removing the ________ must be treated as a special case.
    head - because without the head the entire list is inaccessible
  6. List the 4 questions that verify that a problem can be solved recursively.
    • (Remember SBCR - smaller, base case, closer, reduce)
    • 1) Can you define the problem in terms of smaller versions of itself?
    • 2) What is/are the base case(s) - when the problem is solved?
    • 3) Will each step (recursive call) move you closer to the solution?
    • 4) Are you guaranteed to reach a base case?
  7. Which linked list variant contains no null pointers (unless it's empty)?
    a) Circular
    b) Doubly linked
    c) Dummy head node
    d) Queue
    Circular
  8. Why can't a linked list directly access any of its nodes?
    A linked list node can only be accessed using the pointer to it that is stored in the previous node.
  9. What would you have to do to an array to make it work like a Stack?
    • You would keep track of the index of the top element (the largest index of an element in the array).
    • When an element is added to the stack it must be added to the top + 1 index of the array.
    • When an element is removed from the stack the element at the top position of the array must be deleted.
  10. What would you have to do to a Linked List to make it work like a Queue?
    • You should implement a Linked list with a tail pointer because insertions in a Queue happen at the end, while deletions happen at the head.
    • When you add an item to this queue, you must update the tail pointer and update the previous tail's next to point to the new node.
    • When you delete an item from this queue, you use a pointer (curr) to point to the old head, advance head to head-> next, and delete curr.
  11. What do you have to do when enqueueing and dequeueing an in array-based queue to "wrap-around"?
    ******************Look this up *************************
  12. You have a list of numbers that is almost entirely sorted smallest to largest. Only one small-value number is out of place and it is near the end of the list amongst the large numbers. Why would insertion sort outperform bubble sort in this situation?
    Bubble sort can only move items toward the beginning of the list one position for each iteration of the sort algorithm. Insertion sort will move the small-value number to its proper position in the iteration that positions the small-value number into the sorted portion of the list.
  13. If a sequential search is performed on an array, how many items would have to be looked at to find the n-th item in the list?
    n items. 1st = 1 look, 2nd = 2 looks, ...
  14. If a binary search is performed on an array, how many items would have to be looked at to find the n-th item on the list?
    It depends on the position. Since binary search splits the "list" in half each iteration, it depends on the size of the list.
  15. If you const modify a member function in a class, what is the result?
    a) You cannot call the function
    b) The function can access and change an object's data
    c) The function can access an object's data, but cannot change it.
    d) The function cannot access an object's data.
    c
  16. Class definitions always end with:
    a) }
    b) };
    c) );
    d) }}
    b
  17. If you use the static modifier on a local variable in a function, what is the result?
    a) The function cannot modify the variable.
    b) The variable stays in memory after the function ends.
    c) Once you set the variable's value, you cannot change it.
    d) All functions in the program can change the variable.
    b
  18. Select the default constructor:
    a) Zip (const Zip &zip);
    b) Hype h;
    c) Bowler (string name, int score);
    d) Crayon();
    d
  19. Select the initializing constructor:
    a) Bowler(string name, int score);
    b) Zip(const Zip &z);
    c) Hype h;
    d) Crayon();
    a
  20. Select the copy constructor:
    a) Zip(const Zip &z);
    b) Hype h;
    c) Bowler(string name, int score);
    d) Crayon();
    a
  21. One of these sentences is false, select it.
    a) By default, all functions in C++ are const.
    b) By default, all functions in C++ are global.
    c) Member functions in a class should be in the public: section of the class definition.
    d) The scope resolution operator(::) marks a function as belonging to the class.
    b
  22. The #pragma once and #ifndef - #define - #endif combo serve the same purpose. What is it?
    They both serve to prevent redefining the class in memory.
  23. Public inheritance is which type of class relationship?
    a) has-a
    b) Was-a
    c) Is-a
    d) As-a
    c
  24. (T/F) In C++, you can derive a class directly from more than one superclass.
    true
  25. (T/F) Composition is the same as protected inheritance.
    false
  26. In C++, what notation is used to indicate that a function is a pure virtual function?
    a) *p
    b) &x
    c) =0
    d) <>
    c
  27. (T/F) Any pointer can be used to create a dynamic array.
    true
  28. List the big three functions that you need to make when a class uses pointers to create dynamic memory.
    • overloaded assignment operator
    • copy constructor
    • destructor
  29. When does a class's copy constructor execute?
    a) When a new object is being created as a call-by-reference parameter.
    b) When a new object is being created using an initializing constructor.
    c) When a new object is being created as a call-by-value parameter.
    d) When the object is going out of scope.
    c
  30. What are friend functions?
    a) Non-member functions that have access to member data.
    b) Non-member functions that have access to non-member data.
    c) Member functions that have access to member data.
    d) Member functions that have access to non-member data.
    a
  31. The two overloaded operators shown below can be called using (obj + obj2). Indicate which one is a member function of class Goober and which one is not.
    bool operator < (Goober g1, Goober g2);
    bool operator < (Goober g1);
    The first is a non-member; you can tell because it has two arguments. The second is a member because it has one argument.
  32. To prevent a pointer from 'dangling', set its value to ________.
    NULL
  33. You are given a template sorting function. You use it to sort an array of ints and also an array of doubles, but it won't compile when you give it an array of Jedi. Why won't it work?
    A sorting function must be able to compare two objects and determine which is greater (or if they are equal.) Because the Jedi function did not contain an overloaded comparison operator (> or <), the sorting function would not work.
  34. (T/F) A recursive function cannot ever call any function other than itself.
    False
  35. (T/F) If a recursive function's base case is never met, the function will recurse infinitely.
    False - you will run out of memory (stack overflow)
  36. A ________ variable will stay in memory even after the function that declared it is removed from the stack.
    static
  37. When deleting from a standard linked list, removing the ________ must be treated as a special case.
    a) Head
    b) Tail
    c) both a and b
    d) Neither a nor b
    a
  38. List the 4 questions that verify that a problem can be solved recursively.
    • 1) Can you define the problem in terms of smaller identically structured versions of itself?
    • 2) What is/are the base case(s) - when the problem is solved?
    • 3) Will each step (recursive call) move you closer to the solution?
    • 4) Are you guaranteed to reach a base case?
    • (Mnemonic - sbcr - smaller base case closer reach)
  39. Which linked list variant contains no null pointers (unless it's empty)?
    a) circular
    b) doubly linked
    c) dummy head node
    d) queue
    a
  40. Why can't a linked list directly access any given one of its nodes?
    A linked list can only access a node from the previous node in the list (which holds a pointer to the desired node).
  41. What are the 3 "basic" sorting methods?
    • selection sort
    • bubble sort
    • insertion sort
  42. Name 3 more advanced sorting algorithms.
    • merge sort
    • quick sort
    • radix sort
  43. Describe how selection sort works.
  44. Describe how bubble sort works.
  45. Describe how insertion sort works.
  46. Describe how merge sort works.
  47. Describe how quick sort works.
  48. Describe how radix sort works.
  49. What is a binary tree?
  50. What is a binary insertion tree?
  51. How does a binary insertion tree differ from a binary tree?
  52. What are the six orders ov traversal in binary trees?
    • preorder
    • postorder
    • inorder
    • and the reverse of each of these
  53. A binary tree can be implemented as an ________ or a ________.
    array, linked structured
  54. Why is it preferable for a binary tree to be balanced?
    A balanced tree can be searched more efficiently.
  55. A graph consists of a set of ________ and a set of ________.
    vertices, edges
  56. If the edges are ________ pairs of vertices, then the graph is ________.
    ordered, directed
  57. You can tell if a graph is directed because ________.
    the edges have arrows
  58. A graph can be represented using a/an ________.
    adjacency matrix
  59. An adjacency matrix will contain the same number of rows and columns as there are ________ in the graph.
    vertices
  60. Most graphs have ________ adjacency matrices.
    sparse
  61. Define a topological sort.
    A topological sort of an acyclic directed graph orders the vertices so that if there is a path from the vertex u to vertex v, then vertex v appears after vertex u in the ordering. Example given in class: CS classes at SIUE.
  62. What algorithm would you use to find the shortest path from a specified vertex to every other vertex in a directed unweighted graph?
    Starting at the specified vertex, mark each adjacent vertex with its distance from the specified vertex and its predecessor until all vertices are marked.
  63. <<<<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>>>>
    • What is a struct?
    • a collection of a fixed number of components.
  64. What is the syntax to define a struct?
    • struct structName {
    • datatype1 name1;
    • datatype2 name2;
    • ...
    • datatypen namen;};

    • Components of a struct are called ________ of the struct.
    • members
  65. How are members of a struct accessed?
    The dot operator - or member access operator - is used. e.g. structname.membername
  66. What are the only built-in operations on a struct?
    assignment and member access (dot operator)
  67. (T/F) Relational operations can be used on structs.
    False. (==, >, < would need to be defined to work on a given struct.)
  68. A struct can be passed to a function ________.
    either by value or by reference
  69. (T/F) A function can return a value of type struct.
    True
  70. (T/F) A struct can be a member of another struct.
    True
  71. (T/F) Two structs can be evaluated for equality, as in struct1 == struct2;
    False, structs must be compared memberwise to see if they are equal.
  72. What is a class?
    A class is a collection of a fixed number of components.
  73. Components of a class are called ________ of the class.
    members
  74. Members of a class are assigned one of three visibility modifiers. What are they.
    • public
    • private
    • protected
  75. Where are private members of a class accessible?
    Only within the class.
  76. Where are public members of a class accessible?
    From inside and outside the class.
  77. A member of a class can be ________.
    a function or variable
  78. How are functions declared as members of a class?
    Usually functions are declared as a member of a class using the function's prototype. It is declared in the appropriate section (public, private, protected).
  79. How is a variable declared as the member of a class.
    It is declared like any other variable, and it is declared in the appropriate section (public, private, protected).
  80. How is a protected member of a class designated in a UML diagram?
    #
  81. When is the memory for a class allocated?
    When it is declared. (NOT in the definition)
  82. How is a member of a class accessed?
    Using the member (dot) operator. e.g. className.memberName
  83. What are the built-in operations on classes?
    assignment and member access
  84. Classes can be passed to a function ________.
    by value or by reference
  85. (T/F) A function can return a value of type class.
    true
  86. What is an accessor function?
    A member function of a class that accesses but does not modify the values of member variables of the class.
  87. What is a mutator function?
    A member function of a class that modifies the value(s) of the member variables.
  88. (T/F) A const (or constant) can modify the values of member variables.
    False
  89. A constant (const) member function can only call ________.
    Other constant member functions of the class
  90. What is the purpose of a constructor?
    The constructor guarantees that the member variables are initialized when an object is declared.
  91. The name of a constructor is ________.
    The same as the name of the class.
  92. (T/F) A class can have more than one constructor.
    true
  93. What is a default constructor?
    A constructor that initializes the member variables to default values.
  94. Constructors automatically execute when ________.
    a class object enters its scope
  95. Destructors automatically execute when ________.
    a class object goes out of scope.
  96. (T/F) A class can have more than one destructor.
    False
  97. How is a destructor named?
    ~className();
  98. What is an abstract data type?
    It is a data type that separates the logical properties from the implementation details.
  99. (T/F) To implement an ADT, you must represent the data and write related algorithms to implement the operations.
    true
  100. For each ________ variable of a class, C++ only allocates one memort space. All members of the class refer to the same memory space.
    static
  101. A public static member of a class can be accessed using the class name and the ________.
    scope resolution operator (::)
  102. (T/F) Static members of a class exist even when no object of that class exists.
    true
  103. Non-static member variables of a class are called ________.
    instance variables
  104. ________ and ________ are meaningful ways to relate two or more classes.
    inheritance and composition
  105. Inheritance is a/an ___-a relation.
    is
  106. Composition (aka aggregation) is a ___-a relation.
    has
  107. In ________, the derived class is derived from only one existing class called the base class.
    single inheritance
  108. In ________, the derived class is derived more than one base class.
    multiple inheritance
  109. The public members of a base class can be inherited as ________ or ________ by the derived class.
    public, private
  110. A derived class can ________ the member functions of a base class. This only applies to members of the derived class.
    redefine
  111. How is the construction of the derived object's corresponding base object handled?
    A call to the base class's constructor (with parameters) is specified in the heading of the definition of the derived class's constructor.
  112. What if a derived class's constructor does not specify a call to the base class's constructor?
    The default constructor for the base class is executed during the derived class's object declaration.
  113. When initializing an object of a derived class, is the base class object's constructor executed first of is the derived class object's constructor executed first?
    The base class's constructor is executed first.
  114. In ________ or ________, a member of a class is an object of another class.
    composition, aggregation
  115. What are the three basic principles of object oriented design?
    • encapsulation
    • inheritance
    • polymorphism
  116. What is encapsulation?
    The ability to combine data and operations on that data in a single unit.
  117. What is inheritance?
    The ability to create new object (classes) from existing objects (classes).
  118. What is polymorphism?
    The ability to use the same expression to denote different operations.
  119. Describe an easy way to identify classes, objects and operations?
    Describe the problem in English. Nouns suggest objects, verbs suggest operations.
  120. Pointer variable contain ________ as their values.
    the addresses of other variables
  121. (T/F) In C++, a name is associated with the pointer data type.
    false
  122. A pointer variable is declared by using ________ between the data type and the variable name.
    • *
    • e.g., int *p;
  123. What does *p point to?
    The value stored in the memory address stored in p.
  124. What does p point to?
    A memory address of the type it was declared with. E.g., int *p => p would point to a memory location that will store an integer.
  125. What is & called?
    the address of operator
  126. The address of operator returns ________.
    the address of its operand.
  127. When used as a unary operator, * is called ________.
    the dereferencing operator
  128. How is the memory location indicated by the value of a pointer variable accessed?
    By using the dereferencing operator. If int *p is initialized to 25, *p = 25 and p is the memory address where the value of p is stored (which is currently 25).
  129. What is the member access operator used with pointers?
    The arrow ->. It is used to access members of objects pointed to by the pointers.
  130. What can pointer variables be initialized with?
    0, NULL, or the address of a variable of the same type (often a reference - &).
  131. What arithmetic operations are allowed on pointer variables?
    ++, --, adding or subtracting an integer from a pointer variable, and subtracting a pointer from another pointer.
  132. (T/F) Pointer variables cannot be compared using relational operators.
    false. It makes sense to compare pointers of the same type.
  133. (T/F) A dynamic variable is accessed by its name.
    False. Dynamic variables don't have names, they are only pointed to by pointer variables.
  134. A variable created during program execution is called ________.
    a dynamic variable
  135. What operator is used to create a dynamic variable?
    new
  136. What operator is used to deallocate the memory occupied by a dynamic variable?
    delete
  137. (T/F) The new and delete operators can be used with either single dynamic variables or arrays of dynamic variables.
    true
  138. If p is a dynamic array, what statement would be used to deallocate the memory occupied by p?
    delete [] p;
  139. Describe the variable **p.
    In this example, p is a pointer to a pointer.
  140. Describe the difference between a shallow copy and a deep copy.
    In a shallow copy, two or more pointers point to the same memory space. In a deep copy, two or more pointers of the same type have their own copies of the data.
  141. When is a destructor called?
    When a class object goes out of scope.
  142. If a class has pointer member variables, the built-in assignment operators provide a ________ copy of the data.
    shallow
  143. When does a copy constructor execute?
    When an object is declared and initialized by using the value of another object and when an object is passed by value as a parameter.
  144. (T/F) C++ allows a user to pass an object of a derived class to a formal parameter of the base class type.
    true. It makes sense because the derived class contains an instance of the base class.
  145. What does a virtual function do?
    It allows the binding of the function to occur at runtime (not compile time). This is called dynamic binding.
  146. How are virtual functions declared?
    By using the reserved word virtual.
  147. A class is called ________ if it contains one or more pure virtual functions.
    an abstract class
  148. Why can't you create objects of an abstract class?
    An abstract class contains pure virtual functions - functions that are not defined in the abstract class. For that reason, you cannot create such objects.
  149. Why would you want to declare a pure virtual function?
    If you are creating an abstract class to work with geometric shapes, you might want to include a function to calculate area. Because area is calculated differently for different shapes, declaring a pure virtual function in your class forces classes derived from shape to implement the area function that is appropriate for their class.
  150. Can an abstract contain functions that are not pure virtual?
    Yes; they must be defined in the class. Also, abstract classes can contain instance variables and constructors.
  151. (T/F) The address of operator can be used to return the address of a private member variable of the class.
    true.
  152. If you need to return the location of a variable in a class, but don't want to allow changes to the value of the variable, what can you do?
    declare the function as const (i.e. const int& addressOfX();
  153. An operator that has different meanings with different data types is said to be ________.
    overloaded
  154. Any function that overloads an operator is called a/an ________.
    operator function
  155. What is the syntax of the heading of the operator function?
    return type operator operatorSymbol (parameters)
  156. Operator functions ________.
    must return a value
  157. The only two functions that do NOT need to be overloaded to use on a class are ________.
    the member selection operator and the assignment operator
  158. When must the assignment operator function be overloaded?
    When a class has pointer member variables
  159. What is a major benefit of operator overloading?
    User defined classes are able to use the same concise notation as for built-in data types.
  160. (T/F) When you overload on operator you can change the precendence of the operator.
    False
  161. (T/F) When you overload on operator you can use default parameters.
    False
  162. (T/F) When you overload on operator you can change the number of parameters the operator takes.
    False
  163. (T/F) When you overload on operator you can change how the operator interacts with built-in data types.
    False
  164. Most C++ operators can/can not be overloaded.
    can
  165. The pointer ________ refers to the object as a whole.
    this
  166. The operator functions that overload the operators (), [], ->, or = must be ________.
    members of the class
  167. A ________ is a nonmember of the class.
    friend function
  168. If an operator function is a member of a class, ________ must be a class object (or reference to one).
    the far left operand
  169. (T/F) The heading of the prototype of a friend function is preceded by the word friend.
    True
  170. When a binary operator function is a member of a class, it has ________ parameter(s). When it is a nonmember, it has ________ parameter(s).
    one, two
  171. When the stream insertion and extraction operators of a class are overloaded, they must ________.
    be friend functions of that class
  172. When you want to overload the pre-increment (++) and post-increment (++) operators, how do you distinguish them - since they are both the same operator?
    When you overload the pre- version of an operator, it must have on parameters. When you overload the post-version of an operator, it must have one parameter of type int. It is a dummy parameter.
  173. What is a conversion constructor?
    A constructor that converts on object of one class to an object of another class.
  174. How many parameters does a conversion constructor take?
    one
  175. *Which three functions must be overloaded in classes with pointer variables?
    The assignment operator, the copy constructor and the destructor.
  176. (T/F) In C++ a function name can be overloaded.
    true
  177. There are two types of templates in C++. Name and describe them.
    • Function templates allow you to write a single code segment for a set of related functions (like adding two numbers - int, double, float).
    • Class templates allow you to write a single code segment for a set of related classes.
  178. What is the syntax for a template?
    • template
    • declaration;
  179. Class templates are called ________ types.
    parameterized
  180. What is the syntax for a member function called fun of a class template called cType?
    • template
    • returnType cType::fun(parameters)
  181. Suppose cType is a class template. What does this statement do? cType x;
    It declares an object of type cType and passes int to the class cType.
  182. The function ________ can check whether an expression meets the required condition(s). If the condition(s) are not met it terminates the program.
    assert
  183. What is the syntax of the assert statement?
    • assert(condition);
    • e.g. assert(2+2==4); //the program would continue
    • but assert(2-2==1); //execution stops
  184. Recursion is ________.
    the process of solving a problem by reducing it to smaller versions of itself.
  185. A recursive definition defines a problem in terms of ________.
    smaller versions of itself
  186. (T/T) Every recursive algorithm has one or more base cases.
    true
  187. A function is called recursive if it ________.
    calls itself.
  188. Recursive algorithms are implemented using ________.
    recursive functions
  189. Every recursive function must have ________.
    One or more base cases
  190. The general solution breaks the problem into ________.
    smaller versions of itself.
  191. The general case must eventually be reduced to ________.
    a base case
  192. ________ stops the recursion.
    The base case
  193. Every call to a recursive function has its own ________.
    set of code and its own set of parameters and local variables
  194. What happend when a particular recursive call is completed?
    Control returns to the calling environment, which is the previous call. A recursive call must execute completely before control goes back to the previous call. The execution in the previous call begins from the point immediately following the recursive call.
  195. A function is called ________ if it calls itself.
    directly recursive
  196. A function is said to be indirectly recursive if ________.
    it calls another function and eventually results in the original function call
  197. In a tail recursive function, the call the recursive function is ________.
    the last statement executed
  198. What is a linked list?
    It is a list of items, called nodes, in which the order of the nodes is determined by the address, called next, or right or left, etc., stored in each node.
  199. The pointer to a linked list - the pointer to the first node in a linked list - is stored in a separate location called ________.
    head
  200. A linked list is a ________ data structure.
    dynamic
  201. The length of a linked list is ________.
    the nuber of nodes in the list
  202. (T/F) Item insertion and deletion from a linked list to not require data movement.
    True. Only pointers are adjusted.
  203. To reach the last node in a singly linked list you must ________.
    start at the head node and traverse the list node by node
  204. The search on a linked list is ________.
    sequential
  205. To traverse a linked list, the program must use ________.
    a pointer different from the head pointer, initialized to the first node in the list
  206. In a doubly linked list, each node contains ________ pointers.
    two, one points to the previous node and one points to the next node.
  207. (T/F) A doubly linked list can be traversed in either direction.
    true
  208. In a doubly linked list, insertion and deletion require the adjustment of ________.
    both pointers in the affected nodes
  209. What is a circular linked list?
    A linked list in which the last node points to the head node.
  210. A stack is a data structure in which the items are added and deleted ________.
    to/from one end only
  211. A ________ is a LIFO data structure.
    stack
  212. Stacks can be implemented as ________.
    arrays or linked lists
  213. ________ of a stack should not be accessed directly.
    the middle elements
  214. (T/F) Stacks are restricted versions of arrays and linked lists.
    true
  215. A ________ is a data structure in which the items are added at one end and removed from the other end.
    queue
  216. A queue is a ________ data structure.
    FIFO
  217. Stacks can be implemented as ________.
    arrays or linked lists
  218. ________ of a queue should not be accessed directly.
    The middle elements
  219. ________ are restricted versions of arrays and linked lists.
    Queues
  220. How does the sequential search algorithm work?
    The sequential search algorithm starts with the first element in the list. It compares the current element in the list with the sought item, advancing to the next item in the list if it is not the sought item. It stops when the sought item is found or when the end of the list is reached.
  221. On average, how much of a list does the sequential search look through?
    Half of the list.
  222. (T/F) A sequential search is efficient for large lists.
    false
  223. A binary search is faster/slower than a sequential search.
    faster
  224. The ________ is the optimal worst-case algorithm for solving binary search problems by using the comparison method.
    binary search algorithm
  225. Both the ________ and ________ algorithms sort a list by partitioning it.
    quick sort, merge sort
  226. Describe how the quick sort algorithm works.
    The quick sort alg. first selects an item from the list as the pivot. Then the list is rearranged so that elements in one sublist are less than pivot and the elements in the other sublist are greater than or equal to pivot. Then the process is repeated for each sublist that has been created until the size of all sublists is 1.
  227. In the quicksort method, the work is done in ________.
    partitioning the list. This means that the choice of the pivot points is a major factor in the efficiency of the sort.
  228. Describe how the merge sort algorithm works.
    The merge sort algorithm divides the list into two sublists until the elements are all separated. Then each pair of separate values is merged into a sorted list, continuing up until the entire list has been merged (sorted).
  229. The merge sort partitions the list by ________.
    dividing it in the middle (the item in the physical middle of the list).
  230. In a merge sort, the work is done in ________.
    merging the list
  231. If a binary tree is nonempty, it must have at least one node called ________.
    the root node
  232. A subtree is composed of ________.
    a node in a binary tree and its children
  233. A node in a binary tree can have two subtrees, called ________.
    the left and right subtrees
  234. The node of a binary tree has ________ links in it.
    two
  235. A node in a binary tree is called a leaf if ________.
    it has no children
  236. A node U is clled the parent of node V if ________.
    there is a branch from U to V
  237. What is a path from node A to node Y in a binary tree?
    It is a sequence of pairs of nodes from node A to node Y, like A->B, B->C, ... X->Y.
  238. What is the length of a path in a binary tree?
    It is the number of branches on that path.
  239. What is the level of a node on a binary tree?
    It is the number of branches on the path from the root to that node.
  240. What is the level of the root node of the binary tree?
    0
  241. What is the level of a child of the root node in a binary tree?
    1
  242. What is the height of a binary tree?
    It is the number of nodes on the longest path from the root to a leaf.
  243. What is the order in which nodes are traversed in an inorder traversal of a binary tree?
    • 1) left subtree of the node
    • 2) visit the node
    • 3) right subtree of the node
  244. What is the order in which nodes are traversed in an preorder traversal of a binary tree?
    • 1) visit the node
    • 2) left subtree of the node
    • 3) right subtree of the node
  245. What is the order in which nodes are traversed in an postorder traversal of a binary tree?
    • 1) left subtree of the node
    • 2) right subtree of the node
    • 3) visit the node
  246. What condition must be met for a binary tree to be a binary search tree?
    In a binary search tree, the data in the root node must be larger than the data in every node in the left subtree and smaller than the data in every node in the right subtree. This condition must also be met for every subtree in the tree as well.
  247. How do you delete a node from a binary search tree that has both left and right subtrees that are nonempty?
    You have to locate the immediate predecessor of the node to be deleted (the largest value in the subtrees of the node to be deleted - it will always be the rightmost node in the left subtree of the node to be deleted.) Then the immediate predecessor's value replaces the value of the node to be deleted. If the node containing the immediate predecessor has nonempty left and right subtrees, the changes must "percolate".
  248. What is a graph?
    A graph is a finite nonempty set of vertices and a finite set of edges between those vertices.
  249. What is a directed graph (or digraph)?
    It is a graph in which the vertices are ordered pairs (indicating that travel between the vertices may not be allowed in both directions).
  250. What is an undirected graph?
    It is a graph in which (u,v) represents the same edge as (v,u). In this notation, a letter represents a vertex.
  251. Define a subgraph.
    A graph H is called a subgraph of a graph G if every vertex of H is a vertex of G and every edge in H is an edge in G.
  252. With regard to matrices, what does it mean to say that two vertices are adjacent?
    It means that there is an edge from one to another.
  253. (T/F) An edge can be incident to only one vertex.
    true. This is called a loop. Incident means "an endpoint of"
  254. What is a path in a graph?
    • A path from one vertex to another in a graph is a sequence of vertices that are all connected with edges that form a connected path from the starting point to the ending point.
    • What
    • What are connected vertices?
    • Vertices are said to be connected if there is a path between them.
  255. What is a simple path?
    A simple path is a path in which all of the vertices, except possibly the first and last vertices, are distinct.
  256. What is a cycle?
    A cycle in a graph G is a simple path in which the first and last vertices are the same.
  257. What does it mean if a graph is connected?
    A graph is said to be connected if there is a path from any vertex to any other vertex.
  258. If a graph is directed, it is important to know if, for two vertices u and v, u is ________ v AND if v is ________ u. They do not both have to be true or both false.
    adjacent from, adjacent from
  259. When is a graph said to be strongly connected?
    A directed graph is strongly connected if there is a path between any two of its vertices. (If any two vertices are connected)
  260. What is an adjacency matrix?
    An adjacency matrix is used to show which vertices are adjacent. If two vertices are adjacent, they are represented with a nonzero value; if they are not the entry is zero.
  261. What is an adjacency list?
    It is an alternative to an adjacency matrix. In this form, there is a list of adjacent nodes for each node in the graph.
  262. The ________ traversal of a graph is similar to the preorder traversal of a binary tree.
    depth first
  263. The ________ traversal of a graph is similar to the level by level traversal of a binary tree.
    breadth first
  264. What does the shortest path algorithm do?
    It gives the shortest distance for a given node to every other node in the graph.
  265. In a weighted graph, every edge ________.
    has a non-negative weight
  266. To calculate the weight of a path between two vertices, ________.
    sum the weights of all of the edges on the path P.
  267. What is a tree?
    A tree is a simple graph such that if u and v are two vertices in T, there is a unique path from u to v.
  268. What is a spanning tree?
    A tree is a spanning tree of graph G if all of the vertices of G are in T.
  269. What is a minimum spanning tree?
    A minimum spanning tree of G is a spanning tree with the minimum weight.
  270. How can you build a minimum spanning tree?
    You build the tree iteratively by adding edges until a minimal spanning tree is obtained. At each iteration, a new edge that does not complete a cycle is added to the tree.

Card Set Information

Author:
dimeng
ID:
313164
Filename:
final review
Updated:
2015-12-13 21:52:48
Tags:
diane cs240
Folders:
diane,cs240
Description:
cs240 final exam review
Show Answers:

Home > Flashcards > Print Preview