cpsc221 M2 Flashcards

Card Set Information

cpsc221 M2 Flashcards
2012-12-09 02:12:16
Computer Science

CPSC 221 M2 Flashcards
Show Answers:

  1. A rooted tree is a tree in which ______. 
    One vertex is distinguished from the others and is called the root
  2. The level of a vertex in  a rooted tree is ____. 
    the number of edges along the unique path between it and the root
  3. The height of a rooted tree is ____.
    the maximum level of any vertex of the tree
  4. A binary tree is a rooted tree in which ____.
    every parent has at most two children
  5. A full binary tree is a rooted tree in which ____.
    every parent has exactly two children 
  6. If is a positive integer and T is a full binary tree with internal verticies, then T has a total of __(a)___ verticies and ___(b)__ terminal verticies
    • a) 2k +1
    • b) k +1  
  7. If  T is a binary tree that has terminal verticies and height h, then and are related by the inequality ______.
  8. When an algorithm segment contains a nested for-next loop, you can find the number of times the loob will interate by constructing a table in which each column represents ____.
    one iteration of the innermost loop
  9. In the worst case for an input array of length  n, the sequential search algorith has to look through _____ elements of the array before it terminates.
  10. The worst-case order of the insertion sort algorithm is _(a)__, and its average-case order is _(b)___.
    • a) n2
    • b) n2
  11. for all integers n >= 1


  12. for any real number except 1, and any integer n >= 0

    1 + r + r2+...rn = 
  13. The domain of any exponential function is _(a)_, and its range is  _(b)_.
    • a) the set of all real numbers 
    • b) the set of all positive real numbers
  14. The domain of any logarithmic funcion is _(a)_, and its range is _(b)_.
    • a) the set of all positive real numbers
    • b) the set of all real numbers
  15. if is an integer and  then  
  16. If is a real number with b > 1 and if is a sufficiently large real number, then when the quantities x, x2, logbx, andare arranged in order of increasing size, the result is ___.
    logbx < x < x logx < x2
  17. if is a positive integer, then 1 + 1/2 +1/3 +...+1/n has order ___.
    ln x or equivantly log2x
  18. b0
  19. b-x 
  20.  Is the same as_____.
  21. To solve a problem using a divide-and-conquer algorithm, you reduce it to a fixed number of smaller problems of the same kind, which can themselves be __(a)__, and so forth until _(b)__.
    • a) reduced to the same finite number of smaller problems of the same kind
    • b) easily resolved problems are obtained
  22. To search an array using the binary search algorithm in each step, you compare a middle element of an array to __(a)__. If the middle element is less then __(b)__, you __(c)__, and if the middle element is greater then __(d)__, you  __(e)__.
    • (a) the element uou are looking for
    • (b) the element you are looking for
    • (c) apply the binary search algorithm to the lower half of the array
    • (d) the element you are looking for
    • (e) apply the binary search algorithm to the upper half of the array
  23. The worst case order of the binary search algorithm is ___.
    log2n, where is the length of the array
  24. To sort an array using the merge sort algorithm, in each step until the last one you split the array into approximately two equal sections and sort each section using __(a)__. Then you __(b)__ the two sorted sections.
    • (a) merge sort
    • (b) merge
  25. The worst case order of the merge sort algorithm is ___.
    n log2n
  26. QuickSort
    • Best: n log n 
    • Average: n log n
    • Worst: n2
    • Memory: log n
    • Stable: depends
  27. Merge Sort
    • Best: n log n
    • Average: n log n 
    • Worst: n log n
    • Memory: depends; worst case is n 
    • Stable: yes 
  28. Heapsort
    • Best: n log n
    • Average: n log n
    • Worst: n log n 
    • Memory: 1
    • Stable: no 
  29. Insertion Sort
    • Best: 
    • Average: n2
    • Worst: n2
    • Memory: 1
    • Stable: yes
  30. Hash(n) = 
    n mod 7
  31. Recurrence for Binary Search is: T(n)=

    Big-O solution:
    T(n/2) + O(1)

    O(log n)
  32. Recurrence for Sequential Search is: T(n) = 

    Big-O solution:
    T(n-1) + O(1)

    • O(n)
  33. Recurrence for Tree Traversal: T(n)

    Big-O solution:
    2 T(n/2) + O(1)

    • O(n)
  34. Recurrence for Mergesort and Average case Quicksort: T(n) = 

    Big-O solution:
    2 T(n/2) + O(n)

    • O(n log n)
  35. Recurrence for Selection Sort (other n2 sorts): T(n) = 

    Big-O solution:
    T(n-1) + O(n)

    • O(n2)
  36. What is the formula to calculate the balance for each node in an AVL tree with height 
    hR - h where hR and hL are the heights of the left and right subtrees, respectively.
  37. A tree is called a Left-Left tree because ___.
    its root and left subtree of the root are both left-heavy
  38. What is the Balance Property of an AVL-Tree for all nodes x?
    • Result: height is 
  39. To balance AVL-Tree balance(x) = 
    height(x.left) - height(x.right)

    NB: height(NULL) = -1 
  40. A Loop Invariant is _(a)__. What are three of it's properties?
    • (a) a statement that is true before loop execution begins, at the beginning of each repetition of the loop body, and just after
    • the loop exits
    • 1) Invariant must be true before loop execution begins
    • 2)Must be true at the beginning of each repetition
    • 3) Must be true after loop exit
  41. Binary Heap Navigation:
    left_child(i) = (a)
    right_child(i) = (b)
    parent(i) = (c)
    root() = (d)
    next_free_pos() = (e)
    • (a) 
    • (b)
    • (c) 
    • (d) 
    • (d) 
  42. A graph consists of two finite sets: __(a)__ and __(b)__, where each edge is associated with a set consisting of __(c)__.
    • (a) a finite, nonempty set of verticies
    • (b) a finite set of edges
    • (c) one or two verticies called its endpoints
  43. A loop in a graph is ____ 
    an edge with a single endpoint 
  44. Two distinct edges in a  graph are parallel if, and only if, ___.
    they have the same set of endpoints
  45. Two vertices are called adjacent if and only if __.
    they are connected by an edge.
  46. An edge is incident on ____.
    each of its endpoints.
  47. Two edges incident on the same endpoint are ___.
  48. A vertex on which no edges are incident is ___.
  49. In a directed graph, each edge is associated with ___.
    an ordered pair of vertices called its endpoints 
  50. a simple graph is ___.
    a graph with no loops or parallel edges
  51. A complete graph on vertices is a ___.
    simple graph with vertices whose set of edges contains exactly one edge for each pair of verticies.
  52. A complete bipartite graph on (m,n) vertices is a simple graph whose vertices can be partitioned into two disjoint sets V1 and V2 in such a way that (1) each of the vertices in V1 is __(a)__ to each of the vertices in V2no vertex in V1 is connected to ___(b)__, and no vertex in V2 is connected to __(c)__.
    • (a) connected by an edge
    • (b) any other vertex V1
    • (c) any other vertex in V2

  53. A graph is a subgraph of a graph G if, and only if, (1)__(a)__, (2)__(b)__, and (3) __(c)__.
    • (a)every vertex in H is also a vertex in G
    • (b) every edge in is also an edge in 
    • (c) every edge in has the same endpoints as it has in G. 
  54. The degree of a vertex in a graph is ___.
    the number of edges that are incident on the vertex, with an edge that is a loop counted twice.
  55. The total degree of a graph is defined as ___.
    the sum of the degrees of all the verticies of the graph
  56. The handshake theorem says that the total degree of a graph is ___. 
    equal to twice the number of edges in the graph
  57. in any graph the number of vertices of odd degree is ___.
    an even number.
  58. Let be a graph and and be vertices in G, 

    A walk from to is ____.
    a finite alternating sequence of adjacent verticies and edges of 
  59. Let G be a graph and v and w be vertices in G,

    A trail from to is ____.
    a walk that does not contain a repeated edge
  60. Let G be a graph and v and w be vertices in G,

    a path from to is ____.
    a trail that does not contain a repeated vertex
  61. Let G be a graph and v and w be vertices in G,

    a closed walk is ____. 
    a walk that starts and ends at the same vertex
  62. Let G be a graph and v and w be vertices in G,

    A circuit is ____. 
    a closed walk that contains at least one edge and does not contain a repeated edge
  63. Let G be a graph and v and w be vertices in G,

    a simple circuit is ____. 
    a circuit that does not have any repeated vertex other than the first and the last
  64. Let G be a graph and v and w be vertices in G,

    a trivial walk is ____.  
    a walk consisting of a single vertex and no edge
  65. Let G be a graph and v and w be vertices in G,

    vertices and are connected if, and only if, ____. 
    there is a walk from to w
  66. A graph is connected if, and only if, ____.
    given any two verticies in the graph, there is a walk from one to the other
  67. Removing an edge from a circuit in a graph does not ____.
    disconnect the graph
  68. An Euler circuit in a graph is ____.
    a circuit that contains every vertex and every edge of the graph 
  69. A graph has an Euler circuit if, and only if, ____.
    the graph is connected, and every vertex has positive, even degree
  70. Given verticies and in a graph, there is a Euler path from to if, and only if, ____.
    the graph is connected,  and have odd degree, and all other vertices have positive even degree
  71. A Hamiltonian circuit in a graph is ____.
    a simple circuit that includes every vertex of the graph 
  72. If a graph has a Hamiltonian circuit, then has a sub graph with the following properties: __(a)__, __(b)__, __(c)__, and __(d)__.
    • (a) contains every vertex of G
    • (b) H is connected 
    • (c) H has the same number of edges as vertices
    • (d) every vertex of has degree 2
  73. A traveling salesman problem involves finding a ____ that minimizes the total distance of traveled for a graph in which each edge is marked with a distance.
    Hamiltonian circuit
  74. In the adjacency matrix for a directed graph, the entry in the ith rowand jth colum is ____.
    the number of arrows from vi (the ith vertex) to vj (the jth vertex)
  75. In the adjacency matrix for an undirected graph, the entry in the ith row and jth column is ___.
    the number of edges connecting vi (the ith vertex) and vj (the jth vertex)
  76. An n *  n square matrix is called symmetric if, and only if, for all integers i and from to , the entry row __(a)__, and column__(b)___, equals the entry row __(c)__ and column__(d)__.
    • (a) 
    • (b) j 
    • (c) j
    • (d) i
  77. the ijth entry in the product of two matrices A and is obtained by multiplying row __(a)__ of by row __(b)__ of B 

  78. In an n * n identity matrix the entries on the main diagonal are all __(a)__ and the off-diagonal entries are all __(b)__.
    • (a) 1 
    • (b) 0
  79. if is a graph with verticies v1, v2, ..., vm, and is the adjacency matrix of G, then for each positive integer and for all integers i and with j = 1, 2, ...m, the ijth entry of An = ___.
    the number of walks of length from vi to vj
  80. T/F? if f(n) is O(g(n)) then g(n) is 
  81. T/F? Mergesort and Quicksort have the same worst-case running time. 
  82. T/F? Postorder traversal visits the nodes of a binary search tree (with no duplicate keys) in decreasing order of their keys.
  83. T/F? If every box of jelly-beans contains 20 to 30 beans then I only need to collect 23 boxes to be sure that three of my boxes contain teh same number of beans.
  84. T/F? Skip list nodes (with maximum height 16) are most likely to have height 1 than height 2. 
  85. T/F? For all a, b > 1, 
  86. T/F? An algorithm with worst-case running time O(n) is faster then an algorithm with a best-case running time  on any input.
  87. T/F? 
    int sum(int n) { if ( n==0 ) return 0; else return n+sum(n-1); } is tail recursive.
  88. Suppose, int sum(int n) { if ( n==0 ) return 0; else return n+sum(n-1); } takes  to complete when = 10,000 a reasonable prediction of its running time when n = 1,000,000 is : (a) , (b) 105, (c) , (d) 
  89. T/F? The height of a rooted tree with nodes is at most - 1
  90. 3 % 11 = 
  91. 14 % 11 = 
  92. 13 % 11 = 
  93. 2 %  11 = 
  94. 24 % 11 = 
  95. 24 % 7 = 
  96. 14 % 7 = 
  97. 17 % 7 = 
  98. 11 % 7 =
  99. There are ____ different ways of arranging n distinct objects into a sequence, the permutations of those objects.
  100. A sample space of a random process or experiement is ___.
    the set of all outcomes of the random process or experiement
  101. An event in a sample space is ___.
    a subset of the sample space
  102. To compute the probability of an event using the equally likely probability formula, you take the ratio of the __(a)__ to the __(b)__.
    • (a) number of outcomes in the event
    • (b) total number of outcomes
  103. if  , the number of integers from to inclusive is ___.
    - m + 1
  104. The multiplication rule syas that if an operation can be performed in steps and for each with , the ith step can be performed in ni ways (regaurdless of how previous steps were performed), then the operation as a whole can be performed in ___.
    n1n2...nk ways
  105. A permutation of a set of elements is ___.
    an ordering of the elements of the set in a row
  106. The number of permutations of a set of elements equals ___.
  107. An r-permutation of a set of elements is ___.
    an ordered selection of of the elements of the set
  108. the number of r-permutations of a set of elements is denoted ___.
    P(n, r)
  109. One formula for the numner of r-permutations  of a set of  elements is __(a)__ and another formula is __(b)__.
    • (a) - 1 ) ( - 2 ) ... ( + 1)
    • (b)
  110. The addition rule says that if a finite set equals the union of dsitinct mutally disjoint subsets A1  , A, ... , Ak , then ____.
    • the number of elements in equals N(A1) + N(A2) + ...+ N(An)
  111. The difference rule says that if is a finite set and is a subset of A, then ___.
    The number of elements in A - B is the difference between the number of elements in and the number of elements in B , that is, N(A-B) = N(A) - N(B)
  112. If is a finite sample space and is an event in S, Then the probability of Ac equals ____.
    1 - P(A)
  113. The inclusion/exclusion rule for two sets says that if  and are  any finite sets, then ____.
  114. The inclusion/exclusion rule for three sets says if A, B, and are any finite sets, then ____.
  115. The pigeonhole principal states that ___.
    if pigeons fly into pigeonholes and n > m , then at least two pigeons fly into the same pigeonhole. OR a funcion form one finite set to a smaller finite set cannot be one-to-one
  116. The generalized pigeonhole principal states that ___.
    if pigeons fly into pigeonholes and, for some positive integer k , k < n/m, then at least one pigeonhole contains +1 or more pigeons OR for any funcion from a finite set with elements to a finite set with elements and for any positive integer , if k < n/m, then there is some  such that is the image of at least k +1 distinct elements of Y.
  117. If and are finite sets and is a function form to then is one-to-one iff ___.
    f  is onto