cpsc221 M2 Flashcards

Home > Preview

The flashcards below were created by user forrest.allen57 on FreezingBlue Flashcards.


  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 k is a positive integer and T is a full binary tree with k 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 t terminal verticies and height h, then t and h are related by the inequality ______.
     or 
  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.
    n
  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


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

    OR 
    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 k is an integer and  then  
    k
  16. If b is a real number with b > 1 and if x 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 logb x < x2
  17. if n is a positive integer, then 1 + 1/2 +1/3 +...+1/n has order ___.
    ln x or equivantly log2x
  18. b0 = 
    1
  19. b-x = 
  24.  Is the same as_____.
  29. 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
  30. 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
  31. The worst case order of the binary search algorithm is ___.
    log2n, where n is the length of the array
  32. 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
  33. The worst case order of the merge sort algorithm is ___.
    n log2n
  34. QuickSort
    Best:
    Average:
    Worst:
    Memory:
    Stable:
    • Best: n log n 
    • Average: n log n
    • Worst: n2
    • Memory: log n
    • Stable: depends
  35. Merge Sort
    Best:
    Average:
    Worst:
    Memory:
    Stable:
    • Best: n log n
    • Average: n log n 
    • Worst: n log n
    • Memory: depends; worst case is n 
    • Stable: yes 
  36. Heapsort
    Best: 
    Average:  
    Worst: 
    Memory: 
    Stable:
    • Best: n log n
    • Average: n log n
    • Worst: n log n 
    • Memory: 1
    • Stable: no 
  37. Insertion Sort
    Best:
    Average:
    Worst:
    Memory:
    Stable:
    • Best: n 
    • Average: n2
    • Worst: n2
    • Memory: 1
    • Stable: yes
  38. Hash(n) = 
    n mod 7
  39. Recurrence for Binary Search is: T(n)=

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

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


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

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


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

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


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

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


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

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

    NB: height(NULL) = -1 
  49. 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
  50. 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) 
  51. 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
  52. A loop in a graph is ____ 
    an edge with a single endpoint 
  53. Two distinct edges in a  graph are parallel if, and only if, ___.
    they have the same set of endpoints
  54. Two vertices are called adjacent if and only if __.
    they are connected by an edge.
  55. An edge is incident on ____.
    each of its endpoints.
  56. Two edges incident on the same endpoint are ___.
    adjacent 
  57. A vertex on which no edges are incident is ___.
    isolated
  58. In a directed graph, each edge is associated with ___.
    an ordered pair of vertices called its endpoints 
  59. a simple graph is ___.
    a graph with no loops or parallel edges
  60. A complete graph on n vertices is a ___.
    simple graph with  n vertices whose set of edges contains exactly one edge for each pair of verticies.
  61. 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 m vertices in V1 is __(a)__ to each of the n vertices in V2, no 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
  62. A graph H 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 H is also an edge in G 
    • (c) every edge in H has the same endpoints as it has in G. 
  63. 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.
  64. The total degree of a graph is defined as ___.
    the sum of the degrees of all the verticies of the graph
  65. The handshake theorem says that the total degree of a graph is ___. 
    equal to twice the number of edges in the graph
  66. in any graph the number of vertices of odd degree is ___.
    an even number.
  67. Let G be a graph and v and w be vertices in G, 

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

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

    a path from v to w is ____.
    a trail that does not contain a repeated vertex
  70. 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
  71. 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
  72. 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
  73. 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
  74. Let G be a graph and v and w be vertices in G,

    vertices v and w are connected if, and only if, ____. 
    there is a walk from v to w
  75. A graph is connected if, and only if, ____.
    given any two verticies in the graph, there is a walk from one to the other
  76. Removing an edge from a circuit in a graph does not ____.
    disconnect the graph
  77. An Euler circuit in a graph is ____.
    a circuit that contains every vertex and every edge of the graph 
  78. A graph has an Euler circuit if, and only if, ____.
    the graph is connected, and every vertex has positive, even degree
  79. Given verticies v and w in a graph, there is a Euler path from v to w  if, and only if, ____.
    the graph is connected, v  and w have odd degree, and all other vertices have positive even degree
  80. A Hamiltonian circuit in a graph is ____.
    a simple circuit that includes every vertex of the graph 
  81. If a graph G has a Hamiltonian circuit, then G has a sub graph H with the following properties: __(a)__, __(b)__, __(c)__, and __(d)__.
    • (a) H contains every vertex of G
    • (b) H is connected 
    • (c) H has the same number of edges as vertices
    • (d) every vertex of H has degree 2
  82. 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
  83. 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)
  84. 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)
  85. An n *  n square matrix is called symmetric if, and only if, for all integers i and j from 1 to n , the entry row __(a)__, and column__(b)___, equals the entry row __(c)__ and column__(d)__.
    • (a) i 
    • (b) j 
    • (c) j
    • (d) i
  86. the ijth entry in the product of two matrices A and B is obtained by multiplying row __(a)__ of A by row __(b)__ of B 
    (a) i 

    (b) j 
  87. 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
  88. if G is a graph with verticies v1, v2, ..., vm, and A is the adjacency matrix of G, then for each positive integer n and for all integers i and j with i , j = 1, 2, ...m, the ijth entry of An = ___.
    the number of walks of length n from vi to vj
  89. T/F? if f(n) is O(g(n)) then g(n) is 
    True
  90. T/F? Mergesort and Quicksort have the same worst-case running time. 
    False
  91. T/F? Postorder traversal visits the nodes of a binary search tree (with no duplicate keys) in decreasing order of their keys.
    False
  92. 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.
    True
  93. T/F? Skip list nodes (with maximum height 16) are most likely to have height 1 than height 2. 
    True
  94. T/F? For all a, b > 1, 
    True
  95. 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.
    False
  96. T/F? 
    int sum(int n) { if ( n==0 ) return 0; else return n+sum(n-1); } is tail recursive.
    False
  97. Suppose, int sum(int n) { if ( n==0 ) return 0; else return n+sum(n-1); } takes  to complete when n = 10,000 a reasonable prediction of its running time when n = 1,000,000 is : (a) , (b) 105, (c) , (d) 
    (c)
  98. T/F? The height of a rooted tree with n nodes is at most n - 1
    True
  99. 3 % 11 = 
    3
  100. 14 % 11 = 
    3
  101. 13 % 11 = 
    2
  102. 2 %  11 = 
    2
  103. 24 % 11 = 
    2
  104. 24 % 7 = 
    3
  105. 14 % 7 = 
    0 
  106. 17 % 7 = 
    3
  107. 11 % 7 =
    4
  108. There are ____ different ways of arranging n distinct objects into a sequence, the permutations of those objects.
    n!
  109. A sample space of a random process or experiement is ___.
    the set of all outcomes of the random process or experiement
  110. An event in a sample space is ___.
    a subset of the sample space
  111. 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
  112. if  , the number of integers from m to n inclusive is ___.
    n - m + 1
  113. The multiplication rule syas that if an operation can be performed in k steps and for each i 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
  114. A permutation of a set of elements is ___.
    an ordering of the elements of the set in a row
  115. The number of permutations of a set of n elements equals ___.
    n!
  116. An r-permutation of a set of  n elements is ___.
    an ordered selection of r of the elements of the set
  117. the number of r-permutations of a set of n elements is denoted ___.
    P(n, r)
  118. One formula for the numner of r-permutations  of a set of  n elements is __(a)__ and another formula is __(b)__.
    • (a) n ( n - 1 ) ( n - 2 ) ... ( n - r + 1)
    • (b)
  119. The addition rule says that if a finite set A equals the union of k dsitinct mutally disjoint subsets A1  , A2 , ... , Ak , then ____.
    • the number of elements in A equals N(A1) + N(A2) + ...+ N(An)
  120. The difference rule says that if A is a finite set and B is a subset of A, then ___.
    The number of elements in A - B is the difference between the number of elements in A and the number of elements in B , that is, N(A-B) = N(A) - N(B)
  121. If S is a finite sample space and A is an event in S, Then the probability of Ac equals ____.
    1 - P(A)
  122. The inclusion/exclusion rule for two sets says that if  A and B are  any finite sets, then ____.
  123. The inclusion/exclusion rule for three sets says if A, B, and C are any finite sets, then ____.
  124. The pigeonhole principal states that ___.
    if n pigeons fly into m 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
  125. The generalized pigeonhole principal states that ___.
    if n pigeons fly into m pigeonholes and, for some positive integer k , k < n/m, then at least one pigeonhole contains k +1 or more pigeons OR for any funcion f from a finite set X with n elements to a finite set Y with m elements and for any positive integer k , if k < n/m, then there is some  such that  y is the image of at least k +1 distinct elements of Y.
  126. If X and Y are finite sets and f is a function form X to Y then f is one-to-one iff ___.
    f  is onto

Card Set Information

Author:
 forrest.allen57
ID:
 181746
Filename:
 cpsc221 M2 Flashcards
Updated:
2012-12-09 07:12:16
Tags:
Computer Science
Folders:

Description:
CPSC 221 M2 Flashcards
Show Answers:

What would you like to do?

Home > Flashcards > Print Preview