GoConqr hat ein neues Design! Sag uns, wie es dir gefällt.

Kostenlos registrieren

Karteikarten

BYUI CS235 Final Study

Sara Reece CS 235 Final Exam Practice Englisch 143 Karten

Karten in diesem Stapel (143)

  1. 1Define ADTAbstract Data Type
  2. 2Name All of the Functions in a StackCreate, Assingment, Empty, Size, Capacity, Clear, Push, Pop, Top
  3. 3What best explains a Stack as an ADTLast-in, First-Out
  4. 4In Stack what does Top() Do?Retrieves the top value, but leaves the stack unchanged
  5. 5In Stack what does Push() Do?Modifies the Stack by adding one element to the top
  6. 6In a Stack what does Empty() Do?Returns true if there are no elements, otherwise returns false
  7. 7What does a stack's a default Constructor doCreates an empty stack
  8. 8What does Pop() do in a stackModifies the stack by removing the top element
  9. 9What is a structA way of creating a new data type that is made up of existing data types
  10. 10What is a classA way to create a new data type (object) it encapsulates both the data types and their corresponding fuctions
  11. 11What does void indicatethe empty data-type
  12. 12Give an example of a Macro#define
  13. 13Define enumA data-type whose literals are identifiers each of which is associated with an unique integer
  14. 14Define typedefA method for creating a new type by giving a new name to the existing type
  15. 15What all can * indicate in C++4 things
    Multiplication operator, Used in the declaration of a variable to indicate that a pointer is used, Dereference operator, part of a block comment
  16. 16What all can & indicate in C++4 Things
    Part of the && operator, address-of operator, used to indicate pass-by-reference, Bitwise "and" operator
  17. 17What is this Complex & Complex::operator=(const Complex & rhs)Assignment operator
  18. 18What is this ostream & operator << (ostream & out, const Complex & rhs)Insertion operator
  19. 19What is this Complex::Complex(const Complex & rhs)Copy constructor
  20. 20What is this istream & operator >> (istream & in, Complex & rhs)Extraction operator
  21. 21What is this Complex::~Complex()Destructor
  22. 22What is this Complex::Complex(float real)Non-Default Constructor
  23. 23What is this Complex & Complex::operator () (float r, float i)a functor
  24. 24What is this Complex::Complex()Default constructor
  25. 25What is a good way to describe a queueFirst in first out
  26. 26Define Enqueue (in regards to queue)Process of adding items to the back of the queue
  27. 27Define Front (in regards to queue)The place in a queue where items are removed
  28. 28Define Dequeue (in regards to queue)Removing an item from the queue (front of the line)
  29. 29Define back (in regards to a queue)Place where elements are added
  30. 30Define Queue Creep (Hint: Not the weirdo standing too close)When items are added to an end of a queue until elements walk off the end of the allocated buffer
  31. 31Consider the following queue {70, 80, 50, ?, ?, ?} and myFront = 0 and myBack = 2. What happens when the value 20 is added to the queue?{70, 80, 50, 20, ?, ?} myFront = 0, myBack = 3
  32. 32Consider the following queue {70, 80, 50, ?, ?, ?} and myFront = 0 and myBack = 2. What happens when one item is removed from the queue?{?, 80, 50, ?, ?, ?} myFront = 1, myBack = 2
  33. 33Give an example of a setA collection of students in a class
  34. 34Give an example of a stackA discard pile in a card game
  35. 35Give an example of a queuePrint jobs sent to a printer
  36. 36Describe a VectorSimilar to an array, but can grow
  37. 37Describe a StackItems can only be added or removed from one end (The top)
  38. 38Describe a queueepidemy of First in First out
  39. 39Describe a SetA container of unique elements
  40. 40Describe a DequeA container where items can only be accessed from either end (front or back)
  41. 41what is deque an abbreviation forDouble-Ended Queue
  42. 42Define RecursionThe process of a one function calling itself
  43. 43What are the two parts of a recursive Definition of a functionBase Case
    Recursive Case
  44. 44Some ways of demoing sets{} = 0
    {0,1} = {1,0}
    {1,1} = 1
  45. 45What is Cardinality?The number of unique elements in a set
  46. 46What is the cardinality of this set {a}?1
  47. 47What is the cardinality of this set {a, a, b, c}3
    because a repeats. There are only three unique elements in this set
  48. 48Given the set S = { red, blue, green orange }, what is the result of the function S.find(blue)?an iterator referring to blue
  49. 49Given the set S = { 2, 4, 6, 8 }, what is the result of S.insert(5)?{ 2, 5, 4, 6, 8 }
  50. 50Which of the following represents the result of { a, e, i, o, u } ⋃ { a, b, c, d, e, f }{ a, b, c, d, e, f, i, o, u }
    ⋃, union, means we combine all elements into the set
  51. 51Which of the following represents the result of { a, e, i, o, u } ⋂ { a, b, c, d, e, f }{ a, e }
    ⋂, intersection, means we only take the overlap between the sets
  52. 52Which of the following represents the result of { a, e, i, o, u } - { a, b, c, d, e, f }{ i, o, u }
    -, difference, means we only take elements that do repeat between the sets
  53. 53From fastest to slowest list the Performance Cost NotationsO(1)
    O(log n)
    O(n)
    O(n log n)
    O(n^2)
    O(2^n)
  54. 54Tell me the name and description of this performance Cost O(1)Name: Constant
    Description: Performance is unrelated to the size of the data structure
    Faster than you will notice
  55. 55Tell me the name and description of this performance Cost O(log n)Name: Logarithmic
    Description: Performance is a log of the size of the data structure
    A noticeable lag
  56. 56Tell me the name and description of this performance Cost O(n)Name: Linear
    Description: Performance is directly related to size
    Takes considerable patience
  57. 57Tell me the name and description of this performance Cost O(n log n)Name: N-Log-N
    Description: Performance is linear times logarithmic
    The user will leave the computer to take a walk
  58. 58Tell me the name and description of this performance Cost O(n^2)Name: N-Squared
    Description: Performance is the square of the size of the data structure
    The user lost all hope
  59. 59Tell me the name and description of this performance Cost O(2^n)Name: 2-to-the-N
    Description: Performance is Horrid
    2 trillion times the age of the universe
  60. 60What ADT Matches this description LIFOStack
  61. 61What ADT Matches this description FIFOqueue
  62. 62What ADT Matches this description Random AccessVector (and Array)
  63. 63What ADT Matches this description sequential accessList
  64. 64What ADT Matches this description Access to either endDeque
  65. 65What ADT Matches this description unordered collection of unique itemsSet
  66. 66What is the best structure definition for a linked list?template
    struct Node{
    T data;
    Node * pNext;};
  67. 67Setting the link of the last node in a standard linear linked list to point to the first node produces a(n) ____ linked list.Circular
  68. 68What do you call a linked-list where every node has a pointer to the successor and predecessor?Doubly-linked list
  69. 69In Regards to a Binary Tree What is a Node?An element representing a single value
  70. 70In Regards to a Binary Tree what is a Tree?A finite collection of connected Elements
  71. 71In Regards to a Binary Tree what are directed ArcsThe connection between elements in a tree
  72. 72In Regards to a Binary Tree what is a root?A Node that has no incomming arcs, but from which every node of the tree can be reached
  73. 73In Regards to a Binary Tree what is a path?The collection of arcs from one element to another
  74. 74In Regards to a Binary Tree what is a ParentWhen one element has an arc pointing to a second, this is the name of the first element
  75. 75In Regards to a Binary Tree what is a Child?When one element has an arc pointing to a second element this is the name of the second element
  76. 76In Regards to a Binary Tree what are Siblings?Two children sharing the same parent
  77. 77In Regards to a Binary Tree what is a Binary TreeA special kind of tree where each element has 0, 1, or 2 children
  78. 78In Regards to a Binary Tree what is a subtreeA collection consisting of a node and all of its descendants
  79. 79In Regards to a Binary Tree what is an ancestor?A node that is a parent, and parents parent, etc.
  80. 80In Regards to a Binary Tree what is a leafA node with no outgoing arcs ( has no children)
  81. 81In Regards to a Binary Tree what is completeA tree where all levels are filled in
  82. 82In Regards to a Binary Tree what is balancedA tree where the number of ancestors for each leaf node are different no more than one
  83. 83How do you determine the height of a treeLongest path from bottom Leaf to Root
  84. 84What does LVR meanIn order Traverse
  85. 85What does VLR MeanPre order traverse
  86. 86What does LRV MeanPost Order Traverse
  87. 87What Does RVL MeanBackwards Traverse
  88. 88What do VRL and RLV MeanNothing pertinent to this course
  89. 89Order Preserved, random accessvector
  90. 90ADT with Unordred, unique MembershipSet
  91. 91ADT FILOStack
  92. 92ADT FIFOQueue
  93. 93ADT Remove items from either endDEQUE
  94. 94ADT Order preserved, sequential access.List
  95. 95ADT Binary tree where left < node < right.BST
  96. 96ADTs Unordered, random access. & Unordered, sequential access.Nothing we have studied
  97. 97List three traversal StrategiesLVR
    VLR
    LRV
  98. 98Name Methods Associated with MapCreate, Assignment =, Empty, Size, Clear, Begin, End, Insert, Access[], Find
  99. 99Name Methods Associated with QueueCreate, Assignment =, Empty, Size, Clear, push, pop, front, back
  100. 100Name Methods Associated with Deque (Double Ended Queue)Create, Assignment =, Empty, Size, Clear, Push Front, Push Back, Pop Front, Pop Back, Front, Back
  101. 101Name Methods Associated with SetCreate, Assignment, Empty, Size, Capacity, Clear, Begin, End, Insert, Find, Erase, Union ⋃, Intersection ⋂, Difference -
  102. 102Name Methods Associated with Linked ListCreate, insert, copy, clear, find, Remove
  103. 103Describe a NodeT Data
    Node pNext
    Node pPrev
  104. 104Name Methods Associated with a ListCreate, Assignment, Empty, Size, Clear, Begin, End, Find, Insert, Push Back, Push Front, Pop Back, Pop Front, Erase, Front, Back
  105. 105Name Methods Associated with Binary TreeCreate, Size, Copy, Clear, Add Left, Add Right, Display
  106. 106Name Methods Associated with Binary Search TreeCreate, Assignment, Empty, Size, Clear Begin, End, Insert, Find, Erase
  107. 107Name Methods associated with MapCreate, Assignment, Empty, Size, Clear, Begin, End, Insert, Access, Find
  108. 108Name Methods Associated with HashCreate, Assignment, Empty, Size, Capacity, Clear, Insert, Find
  109. 109Name Methods Associated with GraphCreate, Assignment, Empty, Size, Capacity, Clear, Add, Is Edge, Find Edges, Find Path
  110. 110In regards to tree balancing strategies what is a 2-3-4 TreeA tree with up to 4 nodes
  111. 111In regards to tree balancing strategies what is a Red-BlackBinary Representation of 2-4-5 Tree
  112. 112In regards to tree balancing strategies what is a B-TreeA tree containing many possible children
  113. 113In regards to tree balancing strategies what is a 2 Node, 3 Node, 4 Node or ForestNothing we have studied
  114. 114In a 2-3-4 tree What is a red NodeRepresents a sibling an a 2-3-4 Tree
  115. 115In a 2-3-4 tree What is a black NodeRepresents a child in 2-3-4 tree.
  116. 116Definition of an internal SortA sorting algorithm where the entire collection must be in memory.
  117. 117Define Quick SortA pivot is defined. All items larger than the pivot are put to one side and all items smaller are put to the other. Then the two sublists (Sides) are recursively sorted
    O(n Log n)
  118. 118Define Binary SortAll items in a collection are inserted into a BST. The Tree is traversed using infix traversal
    O(n Log n)
  119. 119Define Bubble SortSystematically interchange pairs of elements until all possible pairs are in the correct order
    O(n^2)
  120. 120Define Heap SortAll elements in collection are put in Binary Tree. Each parent gets the largest value of the two children. The process is continued until the entire tree is sorted using a level ordered traverse.
    O(n log n)
  121. 121Define Selection SortFind smallest Element in collection and put at the head of the ordered list. Then find the second smallest, etc. .
    O(n^2)
  122. 122Define Merge SortA large list is subdivided into two small lists. They are recursively Sorted and then combined into a single sorted list.
    O(n log n)
  123. 123Define Insertion SortTake the first item from a collection and insert it into a sorted list. Take the second item, etc.
    O(n^2)
  124. 124In regards to a hash what is chainingA collision Strategy in which the hash table is an array of lists that store the items
  125. 125In regards to a hash what is a hash functionThe function returning the index from the key value
  126. 126In regards to a hash what is collisionWhen two items need to be placed in the same location in a hash table
  127. 127In regards to a hash what is random hashingA technique used to uniformly scatter items throughout the has table
  128. 128In regards to a hash what is double hashingA technique used to avoid clustering by using a second hash function
  129. 129In regards to a hash what is linear probingA technique used to deal with collisions by moving forward in the hash table looking for an empty slot
  130. 130In regards to a hash what is a hash tableAn array storing values indexed with a hash function
  131. 131In regards to a hash what is clusteringThe tendency for hash tables to be filled non-uniformly
  132. 132What is the cost to: insert an item in a hash table Remove an item for a hash table Search for an item in a hash table0(1)
  133. 133In regards to graphs what is an undirected GraphA graph where the Vertices Do not have a direction
  134. 134In regards to graphs what is a routing problemThe process of finding the shortest pat to a given vertex
  135. 135In regards to graphs what is an edgean Arc
  136. 136In regards to graphs what is the adjacency MatrixA Two Dimensional Array Describing the edges in a graph
  137. 137In regards to graphs what is a vertexA Node
  138. 138In regards to graphs what is a graphA Collection of Vetices and associated Edges.
  139. 139In regards to graphs what is a depth-first searchA method of finding a given vertex by starting at a start vertex and explores as far as possible along each branch before backtracking
  140. 140In regards to graphs what does sparse meanThe condition of an adjacency Matrix being mostly filled with zero values
  141. 141In regards to graphs what is backtrackingWhen searching for a vertex, the process of recovering from a dead end
  142. 142In regards to graphs what is a directed GraphA graph where the vertices have a direction
  143. 143In regards to graphs what is a breadth first searchA method of finding a given vertex by first inspecting all the adjacent vertices. then for each of those adjacent vertex in turn, it inspects their neighbor vertices which were unvisited, and so on.

Informationen

Beschreibung
Flash cards to review the behemoth amount of material the crammed into one course.
Erstellt von
Sara Reece · Apr 2020
Aktualisiert
8 Apr 2020
Aufrufe
6
Bewertung

Feedback

Worum geht es?

Wie gefällt dir das neue Design?

Dein Eindruck