Data Structures Final Review

81 Questions

Settings
Please wait...
Data Structure Quizzes & Trivia

Questions and Answers
  • 1. 
    Stack is an Abstract Class
    • A. 

      True

    • B. 

      False

  • 2. 
    Stack is an Abstract Data Type
    • A. 

      True

    • B. 

      False

  • 3. 
    Pez Dispenser Anaolgy
    • A. 

      Queue

    • B. 

      Stack

    • C. 

      Array

  • 4. 
    LIFO structire stands for...
    • A. 

      Last In Furthest Out

    • B. 

      Least In First Out

    • C. 

      Last In First Out

  • 5. 
    A queue is and ADT in which elemets are added and removed from one end only; first-in-first-out (FIFO) structure.
    • A. 

      True

    • B. 

      False

  • 6. 
    The running time of RETREIVE call on a linked list is O(1) = constant
    • A. 

      True

    • B. 

      False

  • 7. 
    Insert, Append, Delete, and Next are all valid list operations.
    • A. 

      True

    • B. 

      False

  • 8. 
    An enque is the opposite of a deque
    • A. 

      True

    • B. 

      False

  • 9. 
    A node at level X is also said to be a depth of X
    • A. 

      True

    • B. 

      False

  • 10. 
    Postfix notation may not contain negative numbers
    • A. 

      True

    • B. 

      False

  • 11. 
    An ordered tree in which each vertex has 0, 1, or 2 children
  • 12. 
    The name of the second child of a vertex on a binary tree
  • 13. 
    A node connected via edges to a higher node
  • 14. 
    The unique vertex in a rooted tree
  • 15. 
    A node connected via edges to a lower node
  • 16. 
    If "X" is a descendent of "Y", then "Y" is a __________ of "X".
  • 17. 
    A child (grandchild, great-grand-child, etc...) of a specific vertext.
  • 18. 
    The length of the path from the root to the vertext of interst
  • 19. 
    Any non-leaf vertext
  • 20. 
    All the descendents of a vertex
  • 21. 
    • A. 

      A

    • B. 

      B

    • C. 

      Neither

  • 22. 
    The length of the longest path from a vertex to a leaf that is a descendent of the vertex
    • A. 

      Height

    • B. 

      Depth

  • 23. 
    All parents have the same depth, but not necessarily the same height
    • A. 

      True - parents

    • B. 

      False - siblings

  • 24. 
    Property of all trees
    • A. 

      #Edges = #Nodes - 1

    • B. 

      #Nodes = #Edges - 1

  • 25. 
    An ordered tree in which each vertex has either no children, one child, or two children
    • A. 

      Sub Tree

    • B. 

      Ordered Tree

    • C. 

      Binary Tree

  • 26. 
    Every vertex has two children or is a leaf
    • A. 

      Perfect Binary Tree

    • B. 

      Full Binary Tree

  • 27. 
    A Full Binary Tree in which all leaves have the same depth
    • A. 

      Perfect Binary Tree

    • B. 

      Full Binary Tree

  • 28. 
    What is the In Order Traversal:
  • 29. 
    Prior to inserting intoa B.S.T., you must sort the tree
    • A. 

      True

    • B. 

      False

  • 30. 
    The "best case" search time for a B.S.T. is O(n). (where n = the number of nodes in the tree)
    • A. 

      True

    • B. 

      False

  • 31. 
    A Red-Black tree is an BST tree
    • A. 

      True

    • B. 

      False

  • 32. 
    A BST tree is always balanced
    • A. 

      True

    • B. 

      False

  • 33. 
    All AVL trees are BST
    • A. 

      True

    • B. 

      False

  • 34. 
    For a normal (double-linked) binary tree, 8 pointers are assigned to each node.
    • A. 

      True

    • B. 

      False

  • 35. 
    Inserting a node in an AVL tree will sometimes change the height of the tree
    • A. 

      True

    • B. 

      False

  • 36. 
    A splay tree is also an AVL
    • A. 

      True

    • B. 

      False

  • 37. 
    A red-black tree is also a B.S.T.
    • A. 

      True

    • B. 

      False

  • 38. 
    Red-Black trees are tree that have been restrctured with a heuristic similar to a self-organizing list
    • A. 

      True

    • B. 

      False

  • 39. 
    A hash table tends to perform better overall (bot time and space) than an array, linked list, or balanced B.S.T.
    • A. 

      True

    • B. 

      False

  • 40. 
    Linear probing is not a good solution for clustering
    • A. 

      True

    • B. 

      False

  • 41. 
    Double hashing requires more "computational overhead" than linear probing.
    • A. 

      True

    • B. 

      False

  • 42. 
    Rehashing guarentees a reduction in clustering
    • A. 

      True

    • B. 

      False

  • 43. 
    Linear probing uses the numer of times the rehash function has been applied as a value in the hash formula
    • A. 

      True

    • B. 

      False

  • 44. 
    What is a disadvantage of using buckets for collision resolution? Choose all that apply
    • A. 

      The search is long

    • B. 

      It takes longer to walk down

    • C. 

      Wasted space

    • D. 

      Not knowing how big the bucket is

    • E. 

      The return time

  • 45. 
    Choose two ways to resolve problems following a deletion in a list using linear probing. Choose all that apply
    • A. 

      Use recursion

    • B. 

      Using chain down the list

    • C. 

      Shift Everything

    • D. 

      Insert null in deleted vairable

  • 46. 
    All ordered trees are binary trees
    • A. 

      True

    • B. 

      False

  • 47. 
    Reading a book (cover to cover) is an example of Pre Order Traversal
    • A. 

      True

    • B. 

      False

  • 48. 
    A post oder traversal may be used to evaluate an arithmetic expression
    • A. 

      True

    • B. 

      False

  • 49. 
    General trees will always have fewer nodes than its binary tree representation
    • A. 

      True

    • B. 

      False

  • 50. 
    Which are Binary Trees?
    • A. 

      A

    • B. 

      B

    • C. 

      C

    • D. 

      D

    • E. 

      E

  • 51. 
    Which are Full Binary Trees?
    • A. 

      A

    • B. 

      B

    • C. 

      C

    • D. 

      D

    • E. 

      E

  • 52. 
    Which are Perfect Binary Trees?
    • A. 

      A

    • B. 

      B

    • C. 

      C

    • D. 

      D

    • E. 

      E

  • 53. 
    Which are Binary Search Trees?
    • A. 

      A

    • B. 

      B

    • C. 

      C

    • D. 

      D

    • E. 

      E

  • 54. 
    Reading a book (cover to cover) is an example of Post Order Traversal
    • A. 

      True

    • B. 

      False

  • 55. 
    A In Order traversal may be used to print an arithmetic expression
    • A. 

      True

    • B. 

      False

  • 56. 
    For a normal (double linked) binary tree, __ pointers are assigned to each node
  • 57. 
    The DIR command in DOS (which returns fil/folder sizes) untilizes a ___ order traversal of the directory tree structure
  • 58. 
    The maximum height of a 14-node B.S.T. is 13
    • A. 

      True

    • B. 

      False

  • 59. 
    The minimum height of a 14-node B.S.T. is 5
    • A. 

      True

    • B. 

      False

  • 60. 
    The process of creating a B.S.T. (requires/does not require) sorting data.
    • A. 

      Requires

    • B. 

      Does Not Require

  • 61. 
    In Stack Methods: ____ removes the top object of the stack and returns it.
    • A. 

      PUSH(X)

    • B. 

      POP()

    • C. 

      SIZE()

    • D. 

      IsStackEmpty()

    • E. 

      TOP()

  • 62. 
    In Stack Methods: ____ Inserts object X onto the stack.
    • A. 

      PUSH(X)

    • B. 

      POP()

    • C. 

      SIZE()

    • D. 

      IsStackEmpty()

    • E. 

      TOP()

  • 63. 
    In Stack Methods: ____ Returns a boolean inidcating if the stack is empty.
    • A. 

      PUSH(X)

    • B. 

      POP()

    • C. 

      SIZE()

    • D. 

      IsStackEmpty()

    • E. 

      TOP()

  • 64. 
    In Stack Methods: ____ rreturns the # of objects in the stack.
    • A. 

      PUSH(X)

    • B. 

      POP()

    • C. 

      SIZE()

    • D. 

      IsStackEmpty()

    • E. 

      TOP()

  • 65. 
    In Stack Methods: ____ returns the top object of the stack without removing it.
    • A. 

      PUSH(X)

    • B. 

      POP()

    • C. 

      SIZE()

    • D. 

      IsStackEmpty()

    • E. 

      TOP()

  • 66. 
    Which are the Stack Methods
    • A. 

      Enqueue(X), Dequeue(), Size(), isQueueEmpty(), Front()

    • B. 

      POP(), PUSH(X), SIZE(), isStackEmpty(), TOP()

    • C. 

      Size(), Front(), Push(X), Pop()

  • 67. 
    ______ is a data structure in which elements are added to the rear and removed from the front. A First-In-First-Out (FIFO) structure
  • 68. 
    To remove an elemnt from the end (queue)
    • A. 

      Enqueue

    • B. 

      Dequeue

  • 69. 
    To insert an element at the rear (queue)
    • A. 

      Enqueue

    • B. 

      Dequeue

  • 70. 
    Which are the Queue Methods
    • A. 

      Enqueue(X), Dequeue(), Size(), isQueueEmpty(), Front()

    • B. 

      POP(), PUSH(X), SIZE(), isStackEmpty(), TOP()

    • C. 

      Size(), Front(), Push(X), Pop()

  • 71. 
    ____ is the technique used for inserting and accessing elements in a list in a relative constant time by manipulating the key to identify its location in the list
  • 72. 
    A _____ function used to manipulate the key of an element in a list to identify its location in the list
  • 73. 
    ___ is the condition resulting when two or more keys produce the same hash location
  • 74. 
    _____ is resolving a collison by computing a new hash location from a hash function that manipulates the original location rather than the elements key
  • 75. 
    Resolving a hash collision by sequentially searching a hash table beginning at the location returned by the hash function
    • A. 

      Clustering

    • B. 

      Bucket

    • C. 

      Linear Probing

    • D. 

      Chain

  • 76. 
    The tendency of elements to become unevenly distributed in the hash table
    • A. 

      Clustering

    • B. 

      Bucket

    • C. 

      Linear Probing

    • D. 

      Chain

  • 77. 
    A linked list of elements that share the same hash location
    • A. 

      Clustering

    • B. 

      Bucket

    • C. 

      Linear Probing

    • D. 

      Chain

  • 78. 
    A collection of elements associated with a particular hash location
    • A. 

      Clustering

    • B. 

      Bucket

    • C. 

      Linear Probing

    • D. 

      Chain

  • 79. 
    ______ probing is resolving a hash collision by using the rehashing formula
  • 80. 
    _____ probing resolving a hash collision by generating pseudorandom hash values in successive applications of the rehash function
  • 81. 
    ______ hashing uses 2 hash funtions to calculate the probe value