CMSC132 Final Exam review(All solved)
What is the main reason software projects fail? correct answers Complexity of projects
What is the program life-cycle? correct answers Problem Specification, Program Design, Algorithms and Data Structures, Coding and Debugging, Testing and Verification, Deployment, Documentation and Support, Maintenance and Upgrades
True/False: Compared to program verification, empirical testing... correct answers a) Handles larger programs (True)
b) Always catches more errors (False)
c) Ensures code is correct (False)
d) Can be applied without examining code (False, but maybe True?)
True/False: According to the unified model... correct answers a) Design all algorithms before coding (False)
b) Write test cases before coding (False)
c) Use a prototype implementation to refine design (True)
True/False: According to the Waterfall model... correct answers a) Design all algorithms before coding (True)
b) Write test cases before coding (False)
c) Use prototype implementation to refine design (False)
What is the key property of a binary search tree? correct answers Has 0-2 children per node
On average, what is the (algorithmic) complexity of doing an insertion in a binary tree? correct answers O(log(n))
On average, what is the (algorithmic) complexity of doing a find in a binary tree? correct answers O(log(n))
What is the worst case complexity of doing a find in a Binary Search Tree? correct answers O(h), where h is the height of the tree
What can cause worst-case behavior in a binary tree? correct answers Degenerative trees. Meaning that, the data being entered into the tree is already in order, leading to a sorted Linked List. Inserting 10,20,30,40,50,... will lead to a single "column" ? tree that leads to a very large
tree height
What is a tree traversal correct answers The process of finding all the nodes in a Tree, and determining ther relationship
What is the difference between a depth-first and breadth-first traversal? correct answers
Breadth-first visit closer nodes first. Depth-first has three modes:
Preorder - parent > left child > right child
Inorder - left child > parent > right child
Postorder - left child > right child > parent
Pre-order traversals are faster than post-order traversals, T or F correct answers F
Preorder, Inorder and Postorder are all O(n)
What are the two key properties of a heap ? correct answers Complete (Balanced) Binary Tree, Value at Node
What operation(s) supported by binary search trees are not supported by heaps? correct answers Find any value. For BSTs it's either O(log(n)) for balanced trees or O(n)
for degenerate trees.
Heaps can only readily provide Min or Max values
On average, what is the complexity of doing an insertion in a heap ? correct answers O(log(n))
On average, what is the complexity of doing a find in a heap? correct answers O(log(n))
What is algorithmic complexity? correct answers Amount of resources required by algorithm with respect to problem size
List a reason benchmarking is better that analyzing complexity correct answers Precise information for given configuration
Implementation, hardware, inputs details
What is the difference between best case, worst case, and average case ? correct answers Best case: Smallest number of steps required
Worst case: Largest number of steps required
Average case: typical number of steps required
What does big O notation represent? correct answers Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.
Describe the difference between a directed and undirected graph correct answers An Undirected graph is a graph in which the veritcies are connected bidirectionally. A Directed graph is a graph in which the vertices are connected unidirectionally
Describe the difference between a path and a cycle correct answers A cycle is a closed path, starts and ends at the same vertex.
A path starts and ends at different vertices
What is the main reason software projects fail? correct answers Complexity of projects
What is the program life-cycle? correct answers Problem Specification, Program Design, Algorithms and Data Structures, Coding and Debugging, Testing and Verification, Deployment, Documentation and Support, Maintenance and Upgrades
True/False: Compared to program verification, empirical testing... correct answers a) Handles larger programs (True)
b) Always catches more errors (False)
c) Ensures code is correct (False)
d) Can be applied without examining code (False, but maybe True?)
True/False: According to the unified model... correct answers a) Design all algorithms before coding (False)
b) Write test cases before coding (False)
c) Use a prototype implementation to refine design (True)
True/False: According to the Waterfall model... correct answers a) Design all algorithms before coding (True)
b) Write test cases before coding (False)
c) Use prototype implementation to refine design (False)
What is the key property of a binary search tree? correct answers Has 0-2 children per node
On average, what is the (algorithmic) complexity of doing an insertion in a binary tree? correct answers O(log(n))
On average, what is the (algorithmic) complexity of doing a find in a binary tree? correct answers O(log(n))
What is the worst case complexity of doing a find in a Binary Search Tree? correct answers O(h), where h is the height of the tree
What can cause worst-case behavior in a binary tree? correct answers Degenerative trees. Meaning that, the data being entered into the tree is already in order, leading to a sorted Linked List. Inserting 10,20,30,40,50,... will lead to a single "column" ? tree that leads to a very large
tree height
What is a tree traversal correct answers The process of finding all the nodes in a Tree, and determining ther relationship
What is the difference between a depth-first and breadth-first traversal? correct answers
Breadth-first visit closer nodes first. Depth-first has three modes:
Preorder - parent > left child > right child
Inorder - left child > parent > right child
Postorder - left child > right child > parent
Pre-order traversals are faster than post-order traversals, T or F correct answers F
Preorder, Inorder and Postorder are all O(n)
What are the two key properties of a heap ? correct answers Complete (Balanced) Binary Tree, Value at Node
What operation(s) supported by binary search trees are not supported by heaps? correct answers Find any value. For BSTs it's either O(log(n)) for balanced trees or O(n)
for degenerate trees.
Heaps can only readily provide Min or Max values
On average, what is the complexity of doing an insertion in a heap ? correct answers O(log(n))
On average, what is the complexity of doing a find in a heap? correct answers O(log(n))
What is algorithmic complexity? correct answers Amount of resources required by algorithm with respect to problem size
List a reason benchmarking is better that analyzing complexity correct answers Precise information for given configuration
Implementation, hardware, inputs details
What is the difference between best case, worst case, and average case ? correct answers Best case: Smallest number of steps required
Worst case: Largest number of steps required
Average case: typical number of steps required
What does big O notation represent? correct answers Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.
Describe the difference between a directed and undirected graph correct answers An Undirected graph is a graph in which the veritcies are connected bidirectionally. A Directed graph is a graph in which the vertices are connected unidirectionally
Describe the difference between a path and a cycle correct answers A cycle is a closed path, starts and ends at the same vertex.
A path starts and ends at different vertices
