DOC PREVIEW
UMD CMSC 132 - Final Exam Practice Questions

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Table BestKnownDistancesCMSC132 Final Exam Practice QuestionsProblem 1 Software Engineering & Object Oriented Design A. Software Development and Testinga. Software is difficult because programmers are slow T or Fb. Software life cycle refers to how software is used T or Fc. Problem specification is a component of software development T or Fd. Problem specification is less important than program testing T or Fe. Iterative development is a software development methodology T or Ff. Black box testing is usually easier than clear box testing T or Fg. Integration tests are usually more important than unit tests T or Fh. Test coverage includes consideration of lines of code tested T or Fi. Test drivers are only found on NASCAR training tracks T or FB. Object-oriented design a. State, behavior, and identity are the main qualities of objects T or Fb. Object oriented design produces faster programs T or Fc. List two main principles of object-oriented design?d. Inheritance describes a relationship between classes T or Fe. Inheritance discourages code reuse T or Ff. Extension is a form of inheritance T or FC. Object-oriented design II. Given the following problem description, produce an object-oriented solution. Answer the following questions about your object-oriented solution. Design a simulation of a basketball conference. Each conference has 10 teams. Each teamhas 12 players. Each player has a specific height, speed, and accuracy. Players know whichteam they belong to. Some players are scholarship players. Scholarship players need torecord their current grade-point average. Players may be transferred between teams. Teamsplay basketball games against other teams in the conference. The result of each game isdetermined using a function based on the height, strength, speed, and accuracy of theplayers on each team.a. What are the objects in your object-oriented solution?b. What are the interactions between your objects?c. Which objects “have” other objects? (Also list target object)d. Which objects “use” other objects? (Also list target object)e. Which objects “are” other objects? (Also list target object)f. Draw a UML diagram of your solution.1Problem 2 Algorithmic ComplexityD. Algorithmic complexitya. What is algorithmic complexity?b. List a reason benchmarking is better than analyzing complexity c. What is the difference between best case, worst case, and average case?d. What does the Big-O notation represent?e. Why are O(n2) and O(n) not considered equivalent?E. Finding critical regionsCalculate the asymptotic complexity of the code snippets below (using big-O notation) with respect to the problem size n: a. for (i = 0; i < n; i=i*2) { f(n) = O( ) for (j = 1; j < n; j++) { ... }}b. for (i = 0; i < n-2; i++) { f(n) = O( ) for (j = 0; j < n; j=j*2) { for (k = 1; k < 5000; k=k*5) { ... } } for (j = 0; j < 1000*n; j=j+1) { ... } for (j = 0; j < n/5; j=j+5) { ... }}2Problem 3 Data Structures and RecursionF. Taxonomy & propertiesa. Describe the main difference between linear and hierarchical data structuresb. What is the key property of a binary search tree?c. On average, what is the complexity of doing an insertion in a binary search tree?d. Pre-order, in-order, and post-order are all depth-first traversals T or Fe. What operation(s) supported by binary search trees are not supported by heaps?f. What is the difference between a set and a map?g. What happens when an open addressing hash table is close to full?h. Describe the 2 main parts of a recursive algorithmProblem 4 Graph AlgorithmsG. Propertiesa. Describe the main difference between hierarchical and graph data structuresb. Describe the difference between a directed and undirected graphc. Describe the difference between a path and a cycled. Describe two methods of storing edges in a graph. Which requires more space?H. Traversalsa. Why is graph traversal more difficult than a tree traversal?b. Describe the difference between a breadth-first and depth-first traversal of a graphc. Given the following Java class definition for a graphpublic class MyGraph<E> {public class Node<E> {E myValue;boolean tag;ArrayList<Node> myNeighbors;}ArrayList<Node> myNodes;void visitNode(Node n) {/* Action to be performed when traversing node */}void deptFirstSearch(Node n) { /* Perform depth-first search of graph starting at n */ }}i. Write code for the method depthFirstSearch( n ) that performs a depth first traversal starting at node n.ii. Write code for the method breadthFirstSearch(n) that performs a breadth first traversal starting at node n.3I. Single source shortest patha. Describe Djikstra’s algorithm for finding shortest paths in a graphb. Consider the previous graph. Apply Djikstra’s algorithm for this graph to calculate the shortest path from S to every other node. Store intermediate results in the table BestKnownDistances. Show the entries in the table after you finish computing the shortest distance from S to nodes in the set {S, A, B}. Table BestKnownDistancesS A B C D E F G HLowestCostPredecessorc. Which node would be processed next using Dijkstra’s algorithm?d. Update the table BestKnownDistances after adding this node.e. Using Dijkstra’s algorithm, calculate the shortest path (and its cost) from S to every other vertex in the graph. List vertices in the order they are added to the table BestKnownDistances.4A EB FHDC GS101412816 13 5741596 311Problem 5 Java Language FeaturesJ. Java Inner Classesa. What are inner classes?b. What are nested classes?c. When should inner classes be used?d. When should anonymous inner classes be used?e. Write an example anonymous inner class in Java.K. Java support for Object-Oriented programminga. The equals( ) method in Java is typically used to test for name equivalence T or Fb. All non-static initialization blocks are executed when objects are created T or Fc. Code in initialization blocks are executed at the end of every constructor T or Fd. If no visibility modifier is specified, methods are private by default T or Fe. Protected access is less visible than package access T or FL. Exceptions in Javaa. What are exceptions?b. How are exceptions used in Java?c. What should be made an exception in Java?d. What are the differences between try, catch, and finally in Java?e. What is the difference between checked and unchecked exceptions?f. Given the following codepublic


View Full Document

UMD CMSC 132 - Final Exam Practice Questions

Documents in this Course
Notes

Notes

8 pages

Recursion

Recursion

12 pages

Sorting

Sorting

31 pages

HTML

HTML

7 pages

Trees

Trees

19 pages

HTML

HTML

18 pages

Trees

Trees

19 pages

Honors

Honors

19 pages

Lecture 1

Lecture 1

11 pages

Quiz #3

Quiz #3

2 pages

Hashing

Hashing

21 pages

Load more
Download Final Exam Practice Questions
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Final Exam Practice Questions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Final Exam Practice Questions 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?