CMSC132 Final Exam Practice Questions Problem 1 Software Engineering Object Oriented Design A Software Development and Testing a Software is difficult because programmers are slow b Software life cycle refers to how software is used c Problem specification is a component of software development d Problem specification is less important than program testing e Iterative development is a software development methodology f Black box testing is usually easier than clear box testing g Integration tests are usually more important than unit tests h Test coverage includes consideration of lines of code tested i Test drivers are only found on NASCAR training tracks B Object oriented design a State behavior and identity are the main qualities of objects b Object oriented design produces faster programs c List two main principles of object oriented design d Inheritance describes a relationship between classes e Inheritance discourages code reuse f Extension is a form of inheritance T or F T or F T or F T or F T or F T or F T or F T or F T or F T or F T or F T or F T or F T or F C Object oriented design II Given the following problem description produce an objectoriented solution Answer the following questions about your object oriented solution Design a simulation of a basketball conference Each conference has 10 teams Each team has 12 players Each player has a specific height speed and accuracy Players know which team they belong to Some players are scholarship players Scholarship players need to record their current grade point average Players may be transferred between teams Teams play basketball games against other teams in the conference The result of each game is determined using a function based on the height strength speed and accuracy of the players on each team a b c d e f What are the objects in your object oriented solution What are the interactions between your objects Which objects have other objects Also list target object Which objects use other objects Also list target object Which objects are other objects Also list target object Draw a UML diagram of your solution Problem 2 Algorithmic Complexity D Algorithmic complexity 1 a b c d e What is algorithmic complexity List a reason benchmarking is better than analyzing complexity What is the difference between best case worst case and average case What does the Big O notation represent Why are O n2 and O n not considered equivalent E Finding critical regions Calculate 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 for j 1 j n j f n O b for i 0 i n 2 i 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 f n O Problem 3 Data Structures and Recursion F Taxonomy properties a Describe the main difference between linear and hierarchical data structures b 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 F e 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 algorithm 2 Problem 4 Graph Algorithms G Properties a Describe the main difference between hierarchical and graph data structures b Describe the difference between a directed and undirected graph c Describe the difference between a path and a cycle d Describe two methods of storing edges in a graph Which requires more space H Traversals a Why is graph traversal more difficult than a tree traversal b Describe the difference between a breadth first and depth first traversal of a graph c Given the following Java class definition for a graph public 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 I Minimum spanning trees a What is a spanning tree b Describe Kruskal s algorithm for finding minimum spanning trees c Describe Prim s algorithm for finding minimum spanning trees d Describe two methods for finding connected subgraphs e Consider the following graph Using both Prim s and sKruskal s algorithm calculate the minimum spanning tree listing edges in the minimal spanning tree in the order they are added to the tree 16 S 10 A 12 14 8 B C 9 13 5 E D 3 4 6 7 15 3 F G H 11 J Single source shortest path a Describe Djikstra s algorithm for finding shortest paths in a graph b 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 BestKnownDistances S A B C D E F G H LowestCost Predecessor c 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 Problem 5 Compression Huffman Codes K Compression a What are two sources of compressibility b What are two types of compression c What is a prefix code d What are Huffman codes e How do Huffman codes achieve compression f Given the following Huffman tree decode the sequence 00110010 T S 1 0 1 R 0 1 4 A 0 g Using the same Huffman tree encode the string arts as a sequence of 0 s and 1 s h Given the following symbol frequencies create a Huffman tree for the symbols A 5 B 8 C 4 D 6 E 7 Problem 6 Java Language Features L Java Inner Classes a 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 M Java support for Object Oriented programming a The equals method in Java is typically used to test for name equivalence b All non static initialization blocks are executed when objects are
View Full Document
Unlocking...