Data Structures and Algorithm Analysis Exam Questions with Answers

Data Structures and Algorithm Analysis Exam Questions with Answers Abstract Data Type - Correct Answers: realization of a data type as a software component Acyclic graph - Correct Answers: A graph that doesnt have a cycle Adjacency List - Correct Answers: An implementation for a graph that uses an (array-based) list to represent the vertices of the graph, and each vertex is in turn represented by a (linked) list of the vertices that are neighbors. Adjacency Matrix - Correct Answers: An implementation for a graph that uses a 2-dimensional array where each row and each column corresponds to a vertex in the graph. A given row and column in the matrix corresponds to an edge from the vertex corresponding to the row to the vertex corresponding to the column. Asymptotic Analysis - Correct Answers: A method for estimating the efficiency of an algorithm or computer program by identifying its growth rate. Asymptotic analysis also gives a way to define the inherent difficulty of a problem. We frequently use the term algorithm analysis to mean the same thing. Average Case - Correct Answers: In algorithm analysis, the average of the costs for all problem instances of a given input size n. If not all problem instances have equal probability of occurring, then average case must be calculated using a weighted average. Balanced Tree - Correct Answers: A tree where the subtrees meet some criteria for being balanced. Two possibilities are that the tree is height balanced, or that the tree has a roughly equal number of nodes in each subtree. Best Case - Correct Answers: In algorithm analysis, the problem instance from among all problem instances for a given input size n that has least cost. Note that the best case is not when n is small, since we are referring to the best from a class of inputs (i.e, those inputs of size n). Big-O Notation - Correct Answers: In algorithm analysis, a shorthand notation for describing the upper bound for an algorithm or problem. BST - Correct Answers: A binary tree that imposes the following constraint on its node values: The search key value for any node A must be greater than the (key) values for all nodes in the left subtree of A, and less than the key values for all nodes in the right subtree of A. Some convention must be adopted if multiple nodes with the same key value are permitted, typically these are required to be in the right subtree. Binning - Correct Answers: In hashing, binning is a type of hash function. Say we are given keys in the range 0 to 999, and have a hash table of size 10. In this case, a possible hash function might simply divide the key value by 100. Thus, all keys in the range 0 to 99 would hash to slot 0, keys 100 to 199 would hash to slot 1, and so on. In other words, this hash function "bins" the first 100 keys to the first slot, the next 100 keys to the second slot, and so on. This approach tends to make the hash function dependent on the distribution of the high-order bits of the keys. Breadth First Search - Correct Answers: A graph traversal algorithm. As the name implies, all immediate neighbors for a node are visited before any more-distant nodes are visited. BFS is driven by a queue. A start vertex is placed on the queue. Then, until the queue is empty, a node is taken off the queue, visited, and and then any unvisited neighbors are placed onto the queue. Bubble SOrt - Correct Answers: A simple sort that requires Theta(n2) time in best, average, and worst cases. Even an optimized version will normally run slower than insertion sort, so it has little to recommend it. Complete Binary Tree - Correct Answers: A binary tree where the nodes are filled in row by row, with the bottom row filled in left to right. Due to this requirement, there is only one tree of n nodes for any value of n. Since storing the records in an array in row order leads to a simple mapping from a node's position in the array to its parent, siblings, and children, the array representation is most commonly used to implement the complete binary tree. The heap data structure is a complete binary tree with partial ordering constraints on the node values.