CIS c++

[INSERT TITLE HERE] 2

Running head: [INSERT TITLE HERE]

[INSERT TITLE HERE]

Student Name

Allied American University

Author Note

This paper was prepared for [INSERT COURSE NAME], [INSERT COURSE ASSIGNMENT] taught by [INSERT INSTRUCTOR’S NAME].

PART I: Short Response

Directions: Answer each of the following questions. Please ensure that your responses are at least 3 to 5 sentences in length.

• What is meant by the last-in, first-out (LIFO) property?
• What is the difference between the stack pop and getTop operations?
• In a program that uses a stack to check for balanced braces in an string, what condition indicates that the braces are balanced when the end of the string is reached?
• When does the push operation throw a StackException?
• What restriction does the array-based implementation of a stack place on the push operation?
• What is a linear implementation?
• What kind of implementation of the ADT table is appropriate for retrieval-dominated applications, if the maximum size of the table is known? Why?
• What kind of implementation of the ADT table is appropriate for retrieval-dominated applications if the maximum size of the table is NOT known?
• What are the advantages of a linear implementation of the ADT table over a binary search tree implementation?
• In an array-based implementation of the priority queue, where is the item with the highest priority value located?
• What are some of the benefits of modularity?
• What is functional abstraction?
• What is information hiding?
• What are the three types of operations on a data collection?
• What is data abstraction?
• What measurements indicate a program’s efficiency?
• The analysis of algorithms—as an area of study—provides what tools for the computer scientist?
• List three reasons why you should not write and run C++ programs to compare the time efficiency of algorithms.
• What does an algorithm’s growth rate measure?
• What is a growth-rate function?
• What is measured by a worst-case analysis?
• What is measured by an average-case analysis?
• When choosing between two algorithms, under what conditions can the efficiencies of the algorithms be ignored?
• What is an internal sort?
• What is an external sort?
• What is the sort key of a record?
• In the worst case, how many comparisons does a bubble sort require?
• What is the drawback of the mergesort with respect to storage?
• How does the quicksort partition an array?
• Compare the efficiencies of the quicksort and the mergesort in the worst case.
• What are the three general categories of data management operations?
• List three position-oriented ADTs.
• Define the root of a tree.
• Define a leaf of a tree.
• What is a subtree?
• What are the characteristics of a binary tree?
• Define the left child of node n in a binary tree.
• What are the three properties of each node n in a binary search tree?
• In what order does a preorder traversal visit a node and its subtrees?
• In what order does an inorder traversal visit a node and its subtrees?
• In what order does a postorder traversal visit a node and its subtrees?
• In an array-based representation of a binary tree, what is the purpose of a free list?
• What is a search key?
• Define an n-ary tree.
• Describe the STL functions lower_bound and upper_bound.
• Define a path between two vertices.
• What is a simple path?
• What is a cycle?
• What is a simple cycle?
• What is a complete graph?
• What is a self edge?
• What is a weighted graph?
• What are two differences between a directed graph and an undirected graph?
• What are the two most common implementations of a graph?
• How does the depth-first search (DFS) strategy of graph traversal differ from the breadth-first search (BFS) strategy?
• What is a spanning tree?
• What is a minimum spanning tree?
• How is the cost of a spanning tree calculated?
• What is the shortest path between two vertices in a weighted graph?
• What is a planar graph?
• What are two advantages of external storage when compared with internal memory?
• In a sequential access file, how can data stored at a given position be accessed?
• In a random access file, how can data stored at a given position be accessed?
• What is a buffer?
• When you consider the efficiency of an algorithm, why should you not pay much attention to the time required to operate on a block of data once it has been read into internal memory?
• What is the main advantage of an external table implementation in which records are stored in search-key order?
• What is the main disadvantage of an external table implementation in which records are stored in search-key order?
• What is an index to a data file?
• What is a key in an index file?
• What is a pointer in an index file?
• What are the three main advantages to maintaining an index to a data file?
• What is meant by multiple indexing?
• How do insertion and deletion operations for a sorted data file differ from those for an unsorted data file that has a sorted index?
• What are the external table operations for which the hashing of an index file is an appropriate implementation?
• What is the relationship between the number of records and the number of children that an internal node in a B-tree has?