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

1. What is meant by the last-in, first-out (LIFO) property?

2. What is the difference between the stack pop and getTop operations?

3. 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?

4. When does the push operation throw a StackException?

5. What restriction does the array-based implementation of a stack place on the push operation?

6. What is a linear implementation?

7. What kind of implementation of the ADT table is appropriate for retrieval-dominated applications, if the maximum size of the table is known? Why?

8. What kind of implementation of the ADT table is appropriate for retrieval-dominated applications if the maximum size of the table is NOT known?

9. What are the advantages of a linear implementation of the ADT table over a binary search tree implementation?

10. In an array-based implementation of the priority queue, where is the item with the highest priority value located?

11. What are some of the benefits of modularity?

12. What is functional abstraction?

13. What is information hiding?

14. What are the three types of operations on a data collection?

15. What is data abstraction?

16. What measurements indicate a program’s efficiency?

17. The analysis of algorithms—as an area of study—provides what tools for the computer scientist?

18. List three reasons why you should not write and run C++ programs to compare the time efficiency of algorithms.

19. What does an algorithm’s growth rate measure?

20. What is a growth-rate function?

21. What is measured by a worst-case analysis?

22. What is measured by an average-case analysis?

23. When choosing between two algorithms, under what conditions can the efficiencies of the algorithms be ignored?

24. What is an internal sort?

25. What is an external sort?

26. What is the sort key of a record?

27. In the worst case, how many comparisons does a bubble sort require?

28. What is the drawback of the mergesort with respect to storage?

29. How does the quicksort partition an array?

30. Compare the efficiencies of the quicksort and the mergesort in the worst case.

31. What are the three general categories of data management operations?

32. List three position-oriented ADTs.

33. Define the root of a tree.

34. Define a leaf of a tree.

35. What is a subtree?

36. What are the characteristics of a binary tree?

37. Define the left child of node *n* in a binary tree.

38. What are the three properties of each node *n* in a binary search tree?

39. In what order does a preorder traversal visit a node and its subtrees?

40. In what order does an inorder traversal visit a node and its subtrees?

41. In what order does a postorder traversal visit a node and its subtrees?

42. In an array-based representation of a binary tree, what is the purpose of a free list?

43. What is a search key?

44. Define an *n*-ary tree.

45. Describe the STL functions lower_bound and upper_bound.

46. Define a path between two vertices.

47. What is a simple path?

48. What is a cycle?

49. What is a simple cycle?

50. What is a complete graph?

51. What is a self edge?

52. What is a weighted graph?

53. What are two differences between a directed graph and an undirected graph?

54. What are the two most common implementations of a graph?

55. How does the depth-first search (DFS) strategy of graph traversal differ from the breadth-first search (BFS) strategy?

56. What is a spanning tree?

57. What is a minimum spanning tree?

58. How is the cost of a spanning tree calculated?

59. What is the shortest path between two vertices in a weighted graph?

60. What is a planar graph?

61. What are two advantages of external storage when compared with internal memory?

62. In a sequential access file, how can data stored at a given position be accessed?

63. In a random access file, how can data stored at a given position be accessed?

64. What is a buffer?

65. 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?

66. What is the main advantage of an external table implementation in which records are stored in search-key order?

67. What is the main disadvantage of an external table implementation in which records are stored in search-key order?

68. What is an index to a data file?

69. What is a key in an index file?

70. What is a pointer in an index file?

71. What are the three main advantages to maintaining an index to a data file?

72. What is meant by multiple indexing?

73. How do insertion and deletion operations for a sorted data file differ from those for an unsorted data file that has a sorted index?

74. What are the external table operations for which the hashing of an index file is an appropriate implementation?

75. What is the relationship between the number of records and the number of children that an internal node in a B-tree has?