|
|
|
|
|
|
|
3. Describe how the list insertion operation can be used to build a sorted list from unordered input data. (pp. 659-662) |
|
|
|
|
|
|
|
|
4. Describe the basic principle behind the binary search algorithm. (pp. 662-666) |
|
|
|
|
|
|
|
|
5. Using Typedef, define an array data type that holds a string of 15 characters plus the null character. Declare an array variable of this type, initializing it to your first name. Then use a library function to replace the contents of the variable with your last name. (pp. 668-679) |
|
|
|
|
|
|
|
|
Answers 1. The average number is 500 iterations. The maximum is 1000 iterations. 2. The only required change is to replace the ''<" symbol in the inner loop with a ">". As a matter of style, minIndex should be changed to maxIndex. 3. The list initially has a length of 0. Each time a data value is read, insertion adds the value to the list in its correct position. When all the data have been read, they are in the array in sorted order. 4. The binary search takes advantage of ordered list values, looking at a component in the middle of the list and deciding whether the search value precedes or follows the midpoint. The search is then repeated on the appropriate half, quarter, eighth, and so on, of the list until the value is located. |
|
|
|
|
|
|
|
|
5. typedef char String15[16];
String15 name = "Anna";
strcpy(name, "Rodriguez"); |
|
|
|
|
|
|
|
|
Exam Preparation Exercises |
|
|
|
|
|
|
|
|
1. What three factors should you consider when you are deciding which search algorithm to use on a list? |
|
|
|
|
|
|
|
|
2. The following values are stored in an array in ascending order. |
|
|
|
 |
|
|
|
|
28 45 97 103 107 162 196 202 257 |
|
|
|
|
|
|
|
|
Applying function Search2 to this array, search for the following values and indicate how many comparisons are required to either find the number or find that it is not in the list. |
|
|
|
|
|
|
|
|
3. Repeat Exercise 2 using the SearchOrd function. |
|
|
|
|
|
|
|
|
4. The following values are stored in an array in ascending order. |
|
|
|
|
|
|
|
|
29 57 63 72 79 83 96 104 114 136 |
|
|
|
|
|
|
|
|
Apply function BinSearch with item = 114 to this list, and trace the values of first, last, and middle. Indicate any undefined values with a U. |
|
|
|
|
|
|
|
|
5. A binary search is always better to use than a sequential search. (True or False?) |
|
|
|
|
|
|
|
|
6. a. Define a data type NameType to be a string of at most 40 characters plus the null character. |
|
|
|
|
|
|
|
|
b. Declare a variable oneName to be of type NameType. |
|
|
|
|
|
|
|
|
c. Declare employeeName to be a 100-element array variable whose elements are strings of type NameType. |
|
|
|
|
|
|
|
|
7. Given the declarations |
|
|
|
|
|