Chapter 12
APPLIED ARRAYS: LISTS AND STRINGS
QUESTIONS
True/False
1. A sequential search of a list assumes that the list is in sorted order.
2. A binary search of a list assumes that the list is in sorted order.
3. The function heading
void Insert( const ItemType list[], // List of items
int length, // Length of list
ItemType item ) // Item to be inserted
is appropriate for a function that inserts an item into an ordered list.
4. A sequential search on a sorted list cannot be made quicker than one on an unsorted list.
5. A binary search can be used only on arrays of integers.
6. A binary search always can be used in place of a sequential search.
7. The length of the list is not the only consideration when choosing between a sequential search and a binary search.
8. A binary search will work on an unsorted list, but it is much quicker on a sorted list.
9. In C++, a string is a simple (atomic) data type.
10. Unlike other C++ arrays, a string need not be output by the programmer one array element at a time.
11. Inside the computer, the null character is represented as the integer 0.
12. In C++, strings are the only kind of array for which there are aggregate constants.
13. In a C++ program,
't' denotes a single character, whereas "t" denotes two characters.14. When encountering the statement
char myString[] = "Adios";
the C++ compiler allocates an array of 5 elements.
15. The
>> operator cannot be used to input a string of characters into a string variable if the desired input string contains blanks.
Multiple Choice
16. Assuming that a particular general-purpose search function must let the caller know where the item was found, which of the following function parameters is not absolutely essential?
a. the array containing the list to be searched
b. the length of the list
c. the item to be searched for
d. a flag to indicate that the search was successful
e. an index giving the location of the item
17. In deciding which search algorithm to use on a list, which of the following should not be a factor in your decision?
a. the length of the list to be searched
b. whether or not the list contains negative numbers
c. whether or not the list is already in sorted order
d. the number of times the list is to be searched
18. What does the following function do?
void Mystery( const ItemType list[],
int listLength,
ItemType alpha,
Boolean& result )
{
int index = 0;
while (index < listLength && alpha != list[index])
index++;
result = (index < listLength);
}
b. It searches a list for the last occurrence of a given item.
c. It inserts a new item into an ordered list.
d. It inserts a new item into an unordered list.
e. It sorts a list into ascending order.
19. What does the following function do?
void Mystery( const ItemType list[],
int listLength,
ItemType alpha,
Boolean& result )
{
int index = listLength - 1;
while (index >= 0 && alpha != list[index])
index--;
result = (index >= 0);
}
b. It searches a list for the last occurrence of a given item.
c. It inserts a new item into an ordered list.
d. It inserts a new item into an unordered list.
e. It sorts a list into ascending order.
20. What does the following function do?
void Mystery( ItemType list[],
int& listLength,
ItemType alpha )
{
list[listLength] = alpha;
listLength++;
}
b. It searches a list for the last occurrence of a given item.
c. It inserts a new item into an ordered list.
d. It inserts a new item into an unordered list.
e. It sorts a list into ascending order.
21. What does the following function do?
void Mystery( ItemType list[],
int listLength )
{
ItemType beta;
int count1;
int count2;
int i;
for (count1 = 0; count1 < listLength - 1; count1++)
{
i = count1;
for (count2 = count1 + 1; count2 < listLength; count2++)
if (list[count2] > list[i])
i = count2;
beta = list[i];
list[i] = list[count1];
list[count1] = beta;
}
}
b. It inserts a new item into an unordered list.
c. It sorts a list into ascending order.
d. It sorts a list into descending order.
e. It exchanges each list item with its immediate neighbor.
22. A list currently contains
listLength integer items, where listLength < MAX_LENGTH. Which of the following code segments correctly inserts the value 100 into the list at position insertPos?a.
for (i = listLength - 1; i >= insertPos; i--)list[i+1] = list[i];
list[insertPos] = 100;
b.
for (i = insertPos; i < listLength; i++)
list[i+1] = list[i];
list[insertPos] = 100;
c.
for (i = listLength; i > insertPos; i--)list[i] = list[i-1];
list[insertPos] = 100;
d. a and b above
e.
a and c above23. Given the declaration
int list[7] = {10, 15, 20, 25, 30, 35, 40};
a binary search is used to search the list for the value 35. In each iteration of the search loop, the index variables
first, middle, and last define the range of items being searched. When the search is finished, what is the value of first? (Remember that C++ arrays begin at index 0.)a. 0
b. 2
c. 3
d. 4
e. 5
24. Given the declaration
int list[7] = {10, 15, 20, 25, 30, 35, 40};
a binary search is used to search the list for the value 20. In each iteration of the search loop, the index variables
first, middle, and last define the range of items being searched. When the search is finished, what is the value of first? (Remember that C++ arrays begin at index 0.)a. 0
b. 2
c. 3
d. 4
e. 5
25. Given the declaration
int list[7] = {10, 15, 20, 25, 30, 35, 40};
a binary search is used to search the list for the value 33. In each iteration of the search loop, the index variables
first, middle, and last define the range of items being searched. When the search is finished, what is thevalue of
first? (Remember that C++ arrays begin at index 0.)a. 0
b. 2
c. 3
d. 4
e. 5
26. Which of the following cannot be used to store the string "Mary" into
nameStr?a. char nameStr[5] = "Mary";
b.
char nameStr[5];nameStr = "Mary";
c.
char nameStr[] = "Mary";d. char nameStr[5];
strcpy(nameStr, "Mary");
27. Given the declaration
char myName[4] = "Ben";
which of the following does not output "Ben"?
a.
cout << myName;b.
for (i = 0; i < 3; i++)cout << myName[i];
c. for (i = 0; i < 3; i++)
cout << myName;
d. i = 0;
while (myName[i] != '\0')
{
cout << myName[i];
i++;
}s
28. Given the declaration
char message[10];
which of the following statements is invalid?
a.
strcpy(message, "Welcome");b.
cin >> message;c.
message[2] = 'g';d. if (strcmp(message, "Picnic") == 0)
cout << "Hooray!";
e. none of the above--they are all valid
29. Given the two lines of input data
Now is
the time.
what character is stored into the variable
someChar by execution of the following code?char str[20];
char someChar;
cin >> str;
cin.get(someChar);
a.
' ' (blank)b.
'i'c.
'\n'd.
't'e.
It cannot be determined from the information given.
30. Given the two lines of input data
Now is
the time.
what character is stored into the variable
someChar by execution of the following code?char str[20];
char someChar;
cin.get(str, 20);
cin.get(someChar);
a. ' ' (blank)
b. 'i'
c.
'\n'd.
't'e. It cannot be determined from the information given.
Fill-In
31. In a data structure, components are said to be ____________________ if they are all of the same data type.
32. A collection of components in a data structure is said to be ____________________ if each component (except the first) has a unique predecessor and each component (except the last) has a unique successor.
33. A(n) ____________________ is a variable-length, linear collection of homogeneous components.
34. The actual number of values stored in a list is called the ____________________ of the list.
35. A(n) ____________________ search is an algorithm that starts at the beginning of the list and looks at each item in sequence.
36. Arranging the components of a list into order is called ____________________.
37. A(n) ____________________ sort makes several passes through the list, each time swapping a component into its proper position.
38. A(n) ____________________ sort starts with an empty list and places each new item into its proper position in the list.
39. A(n) ____________________ search reduces the range to be searched by approximately one-half after each comparison.
40. In C++, the symbols
'\0' denote the ____________________ character.41. In C++, a(n) ____________________ is a null-terminated sequence of characters stored in a
char array.42. Strings are compared according to ____________________ order (the order in which they would appear in a dictionary).
43. Below is a three-statement sequence to swap two array elements by using a temporary variable. The first statement is missing. What should it be?
Statement 1:
Statement 2:
x[i] = x[j];Statement 3:
x[j] = temp;44. Using a C++ standard library routine, write a function call that copies the string in array
myString to the array yourString: ____________________45. Using a C++ standard library routine, write a function call that determines the length of the string in the array
someString: ____________________46. Write a
typedef statement that defines ArrType to be the same as the type "25-element array of int": ____________________