101
If the exception is thrown with the constructor with parameters with the actual parameter, “May
25. (1) Do nothing; (2) Partially process the exception and throw the same exception or a new
Chapter 15
2. a. The case in which the solution to the problem is obtained directly.
4. An algorithm that finds the solution to a given problem by reducing the problem to smaller
6. a. A function is called directly recursive if it calls itself.
7. a. The statements from Line 3 to Line 6.
b. The statements in Lines 7 and 8.
8. a. The statements in Lines 3 and 4.
11. a. 4 12 28
13. a. 0
b. 4
14. a. 28 28 28 28 10 8 8 2 0 0 0 0 2
16. Suppose that low specifies the starting index and high specifies the ending index in the
array. The elements of the array between low and high are to be reversed.
}
17.
=
nif
0 0
104
Chapter 16
2. a. 6
b. 10
3. int seqOrderedSearch(const int list[], int listLength,
int searchItem)
{
int loc;
bool found = false;
}
5. List before the first iteration: 50, 36, 78, 40, 4, 28, 90, 62, 22
List after the first iteration: 36, 50, 40, 4, 28, 78, 62, 22, 90
List after the second iteration: 36, 40, 4, 28, 50, 62, 22, 78, 90
6. List before the first iteration: 82, 17, 40, 28, 15, 55, 46, 93, 6, 67, 11, 3
List after the first iteration: 17, 40, 28, 15, 55, 46, 82, 6, 67, 11, 3, 93
List after the second iteration: 17, 28, 15, 40, 46, 55, 6, 67, 11, 3, 82, 93
105
12. a.
void bubbleSort(int list[], int length)
{
int temp;
int iteration;
}
}
}
a.
Iteration
first
last
mid
list[mid]
No. of comparisons
1
0
12
6
58
2
2
0
5
2
25
2
3
3
5
4
38
2
4
3
3
3
32
1 (found is true)
5
2
1
The item is found at location 3 and the total number of comparisons is 7.
b.
Iteration
first
last
mid
list[mid]
No. of comparisons
1
0
12
6
58
2
2
0
5
2
25
2
3
0
1
0
5
2
4
1
1
1
12
2
5
2
1
This is an unsuccessful search. The total number of comparisons is 8.
c.
Iteration
first
last
mid
list[mid]
No. of comparisons
1
0
12
6
58
2
2
7
12
9
90
2
3
10
12
11
105
1 (found is true)
The item is found at location 9 and the total number of comparisons is 5.
d.
Iteration
first
last
mid
list[mid]
No. of comparisons
1
0
12
6
58
2
2
7
12
9
90
2
3
7
8
7
62
2
4
7
6
This is an unsuccessful search. The total number of comparisons is 6.
16.
void descendingToAscending(int list[], int length)
{
int temp;
int index;
}
}
18. a. This statement declares list to be a vector object of size 50. The data type of the elements that
20. a. Sheila — Anita — Cecelia — Henry —
21.
a. vector<int> secretList;
b.
23. a. cout << myList.front() << ” ” << myList.back() << endl;
b length = myList.size();
24. Size indicated the number of elements currently in the vector. Capacity indicated the number of
elements that can be currently added to the vector.
108
Chapter 17
2. The two typical components of a single linked list are data and link. The component data stores the
5. Before deletion the link field of the third node stores the address of the fourth node. After deletion the
6. a. 12
b. 92 65
7. a. true
b. true
8. a. Sets the link field of the node with info 5 to nullptr, deletes the last node from the linked list,
and deallocates the memory occupied by the last note, and after deleting the last node sets list
point to the last node of the list.
9. a. p->link->info = 24;
b. q = current->link;
109
e. p = nullptr;
f. temp->link->info = 54;
g. while (first->info != 5)
first = first ->link;
10. a. Valid
b. Valid
c. Valid
d. Invalid; current->link is a pointer whereas temp->info is an int value.
11. a. while (first != nullptr)
first = first->link;
b. q = new nodeType;
q->info = 17;
12. a. 47 12 92 65 80 46 5 78
exist. This code will result in run time error.
16. 46 52 91 72
17. nodeType head, p, q;
head = new nodeType;
head->info = 72;
head->link = nullptr;
p = new nodeType;
18.
a. list
b. 25 16 12
c. nodeType *q;
ptr = list->link;
20. The function insertFirst of the class unorderedLinkedList insert a node at the
21. The item to be deleted is not in the list.
22. list = 16 120 64 40 12 45 35 83 23 11 98
23.
doublyLinkedList<Type>
#count: int
#*first: nodeType<Type>
#*last: nodeType<Type>
+operator=(const doublyLinkedList<Type> &):
const doublyLinkedList<Type>&
+initializeList(): void
+isEmptyList() const: bool
+print() const: void
+reversePrint() const: void
+length() const: int
+front() const: Type
+back() const: Type
+search(const Type&) const: bool
+insert(const Type&): void
+deleteNode(const Type&): void
+doublyLinkedList()
+doublyLinkedList(const doublyLinkedList<Type>&)
+~doublyLinkedList()
24.
dvdType
-dvdTitle: string
-movieStar1: string
-movieStar2: string
-movieProducer: string
-movieDirector: string
-movieProductionCo: string
-copiesInStock: int
+operator<<(ostream&, const dvdType&): friend ostream&
+setDVDInfo(string, string, string, string,
string, string, int): void
+getNoOfCopiesInStock() const: int
+checkOut(): void
+checkIn(): void
+printTitle() const: void
+printInfo() const: void
+checkTitle(string): bool
+updateInStock(int): void
+setCopiesInStock(int): void
+getTitle() const: string
+dvdType(string = “”, string = “”, string = “”,
string = “”, string = “”, string = “”,
int = 0)
+operator==(const dvdType&) const: bool
+operator!=(const dvdType&) const: bool
25.
dvdListType
Chapter 18
2. The value of stack.top gives the number of elements in the stack and if stack.top is nonzero,
5. 13
6. cin >> num;
while (cin)
{
if (!stack.isFullStack())
{
if (num >= 0)
8. Starting from right to left, this program segment stores the 2-digit blocks of an integer into a
9. a. 16
b. -4
e. 15
10. a. x y + z + w t / –
11. a. x * y + z – t
12. Chelsea Jackson
Kirk McCarthy
14. In this linked implementation of stacks, the memory to store the stack elements is allocated
15. If the stack is nonempty, the statement stack.top(); returns the top element of the stack and
16. template <class Type>
void linkedListType<Type>::printListReverse()
{
linkedStackType<nodeType<Type>* > stack;
nodeType<Type> *current;
17. template <class elemType>
elemType second(stackType<elemType> stack)
{
exit(0); //terminate the program
}
temp1 = stack.top();
exit(0); //terminate the program
}
}
18. a. 19
19. a. 4
b. 21
21. cin >> num;
{
case 0:
case 1: case –1:
if (num % 3 == 0)
queue.addQueue(num);
else
{
22. The method mystery reverses the elements of a queue of int objects and also doubles the
values of the queue elements.
23. a. 26
24. a. 23
25. a. 31
26. a. 1
28. a. queueFront = 74; queueRear = 0.
30. The program segment uses a stack and a queue to output the difference of the successive digits of
an integer.
31. template <class Type>
void reverseStack(stackType<Type> &s)
{
linkedQueueType<Type> q;
}
}
32. template <class Type>
void reverseQueue(queueType<Type> &q)
{
stackType<Type> s;
}
}
33. template <class Type>
34.
linkedStackType<Type>
-*stackTop: nodeType<Type>
+operator=(const linkedStackType<Type>&):
const linkedStackType<Type>&
+isEmptyStack() const: bool
+isFullStack() const: bool
+initializeStack(): void
+push(const Type&): void
+top() const: Type
+pop(): void
+linkedStackType()
+linkedStackType(const linkedStackType<Type>&)
+~linkedStackType()
-copyStack(const linkedStackType<Type>&): void
35.
queueADT<Type>
+isEmptyQueue() const = 0: virtual bool
+isFullQueue() const = 0: virtual bool
+initializeQueue() = 0: virtual void
+front() const = 0: virtual Type
+back() const = 0: virtual Type
+addQueue(const Type&) = 0: virtual void
+deleteQueue() = 0: virtual void
36. a.
queueType<Type>
-maxQueueSize: int
-count: int
-queueFront: int
-queueRear: int
-*list: Type
+operator=(const queueType<Type>&):
const queueType<Type>&
+isEmptyQueue() const: bool
+isFullQueue() const: bool
+initializeQueue(): void
+front() const: Type
+back() const: Type
+addQueue(const Type&): void
+deleteQueue():void
+queueType(int = 100)
+queueType(const queueType<Type>&)
+~queueType()
b.
linkedQueueType<Type>
-*queueFront: nodeType<Type>
-*queueRear: nodeType<Type>
+operator=(const linkedQueueType<Type>&):
const linkedQueueType<Type>&
+isEmptyQueue() const: bool
+isFullQueue() const: bool
+initializeQueue():void
+front() const: Type
+back() const: Type
+addQueue(const Type&): void
+deleteQueue():void
+linkedQueueType()
+linkedQueueType(const linkedQueueType<Type>&)
+~linkedQueueType