Data Structure and Algorithm

1
Exercise Solutions
Chapter 1
1. a. true; b. false; c. false; d. false; e. false; f. true; g. false; h. false
2.
Precondition: The value of x must be nonnegative.
Postcondition: If the value of x is nonnegative, the function returns the positive square root
of x; otherwise, the program terminates.
3. a. O(n2
)
b. O(n3
)
c. O(n3
)
d. O(n)
4. 12
5. a. 43
b. 4n + 3
c. O(n)
6. -51, -50, -49, -1, 0, 1, 49, 50, 51
7. #define NDEBUG
8.
a.
int sumSquares(int n)
{
int sum = 0;
for(int j = 1; j <= n; j++)
sum = sum + j * j;
return sum;
}
b. This function is of the order O(n).
9. The black-box refers to testing the correctness of the program; that is, making sure that the program
does what it is supposed to do. In black-box testing, you do not know the internal working of the
algorithm or function. You know only what the function does. Black-box testing is based on inputs and
outputs.
10. The white-box refers to testing the correctness of the program; that is, making sure that the program
does what it is supposed to do. White-box testing relies on the internal structure and implementation of
a function or algorithm. The objective is to ensure that every part of the function or algorithm is
executed at least once.
11. a. Constructors have no type. Therefore, the statement:
int AA(int, int);
should be :

2
AA(int, int);
b. Missing semicolon after }.
c. There should be a : after the member access specifier public. (Replace ; with : after the label
public.)
12.
a. 6
b. 2
c. 2
d.
void xClass::func()
{
u = 10; v = 15.3;
}
e.
void xClass::print()
{
cout<<u<<" "<<v<<endl;
}
f.
xClass::xClass()
{
u = 0; v = 0;
}
g. x.print();
h. xCalss t(20, 35.0);
13.
a. (i) Constructor at Line 1
(ii) Constructor at Line 3
(iii) Constructor at Line 4
b.
CC::CC()
{
u = 0;
v = 0;
}
c.
CC::CC(int x)
{
u = x;
v = 0;
}
d.
CC::CC(int x, int y)
{
u = x;
v = y;
}
CC::CC(double x, int y)

3
{
u = y;
v = x;
}
14.
a.
int testClass::sum()
{
return x + y;
}
void testClass::print() const
{
cout<<"x = "<<x<<", y = "<<y<<endl;
}
testClass::testClass()
{
x = 0;
y = 0;
}
testClass::testClass(int a, int b)
{
x = a;
y = b;
}
b. (One possible solution. We assume that the name of the header file containing the definition of the
class testClass is Exercise14Ch1.h.)
#include <iostream>
#include "Exercise5Ch1.h"
using namespace std;
int main()
{
testClass one;
testClass two(4,5);
one.print();
two.print();
return 0;
}

4
Chapter 3
1. a. false; b. false; c. false; d. true; e. true; f. true; g. false; h. false
2. a. valid
b. valid
c. invalid (p is a pointer variable and x is an int variable. The value of x cannot be assigned to p.)
d. valid
e. valid
f. invalid (*p is an int variable and q is a pointer variable. The value of q cannot be assigned to *p.)
3.
98 98
98 98
4.
35 78
78 78
5. b and c
6. 39 39
7. 78 78
 The statement in Line 5 copies the value of p into q. After this statement executes, both p and q point
to the same memory location. The statement in Line 7 deallocates the memory space pointed to by q,
which in turn invalidates both p and q. Therefore, the values printed by the statement in Line 8 are
unpredictable.
 4 4 5 7 10 14 19 25 32 40
10. 10 15 20 25 30 35 40 45 50 55
11. In a shallow copy of data, two or more pointers points to the same memory space. In a deep copy of
data, each pointer has its own copy of the data.
12. The statement in Line 7 copies the value of p into q. After this statement executes, both p and q point
to the same array. The statement in Line 8 deallocates the memory space, which is an array, pointed to
by p, which in turns invalidates q. Therefore, the values printed by the statement in Line 10 are
unpredictable.
13.
Array p: 5 7 11 17 25
Array q: 25 17 11 7 5
14. The copy constructor makes a copy of the actual parameter data.
15. The copy constructor executes when a variable is passed by value, when a variable is declared and
initialized using another variable, and when the return value of a function is an object.
16. Classes with pointer data members should include the destructor, overload the assignment operator,
and explicitly provide the copy constructor by including it in the class definition and providing its
definition.
17.
a. (i) Function prototypes to appear in the definition of the class:
newString operator+(const newString& right) const;
newString operator+(char ch) const;
(ii) Definitions of the functions to overload +
newString newString::operator+(const newString& right) const
{
newString temp;
temp.slength = slength + right.slength;
temp.sPtr = new char[temp.slength + 1];

5
assert(temp.sPtr != NULL);
strcpy(temp.sPtr, sPtr);
strcat(temp.sPtr, right.sPtr);
return temp;
}
newString newString::operator+(char ch) const
{
newString temp;
char chStr[2];
chStr[0] = ch;
chStr[1] = '0';
temp.slength = slength + 1;
temp.sPtr = new char[temp.slength + 1];
assert(temp.sPtr != NULL);
strcpy(temp.sPtr, sPtr);
strcat(temp.sPtr, chStr);
return temp;
}
b.
(i) Function prototypes to appear in the definition of the class:
const newString& operator+=(const newString& right);
const newString& operator+=(char ch);
(ii) Definitions of the functions to overload +=
const newString& newString::operator+=
(const newString& right)
{
char *temp = sPtr;
slength += right.slength;
sPtr = new char[slength + 1];
assert(sPtr != NULL);
strcpy(sPtr,temp);
strcat(sPtr, right.sPtr);
delete []temp;
return *this;
}

6
const newString& newString::operator+=(char ch)
{
char *temp = sPtr;
char chStr[2];
chStr[0] = ch;
chStr[1] = '0';
slength += + 1;
sPtr = new char[slength + 1];
assert(sPtr != 0);
strcpy(sPtr,temp);
strcat(sPtr, chStr);
delete []temp;
return *this;
}
18.
a. The statement creates the arrayListType object intList of size 100. The elements of
intLits are of the type int.
b. The statement creates the arrayListType object stringList of size 1000. The elements
of stringList are of the type string.
c. The statement creates the arrayListType object salesList of size 100. The elements of
salesList are of the type double.
19.
polynomialType
+operator<<(ostream&, const polynomialType&): ostream&
+operator>>(istream&, polynomialType&): istream&
+operator+(const polynomialType&): polynomialType
+operator-(const polynomialType&): polynomialType
+operator*(const polynomialType&): polynomialType
+operator() (double): double
+min(int, int): int
+max(int, int): int
+polynomialType(int = 100)
arrayListType
polynomialType

7
Chapter 5
1. a. false; b. false; c. false; d. false; e. true; f. true
2. a. 18; b. 32; c. 25; d. 23
3. a. true; b. true; c. false; d. false; e. true
4. a. valid
b. valid
c. valid
d. invalid (B is a pointer while *List is a struct)
e. valid
f. invalid (B is a pointer while A->link->info is int);
g. valid
h. valid
i. valid
5. a. A = A->link;
b. List = A->link->link;
c. B = B->link->link;
d. List = NULL;
e. B->link->info = 35;
f. newNode = new nodeType;
newNode->info = 10;
newNode->link = A->link;
A->link = newNode;
g. p = A->link;
A->link = p->link;
delete p;
6. This is an infinite loop, continuously printing 18.
7. a. This is an invalid code. The statement s->info = B; is invalid because B is a pointer and
s->info is an int.
b. This is an invalid code. After the statement s = s->link; executes, s is NULL and so
s->info does not exist.
8. 10 18 13
9. 30 42 20 28
10.
Item to be deleted is not in the list.
18 38 2 15 45 25
11.
List: 75 48 78 45 30 18 4 32 36 19
Item to be deleted is not in the list.
Copy List = 75 48 45 30 18 4 32 36 19
12. intList = {3, 23, 43, 56, 11, 23, 25}
13. intList = {5, 24, 16, 11, 60, 9, 3, 58, 78, 85, 6, 15, 93, 98, 25}
14.
34 0 45 23 35 50
46 76 34 0 38 45 23 138

8
15.
-videoTitle: string
-movieStar1: string
-movieStar2: string
-movieProducer: string
-movieDirector: string
-movieProductionCo: string
-copiesInStock: string
videoType
+setVideoInfo(string, string, string, string,
string, string , int) : void
+getNoOfCopiesInStock() const: int
+checkOut(): void
+printTitle() const: void
+checkTitle(string): bool
+updateInStock(int): void
+setCopiesInStock(int num): void
+getTitle(): string
+videoType(string = "", string = "",
string = "", string = "",
string = "", string = "",
int = 0)
+operator==(const videoType&) const: bool
+operator!=(const videoType) const: bool
+ostream& operator<<(ostream&, const videoType&)
16.
videoListType
+videoSearch(string): bool
+isVideoAvailable(string): bool
+videoCheckOut(string): void
+videoCheckIn(string): void
+videoCheckTitle(string): bool
+videoUpdateInStock(string, int): void
+videoSetCopiesInStock(string, int): void
+void videoPrintTitle(): void
-void searchVideoList(string, bool&,
nodeType<videoType>* &): void
linkedListType<videoType>
videoListType

9
Chapter 6
1. a. true; b. true; c. false; d. false; e. false
2. The case in which the solution to the problem is obtained directly.
3. The case in which the solution is defined in terms of smaller versions of itself.
4. A function is called directly recursive if it calls itself.
5. A function that calls another function and eventually results in the original function call is said to be
indirectly recursive.
6. A recursive function in which the last statement executed is the recursive call is called a tail recursive
function.
7. a. The statements in Lines 2 and 3.
b. The statements in Lines 4 and 5.
c. Any nonnegative integer.
d. It is a valid call. The value of mystery(0) is 0.
e. It is a valid call. The value of mystery(5) is 15.
f. It is an invalid call. It will result in an infinite recursion.
8. a. The statements in Lines 2, 3, 4, and 5.
b. The statements in Lines 6 and 7.
c. B
9. a. It does not produce any output.
b. It does not produce any output.
c. 5 6 7 8 9
d. It does not produce any output.
10. a. 15
b. 6
11. a. 2
b. 3
c. 5
d. 21
12. 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.
if(low < high)
{
a. swap(list[low], list[high])
b. reverse elements between low + 1 and high - 1)
}
13.









otherwisenmmultiplym
nifm
nif
nmmultiply
)1,(
1
00
),(
14. a.









otherwiserncrnc
rifn
rnorrif
rnc
),1()1,1(
1
01
),(
b. C(5,3) = 10; C(9,4) = 126.

10
Chapter 7
1. x = 3
y = 9
7
13
4
7
2. x = 45
x = 23
x = 5
Stack Elements: 10 34 14 5
3. a. 26
b. 45
c. 8
d. 29
4. a. AB+CD+*E-
b. ABC+D*-EF/+
c. AB+CD-/E+F*G-
d. ABCD+*+EF/G*-H+
5. a. a * b + c
b. (a + b) * (c – d)
c. (a – b – c ) * d
6. Winter Spring Summer Fall Cold Warm Hot
7. 10 20 30 40 50
8.
template<class Type>
void linkedListType<Type>::printListReverse()
{
linkedStackType<nodeType<Type>* > stack;
nodeType<Type> *current;
current = first;
while(current != NULL)
{
stack.push(current);
current = current->link;
}
while(!stack.isEmptyStack())
{
current = stack.top();
stack.pop();
cout<<current->info<<" ";
}
cout<<endl;
}
9.

11
Type second(stackType<Type> stack)
{
Type temp1, temp2;
assert(!stack.isEmptyStack());
temp1 = stack.top();
stack.pop();
assert(!stack.isEmptyStack());
temp2 = stack.top();
stack.push(temp1);
return temp2;
}
10.
template<class type>
void clear(stack<type>& st)
{
while(!st.empty())
st.pop();
}

12
Chapter 8
1. a. queueFront = 50; queueRear = 0
b. queueFront = 51; queueRear = 99
5. 51
b. queueFront = 75; queueRear = 99. The position of the removed element was 75.
7. Queue Elements: 5 9 16 4 2
8. Queue Element = 0
Queue Element = 14
Queue Element = 22
Sorry, the queue is empty
Sorry, the queue is empty
Stack Element = 32
Stack Elements: 64 28 0
Queue Elements: 30
9. 5 16 5
10. The function mystery reverses the elements of a queue and also doubles the values of the queue
elements.
11.
template<class type>
void moveNthFront(queue<type>& q, int n)
{
vector<type> v(q.size());
int count = 1;
int index = 1;
if(1 <= n && n <= q.size())
{
while(count < n)
{
v[index] = q.front();
q.pop();
count++;
index++;
}
v[0] = q.front();

13
q.pop();
while(!q.empty())
{
v[index] = q.front();
q.pop();
index++;
}
for(index = 0; index < v.size(); index++)
q.push(v[index]);
}
else
cout<<"The value of n is out of range."<<endl;
}
12.
template <class Type>
void reverseStack(stackType<Type> &s, queueType<Type> &q)
{
Type elem;
while(!s.isEmptyStack())
{
elem = s.top();
s.pop();
q.addQueue(elem);
}
while(!q.isEmptyQueue())
{
elem = q.front();
q.deleteQueue();
s.push(elem);
}
}
13.
template <class Type>
void reverseQueue(queueType<Type> &q, stackType<Type> &s)
{
Type elem;
while(!q.isEmptyQueue())
{
elem = q.front();
q.deleteQueue();
s.push(elem);
}
while(!s.isEmptyStack())
{
elem = s.top();
s.pop();
q.addQueue(elem);

14
}
}
14.
int queueType<Type>::queueCount()
{
return count;
}

15
Chapter 9
1. a. false; b. true; c. false; d. false
2. a. 8; b. 6; c. 1; d. 8
3.
a.
Iteration first last mid list[mid] Number of comparisons
1 0 10 5 55 2
2 0 4 2 17 2
3 0 1 0 2 2
4 1 1 1 10 2
5 2 1 the loop stops unsuccessful search
This is an unsuccessful search. The total number of comparisons is 8.
b.
1 0 10 5 55 2
2 0 4 2 17 2
3 3 4 3 45 2
4 4 4 4 49 1(found is true)
The item is found at location 4 and the total number of comparisons is 7.
c.
1 0 10 5 55 2
2 6 10 8 92 2
3 9 10 9 98 1(found is true)
The item is found at location 9 and the total number of comparisons is 5.
d.
1 0 10 5 55 2
2 6 10 8 92 2
3 9 10 9 98 2
4 10 10 10 110 2
5 11 10 the loop stops
This is an unsuccessful search. The total number of comparisons is 8.
4.
template<class elemType>
class orderedArrayListType: public arrayListType<elemType>
{
public:
int binarySearch(const elemType& item);
orderedArrayListType(int n = 100);
};
5. There are 30 buckets in the hash table and each bucket can hold 5 items.
6. Suppose that an item with key X is to be inserted in HT. We use the hash function to compute the index
h(X) of this item in HT. Suppose that h(X) = t. Then 0  h(X)  HTSize – 1. If HT[t] is empty, we store

16
this item into this array slot. Suppose that HT[t] is already occupied by another item and so we have a
collision. In linear probing, starting at location t, we search the array sequentially to find the next
available array slot. In linear probing, we assume that the array is circular so that if the lower portion
of the array is full, we can continue the search in the top portion of the array.
7. Suppose that an item with key X is hashed at t, that is, h(X) = t, and 0  t  HTSize - 1. Further
suppose that position t is already occupied. In quadratic probing, starting at position t, we linearly
search the array at locations (t + 1) % HTSize, (t + 22
) % HTSize = (t + 4) % HTSize, (t+32
) % HTSize
= (t+9) % HTSize, ..., (t + i2
) % HTSize. That is, the probe sequence is: t, (t + 1) % HTSize, (t + 22
) %
HTSize, (t+32
) % HTSize, ..., (t + i2
) % HTSize.
8. In double hashing, if a collision occurs at h(X), the probe sequence is generated by using the rule:
(h(X) + i * h (X)) % HTSize
where h is the second hash function.
9. 30, 31, 34, 39, 46, and 55
10. a. The item with index 15 is inserted at HT[15]; the item with index 101 is inserted at HT[0]; the
item with index 116 is inserted at HT[16]; the item with index 0 is inserted at HT[1]; and the item with
index 217 is inserted at HT[17].
b. The item with index 15 is inserted at HT[15]; the item with index 101 is inserted at HT[0]; the
item with index 116 is inserted at HT[16]; the item with index 0 is inserted at HT[1]; and the item
with index 217 is inserted at HT[19].
11. 101
12. Suppose that an item, say R, is to be deleted from the hash table, HT. We first must find the index of R
in HT. To find the index of R, we apply the same criteria that was applied to R when R was inserted in
HT. Let us further assume that after inserting R another item, R, was inserted in HT and the home
position of R and R is the same. The probe sequence of R is contained in the probe sequence of R
because R was inserted in the hash table after R. Suppose that we simply delete R by marking the array
slot containing R as empty. If this array position stays empty, then while searching for R and following
its probe sequence, the search terminates at this empty array position. This gives the impression that R
is not in the table, which, of course, is incorrect. The item R cannot simply be deleted by marking its
position as empty from the hash table.
13. In open hashing, the hash table, HT, is an array of pointers. (For each j, 0  j  HTSize – 1, HT[j] is a
pointer to a linked list.) Therefore, items are inserted into and deleted from a linked list, and so item
insertion and deletion are simple and straightforward. If the hash function is efficient, few keys are
hashed to the same home position. Thus, an average linked list is short, which results in a shorter
search length.
14. Suppose there are 1000 items, each requiring 1 word of storage. Chaining then requires a total of 3000
words of storage. On the other hand, with quadratic probing, if the hash table size is twice the number
of items, only 2000 words are required for the hash table. Also, if the table size is three times the
number of items, then in quadratic probing the keys are reasonably spread out. This results in fewer
collisions and so the search is fast.
15. Suppose there are 1000 items and each item requires 10 words of storage. Further suppose that each
pointer requires 1 word of storage. We then need 1000 words for the hash table, 10000 words for the
items, and 1000 words for the link in each node. A total of 12000 words of storage space, therefore, is
required to implement the chaining. On the other hand, if we use quadratic probing, if the hash table
size is twice the number of items, we need 20000 words of storage.

17
16. The load factor α = 850 / 1001 ≈ .85.
17. The load factor α = 500 / 1001 ≈ .5.
a. (1/2){1 + (1/(1− α))} ≈ 1.5.
b. −log2 (1− α) / α ≈ 2 .
c. (1 + α /2) = 1.25.
18. Suppose that the size of the hash table is x. Then α = 550 / x.
a. (1/2){1 + (1/(1− α))} = 3. Substituting for α and then solving for x, gives x ≈ 690.
b. x ≈ 140

18
Chapter 10
1. 3
2. 4
3. 10, 12, 18, 21, 25, 28, 30, 71, 32, 58, 15
4. 36
5. In the quick sort, the list is partitioned according to an element, called pivot, of the list. After the
partition, the elements in the first sublist are smaller than pivot, and in the second sublist are larger
than pivot. The merge sort partitions the list by dividing it into two sublists of nearly equal size by
breaking the list in the middle.
6. a. 36, 38, 32, 16, 40, 28, 48, 80, 64, 95, 54, 100, 58, 65, 55
b. 28, 16, 32, 38, 40, 36, 48, 80, 64, 95, 54, 100, 58, 65, 55
7. a. 35
b. 18, 16, 40, 14, 17, 35, 57, 50, 37, 47, 72, 82, 64, 67
8. 95, 92, 82, 87, 50, 81, 58, 78, 65, 47, 48, 53, 63, 52, 42, 59, 34, 37, 7,
45
9. During the first pass, 6 key comparisons are made. After two passes of the heap sort algorithm, the list
is:
85, 72, 82, 47, 65, 50, 76, 30, 20, 60, 28, 25, 45, 17, 35, 14, 94, 100
10.
template<class elemType>
class orderedArrayListType: public arrayListType<elemType>
{
public:
int binarySearch(const elemType& item);
void insertOrd(const elemType&);
void selectionSort();
void insertionSort();
void quickSort();
orderedArrayListType(int size = 100);
private:
void recQuickSort(int first, int last);
int partition(int first, int last);
void swap(int first, int second);
int minLocation(int first, int last);
};
11.
class orderedListType: public linkedListType<Type>
{

19
public:
bool search(const Type& searchItem);
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is found
// in the list, false otherwise.
void insertNode(const Type& newItem);
//Function to insert newItem in the list.
//Postcondition: first points to the new list and
// newItem is inserted at the proper
// place in the list.
void deleteNode(const Type& deleteItem);
//Function to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the
// list; first points to the first
// node of the new list.
// If deleteItem is not in the list, an
// appropriate message is printed.
void linkedInsertionSort();
void mergeSort();
private:
void divideList(nodeType<elemType>* first1,
nodeType<elemType>* &first2);
nodeType<elemType>* mergeList(nodeType<elemType>* first1,
nodeType<elemType>* first2);
void recMergeSort(nodeType<elemType>* &head);
};

20
Chapter 11
1. a. false; b. true; c. false; d. false
2.
3. LA = {B, C, D, E}
(12)
(14)
(13)
(9) (10)
(11)
(8)
(7)
(6)
(5)
(1) (2)
(3)
(4)

21
4. RA = {F, G}
5. RB = {E}
6. D C B E A F G
7. A B C D E F G
8. D C E B G F A
9. 80-55-58-70-79
10. 50-30-40
Binary tree after inserting 35:
50
30
98
85
55
80
48
58
25
52
45
40
90
110
70
75
7965
35

22
11.
12.
50
30
98
85
55
80
48
58
25
45
40
90
110
70
75
7965
50
30
98
85
55
80
58
25
5245
48
90
110
70
75
7965

23
13.
50
30
98
85
55
79
48
58
25
52
45
40
90
110
70
7565
Binary Tree
After Deleting
80
50
30
98
85
55
79
48
25
52
45
40
90
11070
7565
Binary Tree
After Deleting
58

24
14. In the preorder traversal, the first node visited is the root node. Therefore, the first
element of the preorder sequence becomes the root node of the tree. In the inorder
traversal, the nodes in the left subtree of the root node are visited before the root node
of the tree. Thus, all the elements that appear before the root node in the inorder
sequence are in the left subtree of the root node, and all the elements appearing after
the root node appear in the right subtree. Next, we consider the second element of the
preorder sequence. If it appears before the root node in the inorder sequence, then it
becomes the root node of the left subtree; otherwise, it becomes the root node of the
right subtree. We repeat this process of determining whether the next element of the
preorder sequence is in the left subtree of the current node or in the right subtree.
When we arrive at an empty subtree, the element (of the preorder sequence) is
inserted into the tree.
15.
16. Consider the following preorder and postorder sequences
Preorder : AB
PostOrder: BA
There are two possible binary trees corresponding to these sequences, as shown
below.
A
B
L
M
H
G
F
I
C
E
D
KJ
A
B
A
B

25
17. The balance factor of the root node is 0.
50
30
100
98
25 40 80
18. The balance factor of the root node is -1.
50
30
55
80
48
25 45
40
19. The balance factor of the root node is 0.
40
30
9855
804825
4220
35
50

26
20.
24 24
39
31
3924
31
3924
46
31
4624
4839 34
39
24
4631
48 34
39
24
4631
48
19
34
39
19
4631
48
5 24
31
39
19
4624
48
5 3429
(v)
(i)
(ii)
(iv)
(iii)
(vi)
(vii)
(viii) (ix)

Data Structure and Algorithm

Recommended

Recommended

More Related Content

What's hot

What's hot (20)

Similar to Data Structure and Algorithm

Similar to Data Structure and Algorithm (20)

Recently uploaded

Recently uploaded (20)

Data Structure and Algorithm