Answers to Selected Exercises Chapter 1

Download 0.49 Mb.

Page	2/7
Date	18.07.2017
Size	0.49 Mb.
	#23634

1 2 3 4 5 6 7

Chapter 4

Chapter 3

1. (a)

Boolean IsThere(ItemType item)

Function: Determines if item is in the list.

Precondition: List has been initialized.

Postcondition: Function value = there exist an item in the list whose key is the same as item's.

(b)

bool IsThere(ItemType item) const;

(d) O(N) where N is the number of items in the list.

5. (a)

DeleteItem (ItemType item )

Function: Deletes the element whose key matches item's key.

Preconditions: List has been initialized.

Key member of item is initialized.

At most one element in list has a key matching item's key.

Postcondition: If an element in list had a key matching item's key, the item has been removed; otherwise, the list is unchanged.

(c)

DeleteItem (ItemType item )

Function: Deletes the element whose key matches item's key.

Preconditions: List has been initialized.

Key member of item is initialized.

Postcondition: No element in list has a key matching item's key.

8. (a) True

(b) True

(d) False. A sequential list may be stored in a statically allocated or a dynamically allocated structure.

(e) True

(f) False. A queue is not a random-access structure; access is always to the first one stored.

10. (a) true

(b) false

(d) true

12. (a) listData = ptr1->next;

(b) ptr2 = ptr2->next;

(d) ptr1->next->info = 60

Answers for the table:

Statements	Memory allocated	What is printed?
int value;	value is assigned to location 200
value = 500;
char* charPtr;	charPtr is at location 202
char string[10] = "Good luck";	string[0] is at location 300
charPtr = string;
cout << &value; // question 19	& means "the address of"	200
cout << value; // question 20		500
cout << &charPtr; // question 21	& means "the address of"	202
cout << charPtr; // question 22		Good luck
cout << *charPtr; // question 23		G
cout << string[2]; // question 24		o

16. None of the changes in Exercises 9 and 10 change the Big-O from that discussed in the chapter. Each of the delete operations still have order O(N).

Chapter 4

(b)

bool IsThere(ItemType item) const;

(c)

bool SortedType::IsThere(ItemType item)

{

int midPoint;

int first = 0;

int last = length - 1;

bool moreToSearch = first <= last;

bool found = false;

while (moreToSearch && !found)

{

midPoint = (first + last) / 2;

switch (item.ComparedTo(info[midPoint])

{

case LESS : last = midPoint - 1;

moreToSearch = first <= last;

break;

case GREATER : first = midPoint + 1;

moreToSearch = first <= last;

break;

case EQUAL : found = true;

break;

}

return found;

}

(d) O(log₂N) where N is the number of items in the list.

3. (a)

Boolean IsThere(ItemType item, UnsortedType list)

Function: Determines if item is in the list.

Precondition: list has been initialized.

Postcondition: Function value = there exist an item in the list whose key is the same as item's.

(b)

bool IsThere(SortedType list, ItemType item)

{

int length;

bool found = false;

int counter = 1;

ItemType listItem;

length = list.LengthIs();

list.ResetList();

while (!found && counter <= length)

{

list.GetNextItem(listItem);

if (listItem.ComparedTo(item) == EQUAL)

found = true;

counter++;

}

return found;

}
or
bool IsThere(SortedType list, ItemType item)

{

bool found;

list.RetrieveItem(item, found);

return found;

}

(c) The client code does not have access to the array containing the data values, so the binary search algorithm could not be used.

(d) The version that iterates through the items is O(N); the version that uses RetrieveItem would have the same complexity as RetrieveItem.

(e) The member function has access to the array holding the values, so the binary search algorithm can be used. Therefore, the complexity if O(log₂N) rather O(N).

4. (a)

void MergeLists(SortedType list1, SortedType list2,

SortedType& result);

(b)

void MergeLists(SortedType list1, SortedType list2,

SortedType& result)

{

int length1;

int length2;

int counter1 = 1;

int counter2 = 1;

ItemType item1;

ItemType item2;
length1 = list1.LengthIs();

length2 = list2.LengthIs();

list1.ResetList();

list2.ResetList();

list1.GetNextItem(item1);

list2.GetNextItem(item2);

result.MakeEmpty();
while (counter1 <= length1 && counter2 <= length2)

switch (item1.ComparedTo(item2))

{

case LESS : result.InsertItem(item1);

if (counter1 < length1)

list1.GetNextItem(item1);

counter1++;

break;

case GREATER: result.InsertItem(item2);

if (counter2 < length2)

list2.GetNextItem(item2);

counter2++;

break;

}

for (; counter1 <= length1; counter1++)

{

result.InsertItem(item1);

if (counter1 < length1)

list1.GetNextItem(item1);

}

for (; counter2 <= length2; counter2++)

{

result.InsertItem(item2);

if (counter2 < length2)

list2.GetNextItem(item2);

}

}
(c) Because the lists that are being merged are sorted, the complexity is O(N) times the complexity of the InsertItem operation.

Directory: samples
samples -> Running head: capstone project
samples -> Memorandum of understanding long beach city college- long beach unified school district
samples -> Cell Phone Antennas: a look at the history and design of vhf antennas
samples -> Affinity program guidelines
samples -> Chapter 2: Setting Up Your Android Development Environment Multiple Choice Questions
samples -> High School Musical
samples -> Finance crisis Introduction
samples -> Android Application Development: Working with the Emulator
samples -> -

Download 0.49 Mb.

Share with your friends:

1 2 3 4 5 6 7