Templating, Introduction to algorithm analysis, Linked list, Stacks/queues (and applications), Recursion

Question 1

Assign. 4 you constructed a sequence template that better constructed the same application. The application (driver) program involved in making the template class particularly advantageous can best be described as

Answer 1

It uses 2 sequences of DIFFERENT ITEM TYPES but both sequences BEHAVE EXACTLY THE SAME WAY

Question 2

Whats the major flaw suffered?
Head unintentionally lost; potential null-pointer exception; stale pointer; illegal access of memory already released

void DestroyList (Node*& head)
{
Node *cursor = head, *next = 0;
while (cursor != 0)
{
next = cursor->link;
delete cursor;
cursor = next;
}
}

Answer 2

Stale pointer because there are other pointers that point to nodes in the list, and those pointers are not updated or invalidated when the list is destroyed

Question 3

Whats the major flaw suffered?
Head unintentionally lost; potential null-pointer exception; stale pointer; illegal access of memory already released

void RemoveHead (Node*& head)
{
if (head == 0) return;
delete head;
head = head->link;
}

Answer 3

Illegal access of memory already released because the function deletes the ‘head’ node before updating the ‘head’ pointer to point to the next node. This means that when the ‘head’ pointer is updated after deletion, it is pointing to a memory location that has already been released.

Question 4

Whats the major flaw suffered?
Head unintentionally lost; potential null-pointer exception; stale pointer; illegal access of memory already released

bool NonEmptyAndNegativelyHeaded (Node* head)
{
return head->data < 0 && head != 0;
}

Answer 4

Potential null-pointer exception because the function first checks if ‘head’s data’ member is less than 0 before checking if ‘head’ is a null pointer. If head is null, then accessing its data member would result in undefined behavior, including a program crash. Therefore, it is important to first check if ‘head’ is null before accessing its data member.

Question 5

Whats the major flaw suffered?
Head unintentionally lost; potential null-pointer exception; stale pointer; illegal access of memory already released

void PrintList (Node*& copyOfHead)
{
while (copyOfHead != 0)
{
cout &laquo_space;copyOfHead->data &laquo_space;endl;
copyOfHead = copyOfHead->link;
}
}

Answer 5

Head unintentionally lost the function takes a reference to a pointer to the head of the list. The problem with this function is that it modifies the value of copyOfHead during its execution, which can result in the head pointer being lost or changed unintentionally. Specifically, the copyOfHead pointer is advanced to the next node each time through the loop, effectively modifying the original head pointer.

Question 6

When implementing a queue with a singly-linked list (that keeps a tail pointer), it is most logical to have _______ because the other choice will not allow us to do _______

First blank:
the front at head and the rear at tail
the rear at head and the front at tail

Second blank:
front operation in O(1) time
push operation in O(1) time
pop operation in O(1) time

Answer 6

the front at head and the rear at tail, pop operation in O(1) time

Question 7

(T/F) From problem-solving strategy recursion can be considered a more general (not more specialized) form of divide-and-conquer (or reduce-and-conquer as some preferred)

Answer 7

False is more specialized

Question 8

(T/F) A recursive function that DOESN’T have at least a base case is likely to cause stack overflow

Answer 8

True

Question 9

(T/F) A recursive function that DOES have at least a base case will never cause stack overflow

Answer 9

False

Question 10

FOUR criteria important for successful application of recursion

Answer 10

recursively decomposible, base case(s), making progress, ultimate reachability of base case(s)

Question 11

How many asterisks are printed by the function call foo (4)?

void foo (int i)
{
if (i > 0)
{
foo (i - 2);
foo (i - 2);
}
cout &laquo_space;’ * ‘;
}

Answer 11

7

Question 12

What could go wrong with the code?

void goo (int n)
{
if (n != 0)
{
cout &laquo_space;n;
goo (n - 2);
}
}

Answer 12

stack overflow, there is no base case or condition that would terminate the recursive calls, the function will keep calling itself until the call stack overflows. Since the function is decrementing n by 2 at each recursive call, it will eventually reach negative values and continue to call itself, leading to a stack overflow.