Computer Science Final Exam Review

Flashcards for Computer Science Final Exam

How many stacks are used for infix evaluation and why? Why does a postfix evaluation algorithm only need one stack?

Infix evaluation typically uses two stacks: one for operators and one for operands, to handle operator precedence and parentheses. Postfix evaluation uses one stack because the order of operations is explicit in the postfix notation.

True/False: The programmer must declare in advance the size of a dynamic stack or queue.

False.

The operation for adding an entry to a stack is traditionally called .

Push.

What problem is overcome by using a circular array for a static queue?

A circular array overcomes the problem of wasted space in a static queue by allowing elements to be added after the rear reaches the end, wrapping around to the front if space is available.

The queue data structure is commonly applied in connection with: A) managing the order of print jobs. B) communications software. C) operating systems. D) All of the above E) None of the above

D) All of the above.

What stack functions are used to avoid stack overflow and stack underflow?

To avoid stack overflow, the isFull() function is used. To avoid stack underflow, the isEmpty() function is used.

What is the difference between a static stack and a dynamic stack?

A static stack has a fixed size declared at compile time, while a dynamic stack can change its size during runtime. A dynamic stack is implemented as a linked list.

Evaluate the post-fix expression of 2 2 + 3 * 10 -

(2 + 2) * 3 - 10 = 4 * 3 - 10 = 12 - 10 = 2

The operation for removing an entry from a stack is traditionally called .

Pop.

A dynamic stack has a _ size and is implemented as a(an) __.

dynamic, linked list.

Name three examples of a practical application of the stack data type.

Examples include: ○ Evaluating arithmetic expressions ○ Syntax parsing ○ Reversing a string ○ Function call management

The queue in which the insertion takes place in the first position after the last element is: A. priority B. dequeue C. circular D. Linked

C. circular

Here is an INCORRECT pseudocode for the algorithm which is supposed to determine whether a sequence of parentheses is balanced: declare a character stack while ( more input is available) { read a character if ( the character is a '(' ) push it on the stack else if ( the character is a ')' and the stack is not empty ) pop a character off the stack else print "unbalanced" and exit } print "balanced" Which of these unbalanced sequences does the above code think is balanced? A. ( ( ( ) ) B. ( ) ) ( ( ) C. ( ( ) ( ) ) ) D. ( ( ) ) ) ( )

A. ( ( ( ) )

In the following code, assume the myQueue object is a queue that can hold integers, and that value is an int variable. (The lines are numbered for reference purposes.) myQueue.enqueue(0); myQueue.enqueue(1); myQueue.enqueue(2); myQueue.dequeue(value); cout << value << endl; Assume that the dequeue function, called in line 4, stores the number removed from the queue in the value variable. What will the statement in line 5 display? A) 0 B) 1 C) 2 D) None of these

A) 0

Consider the following pseudocode: declare a stack of characters while ( there are more characters in the word to read ) read a character push the character on the stack } while ( the stack is not empty ) { write the stack's top character to the screen pop a character off the stack } What is written to the screen for the input "goldenEAGLE"?

ELGAEnedlog

Here is an infix expression: 4+3(63-12)+ (8+2)*(6-4)/5. Suppose that we are using the usual stack algorithm to convert the expression from infix to postfix notation. What is the maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?

3

Suppose the following operations are performed on an empty static queue: enqueue(5); | enqueue(7); dequeue (); enqueue(9); enqueue(12); dequeue (); enqueue(10); Insert numbers in the following diagram to show what will be stored in the static queue after the operations have executed. The following table: , , ,

9, 12, 10

Suppose the following operations were performed on an empty dynamic stack: push(8); push(7); pop (); push(19); push(21); pop (); Insert numbers in the following diagram to show what will be stored in the static stack after the operations have executed. The following table:

8, 19

If user enter "20" for value1 and "10" for value2, what is value1+value2?

It depends on the code, but if the intention is to add them numerically, the answer is 30. If the values are concatenated as strings, the answer is "2010".

Convert infix expression ( (A/B)+( C * D) )-(E^F) and A(B+C(D-E))/F to postfix expression.

○ ( (A/B)+( C * D) )-(E^F) -> AB/CD+EF^- ○ A(B+C(D-E))/F -> ABCDE-+*F/
○ *Note: "^" is often used to denote exponentiation.

Recall the algorithm discussed in class and create the postfix expression from ((5 –3) * 5 + (9 –3) / 3) ^ 2. Draw the stack after each push or pop.

Postfix Expression: 5 3 - 5 * 9 3 - 3 / + 2 ^ ○ (See document for stack trace - too complex for text-based flashcard)

Below is the function enqueue from Static Queue. Write a small code in the enqueue function to calculate the new rear position. void Queue::enqueue(int val) { if (isFull()) { cout << "The queue is full.\n"; } else { //calculate new rear position } }

rear = (rear + 1) % maxSize; (where maxSize is the size of the queue array)

After num = stoi("250"); executes, what value is stored in the variable num?

250 (as an integer)

Evaluate 8 2 + 6 4 - * 5 / and – + ^ / 6 2 2 7 ^ –5 2 1

○ 8 2 + 6 4 - * 5 / = 2
○ - + ^ / 6 2 2 7 ^ –5 2 1 = -5

Trace the algorithm given and evaluate postfix expression 12 7 - 5 * 30 6 - 2 / + 3 ^. Draw the stack after each push and pop. Pseudocode for Evaluating Post-Fix Expression Initialize a stack of double numbers do if (the next input is a number) Read the next input and push it onto the stack else { Read the next character, which is an operation symbol. Use top and pop to get the two numbers off the stack. Combine these two numbers with the operation ( using the second number popped as the left operand) and push the result onto the stack. } while( there is more of the expression to read); At this point, the stack contains one number, which is the value of express

Result: 28 ○ (See document for stack trace - too complex for text-based flashcard)

Write a function to reverse a linked list.

(See document for code - too complex for text-based flashcard)

What are the advantages and disadvantages of using recursion over iteration in C++?

○ Advantages: Can provide simpler, more elegant solutions for some problems.
○ Disadvantages: Can be less efficient due to function call overhead and may lead to stack overflow with deep recursion.

Discuss the advantage a linked list has over a vector.

Linked lists can grow or shrink dynamically, whereas vectors have a fixed size or require reallocation for size changes. Linked lists allow efficient insertion and deletion of elements in the middle of the list.

What is a node in a linked list? A) A data structure that contains data and a pointer to the next node B) A variable used to store the size of the linked list C) A function to traverse a linked list D) A type of array used in linked lists

A) A data structure that contains data and a pointer to the next node

What does the head of a linked list represent?

The head of a linked list is a pointer to the first node in the list.

What is the output of the program if user 7? #include <iostream> using namespace std; int CS(int); int main() { int number; cout << "Enter value and I will display\n"; cout << "the result"; cin >> number; cout << "The result is "; cout << CS(number) << endl; system("pause"); return 0; } int CS(int num) { if (num == 0) return 1; else return num * CS(num - 1); }

5040 (This calculates the factorial of 7)

What happens if you try to access the next pointer of the last node in a singly linked list? A) It will cause a runtime error B) It will loop back to the first node C) It will point to NULL D) It will automatically create a new node

C) It will point to NULL

Each of the following declarations or code segments has errors. Locate as many as possible. catch { quotient = divide(numl, num2); cout << ''The quotient is '' << quotient << endl; } try (string exceptionString) { cout << exceptionString; }

○ The first catch block is missing a parameter declaration. It should specify the type of exception it's intended to catch (e.g., catch (int errorNum)). ○ The try block has a parameter, which is incorrect syntax. try blocks do not take parameters.

Each of the following member functions for performing an operation on a linked list of type NumberList has at least one error. Explain what is wrong and how to fix it. NumberList::printList( ) { while(head) { cout << head->value; head = head->next; } } NumberList::printList( ) { ListNode *p = head; while (p->next) { cout << p->value; p = p->next; } } NumberList::~NumberList() { ListNode *nodePtr, *nextNode; nodePtr = head; while (nodePtr != NULL) { nextNode = nodePtr->next; nodePtr->next = NULL; nodePtr = nextNode; } }

○ In the first printList function, modifying head will lose the reference to the beginning of the list. It should use a temporary pointer. ○ In the second printList function, the loop condition p->next will cause it to stop before printing the last node. It should be while (p != NULL). ○ In the ~NumberList destructor, setting nodePtr->next = NULL; is unnecessary and doesn't free memory. It should delete nodePtr;. It also has a memory leak.

Each of the following declarations or code segments has errors. Locate as many as possible. catch { quotient = divide(numl, num2); cout << ''The quotient is '' << quotient << endl; } try (string exceptionString) { cout << exceptionString; }

(This is a duplicate of Card 33) ○ The catch block needs a parameter specifying the exception type. ○ The try block should not have a parameter.

Each of the following declarations or code segments has errors. Locate as many as possible. a) template <class T> T square(T number) { return T * T; } b) template <class Tl, class T2> Tl sum(Tl x, Tl y) { return x + y; }

○ a) return T * T; should be return number * number; ○ b) The return type Tl might not be appropriate if Tl and T2 are different types. It might be better to return a more general type or the same type as the arguments (if they are the same).

True/False: An exception is a condition that can be caused by a syntax error in the program.

False. Exceptions are runtime errors.

Exception is thrown and not caught anywhere, the program terminates abnormally. Rewrite the catch statement with the default exception. #include <iostream> using namespace std; int main() { try { throw 'a'; } catch (int x) { cout << "Caught "; } return 0; }

● C++ catch (…) { cout << "Caught an exception"; } ● ● *Note: The catch(…) block should be placed after specific catch blocks.

Write a pattern for a loop that transverse every other node of a linked list.

● C++ for (Node* temp = head; temp != nullptr; temp = temp->next) { // Process current node (temp) if (temp->next != nullptr) { temp = temp->next; // Move to the next node } else { break; // Avoid going beyond the end } } ● ● *Or a while loop equivalent.

True/False: Inserting an item into a linked list requires that all the items past the point of the insertion be shifted to make room for the new item

False

True/False: A new node must always be made the last node in the list.

False

How many steps are involved in the process of deleting a node? A) one—delete the node from memory B) two—remove the node without breaking links, then delete it from memory C) three—create a blank node, remove the node being deleted, insert the blank, then delete the node D) four—create a blank, remove the node being deleted, insert the blank, delete the node, delete the blank E) None of these

B) two—remove the node without breaking links, then delete it from memory

A recursive function is designed to terminate when it reaches its . A) return statement B) base case C) closing curly brace D) last parameter

B) base case

To append a node to a list means to . A) delete a node from the beginning of the list B) delete a node from the end of the list C) add a node to the beginning of the list D) add a node to the end of the list

D) add a node to the end of the list

An exception thrown from outside a try block . A) will be caught outside the catch block B) will be caught inside the catch block C) will remain inside the throw block D) will cause the program to abort execution E) None of these

D) will cause the program to abort execution

An insertion or deletion routine requires that you create this many pointers for use during the traversal process. A) Two—one for the node being inspected, and one for the previous node. B) Two—one for the node being inspected, and one for the next node. C) One—for the node being inserted or deleted D) Three—one for the inspected node, one for the next node, and one for the following node

A) Two—one for the node being inspected, and one for the previous node.

True/False: Using a function template requires less code than overloading a function.

True

How many times will the following function call itself, if the value 5 is passed as the argument? void showMessage(int n) { if (n > 0) { cout << "Good day!" << endl; showMessage(n + 1); } }

The code will result in infinite recursion and likely a stack overflow because there's no base case to stop the recursion.

Below is the code for QuickSort Algorithm. If array consists of elements 17, 53, 9, 2, 30, 1, 82, 64, 26, 5. Draw the process of each partitioning using Quicksort Algorithm. (10 points) void quickSort(int arr[ ], int start, int end) { if (start < end) { int p = partition(arr, start, end); quickSort(arr, start, p - 1); quickSort(arr, p + 1, end); } } int partition(int arr[], int start, int end) { int pivotValue = arr[start]; int pivotPosition = start; for (int pos = start + 1; pos <= end; pos++) { if (arr[pos] < pivotValue) { swap(arr[pivotPosition + 1], arr[pos]); swap(arr[pivotPosition], arr[pivotPosition + 1]); pivotPosition ++; } } return pivotPosition;}

(See document for Quicksort trace - too complex for text-based flashcard)

A linked list class must take care of removing the dynamically allocated nodes. This is done by . A) the constructor function B) the destructor function C) overriding the removal function D) overloading the memory persistence operator

B) the destructor function

True/False: Any algorithm that can be coded with recursion can also be coded with an iterative structure.

True

What is the output of the program if user enter 40 for num1 and 12 for num2? #include <iostream> using namespace std; // Function prototype int Exam2(int, int); int main() { int num1, num2; cout << "Enter two integers: "; cin >> num1 >> num2; cout << "The result of " << num1; cout << " and " << num2 << " is "; cout << Exam2(num1, num2) << endl; system("pause"); return 0; } int Exam2(int x, int y) { if (x % y == 0) return y; else return Exam2(y, x % y); }

4 (This calculates the greatest common divisor (GCD) of the two numbers.)

True/False: When you create a linked list, you must know in advance how many nodes the list will contain.

False

In the following statement: template <class T> What does the word class indicate? A) class is a key word that is used to precede the type parameter T. B) You are deriving a class from an existing class called T. C) You are deriving a class called T from a class called template. D) A class named T will automatically be created by the compiler. E) None of these

A) class is a key word that is used to precede the type parameter T.

How much memory is reserved for a function template? A) four bytes B) eight bytes C) two bytes D) no memory E) None of these

D) no memory (Memory is allocated when the template is instantiated with a specific type.)

In a function template, the programmer substitutes for .

type parameters, specific data types

The defining characteristics of a linked list

the locations that store list data do not have to be consecutive in memory.