1.
Suppose you have a directed graph representing all the flights that an airline flies. What algorithm might be used to find the best sequence of connections from one city to another?
Correct Answer
A. A shortest-path algorithm.
Explanation
A shortest-path algorithm would be used to find the best sequence of connections from one city to another in a directed graph representing all the flights that an airline flies. This algorithm is designed to find the shortest path between two nodes in a graph, taking into account the weights or distances associated with each edge. By applying a shortest-path algorithm to the directed graph of flights, the algorithm can determine the sequence of connections that minimizes the total distance or time required to travel from one city to another.
2.
Suppose cursor points to a node in a linked list (using the node definition with member functions called data and link). What Boolean expression will be true when the cursor points to the tail node of the list?
Correct Answer
A. (cursor->link( ) == NULL)
Explanation
The Boolean expression (cursor->link( ) == NULL) will be true when the cursor points to the tail node of the linked list. This is because the link member function of the cursor, when pointing to the tail node, will return NULL, indicating that there is no next node in the list.
3.
Which of the following represents the sequence of nodes visited in a post-order traversal of the binary tree T shown below?
Correct Answer
C. U X W Q Z Y V P
Explanation
The correct answer is U X W Q Z Y V P. In a post-order traversal, the left subtree is visited first, followed by the right subtree, and finally the root node. Starting from the root node U, we visit its left child X, then its left child W, and then its left child Q. We then visit the right subtree of Q, which consists of Z and Y. Finally, we visit the right subtree of U, which consists of V and P. Therefore, the correct sequence of nodes visited in a post-order traversal of the binary tree T is U X W Q Z Y V P.
4.
What does a run-time analysis usually count?
Correct Answer
A. The number of arithmetic and other operations required for the program to run
Explanation
A run-time analysis usually counts the number of arithmetic and other operations required for the program to run. This analysis helps in understanding the efficiency and performance of the program by measuring the computational complexity. By counting the number of operations, developers can identify bottlenecks and optimize the program to improve its efficiency.
5.
Figure 2 is the array representation of a binary tree shown in Figure 1. What should be put into space "a"?
Correct Answer
C. 4
Explanation
In the given binary tree represented by Figure 2, the number 4 should be put into space "a". This is because the numbers in the array representation of a binary tree are placed in a specific order. The order in which the numbers are placed is determined by traversing the binary tree in a specific manner, such as in a pre-order, in-order, or post-order traversal. Without further information about the traversal method used, it is difficult to determine the exact position of "a" in the array. However, based on the given options, the number 4 is the only logical choice to put into space "a".
6.
Consider the following pseudo code:
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 "cartets"?
Correct Answer
D. Stetrac
Explanation
The given pseudo code reads each character in the word "cartets" and pushes them onto the stack. Then, it writes the top character of the stack to the screen and pops it off the stack until the stack becomes empty. Therefore, the characters are written in reverse order, resulting in "stetrac" being written to the screen.
7.
Given a graph G in the box. What is the order of nodes visited using DFS, starting from node a
Correct Answer
B. A c b g l k h i j f e d
Explanation
The order of nodes visited using DFS, starting from node a, is as follows: a, c, b, g, l, k, h, i, j, f, e, d.
8.
Which of the following stack operations could result in stack underflow?
Correct Answer
B. Pop
Explanation
The stack underflow occurs when we try to remove an element from an empty stack. In other words, if we try to perform the "pop" operation on an empty stack, it will result in a stack underflow. Therefore, the correct answer is "pop".
9.
Which of the following is an appropriate description concerning the list and/or array structures?
Correct Answer
D. The list structure allows any data to be inserted or deleted simply by modifying pointers. But, after the data was deleted, the cells that contained the data remain as garbage in memory
Explanation
The correct answer states that the list structure allows for the insertion or deletion of data by modifying pointers. However, it also mentions that after the data is deleted, the cells that contained the data remain as garbage in memory. This means that the memory occupied by the deleted data is not automatically freed up, potentially leading to memory wastage.
10.
There are two important operations on a stack: PUSH and POP. PUSH adds the new data to the top of the stack leaving previous data below, and POP removes and returns the current top data of the stack. When the operations shown below are sequentially executed, which of the following is the correct combination of the values x and y?
Here, the size of the stack is big enough to hold the entire data. “PUSH(a)” inserts the data a into the stack, and “POP(b)” removes the data b from the stack.
[Operations]
PUSH (5);
PUSH (3);
PUSH (6);
PUSH (1);
x = POP ( );
PUSH (7);
y = POP ( );
What are the value of X and Y?
Correct Answer
B. Answer b)
Explanation
The given operations are executed sequentially. First, the values 5, 3, 6, and 1 are pushed onto the stack. Then, the value of x is obtained by popping the topmost element, which is 1. After that, the value 7 is pushed onto the stack. Finally, the value of y is obtained by popping the topmost element, which is 7. Therefore, the correct combination of x and y is 1 and 7, respectively.