Data Structure And Algorithm Quiz: Test!

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?

A shortest-path algorithm.

A minimum spanning tree algorithm.

Breadth first search.

Depth first search.

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.

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?

(cursor->link( ) == NULL)

(cursor->data( ) == 0.0)

(cursor->data( ) == NULL)

(cursor == NULL)

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.

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. What does a run-time analysis usually count?

The number of arithmetic and other operations required for the program to run

The number of seconds plus the number of megabytes

The number of seconds required for the program to run

The number of megabytes required for the program to run

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.

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.

4. Which of the following represents the sequence of nodes visited in a post-order traversal of the binary tree T shown below?

U X Z Q W Y V P

X Z U W Y Q V P

U X W Q Z Y V P

U Q X W P V Z Y

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.

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.

5. Figure 2 is the array representation of a binary tree shown in Figure 1. What should be put into space "a"?

3

5

4

2

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".

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. 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?

Answer a)

Answer b)

Answer c)

Answer d)

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.

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.

7. 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"?

Ccaarrtteettss

Cartets

Serc

Stetrac

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.

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.

8. Which of the following stack operations could result in stack underflow?

Top

Pop

Is_empty

Push

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".

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. Given a graph G in the box. What is the order of nodes visited using DFS, starting from node a

A b c d e f k g h i j l

A c b g l k h i j f e d

A f e d c k g b h i j l

A c d e f k b g h i j l

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.

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.

10. Which of the following is an appropriate description concerning the list and/or array structures?

Using a subscript for each element in an array, quick access to any element can be achieved. The array structure allows any data to be inserted or deleted simply by modifying pointers.

The number of operations is fixed in inserting or deleting an element in an array; it does not depend on the position of the element in the array

The list structure is similar to the array structure in that all data elements of the same type are sequentially lined up. In the list structure, the logical arrangement is the same as the physical arrangement.

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

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.

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.