# Dsa_3

10 Questions | Total Attempts: 67  Settings  Related Topics
• 1.
Which of the following stack operations could result in stack underflow?
• A.

Is_empty

• B.

Top

• C.

Pop

• D.

Push

• 2.
Which of the following is the appropriate statement concerning data sorting methods?
• A.

The “bubble sort” method determines an intermediate reference value and divides the elements into two groups of “larger” values and “smaller” values. This operation is then repeated recursively on these two groups.

• B.

The “shell sort” method repeatedly compares two adjacent elements and swaps them if the first element is larger than the second.

• C.

The “quick sort” method sorts each substring composed of elements extracted at regular intervals, and then the interval is further decreased and the same operation is performed again. This operation is repeated until the interval becomes 1.

• D.

The “heap sort” method builds an ordered tree from the unsorted portion of the elements, extracts the maximum or minimum value from this ordered tree, and moves it to the sorted portion. This operational sequence is then repeated to gradually shrink the unsorted portion.

• 3.
Which formula is the best approximation for the depth of a heap with n nodes?
• A.

The square of n

• B.

N

• C.

The number of digits in n (base 10)

• D.

Log (base 2) of n

• 4.
Define a recursive function F( n ) as following: If n > 0 then F( n ) = n x F(n-1) If n = 0 then F( n ) = 1. As such, what is the value of F(5)?
• A.

5

• B.

120

• C.

15

• D.

1

• 5.
Among Breadth-first search and Depth-first search, which graph traversal algorithm uses a queue to keep track of vertices that need to be processed?
• A.

Only Depth-First Search

• B.

• C.

Both Breadth-first search and Depth-first search

• D.

None of them

• 6.
Given a tree T in the box. What is the order of nodes visited using a pre-order traversal?
• A.

X S Z Y R W P U T V

• B.

X Z Y S P W U V T R

• C.

R S X Y Z T U W P V

• D.

R S T X Y U V Z W P

• 7.
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 cursor points to the tail node of the list?
• A.

• B.

(cursor->data( ) == NULL)

• C.

(cursor == NULL)

• D.

(cursor->data( ) == 0.0)

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

2

• B.

3

• C.

4

• D.

5

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

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.

• B.

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.

• C.

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.

• D.

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.

• 10.
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"?
• A.

Ccaarrtteettss

• B.

Stetrac

• C.

Cartets

• D.

Serc