Name:_______________________



Name:_______________________

Covers Chapters 23-26

50 min |CSCI 2410 Data Structures and Algorithms

Armstrong Atlantic State University

Instructor: Y. Daniel Liang | |

Part I: Multiple-Choice Questions: (1 pts each)

1 O(1) is ________.

A. linear time

B. log-linear time

C. logarithmic time

D. constant time

2 Estimating algorithm efficiency is ________

A. to estimate their growth function.

B. to measure their actual execution time.

C. to estimate their execution time.

3 Which data structure is appropriate to store customers in a clinic for taking flu shots?

A. Stack

B. Linked List

C. Priority Queue

D. Queue

E. Array List

4 Suppose the rule of the party is that the participants who arrive later will leave earlier. Which data structure is appropriate to store the participants?

A. Stack

B. Array List

C. Queue

D. Linked List

5 To add a new node, you need to start a process by first placing it as _______ and move it up to maintain the heap property.

A. the left child of the root

B. the new root

C. the right child of the root

D. the last node in the heap

6 The average-time complexity for merge sort is _________

A. O(1)

B. O(n)

C. O(nlogn)

D. O(n*n)

E. O(logn)

7 The worst-time complexity for quick sort is _________

A. O(1)

B. O(n)

C. O(logn)

D. O(nlogn)

E. O(n*n)

8 The worst-time complexity for heap sort is _________

A. O(n*n)

B. O(nlogn)

C. O(n)

D. O(1)

E. O(logn)

9 The worst-time complexity for merge sort is _________

A. O(1)

B. O(n*n)

C. O(logn)

D. O(nlogn)

E. O(n)

Part II:

1. (1 pts) Show the time complexity of the following program:

for (int k = 0; k < 10; k++) {

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

System.out.print('*');

}

}

}

2. (1 pts) Given the array {45, 11, 50, 59, 60, 2, 4, 7, 10}, apply the bubble sort. Show the contents in the array after finishing the first phase.

3. (2 pts) Add the elements 40, 135, 9, 11, 3, 102, into a heap in this order. Draw the final heap.

4. (2 pts) Given the following heap, show the resulting heap after removing 62 from the heap.

[pic]

5. (2 pts) Add the elements 40, 135, 9, 11, 3, 102, into a binary search tree in this order. Draw the final binary search tree.

6. (5 pts) Give the inorder, preorder, postorder, breadth-first, and depth-first search of the following binary tree.

[pic]

Inorder:

Preorder:

Postorder:

Breadth-first:

Depth-first search:

Part III: Complete the following program.

1. (10 pts) Add the following method in the BinaryTree class to return the number of the leaves as follows:

/** Returns the number of leaf nodes */

public int getNumberOfLeaves()

Keys:

1 O(1) is ________.

A. linear time

B. log-linear time

C. logarithmic time

D. constant time

Key:d

#

2 Estimating algorithm efficiency is ________

A. to estimate their growth function.

B. to measure their actual execution time.

C. to estimate their execution time.

Key:a

#

3 Which data structure is appropriate to store customers in a clinic for taking flu shots?

A. Stack

B. Linked List

C. Priority Queue

D. Queue

E. Array List

Key:d

#

4 Suppose the rule of the party is that the participants who arrive later will leave earlier. Which data structure is appropriate to store the participants?

A. Stack

B. Array List

C. Queue

D. Linked List

Key:a

#

5 To add a new node, you need to start a process by first placing it as _______ and move it up to maintain the heap property.

A. the left child of the root

B. the new root

C. the right child of the root

D. the last node in the heap

Key:d

#

6 The average-time complexity for merge sort is _________

A. O(1)

B. O(n)

C. O(nlogn)

D. O(n*n)

E. O(logn)

Key:c

#

7 The worst-time complexity for quick sort is _________

A. O(1)

B. O(n)

C. O(logn)

D. O(nlogn)

E. O(n*n)

Key:e

#

8 The worst-time complexity for heap sort is _________

A. O(n*n)

B. O(nlogn)

C. O(n)

D. O(1)

E. O(logn)

Key:b

#

9 The worst-time complexity for merge sort is _________

A. O(1)

B. O(n*n)

C. O(logn)

D. O(nlogn)

E. O(n)

Key:d

Part II:

1. O(n^2)

2. (1 pts) Given the array {45, 11, 50, 59, 60, 2, 4, 7, 10}, apply the bubble sort. Show the contents in the array after finishing the first phase.

Answer: 11, 45, 50, 59, 2, 60, 4, 7, 10, 60

3. (2 pts) Add the elements 40, 135, 9, 11, 3, 102, into a heap in this order. Draw the final heap.

[pic]

4. (2 pts) Given the following heap, show the resulting heap after removing 62 from the heap.

[pic]

5. (2 pts) Add the elements 40, 135, 9, 11, 3, 102, into a binary search tree in this order. Draw the final binary search tree.

[pic]

6. (5 pts) Give the inorder, preorder, postorder, breadth-first, and depth-first search of the following binary tree.

[pic]

Inorder: A F G M R T

Preorder: G F A R M T

Postorder: A F M T R G

Breadth-first: G F R A M T

Depth-first search: G F A R M T

Part III: Complete the following program.

1. (10 pts) Add the following method in the BinaryTree class to return the number of the leaves as follows:

/** Returns the number of leaf nodes */

public int getNumberOfLeaves()

/** Displays the leaf nodes */

public int getNumberOfLeaves() {

return getNumberOfLeaves(root);

}

/** Returns the number of leaf nodes */

public int getNumberOfLeaves(TreeNode root) {

if (root == null)

return 0;

else if (root.left == null && root.right == null)

return 1;

else

return getNumberOfLeaves(root.left) + getNumberOfLeaves(root.right);

}

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download