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.
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.
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.
4. (2 pts) Given the following heap, show the resulting heap after removing 62 from the heap.
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.
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<E> root) {
if (root == null)
return 0;
else if (root.left == null & root.right == null)
return 1;
else
return getNumberOfLeaves(root.left) + getNumberOfLeaves(root.right);
}
8