複選題

14. Consider the following recursive definition for a language:

Which of the following strings are in this language?
(A) + ++
(B) + − −
(C) – + +
(D) + .

10. Suppose we start with an empty max-heap of integers, and enter the numbers 20 through 30 into this heap in order. Let the resulting max-heap be stored in an array. Then remove the root node from the heap. What index is 28 stored at in the array?(A) 4；(B) 3；(C) 2；(D) 1.

11. An empty hash table has a capacity of 13, and you insert six entries with keys 21, 16, 8, 10, 22, 34, and 49. Using linear probing and the hash function 1%(13), what index 49 is stored at in the table? Note that % is the remainder operator, e.g., (100)%(13)=9.(A) 0；(B) 5；(C) 11；(D) 8.

12. Consider the integers 30, 41, 25, 29, 94, 37, 70, 23, 65, 75, 68, 67 in order to create an AVL tree. Which of the following about the tree is false?(A) The node for 37 is a leaf node.(B) The root node is 41.(C) The node for 70 has only one child.(D) The height of the tree is 4.

13. Consider the integers 30, 41, 25, 29, 94, 37, 70, 23, 65, 75, 68, 67 in order to create a 2-3 tree. Which of the following about the tree is true?(A) The node for 37 is not a leaf node.(B) The root node is 41.(C) The node for 70 has only one child.(D) The height of the tree is 3.

複選題15. Consider an array A containing 10 integers 42, 3, 17, 22, 32, 7, 12, 74, 47, 8. We use quicksort to sort the integers in ascending order. The first element of the underlying sequence is used as the pivot. Which of the following are false after the first partition?(A) A[5] = 7(B) A[4] = 42(C) A[8] = 47(D) A[0] = 3

16. Which of the following are true?(A) The worst-case running time for quicksort is O(nlogn).(B) No additional memory for array is required for quicksort.(C) The best-case running time for bubble-sort is O(nlogn).(D) The best-case running time for insertion-sort is O(n).

複選題17. Consider an array A containing, initially, 12 integers 30, 41, 25, 29, 94, 37, 70, 23, 65, 75, 68, 67. We convert A into a maxheap. Which of the following are false?(A) A[2] = 70(B) A[5] = 68(C) A[8] = 23(D) A[11] = 30

複選題18. Consider the integers 30, 41, 25, 29, 94, 37, 70, 23, 65, 75, 68, 67 in order to create a binary search tree. Now delete 70 from the tree. Note that the replacement should be the least of the numbers equal to or greater than the deleted element. Which of the following about the resulting tree are true?(A) The node for 75 has only one child.(B) The node for 65 has a left child.(C) The node for 41 has two children.(D) The node for 65 is a child of the node for 94.

複選題19. Which of the following are true?(A) The minimum height of a binary tree with 100 nodes is 6； (B) The minimum height of a tree with 15 nodes is 2； (C) The maximum height of a tree with 20 nodes is 20； (D) The maximum height of a complete binary tree with 200 nodes is 8.

1. 蘋果公司日前釋出心電圖偵測(ECG)App 及心律不整偵測功能的 Watch OS 5.1.2 版，讓 Apple Watch 成為診斷用穿戴裝置；利用 LED 光測器，透過綠光打出在皮膚上、藉由血液的吸收量差異來計算心跳的頻率，此技術屬於下列何種應用？(A)混合實境(B)體感技術(C)Face ID(D)生物辨識