Questions need to be answered
1) 2) 3) Suppose linear search is used to search for a given element in an array with 10,000 elements, which of the choices refers to the number of comparisons in the worst case? · a. 1 · b. 5000 · c. 9999 · d. 10000 4) Suppose binary search is used to search for a given element in an array with 4,000 elements, which of the choices refers to the number of comparisons in the worst case? · a. 10 · b. 11 · c. 12 · d. 13 5) which of the choices describes the time complexity of the power method below, written in java, most appropriately in terms of Big-O notation? public static double power (double a, int n) { if(n==0) return 1; else return a * power (a, n-1); } · a. O(n) · b. O(a) · c. O(n^a) · d. O(a^n) 6) Suppose Merge Sort is used to sort an array with 10,000 elements, which of the choices is closest to the approximate levels of recursion? · a. 10 · b. 13 · c. 16 · d. 19 7) Suppose Merge Sort is used to sort an array with 1,000 elements, which of the choices refers to the maximum number of comparisons at a level of recursion? · a. 1 · b. 500 · c. 999 · d. 1000 8) which of the choices refer to the time complexity of Quick sort on average in terms of Big-O notation, give an array of size n? · a. O(n) · b. O(log n) · c. O(n^2) · d. O(n log n) 9) which of the choices is an in-place sort algorithm? · a. Merge sort · b. Radix sort · c. Bucket sort · d. None of above 10) which of the choices is an in-place sort algorithm? · a. Selection sort · b. Radix sort · c. Shell sort · d. None of above 11) which of the choices is a correct statement about trees? · a. A tree must have at least one node. · b. Each non-leaf node in a binary tree must have two children. · c. A degenerate tree is a binary tree. · d. The height of a tree with only one node is 1. 12) Suppose the balance factor of a node in an AVL tree is -2 which of the choices explains it correctly? · a. Doubly left high. · b. Doubly right high. · c. Left high. · d. Right high. 13) Which of the choices is an incorrect statement about Red Black Trees? · a. The root is always black. · b. The newly inserted node is always colored black before repair. · c. If the shortest path has k nodes, then the longest can have at most 2k nodes. · d. A nodes uncle refers to the only sibling of its parent. 14) Given a B-tree of height 4, which of the choices refers to the number of write assesses needed to enable an insertion with splitting the root? · a. 11 · b. 10 · c. 9 · d. 8 15) which of the choices is correct regarding coding schemes? · a. A coding scheme is allowed to product ambiguous messages. · b. Decoding requires look ahead. · c. More frequently used symbols correspond to longer code words. · d. None of above 16) Perform the bubble sort algorithm on the integer array A and show the array after each pass. A: 5, 1, 9,7,1 Your answer must be provided in the following text box: 17) Perform the Selection sort algorithm on the integer array A and show the array after each pass. A: 5, 1, 9,7,1 Your answer must be provided in the following text box: 18) Perform the insertion sort algorithm on the integer array A and show the array after each pass. A: 5, 1, 9,7,1 Your answer must be provided in the following text box: 19) Perform the Shell sort algorithm on the integer array A with the gap sequence of 4, 2, and 1, and show the array after each H- sort. A: 16, 6, 14, 12, 8, 18, 4, 20, 10 Your answer must be provided in the following text box: 20) Perform the radix sort algorithm on the integer array A and show the array after each pass. A: 31, 90, 87, 62, 0, 22, 77, 69, 18, 45, 25, 14, 19 Your answer must be provided in the following text box: 21) Create a binary search tree by inserting the following elements in the order they are given, show the tree after each insertion. 10,6,4,12,8,14 Your answer must be provided below by attaching an image file that contains the required content. Such an image file can be either a digital drawing or a photograph of a hand drawing. 22) List the elements in the order of visitation of the final tree in Q18. A using the post order traversal. Your answer must be provided in the following text box. 23) Delete 10 from the tree created in Q18. A in the order they are given show the tree after deletion. Your answer must be provided below by attaching an image file that contains the required content. Such an image file can be either a digital drawing or a photograph of a hand drawing. 24) Create a AVL tree by inserting the following elements in the order they are given, show the tree after each insertion and rotation. 9, 7,3,5,4,10 Your answer must be provided below by attaching an image file that contains the required content. Such an image file can be either a digital drawing or a photograph of a hand drawing. 25) 26) Suppose the hash function maps an integer n to location n mod 7. Insert the following elements into a hash table of size 7 in the order given using linear probing. 12, 19, 20, 6, 14 For each insertion, show how you work out which locations to probe and what locations you actually need to probe(i.e., to try) for the insertion. Your answer must be provided below by attaching an image file that contains the required content. Such an image file can be either a digital drawing or a photograph of a hand drawing. 27) Suppose the hash function maps an integer n to location n mod 7. Insert the following elements into a hash table of size 7 in the order given using quadratic probing. 12, 19, 20, 6, 14 For each insertion, show how you work out which locations to probe and what locations you actually need to probe(i.e., to try) for the insertion. Your answer must be provided below by attaching an image file that contains the required content. Such an image file can be either a digital drawing or a photograph of a hand drawing. 28) 29) 30) Create a heap by inserting the following elements in the order they are given. Show the heap after each insertion and trickle. The heap is implemented to keep the largest key at the root. 4, 2, 5, 6, 10 Your answer must be provided below by attaching an image file that contains the required content. Such an image file can be either a digital drawing or a photograph of a hand drawing. 31) Represent the tree created in Q22. A as an array. Your answer must be provided in the following text box. 32) Create a Huffman tree to encode the message. Look OUT the initial queue of the Huffman tree is shown below L1, k1, T1, U1,
1, 03 Continue the process and the process and always place the newly created tree on the right of the other trees with the same priority. Your answer must be provided below by attaching an image file that contains the required content. Such an image file can be either a digital drawing or a photograph of a hand drawing. 33) Draw the code table, including the code for characters that appear in the message in Q23-A. The letters are to be listed in alphabetical order. 34)