Algorigthms and Data Structures Step 1 of 2 50% 姓名*邮箱* 微信号* 1. A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.*A. 46, 42, 34, 52, 23, 33B. 34, 42, 23, 52, 33, 46C. 46, 34, 42, 23, 52, 33D. 42, 46, 33, 23, 34, 522. A language with string manipulation facilities uses the following operations: head(s)- returns the first character of the string s; tail(s)- returns all but the first character of the string s; concat(s1, s2)- concatenates string s1 with s2. If s= acbc, the output of concat(head(s), head(tail(tail(s)))) is:*A. abB. baC. acD. as3. An array A consists of n integers in locations A[0], A[1] ....A[n-1]. It is required to shift the elements of the array cyclically to the left by k places, where 1 <= k <= (n-1). An incomplete algorithm for doing this in linear time, without using another array is given below. Complete the algorithm by filling in the blanks. Assume all the variables are suitably declared.* (Each answer includes 5 pieces of code for 5 blanks in order, separated by ‘;’)A. i > min; j!= (n+i)mod n; A[j + k]; temp; i + 1 ;B. i < min; j!= (n+i)mod n; A[j + k]; temp; i + 1;C. i > min; j!= (n+i+k)mod n; A[(j + k)]; temp; i + 1;D. i < min; j!= (n+i-k)mod n; A[(j + k)mod n]; temp; i + 1;4. Following is an incorrect pseudocode for the algorithm which is supposed to determine whether a sequence of parentheses is balanced: declare a character stack while ( more input is available) { read a character if ( the character is a '(' ) push it on the stack else if ( the character is a ')' and the stack is not empty ) pop a character off the stack else print "unbalanced" and exit } print "balanced"* Which of these unbalanced sequences does the above code think is balanced? A. ((())B. ())(()C. (()()))D. (()))()5. Following is C like pseudo code of a function that takes a Queue as an argument, and uses a stack S to do processing.*A. Removes the last from QB. Keeps the Q same as it was before the callC. Makes Q emptyD. Reverses the Q6. Consider the following program that attempts to locate an element x in a sorted array a[] using binary search. Assume N>1. The program is erroneous. Under what conditions does the program fail?*A. x is the last element of the array a[]B. x is greater than all elements of the array a[]C. Both of the AboveD. x is less than the last element of the array a[]7. Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?*A. P, Q, R, S, T, UB. P, Q, R, U, S, TC. P, Q, R, U, T, SD. P, Q, T, R, U, S8. Consider the undirected graph below: Using Prim's algorithm to construct a minimum spanning tree (MST) starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?*A. (E, G), (C, F), (F, G), (A, D), (A, B), (A, C)B. (A, D), (A, B), (A, C), (C, F), (G, E), (F, G)C. (A, B), (A, D), (D, F), (F, G), (G, E), (F, C)D. (A, D), (A, B), (D, F), (F, C), (F, G), (G, E)9. A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of length m and n respectively, with indexes of X and Y starting from 0. We wish to find the length of the longest common sub-sequence(LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of The LCS of X[m] and Y[n] is given below:*A. expr1 ≡ l(i-1, j) + 1B. expr1 ≡ l(i, j-1)C. expr2 ≡ max(l(i-1, j), l(i, j-1))D. expr2 ≡ max(l(i-1,j-1),l(i,j))10. Let A be a square matrix of size n x n. Consider the following program. What is the expected output?*A. The matrix A itselfB. Transpose of matrix AC. Adding 100 to the upper diagonal elements and subtracting 100 from diagonal elements of AD. None of the above
