國立嘉義大學九十五學年度 資訊管理學系碩士班招生考試（乙組）試題 科目：資料結構 1. Suppose there is a row-major array A[n][m], the address, with decimal system, of A[2][10], A[10][2], and A[20][20] is 740, 1508, and 2580, respectively. The size of each array element is d bytes. (To answer the following questions, you MUST write down the details of equations.) (1) Find d. (3%) (2) Find m. (3%) (3) What is the beginning address of array A? (2%) (4) What is the address of A[25][0]? (2%) 2. (1) What is “AVL tree”? Why do we need it? (5%) (2) Suppose that tree T, shown on the right side, is the original AVL tree. What is the new AVL tree T1 after inserting 27? (5%) 3. (1) For the following AOE network, what is the shortest time to complete the project? (4%) (2) What are the earliest and latest start times of activity a5? (6%) (3) How are AOE networks applied to project management? (5%) 4.Generally, the array structure is suitable for stacks but not for FIFO queues. Give your explanation. (5%) 5. Explain, in a nonempty binary tree, the number of leaf nodes is one more than the number of nodes of degree 2. (5%) 6. (1) What is a “stable” sorting method? (2%) (2) Which sorting methods: insertion sort, quick sort, merge sort, radix sort, heap sort, and bubble sort are stable? (3%) 7. Consider inserting the keys 13, 21, 34, 5, 17, 26, 19, 84, 52 into a hash table of length m=13 using open addressing with primary hash function h1(k)=k mod m. Illustrate the result of inserting these keys using linear probing (h(k, i)=(h1(k) + i) mod m), using quadratic probing (h(k, i)=(h1(k) + c1毕 i +c2毕 i2) mod m) with c1=2 and c2=5, and using double hashing (h(k, i)=(h1(k) + i 毕 h2(k)) mod m) with h2(k)=1+(k mod (m-1)). (15%) 8. Use the Master Method to give tight asymptotic bounds for the following recurrences. (12%) (1) T(n)=9T(n/3)+n (2) T(n)=3T(n/4)+nlgn (3) T(n)=T(2n/3)+1 Hint: T(n)=aT(n/b)+f(n) can be bounded asymptotically as follows: (1) If f(n)=O(nlogba-讨) for some constant 讨>0, then T(n)= 针(nlogba). (2) If f(n)=针(nlogba), then T(n)= 针(nlogbalgn). (3) If f(n)=纹(nlogba+讨) for some constant 讨>0, and if af(n/b) 昼 cf(n) for some constant c<1 and all sufficiently large n, then T(n)= 针(f(n)). 9. Illustrate the operation of QUICKSORT’s PARTITION on the array A={13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21}. What is the values of j and A[j] when the PARTITION(A, 0, 11) is implemented and returns? (8%) Hint: PARTITION(A, p, r) 1.x=A[p] 2.i=p-1 3.j=r+1 4.while TRUE 5. do repeat j=j-1 6. until A[j]昼x 7. repeat i=i+1 8. until A[i]产x 9. if i<j 10. then exchange A[i]<->A[j] 11. else return j 10.Queue is a first-in-first-out (FIFO) data structure. It is implemented by the linear linked list which is stored in the matrix as the following table. The “X” is the buffer for inserting or deleting data. (15%) [ADDR] address 1 2 3 4 5 6 7 8 9 10 [DATA] data 38 70 19 56 79 18 2 66 30 43 [LINK] link 9 5 1 0 0 3 6 2 10 4 AVAIL head tail X Next available address 8 7 4 56 (1) Write out the data value in the queue sequentially from the head. (2) Insert 99 into the queue and show the result table (structure) from modifying above structure assuming the next available address is 2. (3) From the result of Item (2), pop an element out and show the table (structure). V4 a0=12 a4 a2=3 =6 a1=4 start finish V1 V０ V2 a V3 3=2 a５=3 V0 V1 V2 V3 V4 迳 1 迳 4 迳 2 迳 3 迳 4 迳 4 20 10 0 30 25 T: 5 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.130.189.43