國立嘉義大學九十五學年度
資訊管理學系碩士班招生考試（乙組）試題
科目：資料結構
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