第1頁共2頁
資料結構
課堂作業二
系級： 座號： 姓名：
一、是非題(24%)
( )1.A data type is a collection of objects and a set of operations that act on those objects.
( )2. If we trace out the instructions of an algorithm, then for all cases, the algorithm should terminate after a finite number of steps.
( )3. The time complexity of a program is the amount of computer time it needs to run to completion.
( )4. iff there exist positive constants c1, c2, and n0 such that for all n, .
( )5. iff there exist positive constant c and n0 such that for all n, .
( )6.A stack is an ordered list in which all insertions take place at one end and all deletions take place at the opposite end.
二、(20%)Which ones are correct?
( ) 1. If , then
(a) (b) (c)
(d) (e) (f)
( )2. (a) (b) (c)
(d)
三、(7%)Please order the following computing times:
,,,,,,
四、(8%)(簡答題) What are the disadvantages of representing matrices by arrays?
五、(8%)If we have the declaration A[1..15][1..10][1..20] and is the address of A[1][1][1], using row major order, what is the address for A[4][7][6]?
六、(15%)If pattern pat = a b c a b c a b c a c a b, please calculate the values of its failure function.
j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
pat a b c a b c a b c c c a b c c
f
七、(10%) A stack may be regarded as a railway switching network like the one in the following figure. Cars numbered 1, 2, …, n are on the line at the left, and it is desired to rearrange (permute) the cars as they leave on the right-hand track. A car that is on the spur (stack) can be left there or sent on its way down the right track, but it can never be sent back to the incoming track. For example, if n=3, and we have the cars 1,2,3 on the left track, then 3 first goes to the spur. We could then send 2 to the spur, then on its way to the right, then send 3 on the way, then 1, ogtaining the new order 1,3,2.
If n = 5, which permutations that can be obtained by using the stack?
( ) (a) 5 4 3 2 1 (b) 5 2 4 3 1 (c) 2 3 5 4 1 (d) 1 3 2 4 5 (e) 4 3 2 1 5
八、(10%) What is the Knuth-Morris-Pratt algorithm (string pattern matching) ?
1