(2). Assume there is a total ordering of data, and your application requires frequent range queries to the data (i.e. retrieving data with keys in the range [lower _bound, upper _bound]). Range query to your data can be efficiently implemented with the data structure _____.

1. (5%) In the Knuth-Morris-Pratt string-pattern matching algorithm, we need a failure function. Compute the failure function for the following pattern.

2. (5%) In a binary tree, there may be many null pointers. We may use these pointers to point to in-order predecessors and successors. These pointers are called thread pointers. Draw all the thread pointers in the following binary tree.

3. (5%) Assume there are only variables such as a, b, c, and binary operators, such as t, -, *, and /in an arithmetic expression. The expression is fully parenthesized, that is, there is a pair of parentheses for each operator. Examples are (a+b)-c)/d), ((a+(c-(b-a))/d)+1), (((a+b)+c)+d)+e), etc. Write a program that translated a fully-parenthesized expression into its prefix form. The input is a correct, fully-parenthesized arithmetic expression, stored in a read-only array. This program can use 3queues together with the usual stack pointers. You cannot use additional storage, such as arrays, except a fixed number of simple temporary variables. In the program, you can only push, pop, examine the contents of a cell, and compare two contents of two cells for equality. The program can scan the input from left to right only once. It cannot store the input expression somewhere else for repeated examinations. You can use C or Java or Pascal or other similar programming languages to write this program. Your program should clearly show the underlying algorithm. Minor details and errors in the program will be tolerated. In particular you need to explain your data structures with examples.

4. (5%) Assume each node contains a data, Ithread, rthread, Icbild, and rchild fields. Ithread and rthread are Boolean fields. Icbild and rchild are pointers. If Ithread is true, the Ichild field will be considered as a left thread； otherwise, Ichild will point to the left child. Similarly for the rthread and rchild fields. Consider the following algorithm for pre-order traversal of a binary tree using thread pointers: Please fill in the missing line 6 with an assignment statement.

(a)n2n+5．32n=θ(n2n). 

(b) 3n1.0001+ 99n log n =0(n1.1).

(c)n log(2n)=O(n ln n).

(d)n2log(5n)=θ(n2).

(e) n0.999 log n=θ(n2).

(1). If your application requires frequent random access (i.e. retrieving the value for a given key), using the data structure _____ to store the data will give the longest average access time.

102年 - 102 國立交通大學_碩士班考試入學試題_資訊聯招：資料結構與演算法#113274