Data Structure Midterm (20070514)

(5%) Show that 6*2n+n2 = O(2n). Please
use proof by induction if you need to prove some inequality.
Answer: One way to do this is to prove that
6*2n+n2≦7*2n for n≧4, or equivalently,
n2≦2n for n≧4. We shall use proof by induction.

Induction base: When n=4, n2=2n=16 holds.

Induction hypothesis: When n=k, k2≦2k holds.

Induction step: When n=k+1, we have (k+1)2 =
k2+2k+1 ≦ k2+k2 = 2×k2 ≦
2×2k = 2k+1

(10%) The failure function for KMP (Knuth-Moris-Pratt) algorithm is shown
next: void fail(char *pat){
int n=strlen(pat);
failure[0]=-1;
for (j=1; j<n; j++){
i=failure[j-1];
while ((pat[j]!=pat[i+1]) && (i>=0))
i=failure[i];
if (pat[j]==pat[i+1])
failure[j]=i+1;
else
failure[j]=-1;
}
}
Compute the failure function for each of the following patterns:

(5%) abcadabcab

(5%) abcxxabcxxyyabcxxabcxy

Answer:

-1 -1 -1 0 -1 0 1 2 3 1

-1 -1 -1 -1 -1 0 1 2 3 4 -1 -1 0 1 2 3 4 5 6 7 8 -1

(10%) Suppose we have the following declaration for a linked list: typedef struct list_node *list_pointer;
typedef struct list_node {
char data;
list_pointer link;
};
Write a C function invert(list_pointer lead) that can invert the
list pointed to by lead and return the pointer to the inverted list. (Note
that your function should not have more than 15 lines.)
Answer: list_pointer invert(list_pointer lead){
list_pointer middle=NULL, trail;
while (lead){
trail=middle;
middle=lead;
lead=lead->link;
middle->link=trail;
}
return(middle);
}

(30%) Give answers to the following short questions about trees. You do
not need to prove them.

(3%) What is the maximum number of nodes on level i of a binary tree?

Answer: 2i-1

(3%) What is the maximum number of nodes in a binary tree of depth
k?
Answer: 2k-1

(3%) For any nonempty binary tree T, Let n0 be the number of
leave nodes and n2 the number of nodes of degree 2. What the
relationship between n0 and n2?
Answer: n0 = n2+1

(3%) What is the depth of a complete binary tree with n nodes?

Answer: floor(log2n + 1) or
ceil(log2(n+1))

(3%) What are the four 4 methods for tree traversal? Which one of these
methods needs the use of a queue?
Answer: Preorder,
inorder, postorder, level order. The method of level-order traversal
requires the use of a queue.

(3%) How many null links do we have in a n-node binary tree of
linked representation?
Answer: n+1

(3%) Use the left child-right sibling representation to convert the
following tree into a binary tree.

Answer:

(3%) In order to access the tree nodes quickly, the binary tree in the
previous question is stored level-by-levey in a one-dimensional array
A[1..n]. What are the indices of nodes g, j are?
Answer: g ---> 21, j ---> 171

(3%) Draw the binary tree if the preorder sequence is [1, 2, 3, 4, 5, 6,
7] and the inorder sequence is [2, 4, 3, 1, 6, 5, 7].
Answer:

(3%) Draw the binary tree if the postorder sequence is [7, 4, 2, 5, 6,
3, 1] and the inorder sequence is [7, 4, 2, 1, 5, 3, 6].
Answer:

(10%) Please use a stack to indicate how to convert the
a/((a+b)*c-d)*e-a*c into a postfix form (You should draw the stack status
after each step).
Answer: (In the following step, the
bottom of the stack is the first element.)

Token

Stack

Output

a

a

/

/

a

(

/(

a

(

/((

a

a

/((

aa

+

/((+

aa

b

/((+

aab

)

/(

aab+

*

/(*

aab+

c

/(*

aab+c

-

/(-

aab+c*

d

/(-

aab+c*d

)

/

aab+c*d-

*

*

aab+c*d-/

e

*

aab+c*d-/e

-

-

aab+c*d-/e*

a

-

aab+c*d-/e*a

*

-*

aab+c*d-/e*a

c

-*

aab+c*d-/e*ac

eos

aab+c*d-/e*ac*-

(10%) Please use a stack to indicate how to evaluate the postfix
expression 62/3-42*+ step by step. (You should draw the stack status after
each step.)
Answer: (In the following step, the bottom
of the stack is the first element.)

Token

Stack

6

6

2

6 2

/

3

3

3 3

-

0

4

0 4

2

0 4 2

*

0 8

+

8

(10%) Draw the max-heap tree after the following operations are performed
beginning with an empty heap: insert 43, insert 31, insert 68, insert 24,
delete-max, insert 51, insert 44, insert 53, insert 69, insert 71, delete-max.

Answer:

(15%)

(5%) Let bn be the number of different permutations
obtainable by passing the numbers 1, 2, 3, ..., n through a stack and
deleting in all possible ways. Give the recursive formula for bn.
(Be sure to specify the initial condition for your formula.)
Answer: bn = Si=0n-1 bi
bn-i-1, b0=1

(5%) Let cn be the number of different ways to compute the
product of n matrices. What is the relationship between bn and
cn? Why?
Answer: cn+1 =
bn
(You need to state the reason.)

(5%) Derive an explicit formula for bn using the method
described in the class.
Answer: bn =
Cn2n/(n+1)
(You need to show how you derive the
answer.)