推 andy74139 :已收錄至精華區!! 11/15 23:28
推 abacada :推鋼琴社的學長 竟然這麼快就回來教書了 時光飛逝... 11/16 03:57
課程名稱：資料結構與演算法上
課程性質：必修
課程教師：蔡欣穆
開課學院：電資學院
開課系所：資訊系
考試日期（年月日）：2010/11/12
考試時限（分鐘）：120 mins
是否需發放獎勵金：是
（如未明確表示，則不予發放)
Problem 1.In each of the following question, please specify the statement is
true or false. If the statement is true ,explain why it is true. If it is
false, explain why it is true. If it is false, explain what he correct answer
is and why. (40 ponts. For each question, 2 points for the true/false answer
and 3 points for the explanations.)
1.n^1.5 = O(n㏒n)
2.A complete binary tree with a height of h can have more nodes than a full
binary tree with a height of h.
3.A stack follows a FIFO (first-in-first-out) rule.
4.When we use a max heap to implement a priority queue, the time complexity of
both the add and delete operations are O(n).
5.T(n) = T(n-1) + N, T(1) = 1. Then T(n) = O(n^3).
6.In a circular doubly linked list with 10 nodes, we will need to change 4
links if we want to delete a node other than the head node.
7.If F1(n) = Ω(G1(n)) and F2(n) = Ω(g2(n)),then f1(n)*f2(n) = Ω(g1(n)*g2(n))
8.When using linked list to perform insertion sort, each time we remove an
element from the input list and insert it to the correct position in the linked
list. Assume that we have n numbers to be sorted, the time complexity for
sorting these nubmers using the insertion sort algorithm is O(n^2)
Problem 2. "Fill the blank" (20 points. 5 for each question)
1.Please compute The failure functino (in Knuth, Morris, and Pratt's pattern
matching algorihtm) for the pattern sting "babcbcbabcbabc" in Table 1.
2.Please draw all the threads of the threaded tree shown in Figure 2.
3.Please complete Table 2 show the progress of converting the infix expression
"2+1-(4-3*1)*3" to its postifx expression using a stack.
4.Please complete the following function to concatenate two circularly singly
linked list into one circularly singly linked list.
typedef struct listNode * listPointer;
typedef struct listNode{
int data;
listPointer link;
};
listPointer concatenate(listPointer list1,listPointer list2){
/*Produce a new list which contains list1 followed by list2.
Return the pointer which points to the new list.
The argumetns list1 and list pont to the tails of the lists.*/
listPointer temp;
if(list1==NULL)
return list2;
if(list2==NULL)
return list1;
//fill in the blank here.
return list2;
}
Problem 2.的答案要寫在題目卷上 考完交回
Problem 3.The Tower of tHanoi is a mthematical game. The game consists of 3
rods, and n disks of different sizes which can slide onto any rod. The puzzle
starts with the disks stack in ascending order of size of rod number 1 (the
smallest disk is on the top). The objective of the game is to move the entire
stack to rod nubmer 3,obeying the following rules: (10 points)
1.Only one disk can be moved at a time.
2.Each move consists of taking the upper disk from one of the rods and sliding
it onto another rod, on top of the other disks that may already be present on
that rod.
3.No disk may be placed on top of a smaller disk.
In this problem, please write an algorithm using the recursive technique to
output a series of moves whic hsolve the Tower of Hanoi problem. The input and
output are as follows:
Input: one single nubmer which represents the number of disks on the rod
Output:Each line of output consists of a pair (i,j), whic hrepresents a move
from rod number i to rod number j. The sequence of moves should move the entire
stack from rod number 1 to rod number 3.
Example:
Input:
3
Output:
(1,3)
(1,2)
(3,2)
(1,3)
(2,1)
(2,3)
(1,3)
Problem 4.A lower triangular matrix is one in which all elements above the main
diagonal of a square matrix are zero. Assume that we have a lower triangular
matrix L with n rows (Figure 1). Please answer the following related questions
(10 points )
1.What is the total number of nonzero terms of L (3 points)? If each element
can be stored in a 32-bit signed integer, how much memory would be needed to
store all the nonzero elements of matriz L(2 points)?
2.SInce storing a triangular matrix as a two dimensional array wastes space, we
would like to find a way to store only the nonzero terms in the triangular
matrix. FIndan addressing formula for the elements Li,j to be stroe in a one
dimensional array a. In other words, where in the array a would you store the
element Li,j?( you only need to explain how to map each nonzero element to the
one dimensional array. No need to wried down the actual function.) (5 points)
Problem 5.In the following questions, consider the list of numbers:
62,31,70,91,25,11,9,61,73,6.(20 points)
1.Show the result of inserting the numbers in the list in the same order
specified above into an initially empty minimum heap. Note that you need to
show how the heap looks like after each number is inserted. (5 points)
2.Show the result of inserting the numbers in the list int he same order
specified above into an initially empty binary search tree. Note that you need
to show how the binary search tree looks like after each number is inserted.
(5 points)
3.Use the binary search tree you created in question 2. What are the two
possible binary search trees after 62 is deleted? (5 points)
4.Explain how you can utilize a minimum heap to sort the list of numbers in
descending order. (3 points) Let n be the number of elements in the list. What
is the time complexity of your sorting algorithm? (2 points)
Problem 6.In this proble, we consider logic expressions with the following
operands and operators:
Operands: 0 and 1, which represents false and true, respectively.
Operators: &(and),|(or),a
1.Draw the logical expression tree of the expression !(0&!1&0|0)&0.Since !(not)
is an unary operator, we ask you to put its only operand to its right child.
(3 points) Write down its prefix expression (2 points)
2.Please write down an algorithm to take a string of logic expression and
convert it to an exression tree. You can use any data structure you like to
represent the tree. Since !(not) is an unary operator, we ask you to put its
only operand to tis right child. However,please explain how your data structure
relate to the tree logically in details. (Comment: this is the the hardest
question in this exam.Do this after you finish all other questions!) (10 points)
3.Please write down an algorithm to evaluate the outcome of the logical
expression using the tree generated by your algorithm in question 2.(5 points)
4.Please write down an algorithm to output the prefix expression of the logic
expression using the tree generated by your algorithm in question 2.(5 points)
Problem 7.Please provide constructive suggestions to this course in terms of
lectures, homeworks, or any other aspects. (5 points)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.193.6.232