推 andy74139 :已收錄至精華區!! 01/14 20:42
課程名稱︰資料結構與演算法
課程性質︰系必修
課程教師︰蔡欣穆
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2011/1/14
考試時限（分鐘）：180
是否需發放獎勵金：是的，感謝
（如未明確表示，則不予發放）
試題 :
Problem 1.In each of the following question, please specify if the statement
is true or false. If the statement is tre, explain why it is true. If it is
false, explain what the correct answer is and why. (55 points. For each
question, 2 points for the true/false answer and 2 points for the explanations)
a.When the size of the input is small, insertion sort is usually faster than
quick sort.
b.A spanning tree of graph G = (V,E) has |V| edges.
c.A binomial tree of degree i has 2^(i-1) internal nodes.
d.Out of all path from the root to one of the leaves in a leftist tree, the
shortest one is the left-most one.
e.Dijkstra algorithm and Bellman-Ford algorithmare the two algorithms to
search for the shortest paths from one vertex to all other vertices in the
graph. Out of those two algorithms, only Dijkstra algorithm can handle the
case where the edges in the graph can have negative costs.
f.The worst-case time complexity of merge sort is better than that of quick
sort.(In your explanation, write down the worst-case time complexity of both
sorting algorithms)
g.When sorting on multiple keys, Least-Significant-Digit-first(LSD) sorting is
easier to implement than Most-Significant-Digit-first(MSD) sorting.
h.The number of internal nodes in a leftist tree is always larger than
2^(s(r))-1, where s(r) is the distance to the closest external node.
i.In a Fibonacci heap, if an arbitrary node b has a degree of 3,than the
minimum number of nodes in the subtree with b as the root would be 5.
j.In the worst case, any comparison-based sorting algorithm (different items in
the input are compared against each other and their locations are switched
based on the comparison results) will have a running time of Ω(n㏒n).
k.Let T(n) = cn + 2T(n/2) when n > 1 and T(n) = 1 when n <= 1. n is a
nonnegative number. Then T(n) = O(n㏒n).
Problem 2.Please answer the following questions related to red-black trees:
(20%)
a.In both insert and delete operations of red-black trees, we need to implement
the rotation operation to adjust the local tree structure while preserving
the binary-search-tree property. Please draw the two red-black trees after
(1)A right-rotate operation is performed to the red-black tree in Figure 1
on node 53,and (2)A left-rotate operation is performed to the red-black tree
in Figure 1 on node 42.(4 points, 2 points for each answer)
b.Assume that we use the following representaton for each red-black tree node.
Write down the pseudo-code to perform a right rotate operation to tree T on
node x: right-rotate(T,x). (4 points)
typedef struct treeNode * treePointer;
typedef struct treeNode{
treePointer p; //points to its parent
treePointer l; //points to its left child
treePointer r; //points to its right child
int color; //the color of the node. red=1, and black=0.
int key; //the key value of the node
};
c.Assume that we will insert the following numbers into an initially empty
red-black tree in the specified order:5 9 15 20 13 11 12.Show how the
red-black tree looks like after each number is inserted and describe how the
tree is transformed in a step-by-step manner (describe how you apply the left
or right rotate operations and how you change the color of the nodes). (4%)
d.Explain why the distance of the longest path from the root to a leaf is not
larger than twice of the distance of the shortest path from the root to a
leaf in a red-black tree.(4%)
e.Red-black trees are special cases of binary search trees. Prof. Tsai said
that he would use the red-black tree in any case, since he has spent so much
time learning it (and, of course, the running time of all operations of the
red-black tree can be bounded by O(㏒n).) Please use an example to explain to
him that in some cases, it might be better to use a regular binary search
tree.(4%)_
Problem 3.In the class(and the homework), we define tree edges, back edges,
forward edges, and cross edges after performing a depth-first search on an
undirected or directed graph. Using similar definitions, we can also define
these types of edges after performing a breadth-first search on an undirected
or directed graph: (8%)
˙Tree edges are edges in the bredth-first forest.
˙Back edges are those edges < u,v > or (u,v) which connects a vertex u to an
ancestor v in a breadth-first search tree. A self edge is considered as a
back edge.
˙Forward edges are those non tree edges < u,v > or (u,v) which connects a
vertex u to a descendant v in a breadth-first tree.
˙cross edges are all other edges, which can be between vertices in the same
tree ot different trees as long as one is not an ancestor of the other.
a.Prove that in a breadth-first search tree of an undirected graph, there are
no back edges and no forward edges.(4%)
b.Prove that in a breadth-first search tree of a directed graph, there are no
forward edges.(4%)
Problem 4.Assume that we would like to sort n numbers in an input list using
one of the following algorithms: (1)insertion sort (2) quick sort (3) merge
sort (4) heap sort.(16%)
a.When the input is a sorted list, what is the running time (using the big-O
notation) of these algorithms? Explain your answers.(8%,2% for each sorting)
b.When the input is a reversely sorted list, what is the running time (using
the big-O notation) of these algorithms? Explain your anwers(8% , 2% for each
sorting algorithm)
Problem 5.Suppose you are given the following numbers: 20,62,31,14,1,25,3,19,11
, and the hash function
h(x) = x mod 11
We ask you to inser these numbers (in the given order) into an initially empty
hash table with 11 entires using the given hash function. Note that each entry
in the hash table only has space for storing one item.(12%)
a.Explain the difference between a collision and a overflow in a hash table(4)
b.Assume that you will use linear probing to resolve overflows. Show the
content of the hash table after all numbers are insered using Table 1.
c.Assume that you will use chaining to resolve overflows. Show the content of
the hash table after all numbers are insered using Table 2.
Problem 6.In this problem, we ask you to answer the following questions related
to an undirected graph G shown in Figure 2.(24%)
a.Perform a depth-first search (DFS) on graph G starting from vertex 1 and draw
the depth-first search tree obtained from your search.(4%)
b.Write down an iterative (non-recursive) DFS algorithm. Please also explain
how you use a data structure to represent the graph in your algorithm(4%)
c.Based the answer in a, explain how you can determine all articulation points
in graph G in a step-by-step manner.(4%)
d.Plase use the Bellman-Ford algorithm to determine the costs of the shortest
path (the number next to the edges in the graph are the costs for traveling
through them) from vertex 1 to all other vertices. Use Table 3 to show how the
algorithm is executed in each iteratio. (4%)
e.What is the time complexity of the Bellman-Ford algorithm? Assume that there
are |V| vertices and |E| edges in the graph. Please specify the time complexity
using the big-O notation for both the case that we use adjacency matrix to
represent the graph and the case that we use adjacency lists to represent the
graph and explain your answers.(4%)
f.Show how you can use Kruskal's algorithm to obtain a minimum cost spanning
tree of graph G in a step-by-step manner; mark the order of the edges added to
the minimum cost spanning tree next to the edges on Figure 2.(4%)
Problem 7.Out of all topics we covered in the classes this semester, which one
do you like most? Which one do you dislike the most? Why? Please give some
consturctive suggestions.(1%)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.193.6.232