臺北巿立師範學院 九十三學年度研究所碩士班入學考試試題
所 別：數學資訊教育研究所
科 目：計算機概論
考試時間：九十分鐘
總 分：一百分
※ 注意：不必抄題，作答時請將試題題號及答案依照順序寫在答卷上。 ( 於本試題紙上作答者，不予計分 )
１．
Consider the following network. With the indicated link costs, use Dijkstra's shortest-path algorithm to compute the shortest path from D to all network nodes.
G |
H |
F |
E |
D |
B |
A |
C |
2 |
14 |
4 |
1 |
9 |
2 |
6 |
1 |
3 |
1 |
1 |
1 |
3 |
4 |
２．
The Internet implements the flow-control service and congestion-control service. What's the difference between these two services?
３．
cross-over的UTP傳輸線與straight-through的UTP傳輸線有什麼差別？請分別舉例說明此兩種傳輸線的使用時機。
４．
網路遮罩的功能是什麼？各類型位址如何對網路遮罩進行設定？
第 1 頁，共 4 頁
５．
A dog has a name, a breed, and an age (in years, an int). Parts (a) through (d) all deal with the contents of class Dog , below.
(a) Write instance variables for the Dog class.
(b) Write an appropriate constructor with three parameters.
(c) Write equals . Two Dogs are equal if the breeds are the same and the agesdiffer by one year or less.
(d) Write to String . For example, for an object representing a three years old
Samoyed named "Toby", the method should return "Toby – Breed: Samoyed, Age: 3" .
Public class Dog {
//Parts (a) here.------------------------------------
//Parts (b) here.------------------------------------
//Parts (c) here.------------------------------------
//Parts (d) here.------------------------------------
}
６．
Assume that we perform DFS( s ) on the following graph, in order to find a spanning tree. That is, a depth first search is performed starting from the vertex s and any edge that is the first to reach a non-marked vertex is added to the tree.
Draw all the spanning tree that can be the output of DFS( s )
７．
Draw the resulting 2-3 tree after insert(18), insert(1), delete(13) are performed, one after the other, on the tree on the following page. Draw the two intermediate states and the final state.
第 2 頁，共 4 頁
８．
A directed graph is given by the following adjacency matrix, M, in which M( i , j )=1 if and only if there is an edge from i to j . Find a topological sort of the graph and explain your reason.
A |
B |
C |
D |
E |
F |
|
A |
0 |
1 |
0 |
0 |
0 |
0 |
B |
0 |
0 |
1 |
0 |
0 |
0 |
C |
0 |
0 |
0 |
1 |
0 |
0 |
D |
0 |
0 |
0 |
0 |
0 |
0 |
E |
0 |
1 |
1 |
0 |
0 |
0 |
F |
1 |
0 |
1 |
0 |
0 |
0 |
９．
Trees and Stacks problems
(a) Draw the final tree that results from inserting the integers 5, 2, 4, 3, 9, 12, 6 (in that order) into an empty binary search tree with no balance conditions.
(b) What is the sequence of elements that results from a preorder traversal of your tree in part (a)?
(c) Fill in the blanks in the following routine for preorder traversal of a binary tree using a stack. Choose one of the following to fill in each blank:
第 3 頁，共 4 頁
１０．
Binary Heaps and Binomial Queues
(a) What are the two properties that make a binary tree a binary heap?
(b) Draw the binary heap that results from deleting the minimum and then inserting 4 into the following binary heap:
(c) Draw the binomial queue that results from inserting the integers 1, 2, 3, 4, 5, 6, 7 (in that order) into an empty binomial queue and then deleting the minimum.
１１．
This problem asks you to prove the minimum spanning tree problem is NP-hard. The input is a connected undirected graph G with weighted edges. The problem considers a certain subset of the possible spanning trees of G, and asks you to compute the spanning tree with minimum total weight in that subset. Prove that finding the minimum-weight depth first search tree is NP-hard.
第 4 頁，共 4 頁