作者boyenen (TCPN)
看板NTU-Exam
标题[试题] 100-2 吕育道 离散数学 期末考
时间Thu Jun 21 15:08:32 2012
课程名称︰离散数学
课程性质︰
课程教师︰吕育道
开课学院：
开课系所︰资工系
考试日期（年月日）︰2012/06/21
考试时限（分钟）：三节课
是否需发放奖励金：否
（如未明确表示，则不予发放）
试题 :
Note: You may use any result proved in the class.
Problem 1(10 points)
Prove that any two consecutive Fibonacci numbers are relatively prime.
The Fibonacci recurrence equation is
Fn+2 =
Fn+1 +
Fn with
F0 = 0 and
F1 = 1
Problem 2(10 points)
Solve the recurrence relation (
An+2)^2 -5(
An+1)^2 +4(
An)^2 = 0,
where n >= 0 and
A0 = 4,
A1 = 13.
Problem 3(10 points)
If
A0 = 0,
A1 = 1,
A2 = 4,
A3 = 37 satisfy the recurrence relation
An+2 + b(
An+1) + c(
An) = 0, where n >=0 and b,c are constants,
determine b,c and solve for
An.
Problem 4(5 points)
Can a simple graph exist with 15 vertices each of degree five?
Problem 5(10 points) _
If the simple graph G has v vertices and e edges, how many edges does G have?
Problem 6(10 points)
Prove that an acyclic digraph has at least one node of out-degree zero.
(An acyclic digraph is a directed graph containing no directed cycles.)
Problem 7(10 points)
If G =(V,E) is a loop-free undirected graph, prove that G is a tree
if there is a unique path between any two vertices of G.
Problem 8(5 points)
Give an example of an undirected graph G = (V,E), where |V| = |E| + 1 but
G is not a tree.
Problem 9(10 points)
If G is a group, let H = {a属於G |ag = ga for all g属於G }.
Prove that H is a subgroup of G. (The subgroup H is called the center of G.)
Problem 10(10 points)
Verify that ( Z*p ,‧)is cyclic for the primes p = 7 and 11.
Problem 11(10 points)
Prove that every group of prime order is cyclic.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.244.224