Note Đóng lại

GỢI Ý GIẢI ĐỀ THI MÔN TOÁN RỜI RẠC 2(ĐỀ 7)

5/31/2019



Đề số 1: (2014-2015)
Câu 1:
a,
deg(1)=3
deg(2)=2
deg(3)=3
deg(4)=3
deg(5)=2
deg(6)=4
deg(7)=3
deg(8)=2

b,Biểu diễn đồ thị G dưới dạng ma trận kề:
1
2
3
4
5
6
7
8
1
0
1
1
1
0
0
0
0
2
1
0
1
0
0
0
0
0
3
1
1
0
1
0
0
0
0
4
1
0
1
0
0
1
0
0
5
0
0
0
0
0
1
1
0
6
0
0
0
1
1
0
1
1
7
0
0
0
0
1
1
0
1
8
0
0
0
0
0
1
1
0

c, Biểu diễn đồ thị G dưới dạng danh sách cạnh:
Đỉnh đầu
Đỉnh cuối
Đỉnh đầu
Đỉnh cuối
1
2
5
6
1
3
5
7
1
4
6
7
2
3
6
8
3
4
7
8
4
6



Câu 2:
a,
BFS(7)={7(0),5(7),6(7),8(7),4(6),1(4),3(4),2(1)}
àĐường đi từ đỉnh số 7àđỉnh số 2: 7à6à4à1à2
b,
DFS(1)={1(0),2(1),3(1),4(1),6(4),5(6),7(6),8(6)}
àSố thành phần liên thông : k=1
Lập bảng:
Đỉnh u
Số TPLT l của G\{u}
l>k
Đỉnh trụ
1
DFS(2)={2(0),3(2),4(3),6(4),5(6),7(6),8(6)}
àl=1
No
------
4
DFS(1)={1(0),2(1),3(2)}
DFS(5)={5(0),6(5),7(6),8(7)}
àl=2
Yes
4
6
DFS(1)={1(0),2(1),3(2),4(3)}
DFS(5)={5(0),7(5),8(7)}
àl=2
Yes
6
KL: Các đỉnh trụ: 4,6
Câu 3:
a,
Thuật toán Euler-Cycle(u):
Bước 1:(Khởi tạo)
Stack= Ø;//Khởi tạo một stack bắt đầu là Ø
CE= Ø;//Khởi tạo một mảng CE ban đầu là Ø
Push(u,Stack);//Đưa đỉnh u vào ngăn xếp
Bước 2:(Lặp)
While(Stack ≠ Ø){//Lặp nếu stack không rỗng
          s=get(Stack);//Lấy đỉnh đầu của ngăn xếp;
          if(ke(s) ≠ Ø){//Nếu danh sach ke(s) không rỗng
                    t=<t là đỉnh đầu trong ke(s)>;
                    push(t,Stack);//Đưa đỉnh t vào ngăn xếp
                    E=E\{s,t};//Loại cạnh (s,t) khỏi đồ thị
}
else{
          Pop(s,Stack);//Loại đỉnh đầu ngăn xếp
          s=>CE;//Đưa đỉnh s vào mảng CE
}
}
Bước 3:(Trả lại kết quả)
<Lật ngược các đỉnh trong CE thu được chu trình Euler>;
b,
Danh sách kề:
Ke(1)={2,3,5,6}
Ke(6)={1,4,5,8}
Ke(2)={1,3}
Ke(7)={3,5,8,9}
Ke(3)={1,2,7,8}
Ke(8)={3,6,7,9}
Ke(4)={5,6}
Ke(9)={7,8}
Ke(5)={1,4,6,7}


n=9,u=1
Lập bảng:
Bước
Stack
CE
1
1
Ø
2
1,2,3,1,5,4,6,1
Ø
3
1,2,3,1,5,4,6,5,7,3,8,6
1
4
1,2,3,1,5,4,6,5,7,3,8,7,9,8
1,6
5
Ø
1,6,8,9,7,8,3,7,5,6,4,5,1,3,2,1
KL: Chu trình EULER bắt đầu từ đỉnh 1: 1-2-3-1-5-4-6-5-7-3-8-7-9-8-6-1
Câu 4:
a,
Thuật toán Kruskal:
Bước 1:(Khởi tạo)
T=Ø;//Khởi tạo cây khung ban đầu là Ø
d(H)=0;//Khởi tạo độ dài cây khung ban đầu là 0
Bước 2:(Sắp xếp)
<Sắp xếp độ dài các cạnh theo thứ tự tăng dần của trọng số>;
Bước 3:(Lặp)
While(|T|<n-1&&E≠ Ø) do{//Lặp nếu | T|<n-1 và E≠ Ø
          e=<e là cạnh có trọng số nhỏ nhất>;
          E=E\{e};//Loại cạnh e ra khỏi đồ thị
          if(T ᴗ{e} không chứa chu trình) then{
                    T=T ᴗ{e};//Kết nạp cạnh e và cây khung
                    d(H)=d(H)+d(e);//Thiết lập độ dài mới cho cây khung
}
}
Bước 4:(Trả lại kết quả)
If(|T|<n-1) <Đồ thị không liên thông>;
Else return(T,d(H));
b,n=9
Sắp xếp các cạnh theo thứ tự tăng dần của trọng số:
(1,2)<=(2,3)<=(3,7)<=(6,8)<=(1,3)<=(4,6)<=(5,7)<=(1,5)<=(1,6)<=(3,8)<=(7,9)<=(4,5)<=(5,6)<=(7,8)<=(8,9)
Lập bảng:
Cạnh ei
T ᴗei chứa chu trình
T
WT
k
(1,2)
No
(1,2)
1
1
(2,3)
No
(2,3)
2
2
(3,7)
No
(3,7)
3
3
(6,8)
No
(6,8)
4
4
(1,3)
Yes
-------
-------
--------
(4,6)
No
(4,6)
6
5
(5,7)
No
(5,7)
8
6
(1,5)
Yes
-------
-------
-------
(1,6)
No
(1,6)
11
7
(3,8)
No
(3,8)
14
8
KL: WTmin=14
T={(1,2), (2,3), (3,7), (6,8), (4,6), (5,7), (1,6), (3,8)};
Câu 5:
n=10,u=1;
Lập bảng:
Bước
d[1]|p[1]
d[2]|p[2]
d[3]|p[3]
d[4]|p[4]
d[5]|p[5]
1
0|0
4|1
1|1
∞|1
∞|1
2

3|3
1|1
∞|1
6|3
3

3|3

6|2
4|2
4



6|2
4|2
5



6|2

KL: Đường đi ngắn nhất từ đỉnh 1 đến đỉnh 5:
d[1][5]=4:  1à3à2à5

 Tải đề thi: Tải về

*Chú ý: Gợi ý tại mỗi đề chỉ mang tính chất tham khảo rất mong sự góp ý của mọi người để có lời giải hoàn thiện và chính xác nhất.
>>Xem thêm
Tổng hợp bài tập môn Toán rời rạc 2 kèm gợi ý

Nếu thấy tài liệu có ích hi vọng mọi người ủng hộ blog bằng cách like và theo dõi địa chỉ page chính thức của Tài Liệu Blog tại: https://www.facebook.com/TaiLieuBlog/

Nhận xét

1 nhận xét:

Đăng ký: Đăng Nhận xét ( Atom )