Xem mẫu
- CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
1.
K[]={18,12,6,13,9,14,7,15,8,18,9,25,5,11,13,17} 16 phần tử.
a. Trình bầy Bubble Sort sắp xếp dãy khoá K[] theo thứ tự tăng dần?
b. Áp dụng,ghi kết quả mỗi bước.
2.
Cho đồ thị vô hướng G= thực hiện
11
2 7 8
13
1 10
3 6
9
4 5 12
a. Biến đổi đồ thị G dưới dạng ma trận kề.
b. Biến đổi đồ thị G dưới dạng danh sách cạnh.
c. Biến đổi đồ thị dưới dạng danh sách kề.
3.
a. Định nghiã hàng đợi. Các thao tác trên hàng đợi.
b. Xây dựng thuật toán duyệt các đỉnh cuả đồ thị vào hàng đợi.
c. Kiểm nghiệm thuật toán bắt đầu tại đỉnh u=5 và u=10 cho đồ thị được biểu diễn dưới dạng
ma trận kề, chỉ rõ kả các bước thực hiện cuả thuật toán.
0 1 0 0 1 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 0 0 1 0 0
0 0 1 0 1 0 1 1 0 0 1 0 0
1 1 0 1 0 1 0 0 0 0 0 0 0
1 1 0 0 1 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0 1 1
0 0 0 0 0 0 0 0 1 0 0 1 1
0 0 1 1 0 0 0 1 0 0 0 1 0
1
- 0 0 0 0 0 0 0 0 1 1 1 0 1
0 0 0 0 0 0 0 0 1 1 0 1 0
G=
2
- 4.
a. Định nghĩa ngăn xếp; các thao tác ngăn xếp.
b. Xây dựng thuật toán duyệt các đỉnh cuả đồ thị dựa vào ngăn xếp.
c. Kiểm nghiệm thuật toán bắt đầu tại đỉnh u=4 và u=13 cho đồ thị được biểu diễn dưới dạng
ma trận kề ở hình. Chỉ rõ jết quả trung gian mỗi bước thực hiện cuả thuật toán.
0 1 0 0 1 1 0 0 0 0 0 0 0
1 0 0 0 1 1 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 0 0 1 0 0
0 0 1 0 1 0 1 1 0 0 1 0 0
1 1 0 1 0 1 0 0 0 0 0 0 0
1 1 0 0 1 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0 1 1
0 0 0 0 0 0 0 0 1 0 0 1 1
0 0 1 1 0 0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 0 1 1 1 0 1
0 0 0 0 0 0 0 0 1 1 0 1 0
G=
3
- KỸ THUẬT LẬP TRÌNH
1. Cho đoạn chương trình sau:
#include
#include
int X[10], chuaxet[10], n, count;
void Int(void)
{
n=4;
count=0;
for (int i=1;i
- Cho biết kết quả thực hiện đoạn chương trình.
5
- 2. Chuyển thành chương trình mới thỏa mãn:
Giống chương trình cũ với mọi phép thử.
Chỉ dung while và được thêm một số biến phụ. Không dùng for, do… while, if…else, switch.
3.
Cho ma trận vuông A={aij} cấp N được ghi lại trong file matran.in theo khuôn dạng sau:
- Dòng đầu tiên ghi lại số tực nhiên N là cấp của ma trận vuông;
- N dòng kế tiếp ghi lại ma trận vuông A, hai phần tử khách nhau của ma trận vuông được
ghi cách nhau bởi một vài khoảng chống
Viết chương trình kiểm tra và đưa ra thong báo:
N
a) “A đối xứng chẵn” nếu aij = aji và Si= ∑ aij là những số chẵn (i,i=1,2…,N);
j =1
b) “A đối xứng lẻ” nếu aij=aji (I,j=1,2,…,N) và tồn tại đúng 2 chỉ số u,v (1≤u,v≤N) sao cho
N N
∑a ∑ avj
uj
Su= j =1 , Sv= j =1 là những số lẻ;
c) “A là ma trận đối xứng” nếu aij = aji với mọi i,j =1,2,…,N và A không “đối xứng chẵn”
không “đối xứng lẻ”;
d) “A không đối xứng” trong những trường hợp còn lại khác.
4.
Cho ai, ci, B,N (i=1,2,…,N) là những số nguyên dương và tập hợp:
N
∑a xi ≤ B; x j = 0,1 }
D={X=(x1,x2,…..,xN), j
j =1
Viết chương trình tìm phương án tối ưu XOPT = (x1,x2,…..,xN) và giá trị tối ưu FOPT=F(XOPT)
của hàm mục tiêu:
N
F(x1,x2,….,xN)= ∑ c j x j → max vớ X=(x1,x2,…,xN) ∈ D
j =1
Dữ liệu cho bởi file data.in theo khuôn dạng sau:
- Dòng đầu tiên ghi lại số tự nhiên N & B. Hai số được viết cách nhau một vài khoảng
trống.
- Dòng kế tiếp ghi lại N số cj(j=1,2,…..,N). Hai số được viết cách nhau một vài khoảng
trống.
- Dòng kế tiếp ghi lại N số aj(1,2,….,N). Hai số được viết cách nhau một vài khoảng trống.
Giá trị tối ưu của FOPT và phương án của XOPT tìm được ghi lại trong file ketqua.out theo
khuôn dạng:
- Dòng đầu tiên ghi lại gái trị tối ưu của FOPT;
- Dòng kế tiếp ghi lại phương án tối ưu XOPT. Hai phần tử khác nhau của phương án tối
ưu được viết cách nhau bởi một vài khoảng trống.
6
- 7
- Ví dụ minh họa khuôn dạng cho file data.in và ketqua.out của bài toán
data.in ketqua.out
4 10 13
6 5 3 7 1 0 0 1
5 4 6 5
5.
Cho tập các số tự nhiên có 5 chữ số trong file data.in được ghi theo từng dòng, mỗi dòng ghi
nhiều nhất 5 số, 2 số được viết các nhau một vài khoảng trống. Biết rằng mỗi số tự nhiên trong
file data.in hoặc là số nguyên tố hoặc là số thuận nghịch và có thể xuất hiện nhiều lần ở những
vị trí khác nhau trong file. Viết chương trình tách tập các số và đếm số lần xuất hiện của mỗi số
trong file data.in thành 3 file ketqua.out, ketqua2.out, ketqua3.out thỏa mãn những yêu cầu dưới
đây:
a) file ketqua.out ghi lại các số nguyên tố nhưng không là số thuận nghịch cùng với số lần
suất hiện của nó trong file data.in
b) file ketqua2.out ghi lại các số thuận nghịch nhưng không là số nguyên tố cùng với số lần
xuất hiện của nó trong file data.in
c) file ketqua3.out ghi lại các số vừa là số nguyên tố, vừa là số thuận nghịc cùng với số lần
xuất hiện của nó trong file data.in
d) Khuôn dạng của các file kết quả được quy định như sau:
- dòng đầu tiên của mỗi file ghi lại số các số của mỗi file kết quả.
- Những dòng kết tiếp mỗi dòng ghi lại một số cùng với số lần xuất hiện của nó trong file
data.in. Hai số được viết cách nhau một vài khoảng trống.
Ví dụ file data.in, ketqua.out, ketqua2.out, ketqua3.out
data.in ketqua.out ketqua2.out ketqua3.out
10007 10009 10801 10901 13831 2 2 2
10007 10009 10801 10901 13831 10007 4 10801 4 13831 2
10007 10009 10801 10901 13831 10009 4 10901 4 34543 2
10007 10009 10801 10901 13831
8
nguon tai.lieu . vn