Bài tập về Cấu trúc dữ liệu và giải thuật

Chia sẻ: Nguyễn Công | Ngày: | Loại File: DOC | Số trang:8

Thêm vào BST

Báo xấu

219
lượt xem 28
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài tập về Cấu trúc dữ liệu và giải thuật

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