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

Giải thuật Đề 1 Câu 1 (4 điểm) Cho dãy số: 32 17 45 26 10 50 22 15 a) Nêu thuật toán sắp xếp chọn trực tiếp (Selectionsort) b) Áp dụng thuật toán để sắp xếp dãy số tăng dần, nêu rõ từng bước Câu 2 (3 điểm) Giả sử ổ khóa có n công tắc. Mỗi công tắc có một trong 2 trạng thái “đóng” hay “mở”. Khóa mở được nếu có ít nhất [n/2] công tắc có trạng thái mở. Thiết kế thuật toán liệt kê tất cả các cách mở khóa. Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1/(1*5) + 1/(2*5) + 1/(3*5) + …. + 1/(n*5) Đề 2 Câu 1 (4 điểm) Cho dãy số: 20 15 45 26 10 50 22 17 c) Nêu thuật toán sắp xếp chèn trực tiếp (Insertionsort) d) Áp dụng thuật toán để sắp xếp dãy số tăng dần, nêu rõ từng bước Câu 2 (3 điểm) Cho dãy a = (a1, a2, . . ., an ) gồm các số đôi một khác nhau. Thiết kế thuật toán liệt kê tất cả các hoán vị của dãy n phần tử của a. Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1/(2*3) + 1/(4*3) + 1/(6*3) + …. + 1/(2n*3) Đề 3 Câu 1 (4 điểm) Cho dãy số: 45 26 20 50 32 15 10 17 e) Nêu thuật toán sắp xếp nổi bọt (Bublesort) f) Áp dụng thuật toán để sắp xếp dãy số tăng dần, nêu rõ từng bước Câu 2 (3 điểm) Cho dãy a = (a1, a2, . . ., an ) gồm các số đôi một khác nhau. Thiết kế thuật toán liệt kê tất cả các tổ hợp chặp k trong tập gồm n phần tử cuả a. Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1 + 1/3 + 1/5 + … 1/(2n-1) Đề 4 Câu 1 (4 điểm) Cho dãy số: 20 50 32 45 10 17 26 15 g) Trình bày thuật toán sắp xếp đổi chỗ trực tiếp (Interchangesort) h) Áp dụng thuật toán để sắp xếp dãy số tăng dần, nêu rõ từng bước Câu 2 (3 điểm) Cho bàn cờ n x n ô. Một con ngựa được phép đi theo luật cờ vua (theo đường chéo hình chữ nhật 2 x 3). Thiết kế thuật toán tìm tất cả các hành trình của ngựa, bắt đầu từ ô đi qua tất cả các ô của bàn cờ, mỗi ô đúng một lần. Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1 + 1/3 + 1/8 + … 1/(n2-1) Đề 5 Câu 1 (4 điểm) Cho dãy số: 20 10 17 26 50 32 45 15 i) Trình bày thuật toán sắp xếp đổi chỗ trực tiếp (Interchangesort) j) Áp dụng thuật toán để sắp xếp dãy số tăng dần, nêu rõ từng bước Câu 2 (3 điểm) Cho 3 ký tự A, B, C và một số nguyên n. Lập thuật toán liệt kê tất cả các chuỗi tạo ra từ 3 ký tự trên, với chiều dài n, thoả điều kiện không có 2 chuỗi con liên tiếp nào giống nhau. Câu 3 (3 điểm) Viết thủ tục đệ quy thực hiện tìm kiếm nhị phân trên một dãy số trong hai trường hợp: a) (1,5 điểm) Dãy số tăng dần b) (1,5 điểm) Dãy số giảm dần Đề 6 Câu 1 (4 điểm) a) Cho dãy số: 20 10 17 26 50 32 45 15 Áp dụng thuật toán MergeSort để sắp xếp dãy số tăng dần, nêu rõ từng bước b) Hãy cho biết trong đoạn lệnh sau có bao nhiêu phép so sánh các dữ liệu trong mảng: for (i = 1; i < = n-1; i ++) { j = i + 1; do { if (A[i] < A[j]) swap (A[i], A[j]); j ++; } while (j <= n) } so lan so sanh : phep nhan cua 2 vong lap n Câu 2 (3 điểm) Cho 3 ký tự A, B, C và n là một số nguyên dương (n>3) Thiết kế thuật toán liệt kê tất cả các chuỗi tạo ra từ 3 ký tự trên, với chiều dài n sao cho số ký tự A là 3. Câu 3 (3 điểm) Thiết kế thuật toán tìm giá trị min trong một dãy số theo phương pháp chia để trị Đề 7 Câu 1 (4 điểm) Cho dãy số: 45 26 20 50 32 15 10 17 Áp dụng phương pháp nổi bọt cải tiến (ShakerSort) để sắp xếp dãy số trên tăng dần, nêu rõ từng bước Câu 2 (3 điểm) Cho bàn cờ n x n ô. Một con ngựa được phép đi theo luật cờ tướng (theo đường chéo 1 x 2). Thiết kế thuật toán liệt kê tất cả các hành trình của ngựa, bắt đầu xuất phát từ ô đi qua tất cả các ô của bàn cờ, mỗi ô đi qua đúng một lần. Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1/13 + 1/33 + 1/53 + … + 1/(2n-1)3 Đề 8 Câu 1 (4 điểm) Cho dãy số: 17 26 20 10 50 32 15 Áp dụng thuật toán Quicksort để sắp xếp dãy số tăng dần, nêu rõ từng bước Câu 2 (3 điểm) Cho một lưới hình vuông cấp n, mỗi ô được gán với một số tự nhiên. Tại một ô có thể di chuyển đến ô khác theo các hướng : lên trên, xuống dưới, rẽ trái, rẽ phải (4 ô kề cạnh). Thiết kế thuật toán tìm đường đi từ ô đầu tiên (1,1) đến ô ( m, m) sao cho mỗi ô đi qua đúng 1 lần và tổng các ô là nhỏ nhất. (1≤ m≤n). Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1/(1*2) + 1/(2*2) + 1/(3*2) + …+ 1/n*2 Đề 9 Câu 1 (4 điểm) Cho dãy số: 10 50 17 26 20 32 15 45 Áp dụng thuật toán Shellsort để sắp xếp dãy số tăng dần, nêu rõ từng bước Câu 2 (3 điểm) Cho n loại tiền xu tương ứng với các giá trị k1, k2,.., kn xu. Thiết kế thuật toán để đổi T đồng tiền giấy ra tiền xu sao cho số đồng xu cần dùng là ít nhất. Cho 1 đồng bằng 100 xu. Câu 3 (3 điểm) Viết thủ tục đệ quy cho bài toán tháp Hà nội sử dụng 4 tháp Đề 10 Câu 1 (4 điểm) k) Cho dãy số: 32 15 45 10 50 17 26 20 Áp dụng thuật toán SelectionSort để sắp xếp dãy số tăng dần, nêu rõ từng bước l) Đánh giá độ phức tạp của đoạn chương trình sau theo ký pháp O (ô lớn) for (i = 1; i <= n-1; i ++) { j = i + 1; do { if (A[i] < A[j]) HoanVi (A[i], A[j]); j ++; } while (j <= n); } m)For 1: n-1 lan n) For 2: n-i-1 o) Do phuc tap la : n2 Câu 2 (3 điểm) Cho dãy số được định nghĩa như sau • f(n) = 1 nếu n = 0 hay n = 1 • f(n) = 2f(n-1) + f(n-2) nếu n > 1 a) Hãy viết hàm đệ qui tính giá trị của f(n), với n được nhập từ bàn phím. b) Hãy viết hàm không đệ qui tính giá trị của f(n), với n nhập từ bàn phím. Câu 3 (3 điểm) Cho một dãy số bất kỳ. Thiết kế thuật toán sắp xếp dãy số tăng dần theo phương pháp chia để trị Đề 11 Câu 1 (4 điểm) p) Trình bày thuật toán đệ quy quay lui Viet ma gia thuat toan de quy quay lui Void try(int i) q) Cho ví dụ minh hoạ Câu 2 (3 điểm) Cho một dãy số bất kỳ. Thiết kế thuật toán tìm kiếm số nguyên tố nhỏ nhất và lớn nhất trong dãy số theo phương pháp chia để trị Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1/22 + 1/42 + 1/62 + … + 1/(2n)2. Đề 12 Câu 1 (4 điểm) r) Trình bày thuật toán theo phương pháp chia để trị s) Cho ví dụ minh hoạ Câu 2 (3 điểm) Một người du lịch muốn tham quan n thành phố T1, T2, . ., Tn . Xuất phát từ một thành phố nào đó, người du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đi qua đúng một lần rồi quay lại thành phố xuất phát. Gọi Cij là chi phí đi từ thành phố Ti đến thành phố Tj Thiết kế thuật toán tìm hành trình đi từ thành phố Ti đến thành phố Tj thoả yêu cầu bài toán và chi phí là ít nhất. Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1/13 + 1/33 + 1/53 + … + 1/(2n-1)3 Đề 13 Câu 1 (4 điểm) t) Trình bày thuật toán theo phương pháp nhánh cận Cai tien cua de quy quay lui,them dieu kien : truoc khi de quy : kiem tra dieu kien nhanh can,neu ko thoa thi dung u) Cho ví dụ minh hoạ Nguoi du lich Câu 2 (3 điểm) Cho một ma trận vuông cấp n, các phần tử của ma trận là các số tự nhiên. Ta nói đường đi trong ma trận là một đường gấp khúc không tự cắt xuất phát từ một ô nào đó của ma trận, sau đó có thể đi theo các hướng : lên trên, xuống dưới, rẽ trái, rẽ phải. Thiết kế thuật toán tìm một đường đi ngắn nhất trong ma trận, theo nghĩa có tổng giá trị các ô là nhỏ nhất trong đường đi, xuất phát từ ô đầu tiên có toạ độ (1,1) đến ô cuối cùng có toạ độ (n,n). Dung nhanh can Câu 3 (3 điểm) Viết thủ tục đệ quy tìm kiếm nhị phân trong một dãy số tăng dần Đề 14 Câu 1 (4 điểm) v) Trình bày thuật toán theo phương pháp quy hoạch động Giia bai toan lon thi giai bai toan nho nhat truoc va luu ket qua lai (chu y) Dung ket qua do de giai bai toan lon hon Truy vet tim ra pp toi uu nhat w) Cho ví dụ minh hoạ Câu 2 (3 điểm) Có n đồ vật, mỗi vật i đặc trưng bởi trọng lượng Wi và giá trị sử dụng Vi, với mọi i ∈ {1,..,n}. Cần chọn các vật này đặt vào một chiếc túi xách có giới hạn trọng lượng m, sao cho tổng giá trị sử dụng các vật được chọn là lớn nhất Thiết kế thuật toán để giải bài toán trên. Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1/(1*2) + 1/(2*2) + 1/(3*2) + …+ 1/n*2 Đề 15 Câu 1 (4 điểm) x) Trình bày thuật toán đệ quy, cho ví dụ minh họa Co 2 thanh phan: dieu kien dung (quan trong nhat)va de quy y) Dãy số được định nghĩa như sau: Viết hàm đệ quy tìm Xn với n là tham số vào Câu 2 (3 điểm) Một máy ATM có n loại tiền L1,L2,…Ln . Một người khách cần rút số tiền T đồng từ máy ATM. Thiết kế thuật toán cho bài toán trên theo sao cho số tờ tiền người khách nhận được từ máy là ít nhất. Dung quy hoach dong Câu 3 (3 điểm) Cho số n nhập từ bàn phím. Viết hàm đệ quy tính : Sn = 1 + 1/7 + 1/17 + …+ 1/(2n2-1) Đề 16 Câu 1 (4 điểm) z) Hãy tính số lần lặp các lệnh trong {…} của đoạn chương trình sau: for ( i = 0; i < n; i ++) for ( j = i + 1; j < = n; j ++) for ( k = 1; k < 10; k ++) { các lệnh }; So lenh lap = so lan lap cua 3 vong for (dung pp nhan) aa) Trình bày ưu điểm và nhược điểm của phương pháp đệ quy Uu diem:de cai dat Nhuoc diem: de quy nhieu chiem nhieu vung nho Câu 2 (3 điểm) Cho n thành phố đánh số từ 1..n, đường đi từ thành phố i đến thành phố j cho phép xe có tải trọng tối đa Ci,j đi qua. Xuất phát từ thành phố X hãy tìm một con đường đến thành phố Y sao cho tải trọng xe cho phép đi qua là lớn nhất. Câu 3 (3 điểm) Cho hai số k, n nhập từ bàn phím. Viết hàm đệ quy tính tổ hợp: C(n,k) = C(n-1, k-1) + C(n-1, k) Với C(n,0)=C(n,n)=1 Neu k=0 or k=n return 1 Else return C(n-1, k-1) + C(n-1, k)