ĐỀ CƯƠNG ÔN TẬP MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

TÀI LIỆU THAM KHẢO - ĐỀ CƯƠNG ÔN TẬP MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Nội dung trích xuất từ tài liệu:
ĐỀ CƯƠNG ÔN TẬP MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Trường CĐCN Việt Đức Khoa CNTT  ĐỀ CƯƠNG ÔN THI HỌC KỲ 4 Môn: Chuyên ngành ( CTDL & GT) Khóa: 4_2009-2012_Ngành: Công nghệ thông tin Lớp: K4 CĐ Tin Khoa: CNTT ĐỀ CƯƠNG ÔN TẬP MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬTCâu số 1 Cho dãy số: 8, 12, 3, 4, 6, 1, 7, 9, 33, 22. Ứng dụng thuật toán sắp xếp Chọn để sắp xếp dãy số trên.Giải:Thuật toán: type mang = array [1..100] of integer; var a:mang; {sx chon} procedure sapxepchon (var a:mang; n:integer); var j,k,i:integer; tg:longint; begin for i:=1 to n-1 do begin k:=i; for j:=i+1 to n do if a[j] Trường CĐCN Việt Đức Khoa CNTT ví dụlượt 8 12 3 4 6 1 7 9 33 221 1 12 3 4 6 8 7 9 33 222 3 12 4 6 8 7 9 33 223 4 12 6 8 7 9 33 224 6 12 8 7 9 33 225 7 8 12 9 33 226 8 12 9 33 227 9 12 33 228 12 33 229 22 33Kq 1 3 4 6 7 8 9 12 22 33Câu số 2 Cho dãy số: 8, 12, 3, 4, 6, 1, 7, 9, 33, 22. Ứng dụng thuật toán sắp xếp Chèn để sắp xếp dãy số trên.Giải: Thuật toán sắp xếp chèn type mang = array [1..100] of integer; var a:mang; {sx chen} procedure sapxepchen (var a:mang; n:integer); var j,k,i:integer; x:longint; begin for i:=2 to n do begin x:=a[i]; j:=i-1; while (x0) do begin a[j+1]:=a[j]; j:=j-1; a[j+1]:=x;CTDL> -2- Trường CĐCN Việt Đức Khoa CNTT  end; end; end;ví dụ Bảng sau ghi lại các giá trị khoá tương ứng với từng bước. a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]Ban 8 12 3 4 6 1 7 9 33 22đầu 8 12 3 4 6 6 7 9 33 22 8 12 3 4 4 6 7 9 33 22 8 12 3 3 4 6 7 9 33 22 8 12 12 3 4 6 7 9 33 22 8 8 12 3 4 6 7 9 33 22Bước 1 1 8 12 3 4 6 7 9 33 22 8 12 12 4 6 7 9 33 22 8 8 12 4 6 7 9 33 22Bước 2 3 8 12 4 6 7 9 33 22 8 12 12 6 7 9 33 22 8 8 12 6 7 9 33 22Bước 3 4 8 12 6 7 9 33 22 8 12 12 7 9 33 22 8 8 12 7 9 33 22Bước 4 6 8 12 7 9 33 22 8 12 12 9 33 22 8 8 12 9 33 22Bước 5 7 8 12 9 33 22Bước 6 8 12 9 33 22 12 12 33 22Bước 7 9 12 33 22Bước 8 12 33 22 33 33Bước 9 22 33Kết 1 3 4 6 7 8 9 12 22 33quảCâu 3: Cho dãy số: 8,12,3,4,6,1,7,9,33,22. Ứng dụng thuật toán sắp xếp nổi bọn(bubble sort) để sắp xếp dãy số trên.Giải:Thuật toán sắp xếp nổi bọt : {sx noi bon}CTDL> -3- ...