Bài tập ôn tập cuối kỳ - Cấu trúc dữ liệu - Học Viện Kỹ Thuật Mật Mã

Mục lục
Câu 1: . Trình bày (bằng ngôn ngữ tựa C) giải thuật bổ sung một nút mới có chứa dữ liệu X
vào trước nút trỏ bởi Q trong danh sách móc nối hai chiều
Câu 2: Trình bày (bằng ngôn ngữ tựa C) giải thuật loại bỏ một nút trỏ bởi Q trong danh sách
móc nối hai chiều với: Pdau trỏ vào phần tử đầu, Pcuoi trỏ vào phần tử cuối, mỗi nút có cấu trúc như sau
Câu 3: Trình bày (bằng ngôn ngữ tựa C) giải thuật cộng 2 đa thức: C = A + B. Các phần tử
trong mỗi đa thức có cấu trúc như sau:
Câu 4: Trình bày (bằng ngôn ngữ tựa C) giải thuật định giá biểu thức hậu tố bằng cách dùng
STACK. Minh hoạ diễn biến của quá trình đọc biểu thức và sự thay đổi trong STACK với
biểu thức: 8 4 - 6 3 / + theo dạng:
Câu 5 : Trình bày (bằng ngôn ngữ tựa C) giải thuật duyệt cây theo thứ tự trước bằng giải thuật
không đệ qui có sử dụng STACK. Mỗi nút trên cây có cấu trúc như sau:
Câu 6: Trình bày (bằng ngôn ngữ tựa C) giải thuật duyệt cây theo thứ tự giữa bằng giải thuật
không đệ qui có sử dụng STACK. Mỗi nút trên cây có cấu trúc như sau
Câu 7: Trình bày (bằng ngôn ngữ tựa C) giải thuật tìm kiếm nhị phân. Đánh giá thời gian
thực hiện giải thuật với dãy có n phần tử.
Câu 8. Trình bày (bằng ngôn ngữ tựa C) giải thuật tìm kiếm có bổ sung trên cây nhị phân tìm
kiếm. Câu 9 : Trình bày (bằng ngôn ngữ tự nhiên và ngôn ngữ tựa C) giải thuật đệ qui quay
lui tìm tất cả các cách đặt 8 quân hậu vào bàn cờ vua sao cho không quân nào ăn quân nào.
Khi trình bày giải thuật bằng ngôn ngữ tựa C có mô tả cách tổ chức dữ liệu trong giải thuật
Câu 10: Trình bày (bằng ngôn ngữ tựa C) giải thuật cài đặt hàm đệ qui có dùng STACK cho
bài toán tính n!. Minh hoạ diễn biến của STACK, trong quá trình thực hiện giải thuật ứng với n = 3, theo dạng:
Câu 11:Trình bày (tựa C) giải thuật chuyển đổi biểu thức dạng trung tố sang dạng hậu tố
Câu 12. Trình bày (bằng ngôn ngữ tựa C) giải thuật sắp xếp nhanh (Quick Sort). Đánh giá
thời gian thực hiện giải thuật với dãy có n phần tử trong trường hợp tốt nhất
Câu 13. Trình bày (bằng ngôn ngữ tựa C) giải thuật sắp xếp vun đống (Heap Sort). Đánh giá
thời gian thực hiện giải thuật với dãy có n phần tử
Câu 14. Trình bày (bằng ngôn ngữ tựa C) giải thuật sắp xếp hoà nhập (Merge Sort). Đánh giá
thời gian thực hiện giải thuật với dãy có n phần tử
Câu 15 : Trình bày (bằng ngôn ngữ tựa C) giải thuật loại bỏ một nút có giá trị X trên cây nhị
phân tìm kiếm. Chi phí thời gian trung bình của giải thuật này có lớn hơn giải thuật tìm kiếm
rồi bổ sung hay không, vì sao?
Câu 16: Trình bày (bằng ngôn ngữ tự nhiên và ngôn ngữ tựa C) giải thuật Kiểm tra cây nhị
phân T có phải là "cây nhị phân tìm kiếm" hay không? Mỗi nút trên cây có cấu trúc như sau
1. Trình bày (bằng ngôn ngữ tựa C) giải thuật
bổ sung một nút mới có chứa dữ liệu X vào trước
nút trỏ bởi Q trong danh sách móc nối hai chiều
với: Pdau trỏ vào phần tử đầu, Pcuoi trỏ vào
phần tử cuối, mỗi nút có cấu trúc như sau:
P_L Trỏ tới nút bên trái DATA Chứa dữ liệu
P_R Trỏ tới nút bên phải
DOUBLE_IN(Pdau, Pcuoi, Q, X) //X: dữ liệu cần thêm {
Node MOI = malloc(); //khởi tạo nút MOI -> DATA = X; MOI -> P_L = NULL; MOI -> P_R = NULL;
if(Pcuoi == NULL){ //list rỗng thì gán MOI
làm phần tử đầu và cuối luôn Pdau = MOI; Pcuoi = MOI;
}else if(Q == Pdau){ // nếu Q là đầu list
thì... Pdau = MOI; //...gán lại nút đầu thành
nút mới MOI -> P_R = Q; //...nút phải của nút mới thành nút Q
Q -> P_L = MOI; //...nút trái của Q
(nút đầu list) thành nút Mới
}else{ //nếu Q là cuối list hoặc ở giữa
thì... //..chèn MỚI vào trước Q
MOI -> P_L = Q -> P_L; MOI -> P_R = Q; Q -> P_L = MOI;
//..chèn MỚI vào sau nút trước Q
Node TRUOC = MOI -> P_L;
TRUOC -> P_R = MOI;}}
2. Trình bày (bằng ngôn ngữ tựa C) giải thuật loại bỏ
một nút trỏ bởi Q trong danh sách móc nối hai chiều
với: Pdau trỏ vào phần tử đầu, Pcuoi trỏ vào phần tử
cuối, mỗi nút có cấu trúc như sau:
P_L Trỏ tới nút bên trái (Nút trước) DATA Chứa dữ liệu
P_R Trỏ tới nút bên phải (Nút sau)
DOUBLE_DEL(Pdau, Pcuoi, Q) {
if(Pcuoi == NULL){ // list trống thì k có đầu (hoặc cuối) printf("List empty!");
}else if(Pdau = Pcuoi){ //list có 1 phần tử, xoá
Q là thành NULL hết cả lũ Pdau = NULL; Pcuoi = NULL;
}else if(Q == Pdau){ //Pdau trỏ vào Q
Pdau = Pdau -> P_R; //chuyển Pdau thành phần tử tiếp theo
Pdau -> P_L = NULL; //Vì bên trái của phần tử
tiếp theo đó là Q nên phải đặt lại là NULL
}else if(Q == Pcuoi){ //Pcuoi trỏ vào Q, làm
ngược lại bên trên
Pcuoi = Pcuoi -> P_L; Pcuoi -> P_R = NULL;
}else{ //Q ở giữa list
Truoc = Q -> P_L; //lấy 2 phần tử trước và sau của nút Q Sau = Q -> P_R;
//gán lại trước sau cho chúng nó Truoc -> P_R = Sau; Sau -> P_L = Truoc; }
free(Q); //giải phóng bộ nhớ Q }
3. Trình bày (bằng ngôn ngữ tựa C) giải thuật cộng 2 đa thức: C = A + B. Các phần
tử trong mỗi đa thức có cấu trúc như sau: HSO Ghi hệ số, MU Ghi số mũ,
NEXT Ghi địa chỉ đến phần tử tiếp
theoThemNut(HSO, MU, TONG, DUOI){ NUT = malloc(); NUT->HSO = HSO; NUT->MU = MU; NUT->NEXT = NULL; if(TONG == NULL){ TONG = NUT; }elseif(TONG!=NULL){D UOI->NEXT = NUT; } DUOI = NUT; return DUOI; } CongDaThuc(D1, D2, TONG){ TONG = NULL; DUOI = NULL;
while(D1 != NULL && D2 !=
NULL){ if(D1->MU > D2->MU){ //store D1 tong
DUOI = ThemNut(D1->HSO, D1->MU, TONG, DUOI); //tinh tien 1 buoc D1 = D1->NEXT;
}else if(D1->MU < D2->MU){
DUOI = ThemNut(D2->HSO, D2->MU, TONG, DUOI); D2 = D2->NEXT; }else{ //mu 1 == mu 2
DUOI = ThemNut(D1->HSO + D2->HSO, D1->MU, TONG, DUOI); D1 = D1->NEXT; D2 = D2->NEXT; } } if(D1 != NULL){ while(D1 != NULL){
DUOI = ThemNut(D1->HSO, D1->MU, TONG, DUOI); D1 = D1->NEXT; } }else if(D2 !=
NULL){ while(D2 != NULL){
DUOI = ThemNut(D2->HSO, D2->MU, TONG, DUOI); D2 = D2->NEXT; } } return TONG; }
4. Trình bày (bằng ngôn ngữ tựa C) giải thuật định giá biểu thức hậu tố
bằng cách dùng STACK. Minh hoạ diễn biến của quá trình đọc biểu thức và
sự thay đổitrong STACK với biểu thức: 8 4 - 6 3 / + theo dạng: Diễn
biến đọc biểu thức Diễn biến STACK Thực hiện phép toán ***Ý tưởng
Ta xem biểu thức hậu tố như một dãy các thành phần,
mà mỗi thành phần là toán hạng hoặc toán tử
B1: Khởi tạo 1 stack rỗng
B2: Đọc lần lượt các phần tử của biểu thức từ trái qua phải
Nếu là toán hạng, đẩy vào stack
Nếu là toán tử X, lấy từ stack ra 2 giá trị (Y và Z)
sau đó áp dụng toán tử đó vào 2 giá trị vừa lấy ra,
đẩy kết quả tìm được (Z X Y) vào stack
B3: sau khi kết thúc B2, thì tất cả biểu thức hậu tố
đã đọc xong, trong stack còn duy nhất 1 phần tử là
giá trị của biểu thức*** DINH_GIA_BT(){
//sử dụng stack S, trỏ bởi T (top), ban đầu T = -
1; do( X = ký tự tiếp theo; if(X là toán hạng){ PUSH(STACK, T, X); }else if(X là toán tử){ S1 = POP(STACK, T); S2 = POP(STACK, T);
KQ = S2 X S1 //thực hiện phép toán
//(Phải là S2 X S1 vì S2 ở trước S1 (nên
S2 ra sau)) PUSH(STACK, T, KQ); }
)while(không gặp dấu kết thúc); KQ = POP(STACK, T); printf(KQ); }
5. Trình bày (bằng ngôn ngữ tựa C) giải thuật
duyệt cây theo thứ tự trước
bằng giải thuật không đệ qui có sử dụng STACK.
Mỗi nút trên cây có cấu trúc như sau: Ý tưởng: 1. kiểm tra rỗng
nếu cây rỗng thì kết thúc
nếu không rỗng thì khởi tạo stack
2. thực hiện duyệt
in ra khóa của nút gốc
nếu cây con phải khác rỗng thì lưu địa chỉ gốc cây con phải vào stack
chuyển xuống cây con trái, in ra khóa của nút con trái... (lặp lại)
P_L Trỏ tới cây con trái DATA Chứa dữ liệu
P_R Trỏ tới cây con phải TT_TRUOC(TREE){ if(TRE E == NULL){
printf("Cây rỗng"); return; //thoát hàm luôn }else{ //không rỗng TOP = -1; PUSH(STACK, TOP, TREE); } while(TOP > -1){ P = POP(STACK, TOP); while(P != NULL){
printf(P->DATA) //thăm nút P if(P->P_R){
PUSH(STACK, TOP, P->P_R); //lưu
địa chỉ nhánh bên phải để tí POP ra }P = P->P_L; } } }
6. Trình bày (bằng ngôn ngữ tựa C) giải thuật
duyệt cây theo thứ tự giữa bằng giải thuật
không đệ qui có sử dụng STACK. Mỗi nút trên cây
có cấu trúc như sau: Ý tưởng: 1. kiểm tra rỗng
nếu cây rỗng thì kết thúc
nếu không rỗng thì khởi tạo stack
2. thực hiện duyệt
lưu địa chỉ của nút gốc vào stack, chuyển xuống cây con trái
(lặp lại bước này tới
khi cây con trái là rỗng)
lấy phần tử trên cùng ra khỏi stack, trỏ vào vị trí của nút đó trên cây
in ra khóa của nút đang xét
trỏ đến cây con phải
.... (lặp lại cho tới khi stack rỗng)
P_L Trỏ tới cây con trái DATA Chứa dữ liệu
P_R Trỏ tới cây con phải TT_GIUA(TREE){ if(TRE E == NULL){ printf("Cay rong"); }else{
TOP = -1; //khởi tạo STACK rỗng
P = TREE; //P dùng để duyệt cây, gán thành
gốc cây while(TOP > -1 || P !=
NULL){ while(P != NULL){
PUSH(STACK, TOP, P); //lưu địa chỉ gốc..
P = P->P_L; //..rồi chuyển đến con trái
} //sau cái while này mình sẽ ở nút NULL
trái nhất của cây (hoặc cây con) //...và P sẽ là NULL P = POP(STACK, TOP);
printf(P->DATA); //in thông tin
P = P->P_R; //chuyển qua bên phải (có thể
chuyển thành NULL) }}}
7. Trình bày (bằng ngôn ngữ tựa C) giải thuật tìm kiếm nhị phân. Đánh giá
thời gian thực hiện giải thuật với dãy có n phần tử. TK_NP(K, size, x){
int t = 0; //vị trí phần từ đầu tiên trog mảng
int p = size - 1; //vt phần từ cuối while(t <= p){
int g = (t + p) / 2; //vt pt giữa trái và phải if(K[g] == x){ return g; } if(x < K[g]){ p = g - 1; }else{ t = g + 1; } }
printf("Không tìm thấy!"); return -1; }
Xét giải thuật nêu trên, ta thấy:
- Trường hợp tốt nhất là khi phần từ giữa mảng
ban đầu là giá trị cần tìm, trong trường hợp này
độ phức tạp là O(1)
- Trường hợp xấu nhất là khi phần tử cuối cùng
bằng x hoặc không tìm thấy, khi đó dãy phải
tiếp tục chia đôi đến khi còn 1 phần tử
Ta có w(n) biểu thị số lượng phép tính cần thiết: w(n)
= 1 + w(n/2) //cần 1 phép tính để chia đôi mảng = 1 + 1 + w(n/2^2) ... = k + w(n/2^k);
Vì chương trình chỉ dừng khi dãy có độ dài = 1 -->
n/2^k = 1 --> 2^k = n --> log2(n) = k
w(n) = log2(n) + w(1) = log2(n) + 1 Vậy Tx = O(log2(n))
Người ta cũng chứng minh được Ttb = log2(n)
- Có một lưu ý đó là muốn sử dụng thuật toán tìm kiếm
nhị phân thì ta phải sử dụng dãy đã được sắp xếp trước,
vậy nên phải tính thêm thời gian sắp xếp vào với những
dãy khoá biến động, luôn thêm bớt. Vậy đây chính là
nhược điểm của phương pháp tìm kiếm nhị phân
8. Trình bày (bằng ngôn ngữ tựa C) giải thuật tim kiếm có bổ sung trên cây
nhị phân tim kiếm. Mỗi nút trên cây có cấu trúc như sau:
P_L Trỏ tới cây con trái
KEY Chứa giá trị khoá
P_R Trỏ tới cây con phải BST(T, x, P){ /*
Tìm giá trị x trên cây T, nếu thấy thì trỏ P vào,
nếu k tìm thấy thì tạo thêm nút rồi trỏ P vào */ P = T; Q = null; while(P != null){ if(P->KEY = x){ return P; } Q = P; if(x < P- >KEY){ P = P->P_L; }else{ P = P->P_R; } } P = malloc(); P->KEY = x; P->P_L = null; P->P_R = null; if(x < Q- >KEY){ Q- >P_L = P; }else{ Q->P_R = P; }
printf("Không tìm thấy, đã bổ sung!"); return P; }
Câu 9 : Trình bày (bằng ngôn ngữ tự nhiên và ngôn ngữ tựa C)
giải thuật đệ qui quay lui tìm tất cả các cách đặt 8 quân hậu vào
bàn cờ vua sao cho không quân nào ăn quân nào. Khi trình bày
giải thuật bằng ngôn ngữ tựa C có mô tả cách tổ chức dữ liệu trong giải thuật
Xét bàn cờ vua có kích thước 8x8, ta cần đặt 8 quân hậu vào bàn cờ
vua sao cho k quân nào ăn quân nào, 8 quân hậu k ăn nhau tức chúng
nằm ở các hàng, các cột, các dường chéo khác nhau. Giả sử, ta đặt 8
con hậu vào 8 cột: con hậu j nằm ở cột j, hàng i, hai đường chéo là (i+j) và (i-j)
Quy tắc chọn hàng: để hàng I được chấp nhận thì hàng i và 2 đường
chéo i+j và i-j được tự do hay là k có con hậu nào trên hàng đó.
Xét trường hợp tổng quát:Ta tìm cách dặt quân hậu j vào hàng i cột j
bằng cách cho i chạy từ 1 đến 8 nếu tìm được 1 vị trí an toàn thì:
- Đặt con hậu j vào hàng đấy. Vị trí I,j không an toàn nữa
- Nếu là con hậu cuối cũng thì thu được 1 kết quả
- Nếu không phải con hậu cuối cùng, ta đặt caccs con hậu còn lại
ở các cột đến khi j=8 thì kết thúc
- Sau khi tìm được vị trí của con hậu j ta lại đặt vị trí i,j trở thành
an toàn để tìm các cách khác nhau Quy ước:
- x[j]=i: con hậu thứ j được đặt ở hành thứ i - a[j]=1: hàng i an toàn
- b[i+j]=1: đường chéo i+j an toàn
- c[i-j]=1: đường chéo i-j an toàn
10. Trình bày (bằng ngôn ngữ tựa C) giải thuật cài
đặt hàm đệ qui có dung STACK cho bài toán tính n!.
Minh hoạ diễn biến của STACK, trong quá trình thực
hiện giải thuật ứng với n = 3, theo dạng:
Số mức | Các bước thực hiện | Nội dung của STACK Factorial(){ /*
Giải thuật sử dụng stack, mỗi phần từ của Stack
có 2 thành phần: N là giá trị của n ở mức hiện tại,
RETADD là địa chỉ quay về
temrec là biến trung chuyển, chứa PARA (N) và
address ứng với lời gọi chính của chương trình (ĐCC) */ //B1 Push(S, Top, TEMREC);
//Bước 2. kiểm tra điều kiện cơ sở if(Top.N == 0){ GIAI_THUA = 1; goto Bước 4;
}else{//gán thông tin cho biến temrec để push PARA = Top.N - 1; ADDRESS = Bước 3; } goto Bước 1;
//Bước 3. Tính giai thừa
GIAI_THUA = GIAI_THUA * Top.N;
//Bước 4. Khôi phục địa chỉ quay về và N TEMREC = POP(S, Top);
goto ADDRESS; //có thể là địa chỉ chính (với N đầu tiên) //...hoặc Bước 3 return GIAI_THUA; } 1 Số mức Các bước thực hiện Nội dung stack 2 Vào mức 1 Bước 1: 3 | DCC <- TOP (Lời gọi Push(A, -1, (3, ĐCC) chính) Bước 2: N != 0 -> PARA = 3 - 1 = 2 ADDRESS = Buoc 3 goto Buoc 1; 3 Vào mức 2 Bước 1: 2 | Bước 3 <- TOP (Đệ quy Push(A, 0, (2, Bước 3) 3 | ĐCC lần 1) Bước 2:
Top.N != 0 -> Para = 2-1 = 1 Address = Bước 3 4 Vào mức 3 Bước 1: 1 | Bước 3 <- TOP (Đệ quy Push(A, 1, (1, Bươc 3) 2 | Bước 3 lần 2) Bước 2: 3 | ĐCC
Top.N != 0 -> PARA = 1 - 1 = 0 ADDRESS = Buoc 3 goto Buoc 1; 5 Vào mức 4 Bước 1: 0 | Bước 3 <- TOP (Đệ quy Push(A, 2, (0, Bước 3) 1 | Bước 3 lần 3) Bước 2: 2 | Bước 3 Top.N == 0 -> Giai_thua = 1 3 | ĐCC Goto Bước 4 6 Quay lại Bước 4: 1 | Bước 3 <- TOP mức 3 TEMREC = POP 2 | Bước 3 Goto Address (Bước 3) 3 | ĐCC Bước 3 Giai_thua = 1* Top.N = 1*1 = 1 7 Quay lại Bước 4 (sau Bước 3) 2 | Bước 3 <- TOP mức 2 TEMREC = POP(S, Top) 3 | ĐCC Goto Bước 3 Bước 3:
Giai_Thua = 1 * Top.N = 1 *2 = 2 8 Quay lại Bước 4 (sau Bước 3) 3 | DCC <- TOP mức 1 TEMREC = POP(S, Top) Goto Bước 3 Bước 3:
Giai_Thua = 2 * Top.N = 2 * 3 = 6 9 Quay lại Bước 4: Stack trống địa chỉ TEMREC = POP chính Goto Address (ĐCC)
11. Trình bày (bằng ngôn ngữ tự nhiên và ngôn
ngữ tựa C) giải thuật chuyển đổi biểu thức dạng
trung tố sang dạng hậu tố. Ý tưởng:
1. khởi tạo 1 ngăn xếp (stack) rỗng
2. đọc lần lượt các thành phần trong biểu thức
nếu X là toán hạng thì viết nó vào biểu thức
hậu tố (in ra) nếu X là phép toán thì thực hiện:
+ nếu stack không rỗng thì: nếu phần tử ở đỉnh
stack là phép toán có độ ưu tiên cao hơn hoặc
bằng phép toán hiện thời (X) thì phép toán đó
được kéo ra khỏi stack và viết vào biểu thức
hậu tố (lặp lại bước này)
+ nếu stack rỗng hoặc phần ử ở đỉnh ngăn xếp là
dấu mở ngoặc hoặc phép toán ở đỉnh ngăn xếp có
quyền ưu tiên thấp hơn phép toán hiện thời (X)
thì phép toán hiện thời được đẩy vào ngăn xếp
nếu X là dấu mở ngoặc thì nó được đẩy vào stack
nếu X là dấu đóng ngoặc thì thực hiện:
+ (bước lặp):loại các phép toán ở đỉnh ngăn xếp
và viết vào biểu thức dạng hậu tố cho tới khi
đỉnh ngăn xếp là dấu mở ngoặc
+ loại dấu mở ngoặc khỏi ngăn xếp
3. sau khi toàn bộ biểu thức dạng trung tố được
đọc, loại lần lượt các phép toán ở đỉnh stack
và viết vào biểu thức hậu tố cho tới khi stack rỗng Giải thuật:
CHUYEN_TRUNG_TO_SANG_HAU_TO ()
{//Giải thuật này sử dụng 1 stact S, trỏ bởi Top, lúc đầu T = -1
// Biểu thức trung tố gồm có: số, toán
tử, 2 dấu ‘(‘ và ’)’
//Các phép * / có độ ưu tiên cao hơn + -
(nhân chia trước cộng trừ sau)
do{ Đọc thành phần X tiếp theo trong biểu thức; if (X là toán hạng){ printf(X); }else if (X là phép toán){ do {
if ((Top>-1) && (Top là phép
toán có độ ưu tiên cao hơn hay bằng X)){ printf(POP(S, Top)); }
if (Top==-1 || Top=="(" || Top
là phép toán có độ ưu tiên thấp hơn X){ PUSH (S, Top, X); }
}while (phép toán X chưa được đưa
vào S); }else if (X là dấu "("){ PUSH (S, Top, X); }else if (X là dấu ")"){ do{
printf(POP(S, Top)); // in ra
các phép toán}while (Top != "(");
POP(S, Top); // loại dấu ‘(’ ra khỏi S }
}while (chưa gặp dấu kết thúc biểu thức);
do{ printf(POP(S, Top)); // in ra các phép toán còn lại }while (T>-1);}
12. Trình bày (bằng ngôn ngữ tựa C) giải thuật sắp xếp nhanh
(Quick Sort).Đánh giá thời gian thực hiện giải thuật với dãy có n
phần tử trong trường hợp tốt nhất.
GIẢI: K; mảng
trai, phai: chỉ số của phần tử bên trái
và bên phải của mảng
j: chỉ số của phần tử khoá
QuickSort(K, trai, phai){ if(t>p){
j = PhanDoan(K, trai, phai);
QuickSort(K, trai, j-1);
QuickSort(K, j+1, phai); } } PhanDoan(K, vtt, vtp){
i = vtt + 1; //vị trí sau khoá hiện tại j = vtp;
do{ while(i <= j && K[i] < K[vtt]){ i++; }
while(i <= j && K[j] > K[vtt]){ j--; } if(i K[i] <-> K[j]; i++; j--; }
}while(i<=j); //khi ra khỏi vòng lặp là đã
tìm được vị trí cho chốt K[vtt] <-> K[j];
return j; //trả về vị trí đúng của chốt }
Phân tích giải thuật
Gọi T(n) là thời gian thực hiện giải thuật ứng với 1 khoá,
P(n) là thời gian để phân đoạn 1 mảng n khoá
thành 2 mảng con, ta có:
T(n) = P(n) + T(j-t) + T(p-j)
Ta thấy P(n) = Cn = O(n)
- Trường hợp xấu nhất: Dãy đã được sắp xếp sẵn
-> Sau khi phân đoạn thì 1 trong 2 mảng là rỗng (j = t hoặc j = p)
Giả sử j = t ta có:
Tx(n) = P(n) + Tx(0) + Tx(n-1) = C(n) + Tx(n-1)
= C(n) + C(n-1) + Tx(n-2)....
= Tổng từ 1 đến n của Cn + Tx(0) = C(n.(n+1)/2) = O(n^2)
-> Vậy với trường hợp xấu nhất thì Quicksort
không hơn gì các phương pháp sắp xếp đơn giản
- Trường hợp tốt nhất là khi dãy khoá tiếp tục
được chia đều làm 2 nửa
Tt(n) = P(n) + 2*Tt(n/2)= Cn + 2*C(n/2) + 2^2*Tt(n/4) .....
= log2(n)*Cn + 2^(log2(n)) * Tt(1) = log2(n)*Cn + n*Tt(1) = O(nlog2n)
13. Trình bày (bằng ngôn ngữ tựa C) giải thuật
sắp xếp vun đống (Heap Sort).Đánh giá thời gian
thực hiện giải thuật với dãy có n phần tử. HEAP_SORT(){
//vòng for sau đây sẽ tạo thành đống cho cây ban đầu
//và tất cả các cây con của nó
for(int i = (n-1)/2; i >=0; i--){ ADJUST(i, n); }
for(int i = n-1; i >= 0; i--){ K[0] <-> K[i]; ADJUST(0, i); } }
ADJUST(int root, int n){ /*
Giải thuật này thực hiện việc chỉnh sửa 1
câythành ĐỐNG với điều kiện rằng 2 cây con của
câyđã là ĐỐNG rồi. Cây được lưu trữ trên mảng K
có n phần tử (từ 0-n) */ int Key = K[root];
while(root * 2 <= n-2){ //chừng nào nút chưa
phải lá (root *2 < n-1)
int c = root*2 + 1; vị trí nút con trái
if(c+1 < n && K[c] < K[c+1]){ c = c+1; } if(K[c] < Key){ break; } K[root] = K[c]; root = c; } K[root] = Key; }
Đánh giá thời gian thực hiện với dãy n phần tử
Ta sẽ chỉ chú ý vào trường hợp xấu nhất:
Ta thấy ở vòng for đầu tiên ta phải gọi hàm
ADJUST xấp xỉ n/2 lần.
Vòng for thứ 2 gọi hàm ADJUST n lần.
Ta thấy cây được xét ở hàm ADJUST là cây đầy
đủ, nghĩa là chiều
cao của nó cao nhất cũng chỉ là log2(n+1), xấp xỉ log2n
-> Số lần so sánh giá trị khoá khi thực hiện hàm ADJUST cũng
chỉ là log2n lần (bằng chiều cao của cây tương ứng)
Vậy ta có thể nói số lần thực hiện phép so sánh cùng lắm sẽ là: 3/2 * nlog2n Suy ra T(x) = O(nlog2n)
Đây là ưu điểm của Heap Sort so với Quicksort,
trường hợp xấu nhất
của Heap Sort cũng chỉ có đỘ phức tạp là
O(nlog2n), còn Quicksort là O(n^2)
14. Trình bày (bằng ngôn ngữ tựa C) giải thuật sắp xếp hoà nhập (Merge
Sort). Đánh giá thời gian thực hiện giải thuật với dãy có n phần tử.
//giải thuật hoà nhập 2 đường Merge(K, b, m, n, X){ /*
K: mảng chứa 2 mảng con
X: Mảng chứa 1 mảng to được gộp bởi 2 mảng trên
b: vị trí bắt đầu của mảng con 1
m: vị trí kết thúc mảng con 1 n:
vị trí kết thức mảng con 2 */
i = b; //i và j là biến chạy ở mảng con 1 và 2 của K
j = m+1; //vị trí bắt đầu mảng con 2
t = b; //vị trí bắt đầu mảng gộp ở mảng X, biến chạy trên X
while(i <= m && j <= n){ if(K[i] < K[j]){ X[t++] = K[i++] }else{ X[t++] = K[j++]; } }
//đến bước này, 1 trong 2 mảng con đã hết khoá
if(i>m){ //Mảng con 1 hết khoá
//-> cho hết khoá ở mảng 2 xuống for(;j <= n;){ X[t++] = K[j++]; } }else{ for(;i <= n;){ X[t++] = K[i++]; } } }
//Hàm này thực hiện hoà nhập từng cặp mạch có độ dài là h kế cận nhau
// với dãy có n phần tử từ mảng K qua mảng X MPASS(K, X, n, h){ i = 0; while(i + 2*h <= n){
Merge(K, i, i + h - 1, i + 2*h - 1, X); i = i + 2*h; } if(i + h < n){
Merge(K, i, i + h - 1, n-1, X); }else{ for(;i X[i++] = K[i++]; } } }
//Hàm MPASS trên sẽ được gọi trong hàm chính sau STRAIGHT_MSORT(K, n){ /*
Ở đây sẽ dùng 1 mảng phụ X[n], 2 mảng được dùng luân phiên
H lưu kích thước mạch, sau mỗi 1 lần gọi MPASS thì h được nhân đôi */ h = 1; while(h < n){ MPASS(K, X, n, h); h = h*2; MPASS(X, K, n, h); h = h*2; } }
Đánh giá giải thuật:
Ta thấy với Hàm MPASS, mỗi 1 lượt gọi thì các phần tử ở K
sẽ được chuyển hết xuống X, vậy chi phí thời gian cho 1 lượt có cấp O(n).
Với hàm STRAIGHT_MSORT thì số lượt gọi hàm MPASS sẽ là log2n lần,
vì ở lượt gọi đầu tiên thì h = 2^0 = 1, ở lượt thứ i thì h = 2^(i-1).
Mà sau lượt gọi cuối cùng thì kích thước mảng bằng n --> 2^(i-1) = n --> i - 1 = log2n
--> i xấp xỉ log2n
Vậy chi phí thời gian cho giải thuật này là O(nlog2n).
Một lưu ý khác nữa đó là giải thuật này có chi phí không gian
khá lớn do phải dùng mảng phụ có kích thước bằng mảng ban đầu.
Vì vậy ng ta thường dùng phương pháp sắp xếp này với kiểu sắp xếp ngoài.