Sáng kiến kinh nghiệm Định hướng giảng dạy thuật toán sắp xếp và tìm kiếm trong trường THPT

:=1 to n do
begin
read(f,x);
d:=1; c:=n;
while c-d>1 do
begin
g:=(d+c) div 2;
if b[g]>-x then c:=g else d:=g;
end;
gtmin:=min(gtmin,min(abs(x+b[d]),abs(x+b[c])));
if gtmin=0 then
begin
ghikq;
halt;
end;
end;
end;
procedure xuli;
begin
quicksort(1,n);
tinhtiep;
end;
begin
nhapdl;
xuli;
ghikq;
end.
2.5.3.2. Phần đáp án trắc nghiệm thuật toán sắp xếp
Câu hỏi
1
2
3
4
5
6
7
8
Đáp
Án
A
B
A
C
B
B
D
A
Câu hỏi
9
10
11
12
13
14
15
16
Đáp
Án
C
B
D
B
A
B
A
B
Câu hỏi
17
18
19
20
21
22
23
24
Đáp
Án
C
D
A
A
C
D
D
A
Câu hỏi
25
26
27
28
29
30
Đáp
Án
A
B
D
B
C
A
Hướng dẫn lựa chọn:
1. Tư tưởng của thuật toán sắp xếp nổi bọt là: Tìm và đổi chỗ các phần tử kề nhau sai thứ tự (phần tử đứng trước lớn hơn phần tử đứng sau) cho đến khi không tồn tại cặp nào sai thứ tự 
Chọn A
2. Áp dụng thuật toán sắp xếp nổi bọt xét từ đầu dãy về cuối dãy để được dãy tăng dần, ta so sánh hai phần tử đứng liền kề nhau, nếu số đứng trước lớn hơn số đứng sau thì đổi chỗ chúng cho nhau. Sau lượt duyệt 1 phần tử lớn nhất sẽ được đưa về cuối dãy 
Chọn B
3. Dãy chỉ có 1 phần tử thì coi như đã sắp xếp, sau mỗi lượt duyệt sẽ đưa 1 phần tử về đúng vị trí nên số lần duyệt để sắp xếp lại dãy A có N phần tử thành dãy giảm dần là N – 1 
Chọn A
4. Áp dụng thuật toán sắp xếp nổi bọt:
 23 12 34 6 -5 27
	12 23 34 6 -5 27
	12 23 34 6 -5 27
	12 23 6 34 -5 27
	12 23 6 -5 34 27
	12 23 6 -5 27 34	Lượt duyệt 1 
Chọn C
5. Với thủ tục sắp xếp nổi bọt đã cho xét từ cuối dãy về đầu dãy nên câu lệnh thiếu là: 
	For j:= n downto i+1 do 	
Chọn B
6. Áp dụng thuật toán sắp xếp nổi bọt để được dãy giảm dần:
	27 40 -7 5 57
	40 27 -7 5 57
	40 27 -7 5 57
	40 27 5 -7 57
	40 27 5 57 -7 Lần duyệt 1
	40 27 5 57 -7 
	40 27 5 57 -7 
	40 27 5 57 -7 
	40 27 57 5 -7 Lần duyệt 2 
Chọn B	
7. Áp dụng thuật toán sắp xếp nổi bọt để được dãy giảm dần:
	27 40 -7 5 57
	40 27 -7 5 57
	40 27 -7 5 57
	40 27 5 -7 57
	40 27 5 57 -7 Lần duyệt 1
	40 27 5 57 -7 
	40 27 5 57 -7 
	40 27 5 57 -7 
	40 27 57 5 -7 Lần duyệt 2
	40 27 57 5 -7 
	40 27 57 5 -7 
	40 57 27 5 -7 Lần duyệt 3
	40 57 27 5 -7 
	57 40 27 5 -7 Lần duyệt 4 
Chọn D
8. Với thủ tục sắp xếp chọn trực tiếp ở trên ta tiến hành tráo đổi a[j] và a[jmin] thông qua biến tg nên đoạn lệnh được đưa vào là: tg := a[j];
 	 a[j]:= a[jmin];
 	 a[jmin] := tg; 
Chọn A
9. Số phần tử của mảng trên là 10 nên cần thực hiện 9 lần chọn lựa phần tử nhỏ nhất để sắp xếp mảng A có thứ tự tăng dần: 
Chọn C
10. Áp dụng thuật toán sắp xếp chọn trực tiếp:
27 40 -7 5 57 34 18
 -7 40 27 5 57 34 18 Lần duyệt 1: Chọn trong dãy từ a1 an khóa nhỏ nhất là -7 rồi đổi vị trí cho phần tử a1 là 27	
Chọn B
11. Áp dụng thuật toán sắp xếp chọn trực tiếp:
27 40 -7 5 57 34 18
 -7 40 27 5 57 34 18 Lần duyệt 1: Chọn trong dãy từ a1 an khóa nhỏ nhất là -7 rồi đổi vị trí cho phần tử a1 là 27
	-7 40 27 5 57 34 18 
	-7 5 27 40 57 34 18 Lần duyệt 2: Chọn trong dãy từ a2  an khóa nhỏ nhất là 5 rồi đổi vị trí cho phần tử a2 là 40
	-7 5 27 40 57 34 18 
	-7 5 18 40 57 34 27 Lần duyệt 3: Chọn trong dãy từ a3  an khóa nhỏ nhất là 18 rồi đổi vị trí cho phần tử a3 là 27	
Chọn D
12. Áp dụng thuật toán sắp xếp chọn trực tiếp:
27 40 -7 5 57 34 18
 -7 40 27 5 57 34 18 Lần duyệt 1: Chọn trong dãy từ a1 an khóa nhỏ nhất là -7 rồi đổi vị trí cho phần tử a1 là 27
	-7 40 27 5 57 34 18 
	-7 5 27 40 57 34 18 Lần duyệt 2: Chọn trong dãy từ a2  an khóa nhỏ nhất là 5 rồi đổi vị trí cho phần tử a2 là 40
	-7 5 27 40 57 34 18 
	-7 5 18 40 57 34 27 Lần duyệt 3: Chọn trong dãy từ a3  an khóa nhỏ nhất là 18 rồi đổi vị trí cho phần tử a3 là 27
	-7 5 18 40 57 34 27
 -7 5 18 27 57 34 40 Lần duyệt 4: Chọn trong dãy từ a4  an khóa nhỏ nhất là 27 rồi đổi vị trí cho phần tử a4 là 40	
Chọn B
13. Tư tưởng thuật toán sắp xếp kiểu chèn là: sắp xếp dãy a1, a2,, ai trong điều kiện dãy ai-1 đã được sắp xếp rồi bằng cách chèn ai vào đúng vị trí dãy đó khi sắp xếp.	
Chọn A
14. Đoạn lệnh được đưa vào là: tg := a[i];
 j := i – 1; 	
Chọn B
15. Áp dụng thuật toán sắp xếp chèn để được dãy giảm:
27 40 -7 5 57
	40 27 -7 5 57 Lần duyệt 1: chèn 40 vào trước 27	
Chọn A
16. Áp dụng thuật toán sắp xếp chèn để được dãy giảm:
27 40 -7 5 57
	40 27 -7 5 57 Lần duyệt 1: chèn 40 vào trước 27.
40 27 -7 5 57 
	40 27 -7 5 57 Lần duyệt 2: so sánh không có sự đổi chỗ nào.	Chọn B
17. Áp dụng thuật toán sắp xếp chèn để được dãy giảm:
27 40 -7 5 57
	40 27 -7 5 57 Lần duyệt 1: chèn 40 vào trước 27.
40 27 -7 5 57 
	40 27 -7 5 57 Lần duyệt 2: so sánh không có sự đổi chỗ nào.
	40 27 -7 5 57 
	40 27 5 -7 57 Lần duyệt 3: chèn 5 vào trước -7.	
Chọn C
18. Áp dụng thuật toán sắp xếp chèn để được dãy giảm:
27 40 -7 5 57
	40 27 -7 5 57 Lần duyệt 1: chèn 40 vào trước 27.
40 27 -7 5 57 
	40 27 -7 5 57 Lần duyệt 2: so sánh không có sự đổi chỗ nào.
	40 27 -7 5 57 
	40 27 5 -7 57 Lần duyệt 3: chèn 5 vào trước -7.
	40 27 5 -7 57 
40 27 5 -7 57 Lần duyệt 4: chèn 57 vào trước 40	
Chọn D
19. Mảng gồm có 16 phần tử, nếu sắp xếp mảng theo kiểu trộn thì mảng A sẽ được chia nhỏ thành 4 lần. 	
Chọn A
20. Áp dụng thuật toán sắp xếp trộn:
 3 9 10 12 6 7 8 10
 3 9 10 12 6 7 8 10 Lần ghép 1: Tổ hợp 2 phần tử theo cách chia rồi so sánh và đổi chỗ.
	Chọn C
21. Áp dụng thuật toán sắp xếp trộn:
 3 9 10 12 6 7 8 10
 3 9 10 12 6 7 8 10 Lần ghép 1: Tổ hợp 2 phần tử theo cách chia rồi so sánh và đổi chỗ.
	 3 9 10 12 6 7 8 10 Lần ghép 2: Tổ hợp 4 phần tử theo cách chia rồi so sánh và đổi chỗ.
	Chọn A
22. Giá trị lớn nhất của mảng là 14 nên nếu sắp xếp mảng theo kiểu phân phối thì giá trị của V tối đa là giá trị 14.	
Chọn D
23. Áp dụng thuật toán sắp xếp mảng theo kiểu phân phối thì giá trị 5 đầu tiên theo thứ tự từ trái qua phải sẽ ở vị trí 5 của mảng mới sau khi sắp xếp theo thứ tự tăng dần.	
Chọn D
24. Trong thuật toán sắp xếp nhanh, so sánh giá trị các phần tử trong dãy với chốt, nên lệnh được đưa vào là: a[i] < x do inc (i) 	
Chọn A
25. Áp dụng thuật toán sắp xếp nhanh:
	5 0 4 2 6 7 9 8 11 3
(5 0 4 2 3) (7 9 8 11 6) 
Lần duyệt 1: chốt là 6 nên ta chia được thành 2 dãy (5 0 4 2 3) và (7 9 8 11 6)
	Chọn A
26. Áp dụng thuật toán sắp xếp nhanh:
	5 0 4 2 6 7 9 8 11 3
(5 0 4 2 3) (7 9 8 11 6) 
Lần duyệt 1: chốt là 6 nên ta chia được thành 2 dãy (5 0 4 2 3) và (7 9 8 11 6)
(3 0 2) ( 4 5) (7 9 8 11 6) 
Lần duyệt 2: Xét đoạn mới (5 0 4 2 3), chốt mới là 4 ta lại chia thành 2 dãy là (3 0 2) ( 4 5)	
Chọn B
27. Áp dụng thuật toán sắp xếp nhanh:
	5 0 4 2 6 7 9 8 11 3
(5 0 4 2 3) (7 9 8 11 6) 
Lần duyệt 1: chốt là 6 nên ta chia được thành 2 dãy (5 0 4 2 3) và (7 9 8 11 6)
(3 0 2) ( 4 5) (7 9 8 11 6) 
Lần duyệt 2: Xét đoạn mới (5 0 4 2 3), chốt mới là 4 ta lại chia thành 2 dãy là (3 0 2) ( 4 5)
0 (3 2) (4 5) (7 9 8 11 6) 
Lần duyệt 3: Xét đoạn mới (3 0 2), chốt mới là 0 ta lại chia thành 2 dãy mới là 0 và (3 2)	
Chọn D
28. Áp dụng thuật toán sắp xếp nhanh:
	5 0 4 2 6 7 9 8 11 3
(5 0 4 2 3) (7 9 8 11 6) 
Lần duyệt 1: chốt là 6 nên ta chia được thành 2 dãy (5 0 4 2 3) và (7 9 8 11 6)
(3 0 2) ( 4 5) (7 9 8 11 6) 
Lần duyệt 2: Xét đoạn mới (5 0 4 2 3), chốt mới là 4 ta lại chia thành 2 dãy là (3 0 2) ( 4 5)
0 (3 2) (4 5) (7 9 8 11 6) 
Lần duyệt 3: Xét đoạn mới (3 0 2), chốt mới là 0 ta lại chia thành 2 dãy mới là 0 và (3 2)
0 2 3 (4 5) (7 9 8 11 6) 
Lần duyệt 4: Xét đoạn mới (3 2), chốt mới là 3 ta lại chia thành 2 dãy mới là 2 và 3 	
Chọn B
29. Áp dụng thuật toán sắp xếp nhanh:
	5 0 4 2 6 7 9 8 11 3
(5 0 4 2 3) (7 9 8 11 6) 
Lần duyệt 1: chốt là 6 nên ta chia được thành 2 dãy (5 0 4 2 3) và (7 9 8 11 6)
(3 0 2) ( 4 5) (7 9 8 11 6) 
Lần duyệt 2: Xét đoạn mới (5 0 4 2 3), chốt mới là 4 ta lại chia thành 2 dãy là (3 0 2) ( 4 5)
0 (3 2) (4 5) (7 9 8 11 6) 
Lần duyệt 3: Xét đoạn mới (3 0 2), chốt mới là 0 ta lại chia thành 2 dãy mới là 0 và (3 2)
0 2 3 (4 5) (7 9 8 11 6) 
Lần duyệt 4: Xét đoạn mới (3 2), chốt mới là 3 ta lại chia thành 2 dãy mới là 2 và 3
0 2 3 4 5 (7 9 8 11 6) 
Lần duyệt 5: Xét đoạn mới (4 5), chốt mới là 4 ta lại chia thành 2 dãy mới là 4 và 5 	Chọn C
30. Áp dụng thuật toán sắp xếp nhanh:
	5 0 4 2 6 7 9 8 11 3
(5 0 4 2 3) (7 9 8 11 6) 
Lần duyệt 1: chốt là 6 nên ta chia được thành 2 dãy (5 0 4 2 3) và (7 9 8 11 6)
(3 0 2) ( 4 5) (7 9 8 11 6) 
Lần duyệt 2: Xét đoạn mới (5 0 4 2 3), chốt mới là 4 ta lại chia thành 2 dãy là (3 0 2) ( 4 5)
0 (3 2) (4 5) (7 9 8 11 6) 
Lần duyệt 3: Xét đoạn mới (3 0 2), chốt mới là 0 ta lại chia thành 2 dãy mới là 0 và (3 2)
0 2 3 (4 5) (7 9 8 11 6) 
Lần duyệt 4: Xét đoạn mới (3 2), chốt mới là 3 ta lại chia thành 2 dãy mới là 2 và 3
0 2 3 4 5 (7 9 8 11 6) 
Lần duyệt 5: Xét đoạn mới (4 5), chốt mới là 4 ta lại chia thành 2 dãy mới là 4 và 5 
0 2 3 4 5 (7 9 8 11 6) 
Lần duyệt 6: Xét đoạn mới (7 9 8 11 6), chốt mới là 8 ta lại chia thành 2 dãy mới là (7 6 8) và (11 9)	Chọn A
2.5.3.3. Phần tự luận thuật toán tìm kiếm
1. Để xác định số lần ta thực hiện kẻ bảng mô tả thực hiện thuận toán với 2 thuật toán:
- Thuật toán tìm kiếm tuần tự
I
1
2
3
4
5
6
7
8
9
10
A[i]
-9
-9
-5
-2
0
3
7
7
10
15
A[i]=k?
Đúng
Như vậy số lần thực hiện với thuật toán tìm kiếm tuần tự là 1
- Thuật toán tìm kiếm nhị phân:
I
1
2
3
4
5
6
7
8
9
10
A[i]
-9
-9
-5
-2
0
3
7
7
10
15
Dau
1
1
Cuoi
10
4
giua	
5
2
A[giua]=x?
sai
Đúng
Như vậy số lần thực hiện với thuật toán tìm kiếm tuần tự là 2
2. Program phantulonnhat;
var
	f1,f2:text;
	b:array[1..1000] of integer;
	i,n,x:integer;
Procedure nhap;
Begin
	assign(f1,'dulieu.inp');
	reset(f1);
	readln(f1,n,x);
 	For i:=1 to n do read(f1,b[i]);
	close(f1);
end;
function tim2(r,x : longint) : longint;
var	 d,c,g : longint;
begin
 	d:=0;c:=r;
 	g:=(d+c) div 2;
 	while (gd) and (gc) do
 	 begin
 	if b[g]>=x then c:=g else d:=g;
 	g:=(d+c) div 2;
 	end;
 	for g:=c downto d do
 	if b[g]<x then exit(g);
tim2:=g;
end;
Begin
	nhap;
	assign(f2,'dulieu.out');
	rewrite(f2);
	Write(f2,tim2(n,x));
	close(f2);
end.
3. Program phantubenhat;
var
	f1,f2:text;
	b:array[1..1000] of integer;
	i,n,x:integer;
Procedure nhap;
Begin
	assign(f1,'dulieu.inp');
	reset(f1);
	readln(f1,n,x);
 	For i:=1 to n do read(f1,b[i]);
	close(f1);
end;
function tim2(r,x : longint) : longint;
var 	d,c,g : longint;
begin
 	d:=1;c:=r;
 	g:=(d+c) div 2;
 	while (gd) and (gc) do
 	begin
 	if b[g]>=x then c:=g else d:=g;
 	g:=(d+c) div 2;
 	end;
 	for g:=d to c do
 	if b[g]>=x then exit(g);
	tim2:=g;
end;
Begin
	nhap;
	assign(f2,'dulieu.out');
	rewrite(f2);
	Write(f2,tim2(n,x));
	close(f2);
end.
4. Program phantulonnhat;
var
	f1,f2:text;
	b:array[1..1000] of integer;
	i,n,x:integer;
Procedure nhap;
Begin
	assign(f1,'dulieu.inp');
	reset(f1);
	readln(f1,n,x);
 	For i:=1 to n do read(f1,b[i]);
	close(f1);
end;
function tim2(r,x : longint) : longint;
var d,c,g : longint;
begin
 	d:=1;c:=r;
 	g:=(d+c) div 2;
 	while (gd) and (gc) do
 	begin
 	if b[g]>=x then c:=g else d:=g;
 	g:=(d+c) div 2;
 	end;
 	for g:=d to c do
 	f b[g]<=x then exit(g);
	tim2:=g;
end;
Begin
	nhap;
	assign(f2,'dulieu.out');
	rewrite(f2);
	Write(f2,tim2(n,x));
	close(f2);
end.
5. const fi='dulieu.inp';
 fo='dulieu.out';
 maxd= 30001;
var a: array[0..maxd] of longint;
 l: array[0..maxd] of integer;
 n: longint;
 d: longint;
 f1,f2:text;
procedure nhap;
var i:longint;
 f:text;
begin
 	assign(f1,fi); reset(f1);
 	eadln(f1,n);
 	for i:=1 to n do
 	read(f1,a[i]); 
close(f1);
end;
procedure xuli;
var i,k,dau,cuoi:longint;
begin
 	l[1]:=1;d:=1;
 	for i:=2 to n do
 	begin
 	f a[i]>a[l[d]] then
 	begin
 	inc(d);
 	l[d]:=i;
 	end
 	else
 	begin
 	dau:=1;
 	cuoi:=d;
 	while dau<cuoi do
 	begin
 	k:=(dau+cuoi) div 2;
 	if a[l[k]]<a[i] then
 	dau:=k+1
 	else
 	cuoi:=k;
 	end;
 	l[dau]:=i;
 	end;
 	end;
end;
procedure xuat;
begin
 	assign(f2,fo);rewrite(f2);
 	write(f2,d);
 	close(f2);
end;
begin
 	nhap;
 	xuli;
 	xuat;
end.
6. Sử dụng chặt nhị phân thời gian nhỏ nhất thỏa mãn, giả sử đang chặt tới thời điểm mid, xây dựng một đồ thị gồm các cạnh có trọng số <=mid, sau đó tôi tìm xem có thể ghép N công việc cho N người hay không (sử dụng kiến thức cặp ghép). Nếu thỏa mãn thì chặt nhỏ thời gian thỏa mãn, ngược lại chặt tăng thời gian thỏa mãn.
const fi='dulieu.inp';
 fo='dulieu.out';
 nmax=201;
type data=integer;
var
 	f1,f2:text;
 	A:array[0..nmax+1,0..nmax+1] of data;
 	n:data;
 	Q:array[0..nmax*nmax] of data;
 	tr,MatchX,MatchY:array[0..nmax] of data;
 	dau,cuoi,mid:data;
procedure docfile;
var 	i,j:data;
begin
 	assign(f1,fi); reset(f1);
 	readln(f1,n);
 	for i:=1 to n do
 for j:=1 to n do
 read(f1,a[i,j]);
 	close(f1);
end;
procedure them(x:data);
begin
 	inc(cuoi);
 	q[cuoi]:=x;
end;
function lay:data;
begin
 	lay:=q[dau];
 	inc(dau);
end;
function BFS:data;
var i,j,u,v:data;
begin
 	for i:=1 to n do tr[i]:=0;
 	dau:=1;
 	cuoi:=0;
 	for i:=1 to n do
 if MatchX[i]=0 then
 	them(i);
 	while dau<=cuoi do
 	begin
 	 	u:=lay;
 	for v:=1 to n do
 	 if (a[u,v]<=mid) and (tr[v]=0) then
 begin
 tr[v]:=u;
 if MatchY[v]=0 then
 exit(v);
 them(MatchY[v]);
 end;
 	end;
 EXIT(0);
end;
procedure enlager(u:data);
var v,next:data;
begin
 repeat
 v:=tr[u];
 next:=Matchx[v];
 matchx[v]:=u;
 Matchy[u]:=v;
 u:=next;
 until u=0;
end;
function slove:boolean;
var i,j,d:data;
begin
 for i:=1 to n do
 begin
 Matchx[i]:=0;
 Matchy[i]:=0;
 end;
 repeat
 d:=bfs;
 if d0 then
 Enlager(d);
 until d=0;
 for i:=1 to n do
 if Matchx[i]=0 then
 exit(false);
 exit(true);
end;
procedure xuli;
var i,j:data;
begin
	assign(f2,fo);	rewrite(f2);
 	i:=0;
 	j:=maxint;
 	while i<j do
 	begin
 	mid:=(i+j) shr 1;
 	if Slove then
 	j:=mid
 	else
 	i:=mid+1;
 	end;
 	writeln(f2,i);
	close(f2);
end;
begin
 docfile;
 xuli;
end.
7. Ý tưởng: 
Ta có nhận xét, nếu cắt ở độ cao H lấy được M mét gỗ thì khi cắt độ cao H1 cũng lấy được M mét gỗ. Ngược lại, nếu cắt ở độ cao H không lấy được M mét gỗ thì khi cắt độ cao H+1 cũng không lấy được M mét gỗ. Từ nhận xét trên ta có thể sử dụng giải thuật tìm kiếm nhị phân để tìm độ cao H cao nhất cần cắt để lấy được M mét gỗ thỏa mãn yêu cầu bài
* Chương trình:
program laygo;
const
 	fi='wood.inp';
 	fo='wood.out';
var
 	lo,k,hi,mid,s,m:int64;
 	i,n,H:longint;
 	f:text;
 	a:array[0..1000005] of longint;
procedure QSort(l,r:longint);
var x,i,j,tam:longint;
begin
 	x:=a[l+random(r-l+1)];
i:=l; 
j:=r; 
repeat 
while a[i]>x do inc(i); 
while a[j]<x do dec(j);
if i<=j then
begin 
tam:=a[i]; a[i]:=a[j]; a[j]:=tam; inc(i); dec(j); 
end;
until i>j; 
if i<r then Qsort(i,r);
if(l<j) then Qsort(l,j);
end;
Function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b; 
end; 
begin 
assign(f,fi); 
reset(f); 
readln(f,N,M); 
lo:=0; 
hi:=0; 
for i:=1 to n do 
begin 
read(f,a[i]); 
hi:=max(hi,a[i]); 
end; 
close(f);
Qsort(1,n); 
S:=0; 
a[n+1]:=0; 
i:=1; 
while s+int64(i)*(a[i]-a[i+1])<M do
begin 
s:=s+i*(a[i]-a[i+1]); 
inc(i);
 	end;
if (m-s) mod i =0 then k:=(m-s) div i 
else k:=(m-s) div i +1; 
H:=a[i]-k;
assign(f,fo); 
	rewrite(f); 
	write(f,H);	
	close(f); 
end.
2,5.3.4. Phần đáp án trắc nghiệm thuật toán tìm kiếm
Câu hỏi
1
2
3
4
5
6
7
8
Đáp
án
D
A
D
C
C
B
C
D
Câu hỏi
9
10
11
12
13
14
15
Đáp
Án
C
A
B
A
B
D
A
Hướng dẫn lựa chọn:
1. So sánh lần lượt các phần tử của dãy với khóa k, do vậy trong khi i<=n thì thực hiện việc so sánh đo nên đoạn lệnh còn thiếu là: i<=n Chọn D
2. Áp dụng thuật toán tìm kiếm tuần tự với dãy A: 6 8 13 -6 33 46 và k=8. So sánh lần lượt từ phần tử đầu tiên, ta thấy tại i=2 thì a2= 8 =k. Do đó, thuật toán dừng lại.	Chọn A
3. Áp dụng thuật toán tìm kiếm tuần tự với dãy A: 5, 7, 12, -5, 34, 47 và k=34. So sánh lần lượt từ phần tử đầu tiên, ta thấy tại i=5 thì a5= 34 =k. Do đó, thuật toán dừng lại.	Chọn D
4. Thuật toán tìm kiếm tuần tự dừng lại khi xét hết dãy mà không có phần tử nào bằng khóa hoặc khi có phần tử trong dãy bằng khóa.	Chọn C
5. Áp dụng thuật toán tìm kiếm tuần tự với dãy A: 4, 4, 12, -5, 32, 4 và k=4
Để đưa ra số lượng số k trong dãy ta xét từ phần tử đầu tiên đến phần tử cuối cùng xem có bằng k không. Do vậy, tại i=7 (i>n) thì thuật toán dừng lại.	Chọn C	
6. Với thủ tục mô tả thuật toán tìm kiếm nhị phân: ta thấy do x < a[giua] nên cần phải tính chỉ số cuoi mới. Vậy câu lệnh còn thiếu là: cuoi:= giua -1	Chọn B
7. Áp dụng thuật toán tìm kiếm nhị phân với dãy A: 1 3 3 3 4 4 6 7 và k = 3. 
Tại lần duyệt 1: giua = 4, agiua=3=k nên thuật toán dừng lại.	Chọn C
8. Áp dụng thuật toán tìm kiếm nhị phân với dãy A: 2 5 8 9 11 13 15 20 21 và k = 21. 
I
1
2
3
4
5
6
7
8
9
A[i]
2
5
8
9
11
13
15
20
21
Dau
1
6
Cuoi
9
9
giua	
5
7
A[giua]=x?
Sai
Sai
Tại lần duyệt 1: giua = 5
Tại lần duỵệt 2: giua = 7	Chọn D
9. Áp dụng thuật toán tìm kiếm nhị phân với dãy A: 12, 24, 27, 30, 33, 36 và k = 24. 
I
1
2
3
4
5
6
A[i]
12
24
27
30
33
36
Dau
1
Cuoi
6
giua	
3
A[giua]=x?
Sai
Tại lần duyệt 1: giua = 3	Chọn C
10. Áp dụng thuật toán tìm kiếm nhị phân với dãy A: 12, 24, 27, 30, 33, 36 và k = 24. 
I
1
2
3
4
5
6
A[i]
12
24
27
30
33
36
Dau
1
1
Cuoi
6
2
giua	
3
2
A[giua]=x?
Sai
Đúng
Số lần duyệt 2:	Chọn A
11. Áp dụng thuật toán tìm kiếm nhị phân với dãy A: 12, 24, 27, 30, 33, 36 và k = 44. 
I
1
2
3
4
5
6
A[i]
12
24
27
30
33
36
Dau
1
Cuoi
6
giua	
3
A[giua]=x?
Sai
Tại lần duyệt 1: giua = 3	Chọn B
12. Áp dụng thuật toán tìm kiếm nhị phân với dãy A: 12, 24, 27, 30, 33, 36 và k = 34. 
I
1
2
3
4
5
6
A[i]
12
24
27
30
33
36
Dau
1
4
6
6
Cuoi
6
6
6
5
giua	
3
5
6
A[giua]=x?
Sai
Sai
Sai
Số lần duyệt 4:	Chọn A
13. Áp dụng thuật toán tìm kiếm nhị phân với dãy A: 11 22 25 27 30 33 35 và k = 22. 
I
1
2
3
4
5
6
A[i]
11
22
25
30
33
35
Dau
1
1
Cuoi
6
2
giua	
3
2
A[giua]=x?
Sai
Đúng
Số lần so sánh để tìm được phần tử có giá trị bằng k = 22 là 2.	Chọn B
14. Thuật toán tìm kiếm nhị phân dừng khi giua = k hoặc dau>cuoi.
	Chọn D
15. Thuật toán tìm kiếm nhị phân áp dụng cho dãy có tính chất là dãy tăng.
	Chọn A
KẾT LUẬN
1. Sáng kiến đã xây dựng lại cách tiếp cận với một nội dung khó của tin học 11, sáng kiến đã hệ thống các ví dụ minh họa cũng như bài tập theo từng dạng cụ thể: Các thuật toán sắp xếp và tìm kiếm đơn giản cùng các ví dụ áp dụng cụ thể. Các ví dụ minh họa được sắp xếp chi tết từ dễ đến khó phù hợp với nhiều đối tượng học sinh giúp cho học sinh hiểu rõ hơn và sâu sắc hơn nội dung đang được nghiên cứu. Từ đó tạo được hứng thú học tập, phát huy tính tích cực, chủ động và sáng tạo của học sinh. Đồng thời, trong một mức độ nào đó cũng có thể dùng làm tài liệu bồi dưỡng học sinh giỏi.
2. Nhóm tác giả đã tiến hành giảng dạy và triển khai thực nghiệm chuyên đề này tại đơn vị công tác và được hoàn chỉnh, bổ sung sau mỗi năm học. Thực nghiệm đã thu được kết quả đáng kể. Kết quả thực nghiệm bước đầu cho thấy tính hiệu quả, tính khả thi và phổ dụng của sáng kiến này và đặc biệt là trong dạy học sinh giỏi.
3. Nội dung sáng kiến là tài liệu tham khảo bổ ích cho các thầy cô và học sinh nhằm thay đổi tư duy học sinh về việc học môn tin học. Đồng thời, bồi dưỡng năng lực tự học cho học sinh và góp phần đổi mới phương pháp dạy học trong giai đoạn hiện nay.
Tác giả mong nhận được sự góp ý từ các bạn đồng nghiệp, các em học sinh để việc áp dụng sáng kiến đạt hiệu quả hơn nữa và hoàn chỉnh nội dung của sáng kiến này./.
TÀI LIỆU THAM KHẢO
1. Hồ Sĩ Đàm, Sách giáo khoa, sách bài tập tin học 11
2. TS. Dương Xuân Thành, Giáo trình pascal
3. TS. Bùi Thế Tâm, Giáo trình Turbo Pascal 7.0, bài tập lập trình Turbo pascal.
4. Bùi Việt Hà, Tự học lập trình Pascal
5. Lê Văn Doanh, Trần Khắc Tuấn, 101 thuật toán & chương trình
6. Một số tài liệu tham khảo trên mạng