Bài tập Kỹ thuật lập trình - Nguyễn Duy Phương

P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
155 
VI. Các kỹ thuật sắp xếp và tìm kiếm 
6.1. Các phương pháp sắp xếp cơ bản 
BÀI 6.1.1: 
Cho một dãy số nguyên dương: 6, 8, 12, 9, 2, 2, 98, 23, 23. Hãy mô phỏng sắp xếp 
tăng dần bằng các thuật toán: sắp xếp chọn, sắp xếp chèn, sắp xếp nổi bọt, sắp xếp 
Shellsort. 
BÀI 6.1.2: 
Cho dãy n số nguyên a[0], a[1],, a[n-1] đã được sắp xếp tăng dần và một số 
nguyên x. 
a. Hãy viết hàm tìm kiếm nhị phân kiểm tra xem x có thuộc dãy số trên hay không? 
Nếu tìm thấy trả về giá trị i nhỏ nhất mà a[i] = x, nếu không trả về giá trị -1. 
b.Cho dãy n = 8 số nguyên như sau: 
 1 2 4 4 4 9 10 15 
 Nếu x = 4 thì phương pháp tìm kiếm nhị phân cho ra kết quả gì ? 
c.Cho biết k số phần tử lớn nhất của dãy. 
 Ví dụ với n = 12 
 9 6 2 7 9 9 6 5 7 9 6 7 
 Nếu k = 5 thì kết quả là 9, 9, 9, 9, 7 
BÀI 6.1.3: 
Cho mảng 1 chiều n phần tử. Sắp xếp các số nguyên tố tăng dần, các số khác 
giữ nguyên giá trị và vị trí. 
BÀI 6.1.4: 
Cho mảng vuông n. Hãy tìm phần tử lớn nhất trên mỗi đường chéo song 
song với đường chéo chính. 
BÀI 6.1.5: 
Cho ma trận 2 chiều m dòng, n cột.. Hãy sắp tăng dần các phần tử theo chiều 
từ trái qua phải và từ trên xuống dưới. 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
156 
BÀI 6.1.6: 
Sắp xếp các phần tử trên các đường chéo song song với đường chéo chính 
tăng dần. 
BÀI 6.1.7: 
Cho mảng một chiều gồm n phần tử là các số nguyên. Sắp xếp các số chẵn trong 
mảng theo thứ tự tăng, sắp xếp các số lẻ theo thứ tự giảm dần, các số 0 giữ nguyên 
vị trí.. 
BÀI 6.1.8: 
Cho mảng một chiều gồm n phần tử là các số nguyên. Tìm k giá trị lớn nhất khác 
nhau của mảng 
BÀI 6.1.9: 
Cho mảng một chiều gồm n phần tử là các số nguyên. 
a. Chỉ giữ lại một giá trị trong số các giá trị giống nhau. 
b. Sắp xếp các số chẵn trong mảng theo thứ tự tăng, sắp xếp các số lẻ theo thứ tự 
giảm dần, các số 0 giữ nguyên vị trí. 
BÀI 6.1.10: 
Cho tập tin văn bản songuyen.inp chứa các số nguyên. Hãy ghi các số 
nguyên tố trong tập tin songuyen.inp vào tập tin nguyento.out theo thứ tự tăng dần 
mỗi dòng ghi 10 số, các số cách nhau ít nhất một khoảng cách. 
BÀI 6.1.11: 
Cho 2 file số nguyên được sắp tăng dần. Hãy trộn 2 file để được một file cũng được 
sắp tăng dần (không dùng mảng). 
BÀI 6.1.12: 
Trong 3 phương pháp sắp xếp cơ bản là phương pháp chọn, chèn và nổi bọt thì 
phương pháp nào là nhanh nhất đối với một tập tin đã được sắp rồi? 
BÀI 6.1.13: 
Trong 3 phương pháp sắp xếp cơ bản là phương pháp chọn, chèn và nổi bọt thì 
phương pháp nào là nhanh nhất đối với một tập tin đã được sắp thứ tự đảo ngược? 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
157 
BÀI 6.1.14: 
Hãy kiểm chứng 2 câu hỏi trên bằng lập trình với dãy số nguyên. 
BÀI 6.1.15: 
Hãy đưa ra một lý do hợp lý tại sao không thuận tiện khi dùng một khóa cầm canh 
(đứng gác) cho phương pháp sắp xếp chèn (trừ phương pháp phát sinh từ cài đặt của 
Shellsort). 
BÀI 6.1.16: 
Có bao nhiêu phép so sánh được dùng bởi Shellsort với sắp-7, rồi sắp-3 với các khóa 
E A S Y Q U E S T I O N? 
BÀI 6.1.17: 
Hãy cho một ví dụ để minh họa tại sao 8, 4, 2, 1 sẽ không là một cách tốt để kết thúc 
một dãy tăng của Shellsort. 
BÀI 6.1.18: 
Phương pháp sắp xếp chọn có ổn định không? Tương tự đối với chèn và nổi bọt? 
BÀI 6.1.19: 
Hãy thử nghiệm với các dãy tăng khác nhau cho Shellsort, tìm một dãy mà nó chạy 
nhanh hơn dãy được cho bởi một tập tin ngẫu nhiên gồm 1000 phần tử. 
BÀI 6.1.20: SẮP XẾP 2 
Cho một danh sách chứa cả các số và các từ. Yêu cầu bạn hãy sắp xếp danh sách này tăng 
dần sao cho các từ theo thứ tự từ điển, các số theo thứ tự số. Hơn nữa, nếu phần tử thứ n là 
số thì danh sách sau khi sắp xếp phần tử thứ n cũng phải là số, nếu là từ thì vẫn là từ. 
Lưu ý: Các từ chỉ gồm các chữ in thuờng trong bảng chữ cái tiếng Anh. 
Input 
Gồm nhiều dòng, mỗi dòng là một danh sách. Mỗi phần tử của danh sách cách nhau 
bởi dấu phẩy (“,”) theo sau là dấu cách, và danh sách được kết thúc bằng dấu chấm 
(“.”). 
Dữ liệu kết thúc bởi dòng chỉ chứa một dấu chấm. 
Output 
P
T
I
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
158 
Với mỗi danh sách trong dữ liệu, xuất ra danh sách đã sắp xếp thỏa mãn yêu cầu đề 
bài (có định dạng như trong dữ liệu). 
Ví dụ: 
Input: 
0. 
banana, strawberry, orange. 
banana, strawberry, orange. 
10, 8, 6, 4, 2, 0. 
x, 30, -20, z, 1000, 1, y. 
50, 7, kitten, puppy, 2, orangutan, 52, -100, bird, worm, 7, beetle. 
Output: 
0. 
banana, orange, strawberry. 
banana, orange, strawberry. 
0, 2, 4, 6, 8, 10. 
x, -20, 1, y, 30, 1000, z. 
-100, 2, beetle, bird, 7, kitten, 7, 50, orangutan, puppy, 52, worm. 
BÀI 6.1.21: CHỨNG KHOÁN 
Cho trước lịch sử giao dịch của một mã chứng khoán trong n ngày. Hãy xác định k1 ngày 
có giá thấp nhất và k2 ngày có giá cao nhất. 
Input 
Mỗi bộ test gồm 2 dòng 
 Dòng 1 ghi 3 số n, k1, k2 với n<=106. k1+k2<=n và k1,k2<=100. 
 Dòng tiếp theo ghi n số nguyên theo thứ tự là giá của mã chứng khoán trong n 
ngày liên tiếp. 
Bộ test cuối cùng chứa 3 số 0 
Output 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
159 
Với mỗi bộ test, ghi ra màn hình 3 dòng gồm: 
 Dòng 1 ghi số thứ tự bộ test 
 Dòng 2 ghi k1 ngày có giá thấp nhất theo thứ tự các ngày tăng dần. Nếu có nhiều 
danh sách cho kết quả giống nhau thì chọn danh sách thấp nhất theo thứ tự từ 
điển. 
 Dòng 3 ghi k2 ngày có giá cao nhất theo thứ tự các ngày giảm dần. Nếu có nhiều 
danh sách cho kết quả giống nhau thì chọn danh sách cao nhất theo thứ tự từ 
điển. 
Ví dụ: 
Input: 
10 3 2 
1 2 3 4 5 6 7 8 9 10 
10 3 2 
10 9 8 7 6 5 4 3 2 10 0 0 
Output: 
Case 1 
1 2 3 
10 9 
Case 2 
8 9 102 1 
BÀI 6.1.22: CHẠY ĐUA MARATHON 
John cho các con bò của mình chạy đua marathon! Thời gian bò N (1 <= N <= 5,000) về 
đích được biểu diễn theo dạng Số giờ (0 <= Số giờ <= 99), Số phút (0 <= Số phút <= 59), 
và số giây (0 <= Số giây <= 59). Để xác định nhà vô địch, John phải sắp xếp các thời gian 
(theo số giờ, số phút, và số giây) theo thứ tự tăng dần, thời gian ít nhất xếp đầu tiên. 
Ví dụ: Với 3 thời gian như sau: 
 11:20:20 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
160 
 11:15:12 
 14:20:14 
Kết quả sau khi sắp xếp là: 
 11:15:12 
 11:20:20 
 14:20:14 
INPUT FORMAT: 
* Line 1: 1 số nguyên: N 
* Lines 2..N+1: Dòng i+1 chứa thời gian bò i được mô tả bởi 3 số nguyên cách bởi 
dấu cách : Số Giờ , Số Phút, Số giây. 
OUTPUT FORMAT: 
* Dòng 1..N: Mỗi dòng chứa thời gian của 1 con bò là 3 số nguyên cách nhau bởi 
dấu cách sau khi đã sắp xếp. 
SAMPLE INPUT: 
3 
11 20 20 
11 15 12 
14 20 14 
SAMPLE OUTPUT: 
11 15 12 
11 20 20 
14 20 14 
BÀI 6.1.23: REPLACING DIGITS 
Cho số nguyên dương a có N chữ số và số dãy s có M chữ số. Chữ số ở vị trí j (1<=j<=M) 
của dãy s có thể chọn bất kì vị trí i (1<=i<=N) trong số a và thay thế bằng sj. Mỗi chữ số 
của dãy s chỉ được thay thế không quá một lần. 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
161 
Nhiệm vụ của bạn là hãy tìm cách thay sao cho số a đạt giá trị lớn nhất. Bạn có thể không 
cần sử dụng tất cả các chữ số trong s. 
Input 
Dòng đầu chứa số nguyên dương a có độ dài N (không bắt đầu bằng chữ số 0). 
Dòng 2 chứa dãy s có độ dài M 
(1≤N,M≤105) 
Output 
Số a lớn nhất có thể thay thế được. 
Ví dụ: 
Input: 
1024 
010 
Output: 
1124 
Input: 
987 
1234567 
Output: 
987 
6.2. Quicksort 
BÀI 6.2.1: 
Hãy vẽ cây phân hoạch đệ qui của thuật toán Quick-Sort trong trường hợp xấu nhất. 
Từ đó, chứng tỏ rằng chi phí thuật toán Quick-sort trong trường hợp này là O(n2). 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
162 
BÀI 6.2.2: 
Cài đặt một thuật toán Quicksort đệ quy với sự cắt xén bớt phép sắp xếp chèn cho 
các tập tin con có ít hơn M phần tử và xác đinh theo kinh nghiệm giá trị của M mà 
nó sẽ chạy nhanh nhất trên một tập tin có 1000 phần tử. 
BÀI 6.2.3: 
Giải bài toán trên đối bằng khử đệ quy. 
BÀI 6.2.4: 
Giải bài toán trên có bổ sung phép chọn phần tử giữa của 3 phần tử. 
BÀI 6.2.5: 
Quicksort sẽ thực hiện bao lâu để sắp một tập tin gồm N phần tử bằng nhau? 
BÀI 6.2.6: 
Số lần tối đa mà phần tử lớn nhất có thể được di chuyển trong lúc thi hành Quicksort 
là bao nhiêu? 
BÀI 6.2.7: 
Hãy chỉ ra làm thế nào tập tin A B A B A B A được phân hoạch, sử dụng các phương 
pháp đã học? 
BÀI 6.2.8: 
Quicksort dùng bao nhiêu phép so sánh để sắp xếp các khóa E A S Y Q U E S T I 
O N? 
BÀI 6.2.9: 
Cần bao nhiêu khóa “cầm canh” nếu phương pháp sắp xếp chèn được gọi một cách 
trực tiếp từ Quicksort? 
BÀI 6.2.10: 
Có hợp lý không khi dùng một hàng đợi thay vì một ngăn xếp cho một bản cài đặt 
không đệ quy của Quicksort? Tại sao có và tại sao không? 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
163 
BÀI 6.2.11: 
Viết một chương trình để tổ chức lại một tập tin sao cho tất cả các phần tử với các 
khóa bằng với giá trị trung bình thì nằm tại chỗ, với các phần tử nhỏ hơn thì nằm 
bên trái và các phần tử lớn hơn thì nằm bên phải. 
6.3. Heapsort 
BÀI 6.3.1: 
Hãy cho biết số phần tử tối thiểu và tối đa trong một heap có chiều cao h ? 
BÀI 6.3.2: 
Vẽ heap có được khi các thao tác sau thực hiện trên một heap rỗn ban đầu: insert(10), 
insert(5), insert(2), replace(4), insert(6), insert(8), remove, insert(7), insert(3). 
BÀI 6.3.3: 
Một tập tin sắp theo thứ tự ngược có phải là một heap không? 
BÀI 6.3.4: 
Hãy cho heap được tạo bởi việc áp dụng liên tiếp phép chèn trên các khóa E A S Y 
Q U E S T I O N. 
BÀI 6.3.5: 
Các vị trí nào có thể bị chiếm bởi khóa nhỏ thứ ba trong một heap kích thước 32. 
BÀI 6.3.6: 
Tại sao không dùng một biến cầm canh để tránh phép kiểm tra j < N trong 
downheap? 
BÀI 6.3.7: 
Hãy minh họa làm thế nào để nhận được các hàm của ngăn xếp và hàng đợi chuẩn 
như là trường hợp đặc biệt của các hàng đợi có ưu tiên. 
BÀI 6.3.8: 
Số khóa tối thiểu phải được di chuyển trong một thao tác “hủy cái lớn nhất: trong 1 
heap là bao nhiêu? Hãy vẽ 1 heap có kích thước 15 mà số tối thiểu đạt được. 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
164 
BÀI 6.3.9: 
Viết một chương trình để xóa phần tử ở vị trí thứ k trong 1 heap. 
BÀI 6.3.10: 
Hãy so sánh theo kinh nghiệm, việc xây dựng heap từ dưới lên với việc xây dựng 
heap từ trên xuống, bằng cách nào tạo các heap với 1000 khóa ngẫu nhiên. 
6.4. Mergesort 
BÀI 6.4.1: 
Viết chương trình cho phương pháp sắp xếp trộn (Merge sort) đệ quy bằng cách cắt 
xén bớt phương pháp sắp xếp chèn cho các tập tin con nhỏ hơn M phần tử; hãy xác 
định theo kinh nghiệm giá trị của M để nó chạy nhanh nhất trên một tập tin ngẫu 
nhiên gồm 1000 phần tử. 
BÀI 6.4.2: 
So sánh theo kinh nghiệm sắp xếp trộn đệ quy và không đệ quy cho các xâu liên kết 
và N = 1000. 
BÀI 6.4.3: 
Cài đặt phép sắp xếp trộn đệ quy cho một mảng gồm N số nguyên, sử dụng một 
mảng phụ trợ có kích thước nhỏ hơn N/2. 
BÀI 6.4.4: 
Phát biểu “thời gian chạy của sắp xếp trộn không phụ thuộc vào giá trị của các khóa 
trong tập tin nhập” là đúng hay sai? Hãy giải thích câu trả lời của bạn. 
BÀI 6.4.5: 
Số bước tối thiểu mà sắp xếp trộn có thể dùng là bao nhiêu? 
BÀI 6.4.6: 
Hãy chỉ ra các phép trộn được thực hiện khi dùng đệ quy để sắp xếp các khóa E A 
S Y Q U E S T I O N. 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
165 
BÀI 6.4.7: 
Hãy cho biết nội dung của xâu liên kết ở mỗi bước lặp khi dùng sắp xếp trộn không 
đệ quy để sắp xếp các khóa E A S Y Q U E S T I O N. 
BÀI 6.4.8: 
Hãy thử nghiệm một phép sắp xếp trộn đệ quy, sử dụng mảng, lấy ý tưởng thực hiện 
các phép trộn 3-way thay vì 2-way 
6.5. Sắp xếp bằng cơ số 
BÀI 6.5.1: 
So sánh số hoán vị được dùng bởi sắp xếp hoán vị cơ số với số hoán vị được dùng 
bởi Quicksort cho tập tin gồm các khóa 001, 011, 101, 110, 000, 001,010,111, 110, 
010. 
BÀI 6.5.2: 
Tại sao lại không quan trọng khi khử đệ quy từ phương pháp sắp xếp hoán vị cơ số 
như là đối với Quicksort. 
BÀI 6.5.3: 
Hãy sửa đổi phương pháp sắp xếp hoán vị cơ số để nhảy qua các bit dẫn đầu giống 
nhau trên tất cả các khóa. Trong những trường hợp nào thì điều này trở nên phung 
phí vô ích? 
BÀI 6.5.4: 
Điều sau đây đúng hay sai: thời gian thực hiện của phương pháp sắp xếp cơ số trực 
tiếp không phụ thuộc vào thứ tự các khóa trong tập tin nhập. Hãy giải thích câu trả 
lời của bạn. 
BÀI 6.5.5: 
Phương pháp nào sẽ nhanh hơn đối với tập tin gồm các khóa bằng nhau: sắp xếp 
hoán vị cơ số hay sắp xếp cơ số trực tiếp? 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
166 
BÀI 6.5.6: 
Điều sau đây đúng hay sai: cả hai phương pháp sắp xếp hoán vị cơ số và sắp xếp cơ 
số trực tiếp sẽ kiểm tra tất cả các bit của tất cả các khóa trong tập tin. Hãy giải thích 
câu trả lời của bạn. 
BÀI 6.5.7: 
Trừ yêu cầu về bộ nhớ bổ sung, hãy cho biết bất tiện chính của chiến lược thực hiện 
phép sắp cơ số trực tiếp trên các bitđi đầu của các khóa, rồi tiếp tục bằng phương 
pháp chèn sau đó. 
BÀI 6.5.8: 
Cần dùng bao nhiêu bộ nhớ để thực hiện một phép sắp cơ số trực tiếp 4-đường của 
N khóa b-bit? 
BÀI 6.5.9: 
Kiểu nào của tập tin nhập sẽ khiến cho phép sắp hoán vị cơ số chạy chậm nhất (N 
rất lớn)? 
BÀI 6.5.10: 
Hãy so sánh theo kinh nghiệm phép sắp xếp cơ số trực tiếp với phép sắp hoán vị cơ 
số đối với một tập tin gồm 1000 khóa 32-bit. 
6.6. Các phương pháp tìm kiếm cơ bản 
BÀI 6.6.1: 
Cài đặt một thuật toán tìm kiếm tuần tự mà đòi hỏi trung bình khoảng N/2 bước cho 
cả hai trường hợp tìm kiếm thành công và không thành công, thuật toán này lưu các 
mẩu tin trong một mảng được sắp xếp. 
BÀI 6.6.2: 
Hãy đưa ra một cài đặt đệ quy của thuật toán tìm kiếm nhị phân. 
Giả sử a[i] = 2i với 1<= i <= N. Có bao nhiêu vị trí trong bảng được kiểm tra khi 
dùng tìm kiếm nội suy trong trường hợp tìm kiếm không thành công cho 2k – 1? 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
167 
BÀI 6.6.3: THAY THẾ TỪ 
Hai file INPUT1.TXT và INPUT2.TXT được cho như sau: File INPUT1.TXT chứa 
một đoạn văn bản bất kì. File INPUT2.TXT chứa không quá 50 dòng, mỗi dòng gồm hai 
từ: từ đầu là từ đích và từ sau là từ nguồn. Hãy tìm trong file INPUT1.TXT tất cả các từ là 
từ đích và thay thế chúng bằng các từ nguồn tương ứng. Kết quả ghi vào file KQ.OUT (sẽ 
là một đoạn văn bản tương tự như trong file INPUT1.TXT nhưng đã được thay thế từ đích 
bởi từ nguồn). 
Ví dụ: 
Input: 
 File INPUT1.TXT chứa đoạn văn bản sau: 
Nam moi sap den roi, ban co vui khong? 
Chuc cac ban don mot cai Tet that vui ve va hanh phuc. 
Chuc ban luon hoc gioi! 
 File INPUT2.TXT chứa các dòng sau: 
ban em 
zui vui 
Output: 
 File KQ.OUT sẽ chứa đoạn văn bản sau: 
Nam moi sap den roi, em co vui khong? 
Chuc cac em don mot cai Tet that vui ve va hanh phuc. 
Chuc em luon hoc gioi! 
BÀI 6.6.4: DÃY SỐ NGUYÊN 
Dãy các số tự nhiên được viết ra thành một dãy vô hạn trên đường thẳng: 
1234567891011121314..... (1) 
Hỏi số ở vị trí thứ 1000 trong dãy trên là số nào? 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
168 
Hãy làm bài này theo hai cách: Cách 1 dùng suy luận logic và cách 2 viết chương 
trình để tính toán và so sánh hai kết quả với nhau. 
Tổng quát bài toán trên: Chương trình yêu cầu nhập số K từ bàn phím và in ra trên màn 
hình kết quả là số nằm ở vị trì thứ K trong dãy (1) trên. Yêu cầu chương trình chạy càng 
nhanh càng tốt. 
BÀI 6.6.5: BIRTHDATES 
Viết chương trình tìm người trẻ nhất và già nhất trong lớp. 
Input 
 Dòng 1 chứa số n (1<=n<=100), số người trong lớp. 
 N dòng sau, mỗi dòng là thông tin 1 người có dạng: 
personName dd mm yyyy 
Trong đó: personName là tên không quá 15 chữ cái, dd,mm,yyyy lần lượt là ngày, 
tháng, và năm sinh. 
Output 
Dòng 1: tên người trẻ nhất 
Dòng 2: tên người già nhất 
Ví dụ: 
Input: 
5 
Garfield 20 9 1990 
5 
Mickey 1 10 1991 
Alice 30 12 1990 
Tom 15 8 1993 
Jerry 18 9 1990 
Garfield 20 9 1990 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
169 
Output: 
Tom 
Jerry 
6.7. Phép băm 
BÀI 6.7.1: 
Mô tả làm thế nào để cài đặt một hàm băm bằng cách dùng một bộ phát sinh số ngẫu 
nhiên tốt. Có ý nghĩa hay không nếu cài đặt một bộ phát sinh ngẫu nhiên bằng cách 
dùng một hàm băm? 
BÀI 6.7.2: 
Lượng giá trường hợp xấu nhất khi chèn N khóa vào một bảng được khởi tạo trống 
bằng cách dùng xích ngăn cách với các danh sách không thứ tự. 
BÀI 6.7.3: 
Cho biết nội dung của bảng băm có được khi chèn các khóa E A S Y Q U E S T I O 
N theo thứ tự đó vào một bảng được khởi tạo trống kích thước bằng 13 bằng phương 
pháp dò tuyến tính. 
BÀI 6.7.4: 
Cho biết nội dung của bảng băm có được khi chèn các khóa E A S Y Q U E S T I O 
N theo thứ tự đó vào một bảng được khởi tạo trống kích thước bằng 13 bằng phương 
pháp băm kép. (Trong đó h1(k) lấy từ câu hỏi trước, h2(k) = 1 + (k mod 11).) 
BÀI 6.7.5: 
Cần khoảng bao nhiêu lần dò khi dùng phương pháp băm kép để xây dựng một bảng 
với N khóa bằng nhau? 
BÀI 6.7.6: 
Nên dùng phương pháp băm nào cho một ứng dụng mà có nhiều trường hợp khóa 
trùng nhau? 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
170 
BÀI 6.7.7: 
Giả sử rằng cho biết trước số phần tử sẽ được đặt vào bảng băm. Với những điều 
kiện nào thì phương pháp xích ngăn cách thích hợp hơn phương pháp băm kép? 
BÀI 6.7.8: 
Giả sử một lập trình viên có một lỗi trong chương trình dùng phương pháp băm kép 
mà một trong các hàm luôn trả về cùng một giá trị (khác 0). Mô tả điều gì sẽ xảy ra 
trong mỗi tình huống (khi hàm thứ nhất bị sai và khi hàm thứ hai bị sai). 
BÀI 6.7.9: 
Nên dùng hàm băm nào nếu biết trước rằng các giá trị khóa rơi vào một phạm vi 
tương đối nhỏ. 
BÀI 6.7.10: 
Phê bình thuật toán sau đây, thuật toán này nhằm mục đích xóa khóa khỏi một bảng 
băm được xây dựng bằng phương pháp dò tuyến tính. Quét qua phải kể từ phần tử 
được xóa để ra một vị trí trống, kế đến quét trái để tìm một phần tử có cùng giá trị 
băm, sau cùng thay thế phần tử được xóa bởi phần tử vừa tìm được. 
6.8. Tìm kiếm dựa vào cơ số 
BÀI 6.8.1: 
Vẽ cây tìm kiếm số học có được khi chèn các khóa E A S Y Q U E S T I O N theo 
thứ tự đó vào một cây được khởi tạo trống. 
BÀI 6.8.2: 
Phát sinh một cây tìm kiếm số học 1000 nút và so sánh độ cao và số nút mỗi tầng 
của nó với cây tìm kiếm nhị phân chuẩn và cây tìm kiếm đỏ đen được xây dựng từ 
cùng một tập khóa. 
BÀI 6.8.3: 
Hãy tìm một tập hợp 12 khóa mà chúng tạo nên một cây tìm kiếm số học cân bằng 
yếu. 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
171 
BÀI 6.8.4: 
Vẽ cây tìm kiếm cơ số có được khi chèn các khóa E A S Y Q U E S T I O N theo 
thứ tự đó vào một cây được khởi tạo trống. 
BÀI 6.8.5: 
Một vấn đề xảy ra đối với các cây tìm kiếm số học 26-hướng (way) là một số ký tự 
trong bảng chữ cái thì lại được sử dụng rất thường xuyên. Hãy đề nghị một phương 
pháp giải quyết vấn đề này. 
BÀI 6.8.6: 
Mô tả phương pháp xóa một phần tử khỏi cây tìm kiếm cơ số đa hướng. 
BÀI 6.8.7: 
Vẽ cây Patricia có được khi chèn các khóa E A S Y Q U E S T I O N theo thứ tự đó 
vào một cây được khởi tạo trống. 
BÀI 6.8.8: 
Hãy tìm một tập hợp 12 khóa mà chúng tạo nên một cây Patricia cân bằng yếu. 
BÀI 6.8.9: 
Viết chương trình in ra tất cả các khóa trong cây Patricia mà có t bit khởi đầu giống 
với một khóa tìm kiếm đã cho. 
BÀI 6.8.10: 
Trong các phương pháp cơ số thì phương pháp nào thích hợp để viết chương trình 
in ra các khóa theo thứ tự? Phương pháp nào không thích hợp? 
P
T
I
T
BÀI TẬP KỸ THUẬT LẬP TRÌNH – Vesion 1.0 
172 
TÀI LIỆU THAM KHẢO 
1. Lê Minh Hoàng. Giải thuật và lập trình, Đại học Sư phạm Hà Nội, 2010. 
2. Robert Sedgewick. Algorithms 2nd edition, ISBN: 0201066734, Addison Wesley, 
1988. 
3. PTIT Online Judge.  
P
T
I
T