Giáo trình Kỹ thuật lập trình 2

ức hậu tố. 
Trong những năm đầu 1950 nhà logic học người Ba Lan Jan Lukasiewicz đã chứng 
minh rằng: biểu thức hậu tố không cần có dấu ngoặc vẫn có thể tính đúng bằng cách đọc 
lần lượt biểu thức từ trái qua phải và dùng một stack để lưu trữ kết quả trung gian. 
Các bước thực hiện như sau: 
Bước 1: Khởi tạo một stack = {∅} 
Bước 2: Đọc lần lượt các phần tử của biểu thức hậu tố từ trái sang phải, với mỗi phần tử 
đó thực hiện kiểm tra: 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
102
ƒ Nếu phần tử này là toán hạng thì đẩy nó vào stack 
ƒ Nếu phần tử này là toán tử thì ta lấy hai toán hạng trong stack ra và thực hiện 
phép toán với hai toán hạng đó. Kết quả tính được sẽ được lưu vào trong 
stack. 
Bước 3: Sau khi kết thúc bước hai thì toàn bộ biểu thức đã được đọc xong, trong stack 
chỉ còn duy nhất một phần tử, phần tử đó chính là giá trị của biểu thức. 
Ví dụ: tính giá trị biểu thức 10 2 / 3 + 7 4 - *, có biểu thức trung tố là: (10/2 + 3)*(7-4), 
ta có các bước thực hiện như sau: 
Đọc Xử lý Stack Output 
10 Đưa vào stack 10 
2 Đưa vào stack 10 2 
/ 
Lấy hai phần tử đầu stack là 2, 10 và thực hiện 
phép toán 10/2 = 5. Sau đó lưu kết quả 5 vào 
stack 
5 
3 Đưa 3 vào stack 5 3 
+ 
Lấy hai giá trị 3, 5 ra khỏi stack, thực hiện phép 
cộng của hai số đó, kết quả là 8 được đưa vào 
lại stack 
8 
7 Đưa 7 vào stack 8 7 
4 Đưa 4 vào stack 8 7 4 
- 
Lấy hai giá trị 4, 7 ra khỏi stack, thực hiện phép 
tính 7 – 4 = 3, kết quả 3 được đưa vào lại stack 
8 3 
* 
Lấy hai giá trị 3, 8 ra khỏi stack, thực hiện phép 
tính 8 * 3 = 24, lưu kết quả vào stack 
24 
Lấy kết quả từ stack ⇒ đây chính là kết quả của 
biểu thức. 
 24 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
103
5.2 Giới thiệu Queue – hàng đợi 
Hàng đợi Queue là kiểu danh sách với hai phép toán cơ bản là bổ sung một phần tử 
vào cuối danh sách (Rear) và loại bỏ một phần tử ở đầu danh sách (Front). Nói tóm lại là 
hai thao tác cơ bản đưa vào một phần tử và lấy ra một phần tử ở hai đầu của danh sách. 
Danh sách hàng đợi làm việc theo cơ chế FIFO (First In First Out), nghĩa là việc 
thêm một phần tử vào hàng đợi hay lấy một phần tử từ hàng đợi ra ngoài theo thứ tự “Vào 
trước ra trước”. 
Hình 5.5: Minh họa hàng đợi Queue. 
 Hai thao tác chính trên hàng đợi: 
1. Thao tác Insert: thêm một phần tử vào cuối danh sách. 
2. Thao tác Remove: xoá một phần tử ở đầu danh sách. 
 Ví dụ: Cho hàng đợi Q và các thao tác như sau: 
1. Hàng đợi ban đầu có hai phần tử A và B hình 5.6 
2. Thêm một phần tử C vào cuối Queue: Insert(Q, C) hình 5.7 
3. Lấy một phần tử ở đầu Queue: Remove(Q) hình 5.8 
4. Thêm một phần tử D vào cuối Queue: Insert(Q, D) hình 5.9 
5. Lấy một phần tử ở đầu Queue: Remove(Q) hình 5.10 
Lấy ra (Remove) 
Thêm vào (Insert) 
Đầu Queue (Front) Cuối Queue (Rear) 
Queue 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
104
Hình 5.6: Hàng đợi có hai phần tử A và B. 
Hình 5.7: Hàng đợi sau khi thêm phần tử C vào cuối. 
Hình 5.8: Hàng đợi sau khi lấy phần tử ở đầu. 
Hình 5.9: Hàng đợi sau khi thêm phần tử D vào cuối. 
A B 
Front Rear 
A B C 
Rear Front 
 B C 
Rear Front 
 B C D 
Rear Front 
 C D 
Rear Front 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
105
Hình 5.10: Hàng đợi sau khi lấy phần tử ở đầu. 
5.2.1 Cài đặt Queue dùng CTDL mảng 
Để sử dụng cấu trúc dữ liệu mảng mô tả Queue người ta dùng hai chỉ số là Front và 
Rear để đánh dấu vị trí đầu và cuối của hàng đợi trong mảng. Nếu mảng tính từ chỉ số 0 
thì ban đầu chúng ta khởi tạo Rear = -1 và Front = 0. 
 Để thêm một phần tử vào Queue, ta tăng Rear lên 1 và đưa nó vào phần tử thứ Rear. 
 Để loại một phần tử khỏi Queue, ta lấy giá trị ở vị trí Front và tăng chỉ số này lên 1. 
 Khi Rear tăng lên hết khoảng chỉ số của mảng thì mảng đầy, khi đó ta không thể 
thêm vào mảng được nữa. 
 Khi Front > Rear ⇒ Queue = {∅}. 
Tương tự như phần Stack ở đây sẽ xây dựng một cấu trúc Queue chứa các phần tử có 
kiểu dữ liệu là Data, Data là kiểu dữ liệu do người dùng định nghĩa có thể số nguyên, 
thực, ký tự hoặc một cấu trúc dữ liệu nào đó tùy ý. 
Khai báo cấu trúc Queue dùng mảng: 
#define MAX 100 
typedef struct 
{ 
 int Front; // chỉ đến vị trí đầu của queue 
 int Rear; // chỉ đến vị trí cuối của queue 
 Data Q[MAX]; // mảng dữ liệu cần lưu trữ 
} Queue; 
Trong cấu trúc này trường Front chỉ đến vị trí đầu của Queue còn Rear chỉ đến vị trí 
cuối của Queue. Ban đầu khi Queue được khởi tạo rỗng thì Rear = -1 và Front = 0. 
Các thao tác trên cấu trúc Queue: 
ƒ void Insert(Queue &queue, Data x): Đưa phần tử x vào cuối Queue 
ƒ Data Remove(Queue &queue): Lấy một phần tử ở đầu Queue 
ƒ int IsEmpty(Queue queue): Kiểm tra xem Queue có rỗng hay không 
ƒ int IsFull(Queue queue): Kiểm tra xem Queue đầy hay không. 
ƒ void InitQueue(Queue &queue): Khởi tạo Queue. 
Phần cài đặt các thao tác trên Queue: 
#define TRUE 1 
#define FALSE 0 
void Insert(Queue &queue, Data x) 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
106
{ 
 queue.Rear++; // tăng Rear lên 1 
 if (IsFull(queue)) 
 printf(“Queue full!”); 
 else 
 queue.Q[queue.Rear] = x; 
} 
Data Remove(Queue &queue) 
{ 
 Data x; 
if (IsEmpty(queue)) 
 printf(“Queue empty!”); 
 else 
 x = queue.Q[queue.Front++]; 
 return x; 
} 
int IsEmpty(Queue queue) 
{ 
 if (queue.Front > queue.Rear) 
 return TRUE; 
 return FALSE; 
} 
int IsFull(Queue queue) 
{ 
 if (queue.Rear == MAX) 
 return TRUE; 
 return FALSE; 
} 
void InitQueue(Queue &queue) 
{ 
 queue.Rear = -1; 
 queue.Front = 0; 
} 
5.2.2 Các ứng dụng Queue 
Thông thường các vấn đề liên quan đến cơ chế “vào trước ra trước” đều có thể dùng 
cấu trúc dữ liệu Queue. Ví dụ như cơ chế sản xuất và tiêu thụ, hàng hóa sản xuất trước 
được đưa vào kho và sẽ được xuất ra trước. Các ứng dụng đặt vé tàu lửa máy bay, hệ 
thống rút tiền...Ngoài ra hàng đợi còn được dùng nhiều trong hệ điều hành: bộ đệm ứng 
dụng, hàng đợi xử lý các sự kiện, hàng đợi xử lý phím nhấn, tiến trình... 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
107
 Bài toán quản lý kho hàng: 
Đây là dạng bài toán sản xuất & tiêu dùng, mặt hàng được sản xuất ra sẽ được lưu 
vào kho, hàng hóa từ kho này sẽ được xuất ra ngoài cho nhà phân phối. Khi đó những 
mặt hàng nào đưa vào kho trước tiên sẽ ra được xuất kho trước. Đây là dạng FIFO nên 
chúng ta có thể dùng cấu trúc dữ liệu Queue để minh họa cho nó. 
#include "stdio.h" 
#include "conio.h" 
#define MAX 100 
#define TRUE 1 
#define FALSE 0 
typedef struct 
{ 
 char MaSP[10]; // Ma san pham 
 char TenSP[50]; // Ten san pham 
} Data; 
typedef struct 
{ 
 int Rear, Front; 
 Data Q[MAX]; 
}Queue; 
void Insert(Queue &queue, Data x); 
Data Remove(Queue &queue); 
int IsEmpty(Queue queue); 
int IsFull(Queue queue); 
void InitQueue(Queue &queue); 
void Insert(Queue &queue, Data x) 
{ 
 queue.Rear++; // tăng Rear lên 1 
 if (IsFull(queue)) 
 printf("Queue full!"); 
 else 
 queue.Q[queue.Rear] = x; 
} 
Data Remove(Queue &queue) 
{ 
 Data x; 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
108
 if (IsEmpty(queue)) 
 printf("Queue empty!"); 
 else 
 x = queue.Q[queue.Front++]; 
 return x; 
} 
int IsEmpty(Queue queue) 
{ 
 if (queue.Front > queue.Rear) 
 return TRUE; 
 return FALSE; 
} 
int IsFull(Queue queue) 
{ 
 if (queue.Rear == MAX) 
 return TRUE; 
 return FALSE; 
} 
void InitQueue(Queue &queue) 
{ 
 queue.Rear = -1; 
 queue.Front = 0; 
} 
Data InputProduct() // đọc một sản phẩm 
{ 
 Data sp; 
 printf("\nMa san pham: "); scanf("%s",sp.MaSP); 
 printf("Ten san pham: "); scanf("%s", sp.TenSP); 
 return sp; 
} 
void OutputProduct(Data sp) // xuất một sản phẩm 
{ 
 printf("\nSan pham : MaSP: %s, TenSP: %s", sp.MaSP, sp.TenSP); 
} 
void ListProducts(Queue q) // liệt kê những sản phẩm trong kho 
{ 
 if (!IsEmpty(q)) // nếu có sản phẩm trong kho 
 { 
 printf("\n Danh sach san pham trong kho:\n"); 
 for(int i= q.Front; i <= q.Rear; i++) // duyệt qua các phần tử 
 { 
 printf("\nSan pham: MaSP: %s, TenSP: %s",q.Q[i].MaSP, 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
109
 q.Q[i].TenSP); 
 } 
 } 
} 
int main() 
{ 
Queue queue; 
InitQueue(queue); // khởi tạo hàng đợi 
clrscr(); 
int i; 
do 
{ 
 clrscr(); 
 printf("CHUONG TRINH MINH HOA QUAN LY KHO\n"); 
 printf("-----------------------------------------------\n"); 
 printf("1. Them san pham vao kho.\n"); 
 printf("2. Xuat san pham ra khoi kho.\n"); 
 printf("3. Xem san pham chuan bi xuat kho.\n"); 
 printf("4. Xem tat ca hang hoa trong kho. \n"); 
 printf("5. Thoat.\n"); 
 printf("Chon chuc nang: (1- 5): "); 
 scanf("%d",&i); 
 switch (i) 
 { 
 case 1: 
 Insert(queue, InputProduct()); // thêm sp vào kho 
 break; 
 case 2: 
 OutputProduct(Remove(queue)); // lấy sp khỏi kho 
 break; 
 case 3: 
 if (!IsEmpty(queue)) // xem sp sắp lấy 
 OutputProduct(queue.Q[queue.Front]); 
 break; 
 case 4: // xem tất cả sp 
 ListProducts(queue); 
 break; 
 } 
 getch(); 
 } while (i != 5); 
 return 0; 
} 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
110
 Duyệt cây theo chiều rộng trong đồ thị: 
Đây là phương pháp duyệt hay tìm kiếm phổ biến trên đồ thị. Việc duyệt một đỉnh v 
sẽ cho phép chúng ta đi duyệt tiếp với những đỉnh kề của nó sao cho thỏa thứ tự ưu tiên 
theo chiều rộng, tức là đỉnh nào gần với v nhất sẽ được duyệt trước. 
Hình 5.11: Minh họa thứ tự duyệt theo chiều rộng. 
Khi đó tại mỗi bước xét một đỉnh v ta có một danh sách các đỉnh kề của nó, những 
đỉnh này chờ được duyệt do đó ta sẽ đưa những đỉnh này vào cuối danh sách chờ được 
duyệt, khi đó những đỉnh nào vào danh sách chờ trước thì sẽ được duyệt trước. Với cấu 
trúc dữ liệu này thì thích hợp cho việc sử dụng Queue. 
Thuật toán: Breadth First Search 
void BFS(int v) // thủ tục duyệt theo chiều rộng từ một đỉnh v 
{ 
 Queue QList; 
InitQueue(QList); // khởi tạo hàng đợi 
Insert(QList, v); // đưa v vào hàng đợi 
Xet[v] = TRUE; // đánh dấu v đã duyệt 
while (IsEmpty(QList) == 0) 
{ 
 p = Remove(QList); // lấy đỉnh trong hàng đợi 
 Visit(p); // thăm đỉnh p, có thể xuất đỉnh ra ... 
 for( i=1; i <= n; i++) // duyệt qua các đỉnh 
 if ( A[v][i] == 1 && Xet[i] == FALSE) 
// nếu i là đỉnh kề v và chưa xét 
 { 
 Insert(QList, i); // đưa vào hàng đợi 
 Xet[i] = TRUE; // đánh dấu i đã xét. 
 } 
} 
} 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
111
Mảng A[][]: chứa ma trận kề của đồ thị (G) 
Mảng Xet[]: đánh dấu một đỉnh v đã được duyệt hay chưa; 1: đã duyệt, 0: chưa duyệt. Tất 
cả các phần tử của mảng Xet[] ban đầu được khởi tạo là 0. 
Chương trình minh họa duyệt theo chiều rộng: 
#include "stdio.h" 
#include "conio.h" 
#define MAX 100 
#define TRUE 1 
#define FALSE 0 
typedef int Data; 
typedef struct 
{ 
 int Rear, Front; 
 Data Q[MAX]; 
} Queue; 
void Insert(Queue &queue, Data x); 
Data Remove(Queue &queue); 
int IsEmpty(Queue queue); 
int IsFull(Queue queue); 
void InitQueue(Queue &queue); 
void Insert(Queue &queue, Data x) 
{ 
 queue.Rear++; // tăng Rear lên 1 
 if (IsFull(queue)) 
 printf("Queue full!"); 
 else 
 queue.Q[queue.Rear] = x; 
} 
Data Remove(Queue &queue) 
{ 
 Data x; 
 if (IsEmpty(queue)) 
 printf("Queue empty!"); 
 else 
 x = queue.Q[queue.Front++]; 
 return x; 
} 
int IsEmpty(Queue queue) 
{ 
 if (queue.Front > queue.Rear) 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
112
 return TRUE; 
 return FALSE; 
} 
int IsFull(Queue queue) 
{ 
 if (queue.Rear == MAX) 
 return TRUE; 
 return FALSE; 
} 
void InitQueue(Queue &queue) 
{ 
 queue.Rear = -1; 
 queue.Front = 0; 
} 
void BFS(int v, int a[][MAX], int xet[], int n) 
{ 
int d; 
 Queue queue; 
 InitQueue(queue); 
 Insert(queue, v); 
 xet[v] = TRUE; 
 while (!IsEmpty(queue)) 
 { 
 d = Remove(queue); 
 printf("%d\t", d); 
 for(int i=1; i <= n; i++) 
 if (a[d][i]== 1 && xet[i]== FALSE) 
 { 
 Insert(queue, i); 
 xet[i] = TRUE; 
 } 
 } 
} 
int main() 
{ 
int a[MAX][MAX], xet[MAX], n; 
clrscr(); 
char name[50]; 
printf(“Nhap ten file ma tran ke cua (G): ”); 
 gets(name); 
FILE * f = fopen(name,"r"); 
if (f == NULL) 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
113
{ 
 printf("Loi doc file!"); 
 return 1; 
 } 
 fscanf(f,"%d",&n); 
 for(int i=1; i <= n;i++) 
 for(int j=1; j <= n; j++) 
 fscanf(f,"%d",&a[i][j]); 
// danh dau cac dinh chua xet 
for(i =1; i <= n; i++) 
 xet[i] = FALSE; 
// duyet qua cac dinh cua do thi 
printf("Cac dinh cua do thi duoc duyet theo chieu rong\n"); 
 for(i =1; i <= n; i++) 
 if (xet[i] == FALSE) 
 BFS(i, a, xet, n); 
getch(); 
return 0; 
} 
Tập tin ma trận kề có dạng sau: 
N 
A[1][1] A[1][N] 
A[N][1] A[N][N] 
Trong đó A[i][j] = 1 nếu (i, j) có cạnh nối và ngược lại A[i][j] = 0 nếu không có cạnh nối 
Ví dụ tập tin ma trận kề minh họa đồ thị có 5 đỉnh. 
5 
0 1 1 1 1 
1 0 1 1 1 
1 1 0 1 1 
1 1 1 0 1 
1 1 1 1 0 
\”[ 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
114
BÀI TẬP 
1. Tinh chỉnh lại đoạn chương trình sau: 
for (int i=0; i < n; i++) 
{ 
 if ( flag) 
 b[i] = 0; 
 a[i] = a[i] + b[i]; 
 c[i] = a[i] + 2*b[i]; 
} 
2. Tinh chỉnh lại đoạn chương trình sau: 
... 
while ( sqrt( i*i) < sqrt (a*a) ) 
{ 
 // đoạn chương trình 
 . 
 i++; 
} 
3. Tinh chỉnh lại đoạn chương trình sau: 
... 
flag = FALSE; 
k =0; 
while ( k < n) 
{ 
 if (a[i] == x) 
 flag = TRUE; 
 k++; 
} 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
115
if (flag) 
 printf("Tim thay phan tu!"); 
4. Tinh chỉnh lại đoạn chương trình sau: 
... 
while ( i < n) 
{ 
 d = sqrt (a+b)*i; 
 printf("gia tri %.2f", d); 
 i++; 
} 
... 
5. Tinh chỉnh lại đoạn chương trình sau: 
... 
for(int i=0; i < strlen(strBuff); i++) 
{ 
 . 
} 
6. Tinh chỉnh lại đoạn chương trình sau: 
if (a==0 && b==0 && c==0) 
 Function1(); 
else if (a==0 && b==0) 
 Function2(); 
else if (a==0) 
 Function3(); 
else 
 Function4(); 
7. Tối ưu lại đoạn chương trình sau: 
char S1[MAX], S2[MAX]; 
. 
int i; 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
116
for (i=0;i<strlen(S1); i++) 
{ 
 if ( i<strlen(S1)/3 && S1[i] < ’M’ ) 
S2[i]= S1[i]+2; 
 else if ( i < strlen(S1)/2 && S[i] < ‘X’) 
S2[i] = S1[i] +3; 
 else S2[i]= S1[i]; 
} 
8. Tinh chỉnh đoạn chương trình sau 
if (strcmp(s1, s2)==0) 
printf(“equal”); 
else if (strcmp(s1, s2) >0) 
printf(“greater than”); 
else 
printf(“less than”); 
9. Tinh chỉnh lại đoạn chương trình sau: 
x1 = (-b + sqrt(b*b-4*a*c))/(2*a); 
x2 = (-b - sqrt(b*b-4*a*c))/(2*a); 
10. Viết chương trình với giao diện đồ hoạ minh họa cho bài toán tháp Hanoi. 
Chương trình thể hiện từng bước sự chuyển các đĩa. Cho phép nhập vào số n và 
thời gian di chuyển từng đĩa. 
11. Viết hàm đệ quy tìm phần tử lớn nhất và nhỏ nhất trong mảng nguyên. 
12. Viết hàm đệ quy tính tổng các phần tử trong mảng các số nguyên. 
13. Viết chương trình tìm kiếm giá trị x trên ma trận vuông các số nguyên, dùng đệ 
quy để tìm kiếm. 
14. Viết chương trình chuyển đổi cơ số từ hệ thập phân sang hệ k, yêu cầu dùng hàm 
đệ quy để giải. 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
117
15. Viết chương trình tháp Hanoi không dùng đệ quy. 
16. Viết chương trình chuyển đổi số từ cơ số thập phân sang cơ số k bất kỳ, không 
dùng đệ quy. 
17. Viết chương trình liệt kê chuỗi nhị phân n bit. Dùng phương pháp sinh. 
18. Cho tập các số tự nhiên {1, 2, .., n}, viết chương trình liệt kê tập con k phần tử. 
Dùng phương pháp sinh. 
19. Viết chương trình liệt kê hoán vị n phần tử. Dùng phương pháp sinh. 
20. Nhập vào một chuỗi ký tự S, hãy liệt kê các hoán vị ký tự của chuỗi S. 
Ví dụ: chuỗi S nhập vào là "abc" thì kết quả là abc, acb, bac, bca, cab, cba. 
21. Tương tự như bài 1, liệt kê tổ hợp chập k ký tự của chuỗi S. 
22. Một hoán vị hoàn toàn của tập{1, 2, .., n} là dãy hoán vị mà thoả mãn x[i] ≠ i, ∀i: 
1≤ i ≤ n. Viết chương trình nhập vào giá trị n, sau đó xuất ra tất cả hoán vị hoàn 
toàn của tập {1, 2, .., n}. 
23. Viết chương trình nhập vào một số nguyên n, liệt kê tất cả cách chia số tự nhiên n 
thành tổng các số nhỏ hơn. 
Ví dụ: n = 4 
Kết quả 3 1 
 2 2 
 2 1 1 
 1 1 1 1 
24. Cho một bàn cờ tổng quát có kích thước nxn và quân mã. Viết chương trình cho 
phép liệt kê ra hành trình của quân mã từ một vị trí (x ,y) đi qua tất cả các ô còn 
lại của bàn cờ, mỗi ô đi qua một lần. 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
118
 Hình: Các nước đi có thể có của quân mã 
25. Cho bàn cờ vua nxn, hãy viết chương trình minh hoạ bàn cờ và cách sắp xếp n 
quân hậu sao cho các quân hậu không thể ăn lẫn nhau. 
Hình: Một cách bố trí các quân Hậu. 
26. Nhập danh sách tên gồm n người, liệt kê ra tất cả cách chọn k người trong số n 
người đó. 
Ví dụ: n =6: {"Nam", "Hung", "Viet", "Hoa", "Lan", "Tien"}, 
Kết quả: k = 2 {"Nam", "Hung"}, {"Nam", "Viet"}, {"Nam", "Hoa"}. 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
119
27. Nhập danh sách tên gồm n người, xuất ra các cách xếp n người đó vào trong một 
bàn tròn. 
28. Nhập vào danh sách n bạn nam và n bạn nữ, hãy xuất ra danh sách cách xếp 2n 
bạn đó vào một bàn tròn trong đó có sự xen lẫn giữa nam và nữ. 
29. Viết chương trình liệt kê tất cả hoán vị của từ “HUTECH” 
30. Viết chương trình liệt kê tất cả hoán vị chữ cái trong từ "MISSISSIPPI" 
31. Viết chương trình mô phỏng từng bước thực hiện của các thuật toán sắp xếp sau: 
a. Phương pháp chọn 
b. Phương pháp nổi bọt 
c. Phương pháp chèn 
d. Phương pháp đổi chỗ trực tiếp 
e. Phương pháp ShellSort 
f. Phương pháp phân đoạn 
g. Phương pháp cơ số 
32. Cho một mảng nguyên n >100 phần tử, các phần tử phát sinh ngẫu nhiên. Viết 
hàm tìm kiếm một phần tử trong mảng. 
33. Tương tự như bài tập bên trên, nhưng hàm tìm kiếm theo dạng nhị phân. Sinh 
viên có thể dùng một trong các phương pháp sắp xếp để sắp xếp lại mảng trước 
khi thực hiện tìm kiếm nhị phân. 
34. Viết chương trình đo thời gian thực hiện của các thuật toán sắp xếp bên trên. 
Chương trình phát sinh ngẫu nhiên bộ dữ liệu test (mảng số nguyên, có kích thước 
n >= 1000) , cho các thuật toán lần lượt chạy và ghi nhận lại thời gian thực hiện. 
35. Viết chương trình không đệ quy cho thuật giải Quicksort, (áp dụng stack để khử 
đệ quy). 
36. Nhập vào một biểu thức trung tố, chuyển đổi thành biểu thực hậu tố và tính giá trị 
của biểu thức. Lưu ý: toán hạng có thể nhiều hơn một con số hay số thực. Sinh 
viên mở rộng với các toán tử khác... 
Ví dụ: (20+5)*3+(10/5) => 20 5 + 3 * 10 5 / + 
 Kết quả: 77 
37. Viết chương trình mô phỏng hàng đợi mua vé xem phim. Thông tin của việc đăng 
ký gồm: họ tên, địa chỉ, tuổi và số ghế... 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
120
38. Viết chương trình mô phỏng hàng đợi mua vé xe lửa. 
39. Viết chương trình sắp xếp theo cơ số (RadixSort), trong đó sử dụng cấu trúc dữ 
liệu queue để lưu tạm trong quá trình sắp xếp. Hướng dẫn sử dụng 10 hàng đợi để 
lưu tạm các con số. Gồm hàng đợi 0 đến 9, khi đó hàng đợi 0 sẽ chỉ lưu những 
con số có số 0 ở các bước phân hàng đơn vị, hàng chục, hàng trăm tương ứng... 
\”[ 
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
121
TÀI LIỆU THAM KHẢO 
1. Brian W. Kernighan, Rob Pike, The Practice of Programming, Addison 
Wesley, 1999. 
2. Ellis Horowitz, Sartaj Sahni, Fundamentals of Data Structures, ebook, 1981. 
3. R. Neapolitan, K. Naimipour , Foundations of Algorithms Using C++ 
Pseudocode, Jones and Bartlett Publishers , 2004. 
4. Lê Hoài Bắc, Nguyễn Thanh Nghị, Kỹ năng lập trình, NXB KHKT, 2005. 
5. Trần Hoàng Thọ, Giáo trình Kỹ thuật Lập trình Nâng cao, ĐH Đà Lạt, 2002. 
6. Dương Anh Đức, Trần Hạnh Nhi, Nhập môn Cấu trúc dữ liệu và thuật toán, 
ĐH KHTN, 2000. 
7. Lê Hữu Lập, Nguyễn Duy Phương, Giáo trình kỹ thuật lập trình, NXB Bưu 
Điện, 2002. 
8. Lê Minh Hoàng, Giải thuật và lập trình, NXB ĐH Sư Phạm HN, 1999- 2002 
\”[