Chương 2 Các kiểu dữ liệu cơ bản
1. Viết ct thực hiện các phép toán tr ên ma trận vuông số thực: cộng, trừ, nhân
2. Viết ct minh họa một barner quảng cáo gồm một khung cửa sổ v à dòng chữ quảng cáo chạy
qua lại trong khung
3. Viết ct quản lý mặt hàng, thông tin một mặt hàng gồm: mã hàng, tên hàng, đơn vị tính, đơn
giá, số lượng. Chương trình có các chức năng:
a. Nhập mặt hàng
b. In danh mục mặt hàng
c. Tính doanh thu= Tổng(Đơn giá* Số lượng) các mặt hàng
d. Tính thuế GTGT:
i. Nếu đơn vị tính là “Chai” : thuế = 10%
ii. Nếu đơn vị tính là “Kg”: thuế = 5%
iii. Còn lại không có thuế
4. Viết ct đọc nội dung một file văn bản, hiển thị l ên màn hình và cho bi ết trong file có bao nhi êu
từ, đếm số lần xuất hiện của 1 từ do ng ười dùng nhập vào.
5. Viết ct quản lý lương nhân viên sử dụng tập tin nhị phân
a. Dữ liệu lưu trữ gồm: mã nv, họ tên, ngày sinh, lương cơ b ản, hệ số lương, số ngày
công, số ngày nghỉ
b. Tính lương theo công th ức
Lương = Lương cb * h ệ số lương * (ngày công – ngày nghỉ) /24
c. Chương trình có các chức năng
i. Nhập hồ sơ
ii. In danh sách nhân viên
iii. In bảng lương
iv. Tìm kiếm nhân viên
6. Viết ct mô phỏng Karaoke với dữ liệu l ưu trữ trong tập tin nhị phân
7. Hãy nêu giải thuật mà độ phức tạp tính toán của nó l à O(1)
8. Giải thích tại sao T(n) = O(n) th ì cũng sẽ đúng khi ta viết T(n) = O(n2)
9. Với các đoạn chương trình dưới đây hãy xác định độ phức tạp tính toán của giải thuật bằng ký
pháp O lớn, trong trường hợp xấu nhất
a)
Sum := 0
For i := 1 to n do
Begin Readln(x);
Sum := Sum + x;
End
b)
For i := 1 to n do
For j := 1 to n do
Begin
C[i, j] := 0;
For k := 1 to n do
C[i, j] := C[i, j] + A[i, k] * B[k, j]
End;
c)
For i := 1 to n-1 do
Begin
For j := i to n-1 do
If X[j] > X[j+1] then
Begin Temp := X[j];
X[j] := X[j+1];
X[j+1] := Temp
End
End
Chương 3 Các thuật toán sắp xếp và tìm kiếm
1. Viết ct nhập một mảng số nguy ên ( tạo mảng ngẫu nhiên), thực hiện sắp xếp mảng theo các
thuật toán
a. Chọn trực tiếp
b. Chèn trực tiếp
c. Đổi chỗ trực tiếp
d. Nổi bọt
e. Shaker sort
f. Shell sort
g. Heap sort
h. Quick sort
i. Merge sort
j. Radix sort
2. Viết ct nhập một dãy số nguyên, lưu trữ trong tập tin nhị phân, thực hiện thao tác sắp xếp dữ
liệu bằng các thuật toán
a. Trộn tự nhiên
b. Trộn trực tiếp
3. Dùng các phép toán xâu kí t ự cơ bản, viết một thuật toán đệ qui để xác định một xâu kí tự l à
palindrome hay không.
Xâu kí tự được gọi là palindrome nếu nó không thay đổi khi ta đảo ng ược thứ tự của các kí tự
trong xâu kí tự Ví dụ : MADAM, 45811854 …
4. Viết ct minh họa bài toán đặt tám quân hậu
5. Viết ct minh họa bài toán Tháp Hà nội
6. Viết ct minh họa bài toán quân mã đi tuần
7. Viết ct liệt kê dãy nhị phân độ dài n bít
8. Viết ct liệt kê các hoán vị của các số nguyên từ 1 đến n
Chương 4 Cấu trúc dữ liệu động
1. Viết ct minh họa các thao tác tr ên danh sách liên kết đơn chứa các số nguyên
2. Viết ct minh họa các thao tác trên danh sách liên kết kép chứa các số nguy ên
3. Cho moät ngaên xeáp s vaø 1 ñoaïn chöông trình nhö sau:
struct STACK s;
int x, y = 5;
Push(s, 8);
Push(s, y);
Push(s, 9);
Pop(s, x);
Push(s, 18);
Pop(s, x);
Push(s, 22);
while (IsEmp ty(s) == 0)
{Pop(s, x);
printf(“%d “, y);
}
Haõy cho bieát keát quaû in ra maøn hình khi thi haønh ñoaïn chöông trình treân laø gì ?
4. Cho moät haøng ñôïi q vaø 1 ñoaïn chöông trình nhö sau:
struct QUEUE q;
int x = 5, y = 3;
EnQueue(q, 8);
EnQueue(q, 9);
EnQueue(q, y);
DeQueue(q, x);
EnQueue(q, 18);
DeQueue(q, x);
EnQueue(q, 22);
while (IsEmpty(q) == 0)
{DeQueue(q, y);
printf(“%d “, y);
}
Haõy cho bieát keát quaû in ra maøn hình khi thi haønh ñoaïn chöông trình treân laø gì ?
5. Viết ct minh họa các thao tác tr ên ngăn xếp
6. Viết ct minh họa các thao tác tr ên hàng đợi
7. Viết ct chuyển đổi giữa các hệ thồng số d ùng ngăn xếp
8. Viết ct tính giá trị của biểu thức tiền tô, hậu tố d ùng ngăn xếp
9. Viết một chương trình đọc một xâu ký tự, đẩy mỗi kí tự vào ngăn xếp theo thứ tự như khi
chúng được đọc và đồng thời thêm nó vào một hàng đợi. Khi đến kết thúc xâu kí tự, d ùng các
phép toán cơ bản của ngăn xếp và hàng đợi để xác định xâu ký tự đó có phải l à một Palindrome
không.
10. Cho 2 xâu liên kết T1 và T2. Giả thiết mỗi phần tử của chúng chỉ có 2 thông tin :
- Khóa của nút (là số nguyên)
- Con trỏ đến phần tử kế
Viết chương trình tạo một xâu liên kết T nối từ 2 xâu T1 và T2 sao cho :
- Các phần tử trong T có giá trị tăng
-Không có trường hợp trùng nhau
-Xác định chi phí thuật toán
11. Cho một xâu đơn T, mỗi nút của nó chứa các thông tin sau :
- Key : kiểu Integer
- Next : con trỏ chỉ đến phần tử kế
Viết chương trình C/Pascal tách xâu T thành 2 xâu T1 và T2, trong đó T1 chứa các phần tử có khóa > 0
và T2 chứa các phần tử có khóa < 0. Đánh giá chi phí thu ật toán.
12. Cho 2 xâu đơn T1, T2 vi ết ct thực hiện các thao tác
- Sắp xếp tăng dần, giảm dần
- So sánh 2 xâu
-Đếm nút dùng đệ quy
