BÀI TẬP ĐẶC TẢ HÌNH THỨC #1
1. Đặc tả tập hợp X gồm các số tự nhiên lẻ trong khoảng từ 100 đến 1000.
2. Đặc tả tập hợp X gồm các số tự nhiên chẵn trong khoảng từ 100 đến 1000 (không xét 100
và 1000)
3. Đặc tả tập hợp P các số nguyên tố lớn hơn 100 và nhỏ hơn 65537.
P = {x ∈ N | x > 100 ∧ x < 65537 ∧ IsPrime(x)}
4. Đặc tả phát biểu: Với bất kỳ số tự nhiên x, luôn tìm được số nguyên lẻ y không vượt quá x.
5. Đặc tả phát biểu: Với bất kỳ số tự nhiên x, luôn tìm được số tự nhiên lẻ y không vượt quá x.
6. Đặc tả phát biểu: Với bất kỳ số tự nhiên x, luôn tìm được số nguyên y nhỏ hơn x.
7. Đặc tả phát biể
u: Tồn tại số tự nhiên x sao cho x > 1000.
8. Đặc tả phát biểu: Tồn tại số tự nhiên x sao cho x là số chẵn và x là số nguyên tố.
9. Đặc tả phát biểu: Với bất kỳ số tự nhiên x và y, tìm được số tự nhiên z sao cho x + y < z.
10. Đặc tả phát biểu: Với bất kỳ số tự nhiên x và y, luôn tìm được số
tự nhiên z < x + y.
∀ x ∈ N • ∀ y ∈ N • ∃ z ∈ N • z < x + y
Ghi chú: đối với các bài tập từ 4 đến 10, chỉ yêu cầu đặc tả đúng theo phát biểu, không xét
đến tính hợp lý của nội dung phát biểu.

BÀI TẬP ĐẶC TẢ HÌNH THỨC #2
11. Đặc tả hàm kiểm tra số thực a lớn hơn hay bằng số thực b hay không.
12. Đặc tả hàm trả về giá trị lớn nhất trong 3 số thực a, b, c.
13. Đặc tả hàm trả về số nguyên tố lớn nhất không vượt quá số tự nhiên n cho trước hoặc trả
về -1 nếu không tìm được giá trị cần thiết.
14. Đặc tả hàm kiểm tra n
ăm n > 0 là năm nhuận hay không.
15. Đặc tả hàm trả về số ngày tối đa của một tháng trong 1 năm nhuận.
16. Đặc tả hàm trả về số ngày tối đa của tháng t trong 1 năm n > 0.
17. Đặc tả hàm trả về số ngày chênh lệch từ ngày n
1
/t

33. Đặc tả hàm trả về chỉ số của phần tử nh
ỏ nhất không âm trong mảng a hoặc trả về giá trị -
1 nếu mọi phần tử đều là số âm.
34. Đặc tả hàm trả về số chính phương lớn nhất không vượt quá số nguyên dương x cho trước.
35. Đặc tả hàm trả về số nguyên tố nhỏ nhất lớn hơn hay bằng số tự nhiên n cho trước .
36. Đặc tả hàm đếm số lượng năm nhuậ
n từ năm a đến năm b (kể cả năm a và năm b). Chỉ xét
0 < a≤ b.
37. Đặc tả hàm đếm số lượng số nguyên tố từ số tự nhiên a đến số tự nhiên b (tính luôn a và b
với a ≤ b).
38. Đặc tả hàm tìm USCLN của các phần tử trong mảng a các số nguyên dương.
39.Đặc tả hàm tìm BSCNN c
ủa các phần tử trong mảng a các số nguyên dương.
40.Đặc tả hàm sắp xếp tăng dần mảng a các số thực.
BÀI TẬP ĐẶC TẢ HÌNH THỨC #5
41. Hãy đặc tả hàm trả sắp xếp mảng số thực A theo thứ tự giảm dần.
42. Hãy đặc tả hàm sắp xếp mảng số thực A theo thứ tự giá trị tuyệt đối tăng dần.
43. Hãy đặc tả hàm sắp xếp mảng số thực A theo quy luật sau:
- các số dương (nếu có) ở đầu mảng và có thứ tự giảm dần,
-
các số âm (nếu có) ở cuối mảng và có thứ tự tăng dần
44. Hãy đặc tả hàm sắp xếp mảng số nguyên A theo quy luật:
- các số chẵn (nếu có) ở đầu mảng và có thứ tự tăng dần,
- các số lẻ (nếu có) ở cuối mảng và có thứ tự giảm dần
45. Hãy đặc tả hàm sắp xếp mảng số nguyên A theo quy luật:
-
các số chẵn (nếu có) có thứ tự tăng dần,
- các số lẻ (nếu có) có thứ tự giảm dần
- tính chất chẵn/lẻ tại mỗi vị trí trong mảng A không thay đổi sau khi sắp xếp
(tức là trước khi sắp xếp, tại vị trí i của mảng A là số chẵn/lẻ thì tại vị trí i của

chuỗi s không có tiếng nào thì trả về chuỗ
i rỗng
54. Đặc tả hàm kiểm tra mảng số thực B là mảng con (gồm các phần tử liên tiếp nhau) của
mảng số thực A
! Ví dụ: mảng B = [1, 2, 3] là mảng con của mảng A = [4, 5, 1, 2, 3, 7, 8]
mảng B = [1, 2, 3] không phải là mảng con của mảng A = [1, 4, 2, 5, 3, 8]
55. Đặc tả hàm trả về mảng con (gồm các phần tử liên tiếp nhau) tăng dần dài nhất trong
mảng số thực A.
56a. Đặc tả kiểu dữ liệu PHÂN-SỐ và hàm inv-PHÂN-SỐ kiểm tra tính hợp lệ của phân số
b. Đặc tả hàm tính tổng (và rút gọn kết quả) của một mảng gồm các phân số
58a. Đặc tả kiểu dữ liệu ĐIỂM và ĐƯỜNG-THẲNG trong không gian 2 chiều.
b. Đặc tả hàm kiểm tra một điểm có thuộc về một đường thẳng hay không (sử dụng kiểu dữ

liệu đã định nghĩa)
59a. Đặc tả kiểu dữ liệu ĐIỂM và TAM-GIÁC trong không gian 2 chiều.
b. Đặc tả hàm kiểm tra điều kiện tạo thành của một tam giác (3 đỉnh không thẳng hàng)
60a. Đặc tả kiểu STACK chứa các số tự nhiên.
b. Đặc tả các thao tác sau:
POP: lấy phần tử ở đỉnh stack ra khỏi stack, trả về -1 nếu stack rỗng
PUSH: thêm 1 phần t
ử vào đỉnh stack, trả về TRUE nếu thành công và FALSE nếu
ngược lại
TOP: trả về giá trị của phần tử ở đỉnh stack (không xóa phần tử này ra khỏi stack), hoặc
trả về -1 nếu stack rỗng
ISEMPTY: kiểm tra stack rỗng hay không
ISFULL: kiểm tra stack đầy hay không
EMPTY: khởi
t
ạ
o stack về t

pre
post ((len ds-học = 0) ∧ (kq = {}))
∨ ((len ds-học > 0) ∧ (ds-học(1).mã-SV = mã-SV) ∧
(kq = {ds-học(1).mã-Môn} ∪ XLĐệQuy(mã-SV, tl ds-học)))
∨ ((len ds-học > 0) ∧ (ds-học(1).mã-SV ≠ mã-SV) ∧
(kq = XLĐệQuy(mã-SV, tl ds-học)))
62. Cho các kiểu dữ liệu sau:
Sinh-Viên ::
mã-SV: Mã-SV
họ-tênSV: Họ-Tên
Môn ::
mã-Môn: Mã-Môn
tên-Môn: Tên-Môn
hệ-số: ℕ

KQ-Học ::
mã-Môn: Mã-Môn
học-kỳ: {1, 2, 3, 4}
năm-học: ℕ
1
điểm: ℝ
Cho trước ánh xạ kq-Học: Mã-SV
⎯→⎯
m
KQ-Học* thể hiện tất cả kết quả học tập của sinh
viên (nếu sinh viên đã học một môn nhiều lần thì tất cả kết quả học của sinh viên trong môn
học này đều được ghi nhận lại).
Hãy đặc tả hàm trả về danh sách các mã học phần mà sinh viên có mã sinh viên là mã-SV đã
học.
DS-Mã-Môn-Đã-Học

m
Học-Phần*) kq : B
65. Hãy đặc tả hàm trả về tên của chuyên ngành có số lượng học phần nhiều nhất (ghi chú :
trong trường hợp có nhiều chuyên ngành có cùng số lượng học phần nhiều nhất, chỉ cần trả
tên của một chuyên ngành trong số này).
Chuyên-Ngành-Nhiều-Học-Phần-Nhất
(ds-HọcPhần-ChuyênNgành : Tên-Chuyên-Ngành ⎯→⎯
m
Học-Phần*) tênHP : char*
Câu 66 đến 70 :
Cho các kiểu dữ liệu sau :

Sinh-Viên ::
mã-SV: Mã-SV
họ-tênSV: char*
khóa-tuyển:
ℕ
1

Khoa::
mã-Khoa : Mã-Khoa
tên-Khoa: char*Cho các ánh xạ sau:
ds-Khoa : Mã-Khoa
⎯→⎯
m
Khoa
ds-SV : Mã-SV

69. Giả sử các khoa đều có tên phân biệt. Hãy đặc tả hàm trả về mã khoa tương ứng với tên
khoa cho trước.
Tìm-Mã-Khoa-Theo-Tên (tên-Khoa: char*): mã-Khoa: Mã-Khoa

70. Hãy đặc tả hàm trả về số lượng sinh viên trong khóa tuyển khóa-tuyển thuộc Khoa với tên
Khoa là tên-Khoa cho trước. Giả sử các khoa đều có tên phân biệt.
SL-SV-Khoa-Trong-Khóa-Tuyển (tên-Khoa:char*, khóa-tuyển:
ℕ
1
) sốlượngSV: ℕ
BÀI TẬP ĐẶC TẢ HÌNH THỨC #8
Bài 71 : Đặc tả kiểu dữ liệu NGAY. Đặc tả điều kiện của một ngày hợp lệ.
Bài 72: Đặc tả hàm trả về ngày tiếp theo sau 1 ngày cho trước.
Bài 73: Đặc tả hàm trả về ngày thứ n (n >= 0) tiếp theo sau ngày cho trước.
Bài 74: Đặc tả hàm trả về số ngày chênh lệch giữa 2 ngày cho trước.
(ví dụ : ngày 1 : 1/1/2007, ngày 2 : 1/1/2006 " Kết quả : -365)
Bài 75: Cho biết ngày 12/5/2007 là ngày thứ bảy.Hãy đặc tả hàm tr
ả về thứ của 1 ngày cho
trước(trả về chuỗi ký tự).
Bài 76: Hãy đặc tả kiểu ĐƠN-THỨC & ĐA-THỨC.
Bài 77: Đặc tả hàm tính đạo hàm (cấp 1) của 1 đa thức.
Bài 78: Đặc tả hàm tìm tất cả các nghiệm (phân biệt) của 1 đa thức.
Tập-Nghiệm ::
sốNghiệm:
ℕ
nghiệm :
ℝ*
Bài 79: Đặc tả hàm tính giá trị đa thức với giá trị x
0
cho trước

- Đồ thị G có thể vô hướng hoặc có hướng
Bài 86: Đặc tả hàm kiểm tra một đồ thị G có liên thông hay không. Gợi ý: Trong đồ thị liên
thông, luôn tồn tại dây chuyền nối liền hai đỉnh phân biệt bất kỳ
Bài 87: Đặc tả hàm kiểm tra một đồ thị G có phải là cây hay không. Gợi ý: cây là đồ thị liên
thông có đúng n-1 cạ
nh (với n là số lượng đỉnh của đồ thị)
Bài 88: Tự đặc tả kiểu dữ liệu SPANNING-TREE để lưu trữ một cây khung của đồ thị. Đặc tả
điều kiện hợp lệ inv-SPANNING-TREE cho kiểu dữ liệu này.
Bài 89: Đặc tả hàm tính trọng số của một cây khung cho trước. Đặc tả hàm xác định cây
khung nhỏ nhất (có tổng trọng số nhỏ nhấ
t) của một đồ thị vô hướng G cho trước. (không xử
lý khi đồ thị không liên thông)
Bài 90: Đặc tả hàm kiểm tra một đồ thị vô hướng G có tồn tại đường đi Euler hay không? Gợi
ý: đồ thị G có tồn tại đường đi Euler nếu G có 0 hoặc 2 đỉnh bậc lẻ.
BÀI TẬP ĐẶC TẢ HÌNH THỨC #10
Sử dụng các kiểu dữ liệu sau cho các câu từ 91 đến 95:
SÂN-VẬN-ĐỘNG ::
tên-Sân: char*
sức-chứa: ℕ
1

TỶ-SỐ ::
số-bàn-thắng-đội-nhà : ℕ
số-bàn-thắng-đội-khách : ℕ
ĐỘI-BÓNG ::
tên-Đội: char*
sân-nhà : SÂN-VẬN-ĐỘ NG
TRẬN-ĐẤU ::
đội-nhà : ĐỘI-BÓNG
đội-khách : ĐỘI-BÓNG

ℕ
PROCESS_INFO ::
pID : PROCESS_ID
CPUBurstTime: ℝ
READY_LIST = PROCESS_INFO*
Cho trước biến toàn cục ready-List : READY-LIST
96. Hãy đặc tả hàm FIFOScheduler cho phép chọn ra tiến trình theo chiến lược FIFO với
thông tin các tiến trình đang chờ sử dụng CPU trong ready-List.
FIFOScheduler () pID: PROCESS_ID

97. Hãy đặc tả hàm SJFScheduler cho phép chọn ra tiến trình theo chiến lược SJF (Shortest
Job First) với thông tin các tiến trình đang chờ sử dụng CPU trong ready-List. Nếu có nhiều
tiến trình có cùng thời gian thực thi (CPUBurstTime) ngắn nhất bằng nhau thì ưu tiên chọn
tiến trình có thời gian ngắn nhất xuất hiện trước trong ready-List.
SJFScheduler () pID: PROCESS_ID 98. Tự định nghĩa kiểu dữ liệu TOWER_STATE để biểu diễn 1 trạng thái của bài toán Tháp
Hà Nội với 3 cột (A, B, C) và n đĩa (đánh số từ 1 đến n, đĩa 1 < đĩa 2 < … < đĩa n). Đặc tả
điều kiện ràng buộc đối vớ i kiểu dữ liệu này (ghi chú: với mỗi cột, đĩa dưới phải lớn hơn đĩa
trên)
99. Đặc tả thao tác
MoveAB thực hiện việc di chuyển 1 đĩa (trên cùng) từ cột A sang cột B.
Lưu ý chỉ xử lý nếu cột A có ít nhất 1 đĩa, và đĩa trên cùng của cột A phải nhỏ hơn đĩa trên
cùng của cột B, hoặc cột B còn trống.
MoveAB(S
0
: TOWER_STATE) S
1
: TOWER_STATE

1
: TOWER_STATE
Hãy đặc tả hàm biến đổi từ trạng thái S
0
sang trạng thái S
n
cho trước.