Ôn tập thi giữa kì - Cấu trúc dữ liệu và Giải thuật 2023 môn Cấu trúc đại số | Đại học Sư phạm Hà Nội

lOMoAR cPSD| 57855709
Ôn tập thi giữa kì
Chương 1: Thuật toán và phân tích thuật toán
Bài 1: Sử dụng định nghĩa về Big-O và các quy tắc cơ bản, đánh giá độ phức tạp tính toán
của các giải thuật có số lần thực hiện các lệnh như sau a. 𝑓(𝑛) = 3n + 7 e. 𝑓 𝑙𝑜𝑔𝑛 b.
𝑓(𝑛) = 4𝑛3 + 2𝑛 + 2 f. 𝑓 n c.
𝑓(𝑛) = 2𝑛4 + 100𝑛2 + 50 g. 𝑓 d.
𝑓(𝑛) = 𝑛 + 4𝑛2 + 𝑙𝑜𝑔𝑛 h. 𝑓 𝑛𝑙𝑜𝑔𝑛
Bài 2: Cho chương trình bên dưới. Tính thời gian T(n) và đánh giá độ phức tạp của đoạn chương trình đó a) count = 0 def
b) count = 0 def Function(n): Function(n):
for i in range(1, n+1):
for i in range(1, n+1): count = i = i*3 print(i) count + 1 print(count) c) n = d) n = int(input()) i = n int(input()) i = 1
while (i > 1): i = i // 2 while (i <=n): print(i) i = i * 3 print(i) Chương 2: Đệ quy Bài 3:
a) Nêu định nghĩa về đệ quy. Khi thiết kế thuật toán đệ quy cần có những quy tắc nào?
b) Nêu ý tưởng thuật toán đệ quy và viết đoạn mã giả bằng Python để giải bài toán tính số fibonacci thứ n
c) Nêu ý tưởng thuật toán đệ quy và viết đoạn mã giả bằng Python để giải bài toán tháp Hà Nội với n đĩa
Bài 4: Viết chương trình đệ quy tính S𝑛 a) 𝑆 b) 𝑆 1. .𝑛 c) 𝑆 lOMoAR cPSD| 57855709 d) S(n)
Chương 3: Danh sách liên kết
Bài 5: Cho một danh sách liên kết đơn. Nêu ý tưởng (vẽ hình minh họa) thực hiện các công việc sau:
1. Khởi tạo lớp định nghĩa các nút trong danh sách
2. Khởi tạo con trỏ head và tail
3. Thêm nút mới vào đầu hoặc cuối danh sách.
4. Xóa một nút trong danh sách
5. Tìm kiếm một nút trong danh sách
6. Duyệt và in ra danh sách
Bài 6: Một nhà máy cần lưu trữ dữ liệu thông tin cá nhân của công nhân gồm 3 thuộc tính: ID, họ tên, tuổi
a) Đưa ra giải pháp sử dụng danh sách liên kết đơn giải quyết yêu cầu trên
b) Nêu ý tưởng và viết đoạn mã giả thực hiện các công việc sau:
1. Cài đặt lớp định nghĩa các nút trong danh sách
2. Thêm một công nhân vào đầu và cuối danh sách liên kết đơn
3. Tìm kiếm công nhân theo ID trong danh sách liên kết đơn
4. Xóa công nhân theo ID ra khỏi danh sách liên kết đơn 5. In danh sách công nhân
6. Tính tổng số công nhân có trong danh sách
7. Tìm công nhân lớn tuổi nhất và nhỏ tuổi nhất
Chương 4: Stack và queue Bài 7:
a) Nêu định nghĩa cấu trúc dữ liệu Stack. Đưa ra ý tưởng và viết đoạn mã giả cài đặt phép toán
Push, Pop, GetTop trong Stack bằng 2 cách: mảng, danh sách liên kết
b) Nêu định nghĩa cấu trúc dữ liệu Queue. Đưa ra ý tưởng và viết đoạn mã giả cài đặt Enqueue,
Dequeue, GetHead bằng 2 cách: mảng vòng, danh sách liên kết.
Bài 8: Nêu ý tưởng và viết đoạn mã giả cài đặt hàng đợi bằng ngôn ngữ lập trình Python kiểm
tra một xâu có phải là Palindrome hay không? Ta gọi palindromes là xâu mà đọc nó từ trái qua
phải cũng giống như đọc nó từ phải qua trái. VD: NOON, MADAM
Bài 9: Cài đặt ngăn xếp bằng ngôn ngữ lập trình Python kiểm tra một biểu thức dấu ngoặc có hợp lệ hay không. lOMoAR cPSD| 57855709 Input Output (((()))) True ) False ( False Chương 5: Cây
Bài 10: Cho cây nhị phân sau:
a) Nêu ý tưởng và viết đoạn mã giả thủ tục duyệt cây theo thứ tự trước.Viết ra kết quả phép duyệt
b) Nêu ý tưởng và viết đoạn mã giả thủ tục duyệt cây theo thứ tự giữa.Viết ra kết quả phép duyệt
c) Nêu ý tưởng và viết đoạn mã giả thủ tục duyệt cây theo thứ tự sau.Viết ra kết quả phép duyệt
d) Nêu ý tưởng và viết đoạn mã giả thủ tục duyệt cây theo chiều rộng.Viết ra kết quả phép duyệt