Bài tập Các kiểu dữ liệu cơ bản

Chia sẻ: Thanh Tran | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

98
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Viết chương trình 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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài tập Các kiểu dữ liệu cơ bản

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 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 (IsEmpty(s) == 0) { Pop(s, x); printf(“%d “, y); } 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); } 5. ết ct minh họa các thao tác tr ên ngăn xếp 6. ế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
- Tính tổng giá trị các nút, tổng chẵn, tổng lẻ - Kiểm tra xâu T1 có xuất hiện trong xâu T2 không v à ngược lại 13. Hãy cài đặt thuật toán Quicksort không d ùng đệ qui. 14. Cho dãy số f(n) = 1 nếu n = 0 hay n = 1 f(n-1) + f(n-2) nếu n > 1 - Hãy viết một thủ tục/hàm đệ qui tính giá trị của f(n), với n đ ược nhập từ bàn phím. - Hãy viết một thủ tục/hàm không đệ qui tính giá trị của f(n), với n được nhập vào từ bàn phím. Sử dụng Stack để khử đệ qui. 15. Cho 2 xâu đơn T1, T2 ciết ct thực hiện các thao tác - Tìm phần giao của 2 xâu - Tìm phần hội của 2 xâu - Tìm phần hiệu của 2 xâu Chương 5 Bảng băm ết ct mô phỏng các thao tác tr ên bảng băm sử dụng phương pháp dò tuyến tính Viết ct mô phỏng các thao tác tr ên bảng băm sử dụng phương pháp nối kết Viết ct mô phỏng các thao tác tr ên bảng băm sử dụng phương pháp dò bậc hai ết ct tổ chức lưu trữ từ điển dưới dạng bảng băm 5. Hãy chọn cấu trúc dữ liệu thích hợp để biểu diễn trong bộ nhớ chính một từ điển tần số gồm tối đa 1000 từ, mỗi từ có độ dài 10 ký tự, đi kèm với mỗi từ là số lần xuất hiện của từ đó (đ ã được thu thập từ một số văn bản nào đó). Yêu cầu : a. Thời gian truy cập đến một từ l à tối thiểu b. Bộ nhớ được dùng là tối thiểu Giả sử cấu trúc dữ liệu biểu diễn từ điển tần số (câu a.) đ ã được định nghĩa và chứa đầy đủ dữ liệu. Viết chương trình C/Pascal liệt kê ra 100 từ có tần số lớn nhất. Chương 6 Cấu trúc cây 1. Hãy cài đặt thuật toán duyệt cây nhị phân (NLR) không dùng đệ qui (dùng stack) 2. Hãy cài đặt thuật toán duyệt cây nhị phân theo mức không dùng đệ qui (dùng queue) 3. Cho một cây nhị phân tìm kiếm với gốc là Root, giá trị lưu trữ tại mỗi nút là một số nguyên (int). Hãy viết đoạn chương trình tìm phần tử nhỏ nhất trong cây. 4. Cho một cây nhị phân có cấu trúc nút l à NODE, hãy: a. Viết thủ tục/hàm để tính tổng số nút có 1 nhánh con (con trái HAY con phải) bằng cách d ùng thuật toán duyệt gốc giữa NLR. b. Thiết lập 1 công thức đệ qui để thực hiện y êu cầu ở câu [a]. Cài đặt công thức này thành thủ tục/hàm. 5. Cho một cây nhị phân tìm kiếm t có cấu trúc nút là BST_NODE được khai báo như sau: struct BST_NODE { int Key; // Khoá của nút int So_lan; // Số lần xuất hiện của khoá trong cây struct BST_NODE *Left, *Right ; } struct BST_TREE { struct BST_NODE *pRoot; // Nút gốc của cây } struct BST_TREE t; // Cây t a. Hãy viết thủ tục/hàm thực hiện thao tác xoá phần tử có khoá X. Cách xoá nh ư sau:
· Nếu phần tử X có tồn tại, giảm field So_lan của nó 1 đ ơn vị. · Nếu phần tử X không tồn tại, thông báo. b. Hãy viết 1 thủ tục/hàm in lên màn hình giá trị của các phần tử đang tồn tại trong cây theo thứ tự NLR. Ghi chú: một phần tử được gọi là có tồn tại trong cây nếu So_lan > 0. 6. Cho một cây nhị phân có gốc l à Root, mỗi nút chứa một số nguyên. a. Hãy viết chương trình tính trung bình cộng của các nút trong cây. b. Hãy viết chương trình tính trung bình cộng của các số dương trong cây. c. Hãy viết chương trình tính trung bình cộng của các số âm trong cây. d. Hãy viết chương trình tính tỉ số: R=a/b Với a = tổng số các nút có giá trị > 0 b = tổng số các nút có giá trị < 0 7. Hãy viết một thủ tục/hàm tạo một danh sách liên kết đơn từ cây trên sao cho giá trị các phần tử trong danh sách có thứ tự giảm dần. Biết gốc của cây l à ROOT.