Lập trình hướng đối tượng - Ôn tập

Bài Tập Chương 1 Bài 1 Số phần tử nhiều, ít nhất trong một heap chiều cao h là bao nhiêu? Hướng dẫn: Heap chiều cao h có số node lớn nhất M khi các con ở mức h-1 đều có 2 con là lá M=2h+1-1. Số node ít nhất m = [2(h-1)+1-1]+1 =2h Bài 2 Chứng minh 1 heap n phần tử thì có chiều cao là lgn Hướng dẫn: Theo bài 1: 2h  n  2h+1-1 suy ra lg(n+1) -1 h  lgn, vì lgn < lg(n+1) Nên lg(n) -1 < h  lgn. Nghĩa là h = lgn Bài 3 Dãy sau đây có là một max-heap hay không 23, 17, 14, 6, 13, 10, 1, 5, 7, 12 Bài 4 Dựa trên thủ tục MAX-HEAPIFY(A, i) hãy viết mã giả cho thủ tục MIN-HEAPIFY(A, i) thực hiện thao tác tạo ra một min-heap có gốc tại nút i. Bài 5 Biểu diễn thao tác BUILD-MAX-HEAP(A) trên mảng A = 5, 3, 17, 10, 84, 19, 6, 22, 9 Bài 6 Biểu diễn thao tác HEAPSORT(A) trên mảng A = 5, 13, 2, 25, 7, 17, 20, 8, 4 Bài 7 Biểu diễn cấu trúc dữ liệu max-heap như một mảng trong C++ và viết chương trình hiện thực giải thuật heapsort. Bài 8 Sử dụng max-heap biểu diễn dãy các số thực a1, a2, , an  để viết một thuật toán tìm max {a1, a2, , an} Bài 9 Biểu diễn cấu trúc dữ liệu hàng đợi ưu tiên dựa trên mô hình dữ liệu max-heap và viết các thao tác trên hàng đợi trong trong C++. Bài 10 Giả sử heap được bởi một mảng a1, a2, , an . Chứng tỏ các phần tử có chỉ số n/2+1, n/2+2,, n là các lá của heap này. Bài 11 Viết thủ tục BUILD-MIN-HEAP tạo một min-heap ứng với mảng A, sử dụng thủ tục này để viết heap-sort dựa trên min-heap để sắp xếp mảng theo thứ tự giảm dần. Hiện thực heap-sort theo giải thuật vừa viết trong C++. Bài 12 Biểu diễn cấu trúc dữ liệu hàng đợi ưu tiên dựa trên mô hình dữ liệu min-heap và viết các thao tác trên hàng đợi trong trong C++. Bài Tập Chương 2 Bài 1 Biểu diễn thao tác PARTITION trên mảng A = 13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6 Bài 2 Biểu diễn quá trình thực hiện giải thuật QUICKSORT trên A = 13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6 Bài 3 Tính thời gian chạy trong trường hợp tốt nhất và xấu nhất của thuật giải PARTITION. Bài 4 Sửa quicksort để sắp xếp mảng A[p..r] theo trật tự không tăng. Biểu diễn quá trình thực hiện giải thuật này trên A = 13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6. Bài 5 Hiện thực giải thuật quicksort trong C++. Bài 6 Dùng quicksort viết chương trình sắp xếp một tập sinh viên theo thứ tự TEN sinh viên (sinh viên có MSV, TEN, TUOI, NGAYSINH). Bài 7 Đánh giá thời gian thực hiện quicksort trong trường hợp giá trị của các phần tử của mảng được sắp đã có trật tự tăng dần. Bài 8 Đánh giá thời gian thực hiện quicksort trong trường hợp giá trị của các phần tử của mảng được sắp đã có trật tự giảm dần. Bài 9 Tìm hiểu và viết tất cả các giải thuật sắp xếp khác ngoài Heapsort và Quicksort. Hiện thực các giải thuật này trong C++. Bài Tập Chương 3 Bài 1 Biểu diễn thao tác COUNTING-SORT trên mảng A = 6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2. Bài 2 Hiện thực COUNTING-SORT trong C++ để sắp xếp các phần tử được lưu trữ trên mảng A và mỗi phần tử không vượt quá số k cho trước. Bài 3 So sánh COUNTING-SORT và quicksort. Bài 4 Biểu diễn thao tác BUCKET-SORT trên mảng A = .79, .13, .16, .64, .39, 20, .89, .53, .71, .42. Bài 5 Hiện thực BUCKET-SORT trong C++. Bài 6 So sánh BUCKET-SORT và heapsort Bài 7 Hãy sửa BUCKET-SORT để nó có thể sắp xếp một mảng các số thực không âm bất kỳ. Bài Tập Chương 4 Bài 1 Dùng ma trận kề và danh sách kề để biểu diển các đồ thị sau (sinh viên tự đánh số các đỉnh một cách tùy ý): Bài 2 Hãy vẽ đồ thị được biểu diễn bởi ma trận trọng số sau.            042 403 321 C Bài 3 Cho đồ thị vô hướng, viết chương trình xác định bậc của mỗi đỉnh. Bài 4 Cho đồ thị có hướng, viết chương trình xác định bán bậc ra (vào) của mỗi đỉnh. Bài 5 Sử dụng đỉnh 3 như là đỉnh nguồn, chỉ ra các giá trị của d và  khi thực thi thuật toán tìm kiếm theo chiều rộng trên đồ thị sau. Bài 6 Biểu diễn đồ thị như ma trận hoặc danh sách và hiện thực các giải thuật DFS và BFS trong C++. Bài 7 Cho đơn đồ thị, viết chương trình xác định xem đồ thị này có liên thông hay không. Bài 8 Viết chương trình tính số thành phần liên thông của một đồ thị vô hướng. Bài 9 Viết chương trình tìm một đường đi giữa 2 đỉnh s và t trong đơn đồ thị liên thông. Bài 10 Viết chương trình tính bậc của đỉnh có bậc nhỏ nhất trong đồ thị vô hướng. Bài 12 Viết chương trình tính độ dài đường đi ngắn nhất giữa 2 đỉnh bất kỳ trong một đồ thị không có trọng số. 1 2 3 6 4 5 Bài Tập Chương 5 Bài 1 Cho đồ thị vô hướng liên thông G = (V,E). Gọi e = (u, v)  E là cạnh có trọng số bé nhất trong G. C/m có một cây bao trùm bé nhất chứa e. Bài 2 G là một rừng gồm k cây, n đỉnh. Tìm số cạnh của G?. Bài 3 CMR đồ thị G có duy nhất một cây bao trùm thì G là một cây. Bài 4 Viết chương trình kiểm tra một đồ thị có phải là một cây hay không. Bài 5 Cho đồ thị có trọng số G = (E, V) ( Hình vẽ). Hãy dùng thuật toán Kruskal để tìm cây bao trùm bé nhất của G Bài 6 Hãy dùng thuật toán Prim để tìm cây bao trùm bé nhất của đồ thị G trong bài tập 6. Bài 7 Viết chương trình hiện thực thuật toán Kruskal. Bài 8 Viết chương trình hiện thực thuật toán Prim. Bài 9 Giả sử phải nối một mạng máy tính cục bộ. Hãy viết một chương trình để tính toán chi phí đường dây nối sao cho ít nhất, nếu đã biết các khoảng cách giửa các máy tính (nguồn điện cho một máy có thể lấy từ bất kỳ một máy khác đã có điện hoặc lấy từ một trung tâm cung cấp chung cho tất cả các máy- Có thể coi một máy tính nào đó đặt ở trung tâm này). 2 9 s 2 10 7 3 4 u v y x 6 z 5 5