Giải Thuật Và Lập Trình - C: BÀI TẬP | V1Study

• Đào tạo Độ tuổi từ 5 - 11 Độ tuổi từ 12 - 17 Từ 18 tuổi
• Lập trình Python Lập trình C C++ Java C# - C Sharp Android Scratch Pascal Robot mBot
• Web ReactJS HTML5 CSS3 JavaScript Node.js JSP ASP.NET Core jQuery PHP
• FW-CMS Laravel AngularJS Flutter Magento Bootstrap VueJS CodeIgnitor WordPress Sass Drupal
• Video Video Python Video Lập trình C Video C# Video Java Video HTML5-CSS3-JavaScript Video SQL Server Video PHP Video jQuery Video Android Video C++ Video Scratch
• Video1 Video XML-JSON Video MySQL Video Excel Video Giải thuật và Lập trình Video Sức khỏe Video Drupal Video mBot Video Giáo dục - Khoa học
• Other Unity Giải thuật và lập trình Giải thuật và lập trình - C CCNA Mạng máy tính Design Patterns English Facebook SEO Git Tin học đại cương Japanese App-Uti Download
• Data SQL Server XML JSON MySQL
• News

≡ ≡ Giải thuật và lập trình - C Chương I. Mở đầu I. Từ bài toán đến chương trình II. Kiểu dữ liệu trừu tượng (ABSTRACT DATA TYPE - ADT) III. Kiểu dữ liệu, Cấu trúc dữ liệu, Kiểu dữ liệu trừu tượng (DATA TYPES, DATA STRUCTURES, ABSTRACT DATA TYPES) Chương II. Các kiểu dữ liệu trừu tượng cơ bản I. Kiểu dữ liệu danh sách (LIST) II. Ngăn xếp (Stack) III. Hàng đợi (QUEUE) IV. Danh sách liên kết kép (DOUBLE - LISTS) BÀI TẬP Chương III. Cấu trúc cây (TREES) I. Các thuật ngữ cơ bản trên cây II. Kiểu dữ liệu trừu tượng cây III. Cài đặt cây IV. Cây nhị phân (BINARY TREES) V. Cây tìm kiếm nhị phân (BINARY SEARCH TREES) BÀI TẬP Chương IV. Tập hợp I, II. Khái niệm, Kiểu dữ liệu trừu tượng tập hợp III. Cài đặt tập hợp IV. Từ điển (DICTIONARY) V. HÀNG ƯU TIÊN (PRIORITY QUEUE) BÀI TẬP Chương V. Đồ thị (Graph) I. Các định nghĩa II. Kiểu dữ liệu trừu tượng đồ thị III. Biều diễn đồ thị IV. Các phép duyệt đồ thị (Traversals of graph) V. Một số bài toán trên đồ thị BÀI TẬP Solutions Solution CÀI ĐẶT CÂY (TREE) bằng mảng Giải thuật và lập trình - C: BÀI TẬP Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên

1. Trình bày các biểu thức duyệt tiền tự, trung tự, hậu tự của cây sau:

2. Duyệt cây theo mức là duyệt bắt đầu từ gốc, rồi duyệt các nút nằm trên mức 1 theo thứ tự từ trái sang phải, rồi đến các nút nằm trên mức 2 theo thứ tự từ trái sang phải...Và cứ như vậy.

a. Hãy liệt kê các nút theo thứ tự duyệt theo mức của cây trong bài 1.

b. Viết thủ tục duyệt cây theo mức. (Gợi ý: dùng hàng đợi)

3. Vẽ cây biểu diễn cho biểu thức ((a+b)+c*(d+e)+f)*(g+h) Trình bày biểu thức tiền tố và hậu tố của biểu thức đã cho.

4. Viết chương trình để tính giá trị của biểu thức khi cho:

a. Biểu thức tiền tố

b. Biểu thức hậu tố.

Ví dụ:

- đầu vào (input): * + 6 4 5

- thì đầu ra (output) sẽ là: 50 vì biểu thức trên là dạng tiền tố của (6+4) * 5

Tương tự:

- đầu vào (input): 6 4 5 + *

- thì đầu ra (output) sẽ là: 54 vì biểu thức trên là dạng hậu tố của 6 * (4+5)

5. Cho cây nhị phân

a. Hãy trình bày các duyệt: tiền tự (node-left-right), trung tự (left-node-right), hậu tự (left-right-node).

b. Minh hoạ sự lưu trữ kế tiếp các nút cây này trong mảng.

6. Chứng minh rằng: nếu biết biểu thức duyệt tiền tự và trung tự của một cây nhị phân thì ta dựng được cây này.

Điều đó đúng nữa không? Khi biết biểu thức duyệt:

a. Tiền tự và hậu tự

b. Trung tự và hậu tự

7. Nêu các trường hợp mà các giải thuật trên cây TKNP:

- Có hiệu quả nhất

- Kém hiệu quả nhất

Từ đó nêu ra các hướng tổ chức cây TKNP để đạt được hiệu quả cao về thời gian thực hiện giải thuật.

8. a. Vẽ hình cây tìm kiếm nhị phân tạo ra từ cây rỗng bằng cách lần lượt thêm vào các khoá là các số nguyên: 54, 31, 43, 29, 65, 10, 20, 36, 78, 59.

b. Vẽ lại hình cây tìm kiếm nhị phân ở câu a/ sau khi lần lượt xen thêm các nút 15, 45, 55.

c. Vẽ lại hình cây tìm kiếm nhị phân ở câu a/ sau khi lần lượt xoá các nút 10, 20, 43, 65, 54.

9. Hãy dựng cây tìm kiếm nhị phân ứng với dãy khóa (thứ tự tính theo qui tắc so sánh chuỗi (string)): HAIPHONG, CANTHO, NHATRANG, DALAT, HANOI, ANGIANG, MINHHAI, HUE, SAIGON, VINHLONG. Đánh dấu đường đi trên cây khi tìm kiếm khóa DONGTHAP.

10. Cài đặt cây TKNP có khoá là chuỗi (String) với các phép toán thêm, xoá. Bổ sung thêm các thủ tục cần thiết đề có 1 chương trình hoàn chỉnh, cung cấp giao diện để người dùng có thể thêm, xoá 1 khoá và duyệt cây để kiểm tra kết quả.

11. Viết các thủ tục thêm, xoá một nút có khoá x trên cây tìm kiếm nhị phân bằng cách không đệ qui.

12. Để mở rộng khả năng xử lí các khoá trùng nhau trên cây tìm kiếm nhị phân, ta có thể tổ chức cây tìm kiếm nhị phân như sau: tại mỗi nút của cây ta tổ chức một danh sách liên kết chứa các khoá trùng nhau đó. Chẳng hạn cây được thiết lập từ dãy khoá số nguyên 10, 15, 5, 10, 20, 4, 5, 10, 15, 15, 4, 15 như sau:

Trong đó các mũi tên nằm ngang chỉ các con trỏ của danh sách liên kết.

Hãy viết khai báo cấu trúc dữ liệu và các thủ tục/hàm để cài đặt cây TKNP mở rộng như trên.

» Tiếp: I, II. Khái niệm, Kiểu dữ liệu trừu tượng tập hợp « Trước: V. Cây tìm kiếm nhị phân (BINARY SEARCH TREES) Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên Copied !!! Copy linkCopied link!

Bạn muốn tìm kiếm điều gì?

×