Tham khảo tài liệu 'toán rời rạc ứng dụng trong tin học part 8', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Phần III. ĐỔ THỊ VÀ ỨNG DỤNG 287 22. Cho cây ngũ nguyên dưới đây Hãy gán nhãn theo địa chỉ phổ dụng cho tất cả các đỉnh của cây trên. 23. Xây dựng hệ địa chỉ phổ dụng cho cây có gốc và được sắp sau 288 TOÁNRỜI RẠCỨNG DỤNG TRONG TIN HỌC 24. Các lá của cây có gốc và được sắp có thể có danh sách địa chỉ phổ dụng như sau được không Nếu có hãy xây dựng cây có gốc đó a b 1 1 c 2 2 4 . 25. Để biểu diễn biểu thức sô học chứa các toán tử cộng - trừ nhân chia và T lũy thừa ta dùng các dấu ngoặc biểu thị thứ tự các phép toán bằng cây có gốc được sắp trong đó các đỉnh trong biểu thị các phép toán các lá biểu thị các số hay các biến. Mỗi một phép toán tác động lên các cây con bên trái và cây con bên phải của nó đều theo thứ tự này. a Tìm cây có gốc biểu diễn biểu thức x y 2 x - 4 3 . b Tìm dạng tiền tố của biểu thức trên. c Tim dạng hậu tố của biểu thức trên. 26. a Hãy tìm cây có gốc và được sắp biểu diễn mênh đề lôgic phức hợp -1 p A q - ì p V 1 q . b Tìm dạng tiền tố hậu tố và trung tố của biểu thức trên. 27. a Tìm giá trị của biểu thức tiền tố - 235 T234. b Tim giá trị của biểu thức hậu tố 7 2 3 - 4 T 9 3 ì . 28. Cho hai cây có gốc và được sắp . T Xác định thứ tự mà các đỉnh của hai cây nếu ta duyệt nó theo kiểu a Tiền thứ tự b Trung thứ tự c Hậu thứ tụ. 29. a Dùng thuật toán sắp xếp kiểu nổi bọt hãy sắp xếp danh sách L 3 1 5 7 4 6 và chỉ rõ các danh sách nhận được ở mỗi bước. a Dùng thuật toán sắp xếp kiểu nổi bọt hãy sắp xếp danh sách L d f m k a b và chỉ rõ các danh sách nhận được ở mỗi bước. 30. Dùng thuật toán hoà nhập hai danh sách hãy hoà nhập hai danh sách Lj 1 3 5 7 9 và L2 2 4 6 8 10 bằng phương pháp lập bảng. 31. Hãy viết thuật toán sắp xếp kiểu chọn lọc ở dạng giả mã. 32. Sắp xếp danh sách 7 8 1 2 4 3 5 6 9 bằng thuật toán sắp xếp nhanh. 33. Mô tả thuật toán sắp xếp nhanh dưới dạng giả
