Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Bài tập tổng hợp về cây

Share

admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 35
Đến từ : Cần Thơ

Bài tập tổng hợp về cây

Bài gửi  admin on Sun Apr 18, 2010 8:13 pm

BÀI TẬP TỔNG HỢP VỀ CÂY



1. Viết chương trình tính chiều cao của cây

2. Cho m, n là hai node trên cây. Viết các thủ tục kiểm tra:
a. ON_LEFT(m, n)=true nếu m ở bên trái của n (=false nếu không)
b. ON_RIGHT(m,n)=true nếu m ở bên phải của n (=false nếu không)
c. P_ANCESTOR(m, n)=true nếu m là tổ tiên thực sự của n (=false nếu không)
d. P_DESCENDANT(m, n)=true nếu m là hậu duệ thực sự của n (=false nếu không)

3. Viết chương trình tìm tổ tiên chung gần nhất của hai node trên cây (tổ tiên chung gần nhất là node: là tổ tiên của cả hai node và mọi node là tổ tiên của cả hai node là tổ tiên của node này)

4. Duyệt theo mức một cây: đầu tiên liệt kê gốc, sau đến các node ở độ sâu 1, tiếp đó các node ở độ sâu 2 … Các node ở cùng độ sâu được liệt kê từ trái qua phải. Viết chương trình duyệt theo mức một cây.

5. Chuyển biểu thức ((a+b) + c*(d+e) + f)*(g+h) sang:
a. biểu thức prefix
b. biểu thức postfix

6. Cho cây T trong nó mỗi node trong đều có 2 con. Viết chương trình chuyển:
a. duyệt tiền tự của T sang duyệt hậu tự
b. duyệt hậu tự của T sang duyệt tiền tự
c. duyệt tiền tự của T sang duyệt trung tự

7. Bậc của một node là số con của nó. Chứng tỏ rằng trong cây nhị phân số node lá bằng số node bậc 2 cộng 1

8. Chứng tỏ rằng trong cây nhị phân chiều cao h của cây >=log(n+1)/2 trong đó n là số node của cây

9. Cho biết các duyệt tiền tự, trung tự và hậu tự của một cây. Mô tả một thuật toán xác định, với mọi cặp node (m, n), m có là tổ tiên của n hay không.

10. Có thể kiểm thử node m là tổ tiên thực sự của node n bằng cách kiểm thử m đứng trước n trong X-order và sau n trong Y-order (X, Y không thuộc {pre, in, post}). xác định tất cả các cặp X, Y mệnh đề trên là đúng.
( X=pre, Y= post)

11. Thực thi các hoạt động cây trong biểu diễn cây bởi:
a. các con trỏ về cha
b. danh sách các con
c. các con trỏ leftmost_child, right_sibling


nokiatin
Nhập môn
Nhập môn

Tổng số bài gửi : 1
Points : 1
Join date : 09/07/2011

help me

Bài gửi  nokiatin on Sat Jul 09, 2011 7:11 am

co ai co lio giai bai 2 khong giup moi
2. Cho m, n là hai node trên cây. Viết các thủ tục kiểm tra:
a. ON_LEFT(m, n)=true nếu m ở bên trái của n (=false nếu không)
b. ON_RIGHT(m,n)=true nếu m ở bên phải của n (=false nếu không)
c. P_ANCESTOR(m, n)=true nếu m là tổ tiên thực sự của n (=false nếu không)
d. P_DESCENDANT(m, n)=true nếu m là hậu duệ thực sự của n (=false nếu không)
bounce Question Question Question Question Question Question Question Question

    Hôm nay: Mon Dec 05, 2016 11:36 pm