Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    Admin


    Quản trị viên
    Quản trị viên
    Cây nhị phân
    Có nhiều lý thuyết về cây nhị phân, nhưng ở đây chỉ đề cập tới cây nhi phân phục vụ cho đi thi thôi. Tức là phạm vi và tính chất được bó hẹp trong phạm vi đơn giản, chưa mở rộng. Cách tiếp cận này, chưa phải là tiên tiến nhất, nhưng nó làm cho người đi thi dễ hiểu, dễ thuộc và dễ... bắt chước nhất → dễ kiếm điểm nhất.
    Có 2 cách hiểu chính về cây nhị phân tuỳ thuộc vào tính chất của dữ liệu.
    1) Về trực quan: Cây là đồ thị liên thông, không chu trình. Ngoài ra có một nút đặc biệt chọn ra phụ thuộc vào bài toán cụ thể: Gốc. Trình tự từ gốc vô cùng quan trọng. Trình tự từ đỉnh đặc biệt này đến các đỉnh khác cho ta biết về cấp 0, chiều cao 0, nút 0. Đối với các đỉnh khác tính tới gốc có các giá trị 1, 2... ngoài ra còn có lá (không có nút con) hay các nút trong giúp hình dung cây dễ dàng hơn.
    2) Về toán học: Cây dược định nghĩa theo kiểu đệ quy, một nút con là một cây dùng theo dạng đệ quy có nút con, nút cha lúc này thứ tự đặt vấn đề sẽ khác với thứ tự ở 1) → chỉ ra cay có thứ tự rõ ràng, cha trước, con sau. Trong phạm vi nghiên cứu cây đối với đề thi thì cây hị phân không quá 2 nút con, đối với mỗi nút. Ngầm định khi làm việc với cây nhị phân sẽ là trái trước, phải sau. Trái bé, phải to. Nếu khong theo ngầm định phải tuyên bố rằng, bài thi của tôi sẽ coi như là... để người chấm biết. Nếu không tuyên bố mà không làm theo ngầm định, coi như làm sai và không được điểm.
    Về biểu diễn cây thường sử dụng danh sách liên kết là chủ yếu. Thông thường biểu diễn cây qua cấu trúc dữ liệu sau, cấu trúc này sử dụng cho các bài tập và bài thi đó nha, Admin cần chú ý mà nắm cho rõ đừng cố tình nhầm lẫn:
    List = Cây
    Cây = Record;
              d: Data;
              L, R: List;
    end.

    Bài tập ứng dụng cây trong đề thi mật độ lớn. Thường là câu 2 trong đề thi.
    Có 3 dạng bài tập trong đề thi đối với cây gồm:
    1) Duyệt cây: Giống như duyệt đồ thị, có thể đem thuật toán duyệt đồ thị sang duyệt cây, nhưng phải chuyển đổi cho phù hợp với dạng dữ liệu. Thường đề thi yêu cầu duyệt cây thì Output các đỉnh ra theo đúng thứ tự cây.
    2) Sử dụng cây phục vụ bài toán tìm kiếm
    3) Sử dụng cây để mã hoá dữ liệu ở 2 mức đơn giản: Mã tiền tố và mã Huffman.

    Ta làm một vài câu súc miệng để biết cách thức làm nó trong đề thi.
    1. Bài toán duyệt cây nhị phân:
    Về nguyên tắc:
    - Cần đặt tên của nút vừa là tên nút, vừa là giá trị mang để tránh ghi nhiều tên gây rối thuật toán.
    - Đề yêu cầu duyệt cây, thì phải viết ra được cây (Các nút của nó)
    Một cây đơn giản như thế này
    [You must be registered and logged in to see this image.]Có 3 phương pháp duyệt: Tiền, trung và hậu
    a) Duyệt tiền: Thứ tự u → P → x
    b) Duyệt trung: Thứ tự P → u → x
    c) Duyệt hậu: Thứ tự P → x → u
    a)
    Viết thủ tục duyệt tiền thứ thự đối với một cây T cho trước:

    [You must be registered and logged in to see this image.]Proc Tiền_TT(T: List)
    IF (T ≠ NIL)
              a) Output (T^.d)
              b) Tiền_TT (T^.L)
              c) Tiền_TT (T^.R)

    Con số cạnh mỗi nút trên hình là con số thứ tự duyệt.
    b)
    Viết thủ tục duyệt trung thứ thự đối với một cây T cho trước:

    [You must be registered and logged in to see this image.]Proc Trung_TT(T: List)

    IF (T ≠ NIL)

              a) Trung_TT (T^.L)
              b) Output (T^.d)
              c) Trung_TT (T^.R)
    Con số cạnh mỗi nút trên hình là con số thứ tự duyệt.
    c)
    Viết thủ tục duyệt hậu thứ thự đối với một cây T cho trước:


    [You must be registered and logged in to see this image.]Proc Hậu_TT(T: List)

    IF (T ≠ NIL)

              a) Hậu_TT (T^.L)
              b) Hậu_TT (T^.R)
              c) Output (T^.d)

    Con số cạnh mỗi nút trên hình là con số thứ tự duyệt.



    Được sửa bởi Admin ngày Sat Jul 23, 2011 4:21 am; sửa lần 1.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Các bài tập sát đề thi phần này (Đề nghị làm thành thạo, kiểu gì cũng có câu trúng đúng dạng đề thi)
    1)
    Biểu thức M cho ở dạng trung tố đầy đủ dấu ngoặc, chuyển M vào cây nhị phân T có cấu trúc List:

    Proc. ChuyenBT_vao_Cay;
    1) S= Ø;
    2) FOR i: = 1 to /M/
              CASE Mi of:
                        * Toán tử, toán hạng:
                                  New(X); X^.d = Mi; X^.L = Nil; X^.R = Nil; Push (X, S);
                        * Dấu ):
                                  Pop (S, đT); Pop (S, đG); Pop (S, đS)
                                  đG^.L := đS; đG^.R := đT;
                                  Push(đG, S);
    3) Pop (S, T);
    Output ( T );
    2)
    Biểu thức M chứa trong cây nhị phân T, viết thủ tục tính giá trị của M:

    Func Tính_GT (T: Tree)
    IF (T ≠ Nil) THEN
              IF (T^.d là toán hạng) return T^.d
                        ELSE
                                  α: = Tính_GT(T^.L)
                                  β: = Tính_GT(T^.R)
                                  γ = α . T^d . β
                                  return γ
    3)
    Chuyển biểu thức M ở dạng hậu tố vào cây T có cấu trúc List:

    Proc LuuBT_HauTo;
    1) S:= Ø;
    2) For i: = 1 to /M/
              IF (Mi là toán hạng) THEN
                        Push (Mi, S);
                        ELSE
                                  Pop (S, đT); Pop (S, đS)
                                  New (BT); BT := Mi; BT^R = đT; BT^.L = đS;
                                  Push (BT, S)
    3) Pop (S, T);
    Output (T);
    4)
    Biểu thức M cho ở dạng trung tố không dấu ngoặc, chuyển M vào cây nhị phân T có cấu trúc List:

    Proc. Chuyen_vao_Cay;
    1) S= Ø;
    2) FOR i: = 1 to /M/
              CASE Mi of:
                        * Toán hạng:
                                  New(X); X^.d = Mi; X^.L = Nil; X^.R = Nil; Push (X, Sh);
                        * Toán tử:
                                  a) New(X); X^.d = Mi; X^.L = Nil; X^.R = Nil;
                                  b) While (St ≠ Nil) & ƯuTiên(Top (St)^.d) ≥ ƯuTiên(Mi)) DO
                                  Pop (St, Y); Pop (Sh, a); Pop (Sh, b)
                                  Y^.L := b; Y^.R := a;
                                  Push(Y, Sh);
                                  c) Push (X, St)
    3) While (St ≠ Nil) DO
                                  Pop (St, Y); Pop (Sh, a); Pop (Sh, b)
                                  Y^.L := b; Y^.R := a;
                                  Push(Y, Sh);
    4) Pop (Sh, T);
    Output ( T );



    Được sửa bởi Admin ngày Wed Jun 29, 2011 11:29 am; sửa lần 3.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Chuyển biểu thức trung tố M không đủ dấu ngoặc vào cây nhị phân T
    Trước khi đọc lời giải, hãy xem bài [You must be registered and logged in to see this link.]
    Ý tưởng:
    - Duyệt từng phần tử trong M cho đến hết.
    - Nếu Mi là toán hạng: tống nó thêm vào stack Sh.
    - Nếu là dấu mở ngoặc “(“: cho vào stack St
    - Nếu là dấu đóng ngoặc “)”: Lặp công việc: lấy 1 phần tử trong stack St ra:
    * Là toán tử: lấy tiếp 02 phần tử trong Stack Sh ra, tạo lập một cây có 3 thành phần trên, xong tống cả cái cây đó vào trong Sh như một phần tử
    * Là dấu mở ngoặc: Thôi không lặp nữa.
    - Nếu là toán tử xét các trường hợp:

    • Chừng nào ở đỉnh stack St là toán tử và toán tử đó có độ ưu tiên lớn hơn hoặc bằng toán tử hiện tại thì lấy toán tử trong St ra, đồng thời lấy tiếp 02 phần tử trong Stack Sh ra, tạo lập một cây có 3 thành phần trên, xong tống cả cái cây đó vào trong Sh như một phần tử. Đưa toán tử hiện tại vào stack St
    • Không thoả mãn cũng đưa toán tử hiện tại vào stack St

    Khi duyệt xong chuỗi M, nếu St còn chưa rỗng thì lấy lần lượt cứ 1 phần tử trong St ra và 2 phần tử trong Sh ra, tạo cây, tống cả cây vào trong Sh.
    Cuối cùng đưa cây trong Sh ra và viết.
    Giải thuật:

    1) St = Ø; Sh = Ø;
    2) FOR i = 1 TO /M/
              CASE Mi of
              a) Toán hạng:
                                  1) New(X); X.d = Mi; X^.L = Nil; X^.R = Nil;
                                  2) Push (Sh, X)
              b) Dấu mở ngoặc: Push (Mi, St)
              c) Dấu đóng ngoặc:
                        Pop(St, a)
                        WHILE a ≠ dấu ")" DO
                                  Pop(sh, b); Pop(sh, c);
                                  1) New(X); X.d = a; X^.L = b; X^.R = c;
                                  2) Push (Sh, X)
                                  3) Pop(St, a)
              d) Toán tử:
                        WHILE (Top(St) là toán tử) & (ƯuTiên(Top(St)) ≥ ƯuTiên(Mi)) DO
                                  1) Pop(sh, b); Pop(sh, c); Pop(St, a);
                                  2) New(X); X.d = a; X^.L = c; X^.R = b;
                                  3) Push (Sh, X);
                        Push (Mi, St);
    3) WHILE !Empty(St)
              1) Pop(sh, b); Pop(sh, c); Pop(St, a);
              2) New(X); X.d = a; X^.L = c; X^.R = b;
              3) Push (Sh, X);
    4) Pop(Sh, T)
    Output ( T )
    Sửa theo góp ý của LĐS. Phần Stack chỉ lưu một loại dữ liệu.



    Được sửa bởi Admin ngày Fri Jul 01, 2011 8:59 pm; sửa lần 2.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    Nhiều bài không có điểm (đấy là quan điểm của thầy), bởi vì nhầm lẫn khi gán:
    BT.^L = đT; BT^.R = đS;

    Nhớ rằng, thằng nằm bên trái - Vào trước - Ra sau.

    Admin: OK. Đã sửa.


    ================
    [You must be registered and logged in to see this image.]

    hienha


    Chuyên viên
    Chuyên viên
    Chuyển biểu thức trung tố không đầy đủ dấu ngoặc:
    1. Nếu là toán tử:
    - Chừng nào chưa gặp dấu ngoặc mở (một cách viết khác của "vẫn là toán tử") và độ ưu tiên của toán tử ở đỉnh St ≥ độ ưu tiên của Mi, lấy ra tính
    - Sau khi kết thúc vòng lặp, đẩy Mi vào St

    2. Anh Admin vẫn chưa sửa nhận xét của a Mr Phuong
    1) Pop(sh, b); Pop(sh, c); Pop(St, a);
    2) New(X); X.d = a; X^.L = b; X^.R = c;
    nên là:
    2) New(X); X.d = a; X^.L = c; X^.R = b;

    Admin: OK. Đã sửa.


    ================

    Admin


    Quản trị viên
    Quản trị viên
    Một số thủ tục cần trong các bài thi
    Cấu trúc cây nhị phân trong các ví dụ:
    Type Link
              Link = ^Node;
              Node = Record
                        K: Data;
                        L, R: Link;
              End;

    1.
    Thêm nút lá vào cây nhị phân:

    Proc CHEN_LA (x: Data; Var T: List)
    1) NEW (P); P^.K := x; P^.L = Nil; P^.R = Nil;
    2) IF T = Nil THEN T := P
              ELSE
                        a) Q := T;
                        b) WHILE Q^.L ≠ Nil DO
                                  Q := Q^.L;
                                  Q^.L = P;
    2.
    Thêm một nút vào cây nhị phân:

    Proc CHEN_NUT (x: Data; Var T: List)
    1) IF T = Nil THEN
              a) NEW(P)
              b) P^.K = x;
              c) P^.L = Nil;
              d) P^.R = Nil;
              e) T = P;
    ELSE
              IF T^.K > x THEN CHEN_NUT (x, T^.L)
              ELSE
                        IF T^.K < x THEN CHEN_NUT (x, T^.R)
                                  Output ('Đã tồn tại khoá x trong cây')

    Proc INSERT_NPTK (x: data; VAR T: List);
    1) NEW (Q); Q^.K := X; Q^.L := Nil; Q^.R = Nil;
    2) IF T = Nil THEN T := Q
              ELSE
                        a) P := T;
                        b) WHILE P ≠ Nil DO
                                  IF P^.K > x THEN
                                            IF P^.L ≠ Nil THEN P := P^.L
                                            ELSE
                                                      P^.L = Q;
                                                      P := Nil;
                                  ELSE
                                            IF P^.K < x THEN
                                                      IF P^.R ≠ Nil THEN P := P^.R
                                                      ELSE
                                                                P^.R : = Q;
                                                                P := Nil;
                                            ELSE P := Nil;

    Proc THEMKHOA (x: Data; T: Link)
    Stop := False;
    1) WHILE (!Stop) & (T ≠ Nil) DO
    IF x = T^.K THEN Stop := True;
    ELSE
              IF x > T^.K THEN T := T^.R
                        ELSE T := T^.L;
    2) IF T = Nil THEN
    NEW (W); W^.K = X; W^.R = Nil; W^.L = Nil;
    T := W;


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Viết thủ tục đệ quy thực hiện việc trao đổi con trái với con phải tại mọi nút.
    Proc DOI (Var T: Next)
    1) IF T ≠ Nil THEN
    2) IF (T^.L ≠ Nil) & (T^.R ≠ Nil) THEN
              a) W : = T^.L;
                        T^.L = T^.R;
                        T^.R = W
              b) DOI (T^.L); DOI (T^.R)


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Cây nhị phân trước ta vẫn làm theo 4 phép tính cộng trừ nhân chia. Các hàm mũ, căn logarit hay hàm lượng giác chắc ít đề cập. Hãy google để tham khảo các trình nâng cao khác. Ở đây chỉ giải quyết đến mức độ đi thi có thôi. Tức là bài thi cùng lắm là cho đến hàm mũ và căn (để người đi thi còn làm kịp thời gian), còn các hàm khác đưa vào thì đánh đố thí sinh, có lẽ nếu để nghiên cứu thì được, còn cho vào bài thi sẽ bị pass 100%, vì chẳng có đứa nào điên mà đâm đầu vào làm có thể coi là vô ích.
    Một số công thức cần nhớ để áp dụng:
    ab để chuyển thành cấu trúc cho vào cây thì phải viết là a^b, trong đó dấu ^ là toán tử, còn ab là toán hạng.
    [You must be registered and logged in to see this image.] để chuyển thành cấu trúc cho vào cây thì phải viết là A^(1/n), trong đó dấu ^ là toán tử, còn A1/n là toán hạng.

    Bây giờ giả sử đề thi đánh đố như thế này:
    Xây dựng cây nhị phân biểu diễn biểu thức và chuyển nó thành dạng hậu tố:
    [You must be registered and logged in to see this image.]
    Khách viếng thăm căn cứ vào các bài mẫu để làm. Kết quả phải như sau:
    [You must be registered and logged in to see this image.]

    Dạng hậu tố của biểu thức là:
    a 2 ^ b 2 ^ + 2 ^ a 3 ^ - 2 ^ - a * 3 /



    Được sửa bởi Admin ngày Sun Jul 24, 2011 3:49 pm; sửa lần 2.

    http://khmt.123.st

    9 Bài kiểm tra môn CTDL on Sat Jul 23, 2011 5:03 pm

    huyenminh


    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    1. Cho dãy có n số nguyên {A1,...,An} đôi một khác nhau.
    a. Mô tả thủ tục xây dựng cây nhị phân tìm kiếm có khoá là các phần tử trong dãy.

    b. Vẽ sơ đồ khối mô tả thuật toán.

    c. Áp dụng vẽ cây nhị phân tìm kiếm cho danh sách

    19, 25, 21, 22, 18, 16, 45, 32, 11, 14, 37

    Ban QT:
    [You must be registered and logged in to see this link.]

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Sosblogs