Lớp 45TH - ĐH Nha Trang

45TH Đại học Nha Trang - TRAO ĐỔI TIN TỨC, HỌC TẬP


    Cấu Trúc Dữ Liệu & GT

    Share
    avatar
    kenken
    Full Member
    Full Member

    Tổng số bài gửi : 333
    Age : 32
    Registration date : 22/05/2007

    Cấu Trúc Dữ Liệu & GT

    Bài gửi  kenken on Wed Dec 26, 2007 5:23 pm

    Đây là đề của k45, anh em rảnh giúp cho ít, thank anh em nhìu:
    tongue tongue tongue
    Câu 1:
    a) Tạo 1 danh sách liên kết lưu trữ các số nguyên nhập từ bàn phím kết thúc khi gõ vào giá trị 0.
    b) Tính tổng các nút có giá trị chia hết cho 3.
    c) Xóa tất cả các phần tử của danh sách mang giá trị X, X gõ từ bàn phím bằng đệ quy rồi in ra.
    Câu 2:
    Cho khai báo cấu trúc dữ liệu để tạo cây nhị phân như sau:
    Type
    Tro=^nut
    nut= record
    gtri: integer
    trai, phai: tro
    End;
    Var goc:tro;
    a) Viet thủ tục bổ sung một giá trị X vào cây nhị phân tìm kiếm có biến con trỏ đến nút là goc.
    b) Viét hàm đếm xem trên cây nhị phân tìm kiếm có bao nhiêu nút mang giá trị X?
    (Function DemcayTK(goc: tro; X:integer): byte)

    bounce bounce bounce
    Luôn tiện, anh em nào còn đề thi các năm trước hoặc tài liệu ôn tập(chuong trinh, ebook, ...) cho mình xin luôn thể. Cảm ơn anh em nhièu.

    lol! tongue


    Được sửa bởi ngày Fri Dec 28, 2007 10:18 am; sửa lần 1.
    avatar
    lehoangthanh
    Admin
    Admin

    Tổng số bài gửi : 595
    Age : 37
    Registration date : 22/05/2007

    Re: Cấu Trúc Dữ Liệu & GT

    Bài gửi  lehoangthanh on Wed Dec 26, 2007 6:27 pm

    Mình còn nhớ (hoặc còn giữ đoạn code) gì thì post "đại" cái đó. Nói chung 1 bài có rất nhiều cách, có cách hay nhưng cũng có cách dở.
    NAM cứ tham khảo xem sao nhé (nhiều khi cách của mình dở đó... Razz )

    Câu 2: (Hi..hi...cái này còn nhớ nhiều nên trả lời trước !!)

    a) Viết thủ tục bổ sung một giá trị X

    write('Nhap vao gia tri X :');readln(x);
    new(p); p^.gtri:= x; p^.trai:=nil; p^.phai:=nil;
    if root=nil then root:=p
    else
    begin
    tam:=root;
    while tam <> nil do
    begin
    q:=tam;{đặt ra thêm biến q để "nhớ" lại, sau này còn xài}
    if tam^.gtri>x then tam:=tam^.trai
    else tam:=tam^.phai;
    end;
    if q^.gtri>x then q^.trai:=p
    else q^.phai:=p;
    end;


    b/ Viết hàm đếm xem trên cây nhị phân tìm kiếm có bao nhiêu nút mang giá trị X

    procedure DemX(p :contro);
    begin
    if (p^.gtri = X) then dem = dem + 1;
    if (p^.trai<>nil) then DemX(p^.trai);{ duyệt cây theo LRN đệ quy }
    if (p^.phai<>nil) then DemX(p^.phai);
    end;


    Câu 2:

    a) Tạo 1 danh sách liên kết lưu trữ các số nguyên nhập từ bàn phím kết thúc khi gõ vào giá trị 0

    dau:=nil;cuoi:=nil;
    repeat
    write('Nhap vao gia tri:');readln(n);
    if (n <> 0) then
    begin
    new(p);
    p^.gt:=n; p^.next := nil;
    if dau=nil then {trường hợp DS chưa có gì cả}
    begin
    dau:=p;
    cuoi:=dau;
    end
    else {DS đã có vài phần tử rồi}
    begin
    cuoi^.noi:=p;
    cuoi:=p;
    end;
    end
    until (n = 0);

    b) Tính tổng các nút có giá trị chia hết cho 3

    p := dau;
    while (p <> nil) do
    begin
    if (p^.gtri mod 3 = 0) then tong = tong + p^.gtri;
    p := p^.next;
    end;


    c) Xóa tất cả các phần tử của danh sách mang giá trị X, X gõ từ bàn phím bằng đệ quy rồi in ra

    write('Nhap vao gia tri X:');readln(x);
    p := dau; q := dau; {p là con trỏ "dò" phía trước, q "lưu lại vết" phía sau p}
    while (p <> nil) do
    begin
    if (p^.gtri = X) then
    q^.next := p^.next; {móc nối lại DS, bỏ qua phần tử có giá trị bằng X}
    else q := p;
    p:= p^.next;
    end;
    avatar
    bluesky1612
    Full Member
    Full Member

    Tổng số bài gửi : 437
    Age : 34
    Registration date : 22/05/2007

    Re: Cấu Trúc Dữ Liệu & GT

    Bài gửi  bluesky1612 on Wed Dec 26, 2007 9:29 pm

    Code:
    Type
    Tro=^p
    p= record
    gtri: integer
    noi: tro
    End;

    Var
    {-------------------------------}
    procedure chendau(x:integer);
    Var x:integer; p:tro;
    begin
      If dau = nil then begin
      new(p); p^.gtri:= x; p^.noi:=nil; dau:=p;
      end else begin
              new(p); p^.gtri:= x; p^.noi:=dau; dau:=p;
                    end;
    end;
    {-------------------------------}
    procedure caua;
    begin
    writeln("Nhap gia tri");readln(a);
    While a<>0 do chendau(a);
    readln;
    end;
    {-------------------------------}
    procedure caub;
    begin
    k:=0;
    q:=dau;
    q^.noi:=tam;
    While tam <>nil do
      begin
      If (q^.gtri mod 3 = 0) then
          begin
            k:=k+q^.gtri;q:=tam;q^.noi:=tam;
          end
      else
          begin
            q:=tam;q^.noi:=tam;
          end;
      end;
    writeln(k);
    end;
    Còn câu C thì tự làm và tự khai báo nhé cu, lâu rồi cũng ko rờ đến cái này, cũng ko còn giữ kỹ mấy đoạn code đến giờ giống bác Thanh, mới viết tức thì, chưa kiểm tra, các bác kiểm tra giúp nhé.


    _________________
    Câu lạc bộ Aikido Tenshinkai Nha Trang
    http://aikidotenshinkai.com/v4/forumdisplay.php?16-Nha-Trang
    avatar
    kenken
    Full Member
    Full Member

    Tổng số bài gửi : 333
    Age : 32
    Registration date : 22/05/2007

    Re: Cấu Trúc Dữ Liệu & GT

    Bài gửi  kenken on Wed Dec 26, 2007 10:42 pm

    thank anh em nhiu.
    Merry Christmas and a Happy New Year! santa santa santa
    avatar
    lehoangthanh
    Admin
    Admin

    Tổng số bài gửi : 595
    Age : 37
    Registration date : 22/05/2007

    Re: Cấu Trúc Dữ Liệu & GT

    Bài gửi  lehoangthanh on Thu Dec 27, 2007 9:04 am

    Công nhận sau khi TN rồi, bây giờ đọc lại code của môn CTDL & GT thấy vui ghê...Làm việc với mấy "con trỏ" cũng thú vị đấy chứ nhỉ. Very Happy

    Cách tổ chức của NGUYÊN cũng tốt (chỉ dùng 1 con trỏ "đầu" để quản lý toàn bộ DS), cách này thông dụng hơn cách của mình (dùng 2 "em" nằm ở 2 đầu để quản lý toàn bộ DS).
    avatar
    kenken
    Full Member
    Full Member

    Tổng số bài gửi : 333
    Age : 32
    Registration date : 22/05/2007

    Re: Cấu Trúc Dữ Liệu & GT

    Bài gửi  kenken on Fri Dec 28, 2007 10:43 am

    Cho hỏi tý, bổ sung thêm khai báo này có đúng ko vậy:
    bluesky1612 đã viết:
    Type
    Tro=^p
    p= record
    gtri: integer
    noi: tro
    End;

    Var
    dau:tro
    {-------------------------------
    procedure chendau(x:integer);
    Var x:integer; p:tro;{thay p bằng dau, đã khai báo ở trên}
    begin
    If dau = nil then begin
    new(p); p^.gtri:= x; p^.noi:=nil; dau:=p;
    end else begin
    new(p); p^.gtri:= x; p^.noi:=dau; dau:=p;
    end;
    end;
    {-------------------------------}
    procedure caua;
    begin
    writeln("Nhap gia tri");readln(a);
    While a<>0 do chendau(a);
    readln;
    end;
    {-------------------------------}
    procedure caub;
    begin
    k:=0;
    q:=dau;
    q^.noi:=tam;
    While tam <>nil do
    begin
    If (q^.gtri mod 3 = 0) then
    begin
    k:=k+q^.gtri;q:=tam;q^.noi:=tam;
    end
    else
    begin
    q:=tam;q^.noi:=tam;
    end;
    end;
    writeln(k);
    end;
    Còn câu C thì tự làm và tự khai báo nhé cu, lâu rồi cũng ko rờ đến cái này, cũng ko còn giữ kỹ mấy đoạn code đến giờ giống bác Thanh, mới viết tức thì, chưa kiểm tra, các bác kiểm tra giúp nhé.
    avatar
    kenken
    Full Member
    Full Member

    Tổng số bài gửi : 333
    Age : 32
    Registration date : 22/05/2007

    Re: Cấu Trúc Dữ Liệu & GT

    Bài gửi  kenken on Fri Dec 28, 2007 11:01 am

    Anh THANH cho em hỏi:
    b) Tính tổng các nút có giá trị chia hết cho 3

    p := dau;
    while (p <> nil) do
    begin
    if (p^.gtri mod 3 = 0) then tong = tong + p^.gtri;
    p := p^.next;
    end;
    {khi không chia hết cho 3 thì sao, theo em nên bổ sung thêm:
    else}

    Code:
    Function Tong(dau :tro):longint;
    Begin
     If dau = nil then tong :=0
      else
     If dau^. gtri mod 3 =0 then
      Tong := dau ^.gtri + Tong (dau ^.next)
      Else
      Tong:=tong(dau ^.next)
    End.
    Có gì ngố, anh em chỉ bảo thêm. thanks
    avatar
    bluesky1612
    Full Member
    Full Member

    Tổng số bài gửi : 437
    Age : 34
    Registration date : 22/05/2007

    Re: Cấu Trúc Dữ Liệu & GT

    Bài gửi  bluesky1612 on Fri Dec 28, 2007 2:04 pm

    Ko cần thiết đâu cu Nam, thật ra khi kt điều kiện "IF" đúng thì nó mới làm phần "THEN", còn ko thì nó làm câu lệnh sau đó, nên chỉ làm tới đó là được. Cái mày thêm vào là cách làm khác, làm bằng đệ qui rồi, nếu ghép với đoạn kia thì...loạn, phải khai báo gt biến lại. Còn nữa, mày thiếu gt khởi tạo cho tổng, phải là:
    Code:

    p := dau;
    tong:=0; {mày thiếu cái này nè}
    while (p <> nil) do
    begin
    if (p^.gtri mod 3 = 0) then tong := tong + p^.gtri;{chỗ này phải là phép gán}
    p := p^.next;
    end;


    _________________
    Câu lạc bộ Aikido Tenshinkai Nha Trang
    http://aikidotenshinkai.com/v4/forumdisplay.php?16-Nha-Trang
    avatar
    lehoangthanh
    Admin
    Admin

    Tổng số bài gửi : 595
    Age : 37
    Registration date : 22/05/2007

    Re: Cấu Trúc Dữ Liệu & GT

    Bài gửi  lehoangthanh on Fri Dec 28, 2007 3:47 pm

    1/ Quả thật câu hỏi của NAM ở trên ("bổ sung biến 'dau'....") là sao mình không hiểu lắm Very Happy, mình thấy đoạn code đó ổn rồi mà.

    2/ Về câu "chia hết cho 3":

    Cách của NAM cũng tốt thôi, nhưng theo mình NAM nên làm theo cách mà mình đã gợi ý bởi:
    + Ngắn hơn ---> ít phải gõ code hơn Razz
    + Không dùng đệ quy ---> nhanh hơn, rõ ràng dễ hiểu hơn.

    Không cần "ELSE" gì cả, bởi nếu phần tử đó không chia hết cho 3 thì chỉ đơn giản thực hiện việc "nhảy" đến phần tử kế tiếp thôi (không thực hiện việc cộng dồn).
    Thật ra việc khởi tạo ban đầu biến "tổng" như NGUYÊN thì cũng không quan trọng lắm đâu (TP7.0 tự động tạo biến null, hoặc = 0 lúc ban đầu)
    avatar
    kenken
    Full Member
    Full Member

    Tổng số bài gửi : 333
    Age : 32
    Registration date : 22/05/2007

    Re: Cấu Trúc Dữ Liệu & GT

    Bài gửi  kenken on Sat Dec 29, 2007 5:05 pm

    Bài tập về cây nhị phân:

    1. Đếm xem có bao nhiêu nút có cây con phải mà ko có cây con trái.?

    2.
    a) Chép lại cây nhị phân mới mỗi nút cây có 5 thành phần (ko hiểu 5TP đó là gì).
    b) Từ cây nhị phân mới điều chỉnh :
    - Các mỗi nối rỗng
    - Ghi nhận lại Ltype, Rtype.

    3. Cho cây nhị phân, có địa chỉ nút gốc là goc
    Viết thủ tục sao chép cây nhị phân
    Procedure saochep (goc:tro, Var goc: tro)
    {sao chep cây có nút gốc là :goc
    Sang cây có nút gốc là: goc}
    avatar
    lehoangthanh
    Admin
    Admin

    Tổng số bài gửi : 595
    Age : 37
    Registration date : 22/05/2007

    Re: Cấu Trúc Dữ Liệu & GT

    Bài gửi  lehoangthanh on Sat Dec 29, 2007 6:25 pm

    1. Đếm số nút có cây con phải mà ko có cây con trái

    dem := 0;
    procedure nut_conphai(p :contro);
    begin
    if (p^.trai<>nil) then nut_1caycon(p^.trai); {duyệt theo LRN}
    if (p^.phai<>nil) then nut_1caycon(p^.phai);
    if (p^.trai<>nil)and(p^.phai=nil) then dem := dem + 1;
    end;

    2. 5 thành phần gì nhỉ Question Question Question NAM có thể giải thích cụ thể hơn cho mọi người rõ được không

    3. Cũng hơi khó hiểu nhỉ Razz

    Procedure saochep (goc:tro, Var goc: tro)
    cái này không biết trình biên dịch có báo lỗi không ta ?? (bị trùng biến "goc")

    {sao chep cây có nút gốc là :"goc" Sang cây có nút gốc là: "goc"}
    :affraid:cái này thì mình thật sự không hiểu
    avatar
    kenken
    Full Member
    Full Member

    Tổng số bài gửi : 333
    Age : 32
    Registration date : 22/05/2007

    Re: Cấu Trúc Dữ Liệu & GT

    Bài gửi  kenken on Sat Dec 29, 2007 11:19 pm

    Qủa thật là câu 2, 3 em cũng đang thắc mắc ko biết mình có ghi nhầm ko.Theo em:
    Câu 2: Chép lại cây nhị phân có 3 thành phần (Trái, Phải , gtri)
    Cau 3: Chỉ là phát triển của câu 2 mà thôi.

    Anh xem lại giúp em. Thanks

    Sponsored content

    Re: Cấu Trúc Dữ Liệu & GT

    Bài gửi  Sponsored content


      Hôm nay: Wed Oct 18, 2017 12:04 am