Đạ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]

    1 [Lời giải]Đề thi CTDL-GT năm 2010 on Mon Jul 11, 2011 7:34 pm

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp
    ĐỀ TUYỂN SINH CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NĂM 2010 CỦA HV.KTQS
    Câu 1.
    a. Trình bày giải thuật chuyển một biểu thức trung tố có đầy đủ dấu ngoặc về dạng hậu tố sử dụng Stack.
    b. Áp dụng cho biểu thức M = (((3*(8-4))/2)/(6-((9-3)/2)))
    Câu 2.
    a. Danh sách D lưu trữ các ký tự và tần suất xuất hiện của chúng trong văn bản T có n ký tự:
    List = ^Node;
              Node = Record;
              Ch: Ký tự;
              Prob: Tần suất;
              Left, Right: List
              End;
    K: Array[1..n] of List;
    Viết giải thuật xây dựng cây nhị phân Huffman mã hoá văn bản T.
    b. Văn bản T chỉ gồm các ký tự u, r, d, e, e, g, h, p, k với số lần xuất hiện như sau:
    Ký tự
    ur
    de
    g
    h
    p
    k
    Tần suất xuất hiện
    0,210,08
    0,13
    0,09
    0,15
    0,12
    0,1
    0,12
    Xây dựng bộ mã Huffman tối ưu và vẽ cây nhị phân Huffman tương ứng. Cho biết số bit trung bình để mã hoá một ký tự và hiệu suất mã hoá.
    Câu 3:
    Đồ thị có hướng G(V, E) có trọng số dương có n đỉnh đánh số từ 1 đến n, cho bởi ma trận trọng số D.
    [You must be registered and logged in to see this image.]
    Với i, j = 1..n
    Viết thủ tục tìm đường đi ngắn nhất u đến v. Danh sách các đỉnh trên đường đi được lưu trong danh sách c[1..n] of Integer
    Câu 4:
    a) Trình bày thuật toán sắp xếp nổi bọt.
    b) Áp dụng trình bày với x = {24, 15, 44, 42, 22, 16, 25}
    Câu 5:
    Trình bày thuật toán sắp xếp chèn ở dạng sơ đồ khối


    ================
    Nhà em cách 4 quả đồi
    Cách 3 con suối, cách đôi cánh rừng
    Nhà em xa cách quá chừng
    Em van anh đấy, anh đừng yêu em!...

    FaceBook của em

    2 Giải bài 4 đề thi năm 2010 on Sat Jul 16, 2011 1:25 am

    huyenminh


    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    Câu 4:
    a) Trình bày thuật toán sắp xếp nổi bọt.
    b) Áp dụng trình bày với x = {24, 15, 44, 42, 22, 16, 25}
    Giải
    a.
    void bubble (int a[i], int N)
    {
    int i, j, tg;
    for (i = 0; i

    3 Re: [Lời giải]Đề thi CTDL-GT năm 2010 on Sat Jul 16, 2011 5:22 am

    Admin


    Quản trị viên
    Quản trị viên
    Đề tuyển sinh CTDL> 2010 đã viết:Câu 3:
    Đồ thị có hướng G(V, E) có trọng số dương có n đỉnh đánh số từ 1 đến n, cho bởi ma trận trọng số D.
    [You must be registered and logged in to see this image.]
    Với i, j = 1..n
    Viết thủ tục tìm đường đi ngắn nhất u đến v. Danh sách các đỉnh trên đường đi được lưu trong danh sách c[1..n] of Integer
    Giải:
    A)
    Trường hợp đã biết đồ thị đã liên thông rồi:

    PROC NganNhatU_V_1(u, v: đỉnh)
    I)
              1) FOR i = 1 TO n DO λ (i) = +∞;
              2) λ(u) = 0;
              3) FOR i = 1 TO n DO S(i) = 0;
    II) WHILE S(v) = 0 DO
              1)
                        a) a = v;
                        b) FOR x = 1 TO n DO
                                  IF (S(x) = 0) & (λ (x) < λ (a)) THEN a = x
                        c) S(a) = 1;
              2) FOR x = 1 TO n DO
                        IF (D(a, x) < + ∞) & ((λ (x) > λ (a) + D (a, x)) THEN λ (x) = λ (a) + D (a, x)
    III) k = 1; C (k) = v;
    WHILE C(k) ≠ u DO
              1) x = 1
                        WHILE (!D(x , C(k)) < + ∞) & (λ(x) + D(x, C(k)) = λ (C(k)) DO x = x + 1
              2) C(k + 1) = x;
                        k = k + 1;
    IV) OUTPUT λ (v) ; C(k); C( k - 1);...;C(1);

    B)
    Trường hợp chưa biết được liên thông hay không:

    I)
              1) FOR i = 1 TO n DO λ (i) = +∞;
              2) λ(u) = 0; Stop = False;
              3) FOR i = 1 TO n DO S(i) = 0;
    II) WHILE (S(v) = 0) & (!Stop) DO
              1)
                        a) a = v;
                        b) FOR x = 1 TO n DO
                                  IF (S(x) = 0) & (λ (x) < λ (a)) THEN a = x
                        c) IF λ (a) = + ∞ THEN S(a) = 1; ELSE Stop = True;
              2) IF (!Stop) THEN
                        FOR x = 1 TO n DO
                                  IF (D(a, x) < + ∞) & ((λ (x) > λ (a) + D (a, x)) THEN λ (x) = λ (a) + D (a, x)
    III) IF !Stop THEN
              1) k = 1; C (k) = v;
              2) WHILE C(k) ≠ u DO
                        a) x = 1
                                  WHILE (!D(x , C(k)) < + ∞) & (λ(x) + D(x, C(k)) = λ (C(k)) DO x = x + 1
                        b) C(k + 1) = x; k = k + 1;
    IV) IF !Stop THEN OUTPUT λ (v) ; C(k); C( k - 1);...;C(1); ELSE OUTPUT False;


    ================
    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

    4 Re: [Lời giải]Đề thi CTDL-GT năm 2010 on Sat Jul 16, 2011 3:18 pm

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp
    Đề CTDL và GT 2010 đã viết:Câu 1.
    a. Trình bày giải thuật chuyển một biểu thức trung tố có đầy đủ dấu ngoặc về dạng hậu tố sử dụng Stack.
    b. Áp dụng cho biểu thức M = (((3*(8-4))/2)/(6-((9-3)/2)))
    a)
    Giải thuật:
    PROC Chuyen (M: Chuỗi);
    1)N = "";
    2)S= Ø;
    3)FOR i = 1 TO /M/
              CASE Mi OF
                        a)Toán tử: Push (Mi, S);
                        b)Toán hạng: N = N + Mi
                        c)Dấu đóng ngoặc:
                                  i) Pop (S, x);
                                  ii) N = N + x;
    4) Output (N);
    b)
    Áp dụng cho biểu thức M = (((3*(8-4))/2)/(6-((9-3)/2))):

    TTMiS
    1 Ø
    2(Ø
    3(Ø
    4(Ø
    533
    6*3*
    7(3*
    883*8
    9-3*8-
    1043*4-4
    11)3*4
    12)12
    13/12/
    14212/2
    15)6
    16/6/
    17(6/
    1866/6
    19-6/6-
    20(6/6-
    21(6/6-
    2296/6-9
    23-6/6-9-
    2436/6-9-3
    25)6/6-6
    26/6/6-6/
    2726/6-6/2
    28)6/6-3
    29)6/3
    30)2


    ================
    Nhà em cách 4 quả đồi
    Cách 3 con suối, cách đôi cánh rừng
    Nhà em xa cách quá chừng
    Em van anh đấy, anh đừng yêu em!...

    FaceBook của em

    5 [Lời giải] on Sat Jul 16, 2011 5:02 pm

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp
    Đề tuyển sinh 2010 đã viết:Câu 4:
    a) Trình bày thuật toán sắp xếp nổi bọt.
    b) Áp dụng trình bày với x = {24, 15, 44, 42, 22, 16, 25}
    a)
    Thuật toán sắp xếp nổi bọt:
    PROC SẮP_XẾP_Nổi_bọt (X: Dãy);
    FOR i = 1 TO n - 1 DO
              FOR j = n DOWNTO i + 1 DO
                        IF X(j - 1) < X(j) THEN Đổi_chỗ (X(j), X(j - 1);
    b) Áp dụng trình bày với x = {24, 15, 44, 42, 22, 16, 25}

    i
    j
    1
    2
    3
    4
    5
    6
    7
    ←chỉ số phần tử
    1

    24
    15
    44
    42
    22
    16
    25
    ←dãy ban đầu







    đổi chỗ 16,25
    1
    7
    24
    15
    44
    42
    22
    25
    16








    đổi chỗ 22,25
    1
    6
    24
    15
    44
    42
    25
    22
    16








    không đổi
    1
    5
    24
    15
    44
    42
    25
    22
    16








    không đổi
    1
    4
    24
    15
    44
    42
    25
    22
    16








    đổi chỗ 15, 44
    1
    3
    24
    44
    15
    42
    25
    22
    16








    đổi chỗ 24,44
    1
    2
    44
    24
    15
    42
    25
    22
    16
    hết vòng i = 1
    2
    7





    không đổi
    2
    6
    44
    24
    15
    42
    25
    22
    16








    không đổi
    2
    5
    44
    24
    15
    42
    25
    22
    16








    không đổi
    2
    4
    44
    24
    15
    42
    25
    22
    16








    đổi chỗ 15, 42
    2
    3
    44
    24
    42
    15
    25
    22
    16








    đổi chỗ 24, 42


    44
    42
    24
    15
    25
    22
    16
    hết vòng i = 2
    3
    7





    không đổi

    6
    44
    42
    24
    15
    25
    22
    16








    không đổi

    5
    44
    42
    24
    15
    25
    22
    16








    đổi chỗ 15, 25

    4
    44
    42
    24
    25
    15
    22
    16








    đổi chỗ 24, 25


    44
    42
    25
    24
    15
    22
    16
    hết vòng i = 3
    4
    7





    không đổi

    6
    44
    42
    25
    24
    15
    22
    16








    đổi chỗ 15, 22

    5
    44
    42
    25
    24
    22
    15
    16











    44
    42
    25
    24
    22
    15
    16
    hết vòng i = 4
    5
    7





    đổi chỗ 15, 16

    6
    44
    42
    25
    24
    22
    16
    15
    hết vòng i = 5
    6






    không đổi

    7
    44
    42
    25
    24
    22
    16
    15
    hết vòng i = 6


    ================
    Nhà em cách 4 quả đồi
    Cách 3 con suối, cách đôi cánh rừng
    Nhà em xa cách quá chừng
    Em van anh đấy, anh đừng yêu em!...

    FaceBook của em

    6 Re: [Lời giải]Đề thi CTDL-GT năm 2010 on Sun Jul 17, 2011 10:26 am

    Admin


    Quản trị viên
    Quản trị viên
    Đề tuyển sinh 2010 đã viết:Câu 5: Trình bày thuật toán sắp xếp chèn ở dạng sơ đồ khối
    Để vẽ ra sơ đồ khối, ta viết thuật toán đã:
    PROC SẮP XẾP_Chèn (X: dãy)
    A) FOR i = 2 TO n DO
              1) tg = X(i); j = i + 1;
              2) WHILE (j > 0) & (X(j) > tg DO
                        a) X(j + 1) = X(j);
                        b) j = j - 1;
              3) X(j + 1) = tg
    B) OUTPUT X;
    [You must be registered and logged in to see this image.]
    Các members chú ý, cần vẽ lại toàn bộ các sơ đồ khối của các thuật toán sắp xếp, đề năm nay có khả năng sẽ có một câu vẽ tương tự như vậy.


    ================
    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

    7 Re: [Lời giải]Đề thi CTDL-GT năm 2010 on Sun Jul 17, 2011 1:05 pm

    Admin


    Quản trị viên
    Quản trị viên
    Đề tuyển sinh CTDL và GT 2010 đã viết:Câu 2.
    a. Danh sách D lưu trữ các ký tự và tần suất xuất hiện của chúng trong văn bản T có n ký tự:
    List = ^Node;
              Node = Record;
              Ch: Ký tự;
              Prob: Tần suất;
              Left, Right: List
              End;
    K: Array[1..n] of List;
    Viết giải thuật xây dựng cây nhị phân Huffman mã hoá văn bản T.
    b. Văn bản T chỉ gồm các ký tự u, r, d, e, e, g, h, p, k với số lần xuất hiện như sau:
    Ký tự
    ur
    de
    g
    h
    p
    k
    Tần suất xuất hiện
    0,210,08
    0,13
    0,09
    0,15
    0,12
    0,1
    0,12
    Xây
    dựng bộ mã Huffman tối ưu và vẽ cây nhị phân Huffman tương ứng. Cho
    biết số bit trung bình để mã hoá một ký tự và hiệu suất mã hoá.
    a)
    Giải thuật xây dựng cây nhị phân Huffman:
    List = ^Node;
              Node = Record;
              Ch: Ký tự;
              Prob: Tần suất;
              Left, Right: List
              End;
    K: Array[1..n] of List;
    1) FOR i = 1 TO n DO
              K(i).Ch = C(i);
              K(i).Prob = T(i);
              K(i).Left = Null;
              K(i).Right = Null;
    2)WHILE (m > 1) DO
              a) sắp xếp dãy K giảm dàn theo tần suất (Prob);
              b) New (X)
                        X.Prob = K(m - 1). Prob + K(m).Prob
                        X.Left = K(m - 1)
                        X.Right = K(m)
                        K(m) = X
                        m = m - 1
    3) OUTPUT (K(1))
    b) Các bước xây dựng cây xem [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this image.]
    Theo nguyên tắc tính từ gốc của cây, trái là 0, phải là 1 ta có bảng mã hóa Huffman:
    r = 1110, e = 1111, p = 101, k = 011, h = 100, d = 101, g = 110, u = 00
    Số bít của từng ký tự:
    r, e = 4 bít
    p, k, h, d, g = 3 bit
    u = 2 bit
    Số bit trung bình để mã một ký tự
    = (2 x (tần suất của u) + 3 x ( tổng tần suất của p, k, h, d, g) + 4 x (tổng tần suất của r, e))/(Số ký tự x tổng tần suất)
    Thay số:
    = 2, 96.


    ================
    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

    8 Re: [Lời giải]Đề thi CTDL-GT năm 2010 on Thu May 02, 2013 8:35 pm

    vntuan


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Câu 1.
    a. Trình bày giải thuật chuyển một biểu thức trung tố có đầy đủ dấu ngoặc về dạng hậu tố sử dụng Stack.
    b. Áp dụng cho biểu thức M = (((3*(8-4))/2)/(6-((9-3)/2)))

    Ở trên bạn HaiYen tính câu 1. b) cho ra kết quả hình như không đúng thì phải ; Theo mình thì chuyển biểu thức M về dạng hậu tố thì đúng yêu cầu đề bài hơn.

    9 Re: [Lời giải]Đề thi CTDL-GT năm 2010 on Tue Feb 25, 2014 10:19 pm

    loxe9x


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    HaiYen đã viết:
    Đề CTDL và GT 2010 đã viết:Câu 1.
    a. Trình bày giải thuật chuyển một biểu thức trung tố có đầy đủ dấu ngoặc về dạng hậu tố sử dụng Stack.
    b. Áp dụng cho biểu thức M = (((3*(8-4))/2)/(6-((9-3)/2)))
    a)
    Giải thuật:
    PROC Chuyen (M: Chuỗi);
    1)N = "";
    2)S= Ø;
    3)FOR i = 1 TO /M/
              CASE Mi OF
                        a)Toán tử: Push (Mi, S);
                        b)Toán hạng: N = N + Mi
                        c)Dấu đóng ngoặc:
                                  i) Pop (S, x);
                                  ii) N = N + x;
    4) Output (N);
    b)
    Áp dụng cho biểu thức M = (((3*(8-4))/2)/(6-((9-3)/2))):

    TTMiS
    1 Ø
    2(Ø
    3(Ø
    4(Ø
    533
    6*3*
    7(3*
    883*8
    9-3*8-
    1043*4-4
    11)3*4
    12)12
    13/12/
    14212/2
    15)6
    16/6/
    17(6/
    1866/6
    19-6/6-
    20(6/6-
    21(6/6-
    2296/6-9
    23-6/6-9-
    2436/6-9-3
    25)6/6-6
    26/6/6-6/
    2726/6-6/2
    28)6/6-3
    29)6/3
    30)2
    áp dụng chuyển biểu thức có phải thế này k a?
    384-*2/6-93-2/-/

    10 Re: [Lời giải]Đề thi CTDL-GT năm 2010 on Wed Sep 17, 2014 11:54 pm

    Minto Trầm


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Chuẩn luôn!
    loxe9x đã viết:
    HaiYen đã viết:
    Đề CTDL và GT 2010 đã viết:Câu 1.
    a. Trình bày giải thuật chuyển một biểu thức trung tố có đầy đủ dấu ngoặc về dạng hậu tố sử dụng Stack.
    b. Áp dụng cho biểu thức M = (((3*(8-4))/2)/(6-((9-3)/2)))
    a)
    Giải thuật:
    PROC Chuyen (M: Chuỗi);
    1)N = "";
    2)S= Ø;
    3)FOR i = 1 TO /M/
              CASE Mi OF
                        a)Toán tử: Push (Mi, S);
                        b)Toán hạng: N = N + Mi
                        c)Dấu đóng ngoặc:
                                  i) Pop (S, x);
                                  ii) N = N + x;
    4) Output (N);
    b)
    Áp dụng cho biểu thức M = (((3*(8-4))/2)/(6-((9-3)/2))):

    TTMiS
    1 Ø
    2(Ø
    3(Ø
    4(Ø
    533
    6*3*
    7(3*
    883*8
    9-3*8-
    1043*4-4
    11)3*4
    12)12
    13/12/
    14212/2
    15)6
    16/6/
    17(6/
    1866/6
    19-6/6-
    20(6/6-
    21(6/6-
    2296/6-9
    23-6/6-9-
    2436/6-9-3
    25)6/6-6
    26/6/6-6/
    2726/6-6/2
    28)6/6-3
    29)6/3
    30)2
    áp dụng chuyển biểu thức có phải thế này k a?
    384-*2/6-93-2/-/

    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 | Create a free blog