Đạ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]Đề TEST, CTDL & GT năm 2011 on Tue Jul 12, 2011 6:23 pm

    Admin


    Quản trị viên
    Quản trị viên
    Đề Test CTDL & GT năm 2011

    Đây là một đề có 8 câu, mà các ý của nó liên quan đến đề tuyển sinh cao học năm 2011. Đề nghị các members tập làm thành thạo trước khi thi nha.

    Câu 1: Danh sách X được tổ chức bởi cấu trúc:
    List = ^Element;
    Element = Record
              d: Data;
              Next : List;
              End;
    Cho danh sách P và Q. Hãy viết thủ tục để:
    a. Xóa nút đứng cuối cùng trong danh sách P.
    b. Nối danh sách Q vào sau danh sách P.

    Câu 2
    :
    Viết thủ tục sử dụng ngăn xếp S để chuyển biểu thức M dạng trung tố không có dấu ngoặc về dạng hậu tố.Dùng bảng minh họa sự thay đổi của ngăn xếp S khi áp dụng thuật toán trong câu trên để chuyển biểu thức sau về dạng hậu tố.
    M = 5 - 6 / 3 * 2 - 5 + 3 * 2 / 3 - 3 * 5 + 4

    Câu 3
    :
    Văn bản T chứa các ký tự a, b, c, d , e , f , g , h, m , n với tần suất xuất hiện: 0.18, 0.06, 0.12, 0.14, 0.08, 0.05, 0.07, 0.12, 0.08, 0,10. Xây dựng bộ mã Huffman cho T. Vẽ cây nhị phân tương ứng. Tính hiệu suất.

    Câu 4
    :
    Văn bản T chứa n ký tự K(1), K(2)...K(n) có tần suất xuất hiện T(1), T(2)...T(n). Viết thủ tục tạo cây nhị phân Huffman để mã hóa văn bản.

    Câu 5
    :
    Viết thủ tục HN2P(X: Mảng; d,m, c: Chỉ số, VAR Y: Mảng) có nhiệm vụ tạo mảng Y(d..c) không giảm từ 2 phần của mảng X, biết rằng hai phần của mảng X đã được sắp xếp:
    X(d) ≤ X(d + m) ≤ ... ≤ X(m) và X(m + 1) ≥ X(m + 2) ≥ ... ≥ X(c) với d ≤ m ≤ c.

    Câu 6
    :
    Ma trận A =(A (i, j) ; 1 ≤ i ≤ m, 1 ≤ j ≤ n) được sắp xếp không giảm theo từng hàng và từng cột. Viết giải thuật tạo mảng X (i.. mxn) không giảm từ các phần tử của A. Đánh giá số phép so sánh phải thực hiện.

    Câu 7
    :
    Đồ thị G có n đỉnh, U1, U2... Un được cho bởi danh sách cạnh
    Cạnh = Record
              d, c : Tên đỉnh;
              t: trọng số;
              End;
    D (1..m) of Cạnh
    Viết chi tiết thuật toán KRUSKAL tìm cây khung bé nhất của G
    Áp dụng thuật toán để tìm cây khung bé nhất của đồ thị G vô hướng sau:



    1

    2

    3



    5

    1

    3



    9

    5

    1



    7

    12

    2



    3

    4

    4

    2

    3

    3



    6

    2

    2



    10

    6

    3



    12

    8

    2



    5

    10

    4

    1

    6

    2



    7

    3

    5



    6

    11

    3



    9

    10

    4



    7

    8

    2

    2

    7

    1



    8

    4

    2



    6

    7

    4



    10

    11

    4



    4

    1

    7

    3

    8

    4



    5

    6

    4



    11

    7

    2



    11

    12

    5



    12

    9

    2


    Câu 8
    :
    Đồ thị G có n đỉnh được đánh số từ 1 đến n lưu trong danh sách kề
    V = ARRAY (1..n) of List
    List = ^Vertex;
    Vertex = Record
              t: Tên đỉnh;
              Next: List;
              End;
    Cho đỉnh u. Hãy tính số đỉnh thuộc vùng liên thông chứa u.


    ================
    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
    Đề Test CTDL & GT năm 2011 đã viết:Câu 1: Danh sách X được tổ chức bởi cấu trúc:
    List = ^Element;
              Element = Record
                        d: Data;
                        Next : List;
              End;
    Cho danh sách P và Q. Hãy viết thủ tục để:
    a. Xóa nút đứng cuối cùng trong danh sách P.
    b. Nối danh sách Q vào sau danh sách P.
    a)
    Xóa nút đứng cuối cùng trong danh sách P:
    PROC Xóa (P: List);
    1) IF P = Ø THEN Exit
    2)WHILE P^.Next ^.Next ≠ Nil DO P = P^.Next
    3) P^.Next = Nil
    b)
    Nối danh sách Q vào sau danh sách P:
    PROC Nối (P: List, Q: List);
    1) WHILE (P ≠ Ø) & (P^.Next ≠ Nil) DO P = P^.Next
    2) P^.Next = Q
    Đề Test CTDL & GT năm 2011 đã viết:Câu 2: Viết thủ tục sử dụng ngăn xếp S để chuyển biểu thức M dạng trung tố không có dấu ngoặc về dạng hậu tố. Dùng bảng minh họa sự thay đổi của ngăn xếp S khi áp dụng thuật toán trong câu trên để chuyển biểu thức sau về dạng hậu tố.
    M = 5 - 6 / 3 * 2 - 5 + 3 * 2 / 3 - 3 * 5 + 4
    a)
    Viết code:
    PROC Chuyen
    1) S := Ø; N = Ø;
    2)
    - Xây dựng hàm con xét độ ưu tiên
    UT(x)


    CASE x
    of

    *,/:
    UT=2

    -, + :
    UT=1

    END

    3) For i :=1 to /M/



    CASE Mi of


    a)Toán hạng:



    N = N + Mi;

    b) Toán tử:




    WHILE (S ≠ Ø) & (UT(Top(S)) ≥ UT(Mi)) DO



    Pop(S, x);



    N = N + x;



    Push(Mi, S)

    End Case


    4) Repeat




    Pop(S,x);
    N := N + x

    Until Empty(S)



    5) Output (N)
    Đề Test CTDL & GT năm 2011 đã viết:
    Câu 5
    :
    Viết thủ tục HN2P(X: Mảng; d,m, c: Chỉ số, VAR Y: Mảng) có nhiệm vụ tạo mảng Y(d..c) không giảm từ 2 phần của mảng X, biết rằng hai phần của mảng X đã được sắp xếp:
    X(d) ≤ X(d + m) ≤ ... ≤ X(m) và X(m + 1) ≥ X(m + 2) ≥ ... ≥ X(c) với d ≤ m ≤ c.
    Viết thuật toán:
    HN2P(X: Mảng; d, m, c: Chỉ số, VAR Y: Mảng)
    1) i := d; j := c ; k := d;
    2) {so sánh các phần tử của hai mảng con với nhau chọn phần tử nhỏ hơn}
    WHILE (i ≤ m) & (j ≥ m) DO
              IF X[i] < X[j] THEN Y[k]: = X[i]; i ++; k++;
                        ELSE Y[k]: = X[j]; j --; k++;
    {Phần nào xong rồi thì hạ phần còn lại xuống:}
    3) IF (i > m) & (j > m) THEN
              FOR i := j DOWNTO m DO Y[k] : = X[i]; k++;
    4) IF (i < m) & (j < m) THEN
              FOR j := i TO m DO Y[k] : = A[j]; k++
    5) End.



    Được sửa bởi Admin ngày Sat Jul 16, 2011 6:13 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

    3 [Lời giải] on Wed Jul 13, 2011 6:02 pm

    toxido202


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Đề TEST 2011 CTDL và GT đã viết:Câu 4: Văn bản T chứa n ký tự K(1), K(2)...K(n) có tần suất xuất hiện T(1), T(2)...T(n). Viết thủ tục tạo cây nhị phân Huffman để mã hóa văn bản.
    A) {Khai báo cấu trúc cây nhị phân}
    List = ^bg;
              bg = Record
              k : tên ký tự;
              T : tần suất xuất hiện;
              L, R : List;
              End;
    X[1...n] of List;
    B) {Các bước thực hiện}
    1) FOR i := 1 TO n DO
              New(p);
              p^.k := ki;
              p^.T := Ti;
              p^.L:= Nil;
              p^.R := Nil;
    X(i):= p;
    2) FOR m := n DOWNTO 2 DO
              a) Sắp xếp X(1).T > X(2).T >...> X(m).T {sắp xếp tần suất giảm dần}
              b) New(q);
                        q^.T := X(m)^.T + X(m-1)^.T;
                        q^.R:=X(m);
                        New(G);
                        G:=X(m-1);
                        q^.L:=G;
                        X(m-1):=q;
    3) OUTPUT X(1);



    Được sửa bởi toxido202 ngày Mon Jul 25, 2011 9:56 am; sửa lần 2. (Reason for editing : Viết lại đúng cấu trúc, sửa chính tả cho dễ xem)

    Tongmanhcuong


    Thành viên cao cấp
    Thành viên cao cấp
    Theo tôi nghĩ câu 1 rất dễ nhưng cũng rất dễ điểm. Tôi cũng bị mất điểm câu này.


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

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp
    Không thấy các anh chị chuyên gia ngọ nguậy gì, em mạn phép xin trình bày cách làm Câu 6: Ma trận A =(A (i, j) ; 1 ≤ i ≤ m, 1 ≤ j ≤ n) được sắp xếp không giảm theo từng hàng và từng cột. Viết giải thuật tạo mảng X (i.. mxn) không giảm từ các phần tử của A. Đánh giá số phép so sánh phải thực hiện.
    Chọn cách tối ưu nhất có thể có. Em tham khảo 2 cuốn sách sau:
    [1] M. Schimmler. Fast Sorting on the Instruction Systolic Array. Bericht Nr. 8709, Institut fr Informatik, Christian-Albrechts-Universitt Kiel (1987).
    [2] C.D. Thompson, H.T. Kung. Sorting on a Mesh-Connected Parallel Computer. Communications of the ACM 20, 4, 263-271 (1977).

    Có nhiều phương pháp sắp xếp. Song, tùy thuộc vào sự tổ chức của dữ liệu, người ta chọn phương pháp sắp xếp sao cho phù hợp. Dưới đây, em xin chia sẻ với anh chị phương pháp sắp xếp hòa nhập bốn đường (4-Way Mergesort) trên mảng 2 chiều. Còn việc áp dụng cụ thể vào bài toán này, xin nhường anh chị, vì nếu em làm luôn, sợ múa rìu qua mắt.... rất nhiều thợ.
    1. Thiết kế giải thuật
    Định nghĩa:
    Một mảng 2 chiều mxn gọi là mảng sắp xếp thô (roughly sorted) nếu ta chỉ cần sắp xếp các dòng của nó thì toàn bộ mảng sẽ được sắp xếp hoàn toàn.
    Vậy, trong mảng sắp xếp thô, mỗi phần tử của mảng đã nằm đúng trên dòng của nó.
    Ví dụ 1:
    [You must be registered and logged in to see this image.]
    ý tưởng của sắp xếp hòa nhập bốn đường là hòa nhập bốn mảng sắp xếp thô [You must be registered and logged in to see this image.] lại với nhau để được một mảng sắp xếp thô m x n. (ở đây, ta mặc định là sắp tăng dần)
    Procedure Four_Way_Merge (m, n)
    Dữ liệu vào:
    Mảng m x n thỏa mãn bốn mảng con [You must be registered and logged in to see this image.] của nó là sắp xếp thô.
    Dữ liệu ra:
    Mảng sắp xếp thô m x n.
    Các bước thực hiện:
    B1. Sắp xếp các dòng của bốn mảng con theo cách:
    - Sắp xếp giảm dần với mảng con có chỉ số nhỏ hơn,
    - Sắp xếp tăng dần với mảng con có chỉ số lớn hơn.
    B2. Sắp xếp tăng dần các cột của mảng m x n.
    B3. Sắp xếp các dòng của mảng m x n theo cách:
    - Dòng lẻ thì sắp xếp tăng dần,
    - Dòng chẵn thì sắp xếp giảm dần.
    B4. Sắp xếp tăng dần các cột của mảng m x n.
    Ví dụ 2:
    Với m =5 và n =5, mỗi mảng con sắp xếp thô có kích thước là 2 x 2. Các bước thực hiện giải thuật như sau:

    [You must be registered and logged in to see this image.]
    a) Mảng ban đầu có 4 mảng con sắp xếp thô.
    b) Mảng có được sau bước 1.
    c) Mảng có được sau bước 2.
    d) Mảng có được sau bước 3.
    e) Mảng có được sau bước 4. Đây là mảng sắp xếp thô.
    f) Mảng đã được sắp xếp hoàn toàn sau khi sắp xếp các dòng.
    Minh họa trên cũng cho chúng ta thấy được sự đúng đắn của giải thuật (phần chứng minh tính đúng đắn xin dành cho các anh chị).
    Để có được các mảng con sắp xếp thô từ một mảng ban đầu chưa sắp xếp, ta nên dùng chiến lược chia để trị với kĩ thuật đệ quy.
    Thuật toán sơ bộ:
    Procedure Rough_Sort (m, n)
    Dữ liệu vào:
    Mảng m x n chưa sắp xếp
    Dữ liệu ra:
    Mảng m x n sắp xếp thô
    Các bước thực hiện:
    if m > 1 then
    begin
    B1. Gọi Rough_Sort (m/2, n/2) cho bốn mảng con;
    B2. Gọi Four_Way_Merge (m, n);
    end;
    Vậy, một mảng m x n được sắp xếp hoàn toàn bằng cách làm cho nó trở thành mảng sắp xếp thô và rồi sắp xếp các dòng của nó.
    Procedure Four_Way_ Mergesort (n):

    Dữ liệu vào:
    Mảng m x n chưa sắp xếp
    Dữ liệu ra:
    Mảng m x n đã được sắp xếp
    Các bước thực hiện:
    B1. Gọi Rough_Sort (m, n)
    B2. Sắp xếp các dòng của mảng sắp xếp thô m x n.
    2. Phân tích giải thuật
    Ta thử phân tích độ phức tạp của giải thuật khi sắp xếp một mảng n x n.
    Ta có thể sắp xếp mỗi một dòng n phần tử theo phương pháp sắp xếp nổi bọt. Vậy, như anh chị đã biết, trong trường hợp xấu nhất ta phải mất thời gian là n(n - 1)/2. Gọi việc sắp xếp một dòng hay một cột là một bước sắp xếp thì việc sắp xếp n dòng hoặc n cột của mảng n x n phải mất n bước. Trong thủ tục Four_Way_Merge, số lượng các bước là:
    B1: n/2 bước
    B2: n bước
    B3: n bước
    B4: n/2 bước
    Tổng: 3n bước.
    Chú ý rằng, B4 chỉ cần n/2 bước bởi vì mỗi cột đã được chia thành 2 phần (trên và dưới) bởi 4 mảng con ban đầu, nên ta chỉ cần sắp xếp trong nội bộ 2 phần của mỗi cột đó.
    Việc gọi đệ quy Four_Way_Merge trong Rough_Sort mất 3n+3n/2+3n/4+…+3 ≤ 6n bước. Do vậy, cộng thêm việc sắp xếp các dòng của mảng n x n trong Four_Way_Mergesort ta có tổng thời gian của giải thuật là: T(n) ≤ 7n bước. Mỗi bước mất thời gian ít nhất là n(n - 1)/2 nên T(n) ≤ 7n.2(n - 1)/2. Với kích thước của mảng hai chiều là n x n thì độ phức tạp tính toán của giải thuật là: O(n3/2).
    3. Kết luận
    Đến đây, anh chị đã biết được giải thuật sắp xếp hòa nhập bốn đường là gì. Độ phức tạp của nó là chấp nhận được, cụ thể là O(n3/2). anh chị cũng sẽ biết cách cài đặt giải thuật này một khi anh chị muốn sắp xếp một mảng 2 chiều. Xin góp ý của các anh chị về giải thuật này.


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

    trungttnd


    Thành viên cao cấp
    Thành viên cao cấp
    Xóa nút đứng cuối cùng trong danh sách P:
    PROC Xóa (P: List);
    1) WHILE P^.Next ^.Next ≠ Nil DO
    P = P^.Next
    2) P^.Next = Nil

    Cái P^.next^.next dùng được hả anh. Có lẽ kiến thức em hạn hẹp không biết có cái này

    Ban QT: Không hiểu câu hỏi "Cái P^.next^.next dùng được hả anh?"

    abc


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Bạn có thể hiểu Cái P^.next^.next = nil được viết thành
    p^.next = q
    q^.next = nil


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

    http://www.cafetuoitre.com

    Admin


    Quản trị viên
    Quản trị viên
    Đề TEST 2011 CTDL và GT đã viết:Câu 8: Đồ thị G có n đỉnh được đánh số từ 1 đến n lưu trong danh sách kề
    V = ARRAY (1..n) of List
    List = ^Vertex;
              Vertex = Record
              t: Tên đỉnh;
              Next: List;
    End;
    Cho đỉnh u. Hãy tính số đỉnh thuộc vùng liên thông chứa u.
    Trước khi giải ta hãy xem xét bài tập này một chút.
    Ở đây là mảng V có n phần tử. Mỗi phần tử là một đỉnh. Cấu trúc dữ liệu của nó có gì đặc biệt? Đó là mỗi đỉnh lại trỏ vào một đỉnh kề với nó. Nghĩa là nếu bắt đầu là đỉnh a trỏ vào đỉnh b → đỉnh c.... → đỉnh z, khi đỉnh z không trỏ được vào đỉnh nào, nó sẽ phải trỏ vào nil. Đấy là một phần của vùng liên thông. Một phần của vùng liên thông khác cũng bắt đầu từ a phảy lặp lại đúng như vậy.
    Cái khó ở đây là chúng ta không thể biết được đỉnh nào là đỉnh bắt đầu. Nghĩa là nếu sắp xếp các đỉnh thành một dãy mà ta duyệt từ một đỉnh a nào đó, thì với cấu trúc dữ liệu dạng này, ta chỉ duyệt được từ đỉnh a đó đến cuối dãy, nếu có đếm thì cũng đếm từ đỉnh a duyệt đến cuối dãy thôi. Vậy ta làm thế nào để biết được đỉnh nào là đầu tiên nhỉ?
    Vậy bài toán ở đây đưa ra là cách đánh dấu duyệtcách đếm thôi.

    Giả sử duyệt từ đỉnh 1 đi lòng vòng đến hết vùng liên thông của 1 ta đánh một dấu. Đây là vòng duyệt 1.
    Sang đỉnh 2, ta cũng phải làm vòng duyệt 2. Nếu như đỉnh 2 đã được đánh dấu của vòng duyệt 1 rồi thì may quá, nhảy tiếp sang đỉnh kế, còn nó chưa thấy đánh dấu thì cũng phải đánh dấu lại vì có 2 trường hợp:
    - Trường hợp 1, nếu nó cũng thuộc vùng liên thông của 1 (nhưng trong dãy nó đứng trước đỉnh 1 thì nó cũng không được đánh dấu ở vòng 1, do vòng 1 chỉ duyệt các đỉnh từ vòng 1 về sau mà). Khi duyệt dần gặp đánh dấu của đỉnh 1 thì ta cũng đếm từ đỉnh 2 này + với đếm của vòng 1. Biết đếm sẽ có khi vô ích, khi mà đến cuối cùng vùng này không chứa u. Nhưng dữ liệu kiểu này đều là nhỡ may mà.
    - Nhỡ may đỉnh 2 không cùng vùng liên thông của 1 thì sao. Đương nhiên việc đếm này là độc lập.
    Vậy ta phải sử dụng 2 mảng độ dài n, hoặc 1 mảng 2 x n trong đó 1 mảng để đánh dấu đã duyệt đã đếm, còn một mảng thứ 2 để đếm các đỉnh của vùng liên thông của đỉnh đánh dấu đó. uh, mệt thật đấy.

    Bây giờ viết lệnh nhé!
    Thực ra viết thẳng ra chỉ có ít dòng thôi. Nhưng tôi muốn vừa viết vừa phân tích để những bạn nghỉ học hôm thầy giảng có thể hiểu được, nên các bạn vui lòng xem dài một tý nhé! Ở đây tôi làm 2 mảng song song cho dễ lý giải, bạn cũng có thể dùng một mảng dung lượng gấp đôi cũng được.
    PROC DemVungLienThongChua_U (V: list)
    I) {Đánh dấu tất cả các đỉnh là số thứ tự đỉnh, mỗi đỉnh là một nhóm, đồng thời đưa số đếm của tất cả các nhóm về 1}
    FOR i: = 1 TO n DO
              1) Nhom(i) = i;
              2) Dem(i) = 1;
    II) {Duyệt lần lượt các đỉnh cho đến hết, ở đây nếu đã cùng vùng liên thông thì đánh lại nhóm chính là chỉ số của đỉnh bé hơn nha}
    A) NEW(P);
    B) FOR i = 1 TO n DO
    C) Stop = False
    D)WHILE !Stop DO
              1) P = V(i) {Dùng biến con trỏ P để duyệt danh sách, duyệt từ đỉnh i}
              2) j = i {Dùng biến j để xử lý nội bộ vòng lặp, tránh ảnh hưởng đến vòng lặp chung này}
              3)WHILE (P^.Next ≠ Nil) &!Stop DO {Lặp các đỉnh là danh sách kề chưa được xét}
                        IF (Nhom(P^.Next.t) = t THEN {Các đỉnh này chưa được xét}
                                  i) Dem(j) = Dem(j) + 1 {Tăng biến đếm cho nhóm vì có đỉnh kế}
                                  ii) P = P^.Next {Chuyển con trỏ sang đỉnh kế}
                                  iii) j = P^.t {Lấy đỉnh kề mới}
                                  iv) Nhom (j) = i {Đặt lại các phần tử thuộc vùng liên thông theo tên nhóm là đỉnh thứ i}
                        ELSE {Các đỉnh này đã xét ở vòng FOR i trước rồi, do đã đánh dấu theo đỉnh nhỏ}
                                  i) Dem (i) = Dem (i) + Dem (Nhom(P^.Next.t)) {Cộng biến đếm}
                                  ii) FOR x = 1 TO n DO
                                            IF Nhom(x) = Nhom(P^.Next.t)) THEN Dem (x) = Dem(i);Nhom(x) = Nhom(i);
                                            {Đặt lại biến đếm và nhóm cho cả nhóm trong mảng theo dõi}
                                  iii)Stop = True
    III) OUTPUT (Dem (u)) {Xuất ra kết quả đếm đối với đỉnh u, là vùng liên thông chứa u}


    ================
    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
    Đề TEST 2011 CTDL và GT đã viết:Câu 7: Đồ thị G có n đỉnh, U1, U2... Un được cho bởi danh sách cạnh
              Cạnh = Record
              d, c : Tên đỉnh;
              t: trọng số;
              End;
    d (1..m) of Cạnh
    Viết chi tiết thuật toán tìm cây khung bé nhất của G
    KRUSKAL by LĐS:

    1) Sắp xếp các danh sách cạnh sao cho:
    d[1].t ≤ d[2].t ≤
    ...≤ d[m].t


    2) FOR i := 1 TO n DO
    VT(i) := i;


    3) k = 0; ts := 0;



    4) FOR j = 1 TO m DO




    IF VT(d[j].d) !=
    VT(d[j].c) THEN



    a) k ++;



    T[k] := d[j];



    ts := ts + ds[j];



    b) tgd := VT(d[j].d);



    tgc := VT(d[j].c);



    FOR i := 1 TO n DO



    IF VT(i) := tgd THEN VT(i) := tgc;
    5) OUTPUT T, m



    KRUSKAL by HTH:
    proc KRUSKAL()
    1) Sắp xếp ds[1].t <= ds[2].t <=....<= ds[m].t;
    2) FOR x := 1 TO n DO sh[x] := x;
    3) k := 0; ts := 0; j := 1;
    4) WHILE k ≤ n -1 DO
              WHILE (sh[ds[j].d] = sh[ds[j].c] ) DO j++;
              d := ds[i].d; c := ds[i].c; {cho viết đoạn sau nó gọn thôi, k có mục đích gì khác}
              p := sh(d); q := sh(c);
              FOR x:=1 TO n DO
                        IF (sh(x) = p) THEN sh(x) := q;
    //thêm cạnh vào T:
                        k := k + 1;
                        E’[k]:= ds[j]; ts = ts + ds[j].t;
                        j := j + 1;
    5) OUTPUT E', ts
    Làm bằng tay phần b)
    Đánh dấu tất cả các đỉnh theo tên của nó.
    Sắp xếp tăng dần theo trọng số, sau đó lấy các cạnh, đánh dấu các đỉnh được lấy bằng chỉ số đánh dấu của cạnh đầu.
    Khi lấy đủ các đỉnh, bài toán hoàn thành.
    [You must be registered and logged in to see this image.]


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

    green.lotus84


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    Câu 1 nếu đổi thành danh sách móc nối đơn và mô tả như sau
    List = ^LINK;
    LINK = record
    K : Data;
    Next : List;
    End;
    Và câu hỏi giống y như câu 1 thì lời giải có gì khác không bạn?

    Admin


    Quản trị viên
    Quản trị viên
    Đây là nhận xét của thầy tôi ghi lại để những người vắng rút kinh nghiệm.
    - Thứ nhất là yếu về kiến thức cơ bản, sao chép của nhau nhiều, chữ viết cẩu thả, thụt thò không đúng, cách viết chỉ số tùy tiện thiếu nhất quán (chỗ thì ghi là Xj, chỗ thì ghi là X[j]), ký hiệu hỗn độn lẫn lộn chữ hoa và chữ thường (chỗ thì x, chỗ khác lại X...).
    - Cây thì vẽ ngang phè, con và cha không rõ ràng.
    - Viết các con số liền tù tì (563) lẽ ra phải có dấu cách đủ lớn để phân biệt 5 và 6 và 3, hay 5 và 63, hay 56 và 3.
    - Dùng các dấu ngoặc đóng mở không chính xác, không rõ ràng.
    - Bài toán tìm cây khung bé nhất không ghi STT bên cạnh các bước, dẫn tới lý giải và khó khăn nhiều cho người chấm theo dõi, rất tối kỵ.
    - Cây khung cần có tên nút, nhưng nhiều bài không có tên nút.
    - Thiếu không chỉ ra câu "Tập cạnh của cây khung bé nhất là..."
    - Nhiều bài thiếu, không khai báo cấu trúc cây khung, trừ đến 0,25 đ.
    Cụ thể sai sót đối với từng câu như sau:

    Với những câu dễ là câu 2 mất điểm vì:

    - Lý luận là x, nhưng push, pop lại là Mi. Nếu dùng x phải có câu "đọc x từ M", nhưng nên dùng Mi để người chấm nhận ra luôn thứ tự của phần tử.
    - Câu lệnh FOR i := 1 To /M/ nhưng nhiều người thiếu 2 gạch 2 bên chữ M, nên bị đánh giá không hiểu và trừ điểm nặng.
    - Trong vòng lặp làm 2 công việc là pop từ ngăn xếp ra và đưa vào sau N. Càn ghi thụt thò cẩn thận, hoặc ghi trên cùng hàng thì dùng dấu {}, cùng lắm thì mới dùng BEGIN, END cũng thụt thò, nhưng dùng cái này sẽ rối, khiến giáo viên chấm mất tập trung vì loãng nội dung nếu như cứ BEGIN END toàn bài. Nếu chấm khó theo dõi chỉ cần 1 sai sót nhỏ sẽ có cớ để trừ toàn bộ số điểm.
    - Lưu ý biểu thức mà không chỉ rõ chứa bên trong là gì thì M, N chấm như nhau.
    - Có thể giải quyết vấn đề bằng nhiều cách, không quan trọng, miễn là phải đúng vẫn chấm điểm, tuy nhiên cách làm không tối ưu thì không được tối đa điểm.
    - Khi duyệt tay, để tránh phải viết đi viết lại dãy ký tự ví dụ dòng trên viết 5 6 3 / 2 * dòng dưới có thể viết ...2 * - 5
    tức là dùng dấu 3 chấm để viết. Điều này không sai, người chấm thi không phải trình độ kém đến mức không hiểu dấu 3 chấm là cái gì, cách viết này để bài thi gọn gàng, không rối mắt. Tuy nhiên lưu ý, trong stack nên dùng khoảng trống rộng, không nên dùng dấu phảy, điều này giúp cho việc theo dõi của người chấm được bao quát cũng như đánh giá chính xác đáp án hơn.

    Về câu cây nhị phân Huffman:

    Chỉ có 1 lời giải.
    Không nên dùng dấu lớn hơn hay nhỏ hơn hoặc bằng, vì khi thi thì người thi hay rối. Nói là sắp xếp giảm dần nhưng lại dùng nhầm dấu ≤ dẫn tới bài thi được luôn 0 điểm. Chỉ cần viết 1 dòng là "Sắp xếp theo tần suất giảm dần" là tốt nhất."
    Thứ nữa là khi tạo con lưu ý phải tạo riêng Y sau đó mới sao chép vào, chuyển trỏ vào... chứ làm luôn là sai, 0 đ.

    Về câu 5:
    Trước khi viết lệnh nên xếp thành một dãy tăng dần từ Xd đến Xm, giảm dần từ Xm+1 đến Xc viết trên cùng một hàng. Viết một vài dòng ý tưởng, để nếu có làm sai sót thì vẫn không bị trừ nhiều điểm.
    Sai sót thường thấy là i tăng lên i := i + 1; hoặc i ++; và j giảm đi phải viết là j := j - 1; hay j-- thế nhưng nhiều bài vẫn viết nhầm là j = j + 1 và j ++ nên sẽ bị trừ 0 điểm. Bị đánh giá là không hiểu gì.
    Khi một đoạn xong trước, lấy đoạn còn lại hạ xuống, chỉ cần một vòng FOR đối với các phần tử chưa xét. Có thể viết:
    Yk = Xt và k = k + 1 hoặc
    Yk+j-t = Xt
    đều được, thấy cái nào dễ nhớ, dễ hiểu hơn thì sử dụng. Tuy nhiên cần chú ý tránh tạo sai mảng đích đối với chỉ số k.

    Về câu 7:
    Áp dụng danh sách cạnh
    + Thông tin trong lời giải không đầy đủ.
    + Sắp xếp cạnh theo trọng số tăng dần sau đó pải chú ý đánh số thứ tự bên cạnh.
    + Chọn cạnh nào đánh số cạnh thứ mấy để người chấm dễ theo dõi. Khi chọn cạnh xong pải ghi đủ các thông tin sau: Cạnh nào, trọng số là bao nhiêu, tổng trọng số từ điểm xuất phát đến hết cạnh vừa chọn là bao nhiêu. Kết thúc phải nói được là tổng trọng số tìm thấy là con số cụ thể.
    + Trong bài làm chú ý khi sử dụng T[1..n-1] of Cạnh chú ý rằng tìm được cạnh D[j] nào đó , đưa vào chỉ cần T[k] = D[j] , không dùng cách là cho 2 đầu bằng nhau → được đánh giá là trình độ tồi.
    + Nên sắp xếp theo chiều tăng của trọng số trước. Một số bài làm không sắp xếp, như thế là người chấm sẽ khó theo dõi và rất mệt.
    + Viết chú giải giải thích kỹ số hiệu, cấu trúc cây T, G , rồi sự liên thông sẽ được đánh giá cao.

    Về câu 8:
    + Nên duyệt theo chiều rộng an toàn hơn. Mỗi khi đánh dấu mới đếm. Đánh dấu xong, đếm luôn để tránh phải duyệt lại, là an toàn nhất. Luôn chọn u là điểm xuất phát, chỉ cần nói "Chọn đỉnh xuất phát là u" thôi.
    + Một số bài nhầm u và v rất nguy hiểm. Nên viết chữ v rõ ràng, không nên viết ngoáy để người chấm không đoán được là u hay v sẽ bị trừ, thậm chí đánh giá sai sẽ không có điểm.

    Về câu 6:
    Bài này phải giải là sắp xếp hòa nhập, có nhiều cách giải, ở đây chỉ cần hiểu là tại một thời điểm, lấy mỗi hàng một phần tử hiện tại của hàng đó. Chọn phần tử nhỏ nhất trong số đó, đưa vào mảng đích. Hàng nào có phần tử bị lấy sẽ tăng chỉ số phần tử hiện tại lên 1.
    code:
    FOR j = 1 TO m DO CS[j] = 1
    A[jo, CS[jo]]= min {A[j, CS[j]] j = 1..m}
    X[k] := A [jo, CS[jo]];
    k := k + 1;
    CS[jo] = CS[jo] + 1]

    Về câu 1:
    - Không ghi thủ tục mà chỉ có code không thì không có điểm
    - Không khai tham trị
    - Hiểu không rõ, không khai báo mà di chuyển lên P mất dữ liệu ngay
    - Không dùng tham số
    Code:
    s : = P;
    IF (s !=Nil) THEN
              1)WHILE (s !=Nil) DO { c := s; s := s^.Next}
    c^.next = Q;
    ELSE P = Q;
    OUTPUT P;
    Xóa phần tử cuối được xem là bài khó nhất vì nếu có 1 phần tử mà dùng lệnh xóa thông thường sẽ không xóa được. Nên chưa làm 3 trường hợp:
    P có 1 phần tử, P rỗng và P có nhiều phần tử.
    Code:
    1)Input P
    2) IF (P != Nil) & (P^.Next = Nil) THEN
              a) s : = P;
              b) WHILE (s^.Next ≠ Nil) DO {c: = s; s = s^.Next}
    ELSE P: = Nil;
    3) Output P


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

    12 [Ý kiến] gửi bạn green.lotus84 on Sat Jul 23, 2011 10:50 pm

    sinhmd


    Quản trị viên
    Quản trị viên
    green.lotus84 đã viết:Câu 1 nếu đổi thành danh sách móc nối đơn và mô tả như sau
    List = ^LINK;
    LINK = record
    K : Data;
    Next : List;
    End;
    Và câu hỏi giống y như câu 1 thì lời giải có gì khác không bạn?

    Bạn hỏi như thế chứng tỏ bạn chả hiểu gì về danh sách móc nối cả...????


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

    http://climategis.com/forum/

    13 [Ý kiến][Kinh nghiệm][Lời giải] on Sun Jul 24, 2011 5:12 pm

    hoadqbk


    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ

    Đọc theo M

    x

    Công việc thực hiện

    S

    N

    5

    5

    Đưa 5 vào N

    NULL

    5

    5-

    -

    Đưa – vào S

    -

    5

    5-6

    6

    Đưa 6 vào N

    -

    5,6

    5-6/

    /

    Kiểm tra UT(Top(S))





    5-6/3

    3

    Đưa 3 vào N


    -,/

    5,6,3

    5-6/3*

    *

    Kiểm tra
    UT(Top(S)) ≥ UT(*) lấy / từ dỉnh S đưa vào N, và đưa * vào S


    -,*

    5,6,3,/

    5-6/3*2

    2

    Đưa 2 vào N

    -,*

    5,6,3,/,2

    5-6/3*2-

    -

    Kiểm tra
    UT(UT(Top(S)) ≥ UT(-) lấy * từ đỉnh S đưa vào N, và đưa – vào S


    -,-

    5,6,3,/,2,*

    5-6/3*2-5

    5

    Đưa 5 vào N

    -,-

    5,6,3,/,2,*,5

    5-6/3*2-5+

    +

    Kiểm tra
    UT(UT(Top(S)) ≥ UT(-) lấy -,- từ đỉnh S đưa vào N, và đưa + vào S


    +

    5,6,3,/,2,*,5,-,-

    5-6/3*2-5+3

    3

    Đưa 3 vào N


    +

    5,6,3,/,2,*,5,-,-

    5-6/3*2-5+3*

    *

    Kiểm tra
    UT(UT(Top(S))






    5-6/3*2-5+3*2

    2

    Đưa 2 vào N

    +,*

    5,6,3,/,2,*,5,-,-,2

    5-6/3*2-5+3*2/

    /

    Kiểm tra
    UT(UT(Top(S)) ≥ UT(/) lấy * từ đỉnh S đưa vào N và đưa / vào S


    +,/

    5,6,3,/,2,*,5,-,-,2,*

    5-6/3*2-5+3*2/3

    3

    Đưa 3 vào N

    + /

    5,6,3,/,2,*,5,-,-,2,*,3

    5-6/3*2-5+3*2/3-

    -

    Kiểm tra
    UT(UT(Top(S)) ≥ UT(-) lấy /,+ từ đỉnh S đưa vào N và đưa - vào S


    -

    5,6,3,/,2,*,5,-,-,2,*,3,/,+

    5-6/3*2-5+3*2/3-3

    3

    Đưa 3 vào N


    -

    5,6,3,/,2,*,5,-,-,2,*,3,/,+,3

    5-6/3*2-5+3*2/3-3*

    *

    Kiểm tra
    UT(UT(Top(S))






    5-6/3*2-5+3*2/3-3*5

    5

    Đưa 3 vào N


    -,*

    5,6,3,/,2,*,5,-,-,2,*,3,/,+,3,5

    5-6/3*2-5+3*2/3-3*5+

    +

    Kiểm tra
    UT(UT(Top(S)) ≥ UT(+) lấy *,- từ đỉnh S đưa vào N và đưa + vào S


    +

    5,6,3,/,2,*,5,-,-,2,*,3,/,+,3,5*,-

    5-6/3*2-5+3*2/3-3*5+4

    4

    Đưa 4 vào N


    +

    5,6,3,/,2,*,5,-,-,2,*,3,/,+,3,5*,-,4


    Lấy toàn bộ S đưa ra N 5, 6, 3, /, 2, *, 5, -, -, 2, *, 3, /, +, 3, 5, *, -, 4, +

    Ban QT: Bạn có thể đánh vào bảng trong Word rồi copy dán vào. Hoặc chọn nút
    [You must be registered and logged in to see this image.], sau đó đánh vào bên trong, các khoảng cách khi đó sẽ được giữ nguyên để mọi người đọc chính xác được bài viết của bạn

    tranhue


    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    các bác cho em tý. dòng 8 khi đưa dấu + vào thì thì ut(*)>ut(+) lấy (*) đưa vào n. rồi đưa + vào s. không cần so sánh ut(+) và dấu (-) trong stact nũa.
    nhưng dòng số 10. đưa dấu + vào thì lại lấy luôn 2 dấu - đưa sang n?

    http://khmt.123.st

    Tongmanhcuong


    Thành viên cao cấp
    Thành viên cao cấp
    Trình bày như bạn là rất tốt nhưng theo mình có lẽ là mất nhiều thời gian, hiệu quả lại không cao. Theo mình bạn nên nghiên cứu cách trình bày khác sao cho thỏa mãn hai yêu cầu: 1. Mất ít thời gian; 2. Hiệu quả lại cao.


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

    PHL102


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Em nghĩ câu 2 đáp án thế này mới đúng
    ≡≡≡≡≡-
    Câu 2: Viết thủ tục sử dụng ngăn xếp S để chuyển biểu thức M dạng trung tố không có dấu ngoặc về dạng hậu tố.Dùng bảng minh họa sự thay đổi của ngăn xếp S khi áp dụng thuật toán trong câu trên để chuyển biểu thức sau về dạng hậu tố.
    M = 5 - 6 / 3 * 2 - 5 + 3 * 2 / 3 - 3 * 5 + 4




    Đọc theo M

    x

    Công việc thực hiện

    S

    N

    5

    5

    Đưa 5 vào N

    NULL

    5

    5-

    -

    Đưa – vào S

    -

    5

    5-6

    6

    Đưa 6 vào N

    -

    5,6

    5-6/ 


    Kiểm tra UT(Top(S))

    5-6/3

    3

    Đưa 3 vào N

    -,/ 

    5,6,3

    5-6/3* 

    *

    Kiểm tra
    UT(Top(S)) ≥ UT(*) lấy / từ dỉnh S đưa vào N, và đưa * vào S

    -,* 

    5,6,3,/

    5-6/3*2 

    2

    Đưa 2 vào N

    -,* 

    5,6,3,/,2

    5-6/3*2-

    -

    Kiểm tra
    UT(UT(Top(S)) ≥ UT(-) lấy *,- từ đỉnh S đưa vào N, và đưa - vào S

    -,- 

    5,6,3,/,2,*,-

    5-6/3*2-5 

    5

    Đưa 5 vào N

    -

    5,6,3,/,2,*,-,5

    5-6/3*2-5+ 

    +

    Kiểm tra
    UT(UT(Top(S)) ≥ UT(-) lấy - từ đỉnh S đưa vào N, và đưa + vào S


    5,6,3,/,2,*,-,5,-

    5-6/3*2-5+3 

    3

    Đưa 3 vào N

    +

    5,6,3,/,2,*,-,5,-,3

    5-6/3*2-5+3* 

    *

    Kiểm tra UT(Top(S))

    5-6/3*2-5+3*2 

    2

    Đưa 2 vào N

    +,* 

    5,6,3,/,2,*,-,5,-,3,2

    5-6/3*2-5+3*2/

    /

    Kiểm tra
    UT(UT(Top(S)) ≥ UT(/) lấy * từ đỉnh S đưa vào N và đưa / vào S

    +,/ 

    5,6,3,/,2,*,-,5,-,3,2,*

    5-6/3*2-5+3*2/3 

    3

    Đưa 3 vào N

    + / 

    5,6,3,/,2,*,-,5,-,3,2,*,3

    5-6/3*2-5+3*2/3- 

    -

    Kiểm tra
    UT(UT(Top(S)) ≥ UT(-) lấy /,+ từ đỉnh S đưa vào N và đưa - vào S


    5,6,3,/,2,*,-,5,-,3,2,*,3,/,+

    5-6/3*2-5+3*2/3-3 

    3

    Đưa 3 vào N


    5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3

    5-6/3*2-5+3*2/3-3* 

    *

    Kiểm tra
    UT(UT(Top(S))

    5-6/3*2-5+3*2/3-3*5 

    5

    Đưa 3 vào N

    -,* 

    5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3,5

    5-6/3*2-5+3*2/3-3*5+ 

    +

    Kiểm tra
    UT(UT(Top(S)) ≥ UT(+) lấy *,- từ đỉnh S đưa vào N và đưa + vào S 

    +

    5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3,5*,-

    5-6/3*2-5+3*2/3-3*5+4 

    4

    Đưa 4 vào N

    +

    5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3,5*,-,4
      Lấy toàn bộ S đưa ra N 5  6  3 / 2 *- 5 - 3  2 * 3 /+ 3  5 *- 4+


    Vậy biểu thức M dạng trung tố không có dấu ngoặc về dạng hậu tố:


    5  6  3 / 2 *- 5 - 3  2 * 3 /+ 3  5 *- 4+

    Minto Trầm


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    PHL102 đã viết:Em nghĩ câu 2 đáp án thế này mới đúng
    ≡≡≡≡≡-
    Câu 2: Viết thủ tục sử dụng ngăn xếp S để chuyển biểu thức M dạng trung tố không có dấu ngoặc về dạng hậu tố.Dùng bảng minh họa sự thay đổi của ngăn xếp S khi áp dụng thuật toán trong câu trên để chuyển biểu thức sau về dạng hậu tố.
    M = 5 - 6 / 3 * 2 - 5 + 3 * 2 / 3 - 3 * 5 + 4




    Đọc theo M

    x

    Công việc thực hiện

    S

    N

    5

    5

    Đưa 5 vào N

    NULL

    5

    5-

    -

    Đưa – vào S

    -

    5

    5-6

    6

    Đưa 6 vào N

    -

    5,6

    5-6/ 


    Kiểm tra UT(Top(S))

    5-6/3

    3

    Đưa 3 vào N

    -,/ 

    5,6,3

    5-6/3* 

    *

    Kiểm tra
    UT(Top(S)) ≥ UT(*) lấy / từ dỉnh S đưa vào N, và đưa * vào S

    -,* 

    5,6,3,/

    5-6/3*2 

    2

    Đưa 2 vào N

    -,* 

    5,6,3,/,2

    5-6/3*2-

    -

    Kiểm tra
    UT(UT(Top(S)) ≥ UT(-) lấy *,- từ đỉnh S đưa vào N, và đưa - vào S

    -,- 

    5,6,3,/,2,*,-

    5-6/3*2-5 

    5

    Đưa 5 vào N

    -

    5,6,3,/,2,*,-,5

    5-6/3*2-5+ 

    +

    Kiểm tra
    UT(UT(Top(S)) ≥ UT(-) lấy - từ đỉnh S đưa vào N, và đưa + vào S


    5,6,3,/,2,*,-,5,-

    5-6/3*2-5+3 

    3

    Đưa 3 vào N

    +

    5,6,3,/,2,*,-,5,-,3

    5-6/3*2-5+3* 

    *

    Kiểm tra UT(Top(S))

    5-6/3*2-5+3*2 

    2

    Đưa 2 vào N

    +,* 

    5,6,3,/,2,*,-,5,-,3,2

    5-6/3*2-5+3*2/

    /

    Kiểm tra
    UT(UT(Top(S)) ≥ UT(/) lấy * từ đỉnh S đưa vào N và đưa / vào S

    +,/ 

    5,6,3,/,2,*,-,5,-,3,2,*

    5-6/3*2-5+3*2/3 

    3

    Đưa 3 vào N

    + / 

    5,6,3,/,2,*,-,5,-,3,2,*,3

    5-6/3*2-5+3*2/3- 

    -

    Kiểm tra
    UT(UT(Top(S)) ≥ UT(-) lấy /,+ từ đỉnh S đưa vào N và đưa - vào S


    5,6,3,/,2,*,-,5,-,3,2,*,3,/,+

    5-6/3*2-5+3*2/3-3 

    3

    Đưa 3 vào N


    5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3

    5-6/3*2-5+3*2/3-3* 

    *

    Kiểm tra
    UT(UT(Top(S))

    5-6/3*2-5+3*2/3-3*5 

    5

    Đưa 3 vào N

    -,* 

    5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3,5

    5-6/3*2-5+3*2/3-3*5+ 

    +

    Kiểm tra
    UT(UT(Top(S)) ≥ UT(+) lấy *,- từ đỉnh S đưa vào N và đưa + vào S 

    +

    5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3,5*,-

    5-6/3*2-5+3*2/3-3*5+4 

    4

    Đưa 4 vào N

    +

    5,6,3,/,2,*,-,5,-,3,2,*,3,/,+,3,5*,-,4
      Lấy toàn bộ S đưa ra N 5  6  3 / 2 *- 5 - 3  2 * 3 /+ 3  5 *- 4+


    Vậy biểu thức M dạng trung tố không có dấu ngoặc về dạng hậu tố:


    5  6  3 / 2 *- 5 - 3  2 * 3 /+ 3  5 *- 4+

    Mình cũng có đáp án giống của bạn!

    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

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