BỘ CÔNG THƯƠNG    CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM

    TRƯỜNG  ĐẠI HỌC  SAO ĐỎ    Độc lập - Tự do - Hạnh phúc

    *****    -----o0o-----   

ĐỀ CƯƠNG ÔN TẬP

Môn học:  Cấu trúc dữ liệu và giải thuật

    Hệ:           Đại học                            

Câu 1

Hãy xác định độ phức tạp tính toán của giải thuật bằng ký pháp chữ O lớn trong trường hợp tồi nhất của đoạn chương trình sau:

1. Read(x); S := 1;

2. For i := 1 to n do    

    Begin

        P := 1;

        For j := 1 to i do p := p*x/j;

        S := S + p;

End;

Tn=O(n2)

Câu 2

Hãy xác định độ phức tạp tính toán của giải thuật bằng ký pháp chữ O lớn trong trường hợp tồi nhất của đoạn chương trình sau:

Read(x); S := 1;

For i := 1 to n do

        If M >= 1000 then

        For j := 1 to n do

            Begin

                S := S + x;

                Writeln(S:6);

            End;

Tn=O(n2)

Câu 3

Hãy xác định độ phức tạp tính toán của giải thuật bằng ký pháp chữ O lớn trong trường hợp tồi nhất của đoạn chương trình sau:

      For i := 1 to n - 1 do

 Begin   

        k := i;

        For j := i + 1 to n do

            If a[j] < a[k]

then k := j;

            If k <> i then

                Begin

                x := a[i];

                a[i] := a[k];

                a[k] := x;

                End;

     End;

Tn=O(n2)

Câu 4

Giải thuật tính ước số chung lớn nhất của hai số nguyên dương p và q (p > q) được mô tả như sau:

Gọi r là số dư trong phép chia p và q.

- Nếu r = 0 thì q là ước số chung lớn nhất.

- Nếu r  0 thì gán cho p giá trị của q, gán cho q giá trị của r rồi lặp lại quá trình.

a. Hãy xây dựng một định nghĩa đệ qui cho hàm USCLN (p.q).

b. Viết một giải thuật đệ qui và một giải thuật lặp thể hiện hàm đó.

Câu 5

Xét định nghĩa đệ qui:

        n+1 nếu m=0

Acker(m,n) =        Acker(m-1,1) nếu n = 0

        Acker(m-1,Acker(m,m-1)) với các T. hợp khác.

- Hãy xác định Acker (1,2) =3

- Viết một thủ tục đệ qui thực hiện tính giá trị hàm này.

Câu 6

Cho hàm số S(n) với n là đối số nguyên dương lớn hơn 0 được định nghĩa đệ quy như sau:

a. Tính S(10) = 55, giải thích cách tính.

b. Viết giải thuật đệ qui để tính giá trị hàm S.

int S(n)

{

    If (n =1) return 1;

    If (n>1)

return (n + s(n-1));

    }

c. Viết giải thuật khử đệ quy tính giá trị hàm S.

{

While (n>1)

{    T = T+n;

    N=n-1;   } return (T);

}

Câu 7

Cho hàm số f(m, n) với m, n là các đối số kiểu nguyên như sau:

a. Tính f(2,3), giải thích cách tính.

b. Viết giải thuật đệ qui để tính giá trị hàm f.

Câu 8

Trình bày khái niệm hàng đợi; giải thuật bổ sung một phần tử vào hàng đợi lưu trữ bởi mảng tròn.

Câu 9

Cho một Queue được lưu trữ trong bộ nhớ bởi một vectơ Q có n=6  phần tử (ô nhớ), được hoạt động theo cấu trúc kiểu vòng tròn.

Thoạt đầu Queue có dạng

1    2    3    4    5    6

    London    Berlin    Rom    Paris   

Hãy minh hoạ tình trạng của Q và nêu rõ giá trị tương ứng của F và R sau mỗi lần thực hiện các phép dưới đây:

a.    “Marid” được bổ sung vào Queue

b.    Loại tên hai thành phố ra khỏi Queue

c.    “Oslo”  được bổ sung vào Queue

d.    “Moscow” được bổ sung vào Queue

e.    Loại tên ba thành phố ra khỏi Queue

Câu 10

Cho biểu thức sau: A/(B+C) + D*E – A*(C-D).

a.    Vẽ cây nhị phân biểu diễn biểu thức trên.

b. Biểu diễn cây nhị phân vừa vẽ bằng vector liên tiếp.

c. Viết thứ tự các nút được thăm khi duyệt cây theo thứ tự: trước, giữa,

sau.

Trước : +/A+BC-*DE*A-CD

Giữa :

Câu 11

Cho cây nhị phân như hình vẽ:

a. Viết trình tự các nút được thăm trong phép duyệt cây theo thứ tự trước, giữa, sau.

b. Minh họa hoạt động của stack trong phép duyệt cây theo thứ tự trước.

Câu 12

Cho danh sách nối đơn mà phần tử đầu danh sách  trỏ bởi L, M là một nút có trong danh sách. Hãy viết các giải thuật thực hiện các phép sau:

a.    Chèn vào sau node trỏ bởi M một node có trường info bằng x cho trước.

b.    Xóa node trỏ bởi M.

Câu 13

Giả sử a và b là những số nguyên dương. Q là hàm số của a,  b và được định nghĩa như sau:

a.    Hãy tính  Q(2, 3) và Q(14, 3)

b.    Xây dựng giải thuật đệ quy tính giá trị hàm Q trên.

Câu 14

Cho giải thuật:

Function Fib(n);

1. if n <= 2 then Fib:=1

   else Fib:= Fib(n-2) + Fib(n-1);

2. Return;

a. Giải thuật trên có phải là giải thuật đệ quy không? Tại sao?

b. Nếu giải thuật trên là đệ quy, hãy xây dựng định nghĩa đệ quy tính Fib(n) dựa trên giải thuật đó. Khi gọi Fib(8), có bao nhiêu lần gọi Fib(4)?

Câu 15

Cho biểu thức sau: a/(b+c)+d*e-a*c

a.    Vẽ một cây nhị phân biểu diễn bởi biểu thức trên.

b.    Viết dãy các nút được thăm khi duyệt cây vừa vẽ theo: Thứ tự trước, thứ tự sau.

c.     Vẽ hình minh họa biểu diễn cây bằng danh sách móc nối.

Câu 16

Cho biểu thức sau: 8 / (1 + 3) + 6 * 5 – 4 * 2

a.    Vẽ một cây nhị phân biểu diễn bởi biểu thức trên.

b.    Viết dãy các nút được thăm khi duyệt cây vừa vẽ theo: Thứ tự trước, thứ tự sau.

c.    Minh họa hoạt động stack khi chuyển đổi biểu thức trung tố sang biểu thức hậu tố.

Câu 17

Cho biểu thức sau: (5 - 2) * (4 + 3) – (7 * 2) / (6 - 4)

a.    Vẽ một cây nhị phân biểu diễn bởi biểu thức trên.

b.    Viết dãy các nút được thăm khi duyệt cây vừa vẽ theo: Thứ tự trước, thứ tự sau.

c.    Minh họa hoạt động stack tính giá trị biểu thức hậu tố.

Câu 18

Cho cây nhị phân như hình vẽ:

a. Biểu diễn cây nhị phân vừa vẽ bằng vecto liên tiếp và bằng danh sách móc nối.

b. Viết thứ tự các node khi duyệt cây theo thứ tự: trước, giữa, sau.

Câu 19

Cho danh sách nối đơn mà phần tử đầu danh sách trỏ bởi L. Viết giải thuật thực  hiện các công việc sau:

a. In ra giá trị của trường info của các node có trong danh sách.

b. Chèn một node mới có trường info bằng x cho trước vào sau node thứ k có trong danh sách.     

Câu 20

Cho danh sách nối đơn  mà phần tử đầu danh sách trỏ bởi L. Một con trỏ M trỏ tới một node có trong danh sách. Viết giải thuật thực hiện các công việc sau:

a. Đếm số node có trường Info không âm

b. Tách danh sách thành hai danh sách: một danh sách trỏ bởi L, một danh sách trỏ bởi M.

Câu 21

Cho một danh sách nối đơn, có con trỏ L trỏ tới nút đầu tiên của danh sách này. Hãy viết giải thuật thực hiện:

a. Cộng thêm một số A vào số đang chứa tại trường INFO của mỗi nút.

b. Đếm số lượng các nút có trong danh sách đó.

Câu 22

Cho một danh sách nối đơn, có con trỏ L trỏ tới nút đầu tiên của danh sách này. Hãy viết giải thuật thực hiện:

a.    Đếm số lượng các nút đang chứa số dương thuộc danh sách (giả sử các số chứa trong mỗi nút là số đại số khác không)

b.    Tính giá trị trung bình của các số chứa trong danh sách.

Câu 23

Cho danh sách nối đơn mà phần tử đầu danh sách trỏ bởi L. Một con trỏ M trỏ tới một node có trong danh sách. Viết giải thuật thực hiện các công việc sau:

a. Đếm số node có trường Info không âm

b. Cho biết node có giá trị trường info nhỏ nhất trong danh sách.

Câu 24

Cho danh sách nối đơn mà phần tử đầu danh sách trỏ bởi L. Viết giải thuật thực hiện các công việc sau:

a. In ra thứ tự các node trong danh sách có trường info bằng k cho trước.

b. Sắp xếp danh sách đã cho theo thứ tự giảm dần. Viết ra trường info của các node trong danh sách đã sắp xếp.

Câu 25

Cho danh sách nối đơn mà phần tử đầu danh sách trỏ bởi L. Viết giải thuật thực hiện các việc sau:

a. Bổ sung một nút có trường Info bằng X vào đầu danh sách.

b. Loại bỏ phần tử ở đầu danh sách.

c. Bổ sung một phần tử vào cuối danh sách.

Câu 26

Cho đoạn chương trình tính tổng các phần tử nằm trên đường chéo chính của ma trận vuông A cấp n như sau :

S :=0 ;

For     i :=1     to     n     do

For     j :=1     to     n     do

If    i=j    then

S :=S+A[i, j]

    Return (S) ;

a.    Tìm độ phức tạp của đoạn chương trình trên theo ký pháp chữ O lớn.

b.    Cải tiến đoạn chương trình trên để giảm độ phức tạp về thời gian thực hiện. Tìm độ phức tạp của chương trình đã cải tiến.

Câu 27

Trình bầy dạng giả định giải thuật sắp xếp kiểu trộn (hòa nhập). Hãy thực hiện sắp xếp kiểu trộn (hay hoà nhập) hai đường tự nhiên với dãy đã cho.

A:      2         4         21         39       43        58        72        99        175

B:       1         6         41         59       65       80      172

Câu 28

Trình bầy dạng giả định giải thuật sắp xếp trong Quick Sort (Phương pháp sắp xếp nhanh). Ví dụ minh họa sắp xếp tăng dần bằng phương pháp Quick Sort với dãy 7 phần tử sau:

10     65     98     5     30  78    4

Câu 29

Trình bầy giải thuật tìm kiếm nhị phân. Cho ví dụ minh họa tìm phần  tử 10 trong dãy sau:

4    5    10    30    65    78    98

Câu 30

a.    Trình bày dạng giả định giải thuật tìm kiếm tuần tự.

b.    Minh họa giải thuật tìm kiếm tuần tự để tìm phần tử x=5 trong dãy số sau:

10     65     98     5     30  78    4     45  20

Câu 31

a.    Trình bày dạng giả định giải thuật sắp xếp dãy số tăng dần kiểu đổi chỗ trực tiếp (nổi bọt).

b.    Minh họa các bước của giải thuật sắp xếp dãy số tăng dần kiểu đổi chỗ trực tiếp (nổi bọt) với dãy số sau:

10     65     98     5     30  78    4     45  20

Câu 32

a.    Trình bày dạng giả định giải thuật sắp xếp dãy số tăng dần kiểu thêm dần (chèn trực tiếp).

b.    Minh họa các bước của giải thuật sắp xếp dãy số tăng dần kiểu thêm dần (chèn trực tiếp) với dãy số sau:

10     65     98     5     30  78    4     45  20

Câu 33

a.    Trình bày dạng giả định giải thuật sắp xếp dãy số tăng dần kiểu lựa chọn (chọn trực tiếp).

b.    Minh họa các bước của giải thuật sắp xếp dãy số tăng dần kiểu lựa chọn (chọn trực tiếp) với dãy số sau:

10     65     98     5     30  78    4     45  20