Đề cương CTDL-GT-01ĐH Tin
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;
Giải:;
1,xd phép tích cực p := p*x/j;
2, với i=1->phép tích cực thực hiện 1 lần
i=2 2
i=n n
3.tổng=1+2+..+n=n(n+1)/2;
4.t(n)=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;
1.trường hợp xấu nhất m luôn>=1000
Phép toán tích cực s:=s+x;
Với i=1->phép tích cực lặp n lần
I=2 n
I=n n
=>tổng số lần lặp là n.n=n2=>t(n)=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;
Phép toán tích cực nhất: phép so sánh a[j]<a[k]/./phải so sánh trc
I=1…j chạy từ 2=>n có n-2+1=n-1 lần thực hiện
I=1…. Chạy từ 3=>n có n-2 lần thực hiện
I=3… 4=>n có n-3 lần thực hiện
I=n-1 thì j=n có 1 lần thực hiện
Tống(i=1-:>n-1)=1+2+3+…+(n-3)+(n-2)+(n-1)=n(n-1)/2
Vậy I(n)=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)
- Viết một thủ tục đệ qui thực hiện tính giá trị hàm này.
Giải:
A(1,2)=a(0,A(0,1))=a(0,2)=2+1=3;
Int a(m,n);
{
If(m=0) return n+1;
Else
if (n=0) return a(m-1,1);
Else return a(m-1,a(m,m-1);
}
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), giải thích cách tính.
b. Viết giải thuật đệ qui để tính giá trị hàm S.
c. Viết giải thuật khử đệ quy tính giá trị hàm S.
a, s(10)=10+s(9)=…=10+9+8+7+6+5+4+3+2+1=55;
b,
int S(n);
{if n=1 return 1;
Else return n+S(n-1);
c;
{
Int i;s=0;
For(i=1;i<=n;i++)
S=s+i;
Return s;
}
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.
giải:
f(2,3)=f(1,3)+f(2,2)=f(0,3)+2*f(1,2)+f(2,1)=3+f(1,2)+2*f(1,2)+
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 vecto 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.
giải:
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
Bạn đang đọc truyện trên: AzTruyen.Top