cau truc du lieu va giai thuat
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
Họ và tên: Triệu Văn Thơ
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;
Bài Giải:
1, Xác định phép tích cực p := p*x/j;
2, Với i=1->n 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;
Bài giải:
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->n 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;
Bài giải:
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…j chạy từ 3=>n có n-2 lần thực hiện
I=3… j chạy từ 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 đó.
Bài giải:
a,
Định nghĩa đệ quy
q là ước số chung lớn nhất nếu r=p/q=0
USCLN(p,q)
USCLN(q,r) nếu r ¹ 0
b,
// Giải thuật đệ quy
unsigned USCLN (unsigned p, unsigned q)
{
R= p mod q;
while (n != 0 && m != 0)
if (r=0)
return Q;
else
p=q;
q=r;
return r;
}
// Giải thuật lặp
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.
Bài 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.
Bài giải:
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 s(int n);
{
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.
Bài giải:
a,
F(2,3)=f(2-1,3)+f(2,3-1)=f(1,3)+f(2,2)
Mà
F(1,3)=f(0,3)+f(1,2)=3+2f(1,2)
F(2,2)=f(1,2)+f(2,1)
F(2,3)=3+3f(1,2)+f(2,1)=3+3(f(0,2)+f(1,1))+f(1,1)+f(2,0)
= 3+3f(0,2)+f(2,0)+4f(1,1)=3+3(2+f(1,1))+2+5+4f(1,1)
=10+6+7f(1,1)=16+7(f(0,1)+f(1,0))=16+7(1+f(1,0)+6)
=16+7+42+42=107
b,
int f(m,n)
{
if (n<=0) return (m+5);
if (m<=0) return ( n+f(1,n-1));
else
return f(m-1,n)+f(m,n-1);
}
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.
Bài làm:
Hàng đợi queue là kiểu danh sách tuyến tính mà phép bổ sung được thực hiện 1 đầu ,gọi là nối sau( rear) và phép loại bỏ thực hiện ở 1 đầu, gọi là nối trước(front).
Giải thuật:
#include<conio.h>
#include<dos.h>
#include<stdio.h>
#define max 100 //khai báo
Int q[max+1];
Int front, rear, size;
Void initq() // khởi tạo
{
Front =rear=size=0;
}
Int emptyq() // hàng đợi rỗng
{
Return ( size==0);
}
Int full() // Hàng đợi đầy
{
Return (size==max);
}
Int push ( int value)
{
If (size<max)
{
size++;q[rear++]=value; if (rear ==max)
Rear=0;
}
Return value;
}
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
Bài giải:
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
F(2),R(6)
1 2 3 4 5 6
LonDon
Berlin
Rom
Paris
Maris
b. Loại tên hai thành phố ra khỏi Queue
F(4),R(6)
1 2 3 4 5 6
Rom
Paris
Maris
c. “Oslo” được bổ sung vào Queue
F(4),R(1)
1 2 3 4 5 6
Oslo
Rom
Paris
Maris
d. “Moscow” được bổ sung vào Queue
F(4),R(2)
1 2 3 4 5 6
Oslo
MosCow
Rom
Paris
Maris
e. Loại tên ba thành phố ra khỏi Queue
F(1),R(2)
1 2 3 4 5 6
Oslo
Moscow
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:
Bài giải:
a, Vẽ cây nhị phân biểu diễn biểu thức trên
a. Biểu diễn cây nhị phân vừa vẽ bằng vecto liên tiếp.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
+
/
-
A
+
*
*
B
C
D
E
A
-
21
22
23
24
25
26
27
28
29
30
31
C
D
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: A/B+C+D*E-A*C-D
Sau: ABC+/DE*ACD-*-+
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 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.
Trước: ABDHCFGEI
Giữa: HDBAFCEGI
Sau: HDBFEIGCA
b. Minh họa hoạt động của stack trong phép duyệt cây theo thứ tự trước.
X
S
E
A
A
A
B
C
AB
D
C
ABD
H
C
ABDH
C
ABDHC
F
G
ABDHCF
G
ABDHCFG
E
I
ABDHCFGE
I
ABDHCFGEI
ABDHCFGEI
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.
chen (nodep M, infotype x)
{
N=(nodep malloc(sizeof (struct node))
N->data=X// tạo nut mới
N->next=null;
If(L=null)
L=N;
Else
{
N->next=M->next;
M->next=N;
}
b. Xóa node trỏ bởi M.
xoa(nodep L, nodep M)
{
Nodep N;
If(L=null)
L=N;
Else
While (N->next !=M);
N=N->next;
N->next=M->next;
Free(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:
Q(a,b)=0 nếu a<b or Q(a-b,b)+1 nếu a=>b
a. Hãy tính Q(2, 3) và Q(14, 3)
Ta có :
Q(2,3)= 0 vi a=2,b=3 a<b;
Q(14,3) vì a=14,b=3 nên Q(14,3)=Q(11,3)+1
Q(11,3)= Q(8,3)+1
Q(8,3)=Q(5,3)+1
Q(5,3)=Q(2,3)+1
Vì Q(2,3)=0 nên Q(14,3)=1+1+1+1=4
b. Xây dựng giải thuật đệ quy tính giá trị hàm Q trên.
Int Q(a,b)
{
If (a<b) return 0
Else Q=Q(a-b,b)+1;
Return Q;
}
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?
· Trong thân có lời gọi tới chính nó( return).
· Kích thước chương chình giảm f(n-2),f(n-1)
· Trường hợp suy biến n<=2
giải thuật trên là giải thuật đẹ quy vì
1 nếu n<=2;
Fib(n)
Fib =fib(n-2)+fib(n-1) nếu n>2;
c. 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)?
Fib(8)=fib(6)+fib(7)=2fib(6)+fib(5)=2fib(4)+3fib(5)
=5fib(4)+3fib(3)
vậy khi gọi fib(8) sẽ có 5 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. Trươc:+/A+BC-*DE*AC
d. Sau:ABC+/DE*AC*-+
e. 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.
trước:+/8+13-*65*42
sau: 813+/65*42*-+
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ố.
X
S
E
8
8
/
/
8
(
/(
8
1
/(
81
+
/(+
81
3
/(+
813
)
/
813+
+
+
813+/
6
+
813+/6
*
+*
813+/6
5
+*
813+/65
-
+-
813+/65*
4
+-
813+/65*4
*
+-*
813+/65*4
2
+-*
813+/65*42
813+/65*42*-+
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.
thứ tự trước: -*-52+43/*72-64
thứ tự sau: 52-43+*72*64-/-
c. Minh họa hoạt động stack tính giá trị biểu thức hậu tố.
X
S
X
S
5
5
*
21,14
2
5,2
6
21,14,6
-
3
4
21,14,6,4
4
3,4
-
21,14,2
3
3,4,3
/
21,7
+
3,7
-
14
*
21
7
21,7
2
21,7,2
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.
Danh sách móc nối:
Danh sách vecto liên tiếp:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A
B
C
D
E
F
G
H
I
b. Viết thứ tự các node khi duyệt cây theo thứ tự: trước, giữa, sau.
· duyệt trước: ABDHEICFG
· duyệt giữa: HDBIEAFCG
· duyệt sau: HDIEBFGCA
Bài giải:
a,
void Print(nodep L);
{
Nodep p;
p=L;
while (p!=NULL)
{
Printf(“%d”, pàinfo);
P=pànext;
}
b,
void chen(nodep L,int x,int k);
{
nodep P,N;
N=(nodep)malloc(sizeof(struct node));
N->info=x;
N->next=NULL;
P=L;
int i=0;
while(P!=NULL&&i!=k)
{
i=i++;
P=P->next;
}
N->next=P->next;
P->next=N;
}
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.
a,
void Count(nodep L);
{
Nodep p;
p=L;
while (p!=NULL)
{
if(pàinfo >= 0)
i=i++;
p=pànext;
}
}
b,
void Insert(nodep L, nodep M);
{
Nodep p,M; //Với M là nút mà chúng ta biết trước về giá trị, vị trí
p=L;
while (p!=M)
{
p=pànext;
}
pànext=NULL;
}
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 đó.
Bài giải:
a,
void Insert(nodep L, int A);
{
Nodep p;
p=L;
while (p!=NULL)
{
pàinfo=pàinfo + A;
p=pànext;
}
}
b,
void Count(nodep L);
{
Nodep p;
p=L;
while (p!=NULL)
{
i=i++;
p=pànext;
}
}
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.
Bài giải:
void Count(nodep L);
{
Nodep p;
p=L;
while (p!=NULL)
{
if(pàinfo > 0)
i=i++;
p=pànext;
}
}
b,
void TrungBinh(nodep L);
{
Int Tong,i;
Nodep p;
p=L;
while (p!=NULL)
{
Tong = Tong + pàinfo;
i=i++;
p=pànext;
}
printf(“Trung binh cong la: %f”,Tong/i);
}
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.
Bài giải:
a,
void Count(nodep L);
{
Nodep p;
p=L;
while (p!=NULL)
{
if(pàinfo >= 0)
i=i++;
p=pànext;
}
}
b,
void FindMin(nodep L);
{
Nodep p;
int min,Vitri;
p=L;
while (p!=NULL)
{
if(pàinfo <min)
{
min=pàinfo;
Vitri=i;
}
p=pànext;
}
printf(“Vi tri phan tu co gia tri nho nhat la %d, gia tri la : %d”,Vitri,min);
}
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.
Void Hienthi(nodep L, infotype k);
{
Nodep P,int i=0;
If (L==NULL) return();
Else
{
P=L;
While (P!=NULL)
{
if (p->data =k);
{
I=i+1;
Printf(“%d”,i);
}
P=p->next; }
}
}
}
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.
Void sapxep(nodep l)
{
Nodep p;
Int tg,i,n=0;
If(l==null)
return ();
Else
{
p=l;
While (p!=null)
{
N=n+1;
P=p->next; }
For ( i=1,i<=n,i++)
{
P=l;
While (p->next !=null)
{
If (p->data < (p->next)->data)
tg=p->data;
p->data = (p->next->data);
(p->next)->data=tg;
}
P=p->next;
}
}
}
}
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.
Void bosung(nodep l,infotype x)
{
nodep q;
Q=(nodep)malloc(sizeof(struct node));
q->data=x;
q->next=L;
L=q;
}
b. Loại bỏ phần tử ở đầu danh sách.
Void loaibo(nodep L)
{
nodep p;
If (L==null) return(0);
Else
{
p=L;
L=L->next;
Free(p);
}
}
c. Bổ sung một phần tử vào cuối danh sách.
Voi bosung( nodep l)
{
nodep p,q;
Q=(nodep)malloc(sizeof(struct node));
q->data=x;
If (l==null)
{
l=q;
q->next=null;
}
Else
{
p=l;
While(p->next!=null)
{
P=p->next;
}
p->next=q;
q->next=null;
}
}
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.
Phép toán tích cực: if i=j
I=1………………….lặp n lần
I=2….. lặp n lần
I=n-1…………………………
Ø Độ phức tạp của thuật toán = O(n2)
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.
Đoạn ct đã được cải tiến:
S=0;
For(i=1,i<n;i++)
S:=S+A[i];
Return S;
Ø Độ phức tạp của thuật toán: =O(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
Bài giải:
Giải thuật sắp xếp kiểu trộn(hoà nhập)
Void merging(X[],m,Y[],n,Z)
{
I=1, j=1, k=1;
While (i<=m && j<=n)
{
If (x[i] < x[j])
{
Z[k]=x[i], i++,k++;
}
Else
{
Z[k]=y[j], j++,k++;
}
}
While(i<=m)
{
Z[k]=x[i], i++,k++;
}
While(j<=n)
{
Z[k]=y[j], j++,k++;
}
}
A: 2 4 21 39 43 58 72 99 175
B: 1 6 41 59 65 80 172
I
J
C
1
1
1
1
2
1 2
2
2
1 2 4
3
2
1 2 4 6
3
3
1 2 4 6 21
4
3
1 2 4 6 21 39
5
3
1 2 4 6 21 39 41
5
4
1 2 4 6 21 39 41 43
6
4
1 2 4 6 21 39 41 43 58
7
4
1 2 4 6 21 39 41 43 58 59
7
5
1 2 4 6 21 39 41 43 58 59 65
7
6
1 2 4 6 21 39 41 43 58 59 65 72
8
6
1 2 4 6 21 39 41 43 58 59 65 72 80
8
7
1 2 4 6 21 39 41 43 58 59 65 72 80 99
9
7
1 2 4 6 21 39 41 43 58 59 65 72 80 99 172
9
7
1 2 4 6 21 39 41 43 58 59 65 72 80 99 172 175
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
Bài giải:
Giải thuật:
Void quick_sort(int X[], int left, int right)
{
Int i=left;
Int j=right;
Int k=(left+right)/2;
Int t=X[k];
If(left<right)
{
While (i<=j)
{
While (X[i] <t)
{
i=i+1;
}
While (X[i] <t)
{
j=j-1;
if (i<=j)
{
Int tg=X[i];
X[i]=X[j];
X[j]=tg;
I++;j--;
}
}
Quick_sort(X,left,j);
Quick_sort(X,i,right);
}
}
Ø 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
T=X[k]=5
Lần
I
J
k
X
Ghi chú
1
1
7
4
10 65 98 5 30 78 4
Tăng i cho đến khi gặp khóa>=chốt, giảm j cho đến khi gặp khóa <=chốt
1
7
4
4 65 98 5 30 78 10
Đổi chỗ X[1] và X[7]
2
6
4
4 65 98 5 30 78 10
2
5
4
4 65 98 5 30 78 10
2
4
4
4 5 98 65 30 78 10
Đổi chỗ X[2] và X[4]
3
3
4
4 5 98 65 30 78 10
4
2
4
4 5 98 65 30 78 10
2
3
7
5
4 5 98 65 30 78 10
3
7
5
4 5 10 65 30 78 98
Đổi chỗ X[3] và X[7]
4
6
5
4 5 10 65 30 78 98
4
5
5
4 5 10 30 65 78 98
Đổi chỗ X[4] và x[5]
5
4
5
4 5 10 30 65 78 98
3
5
7
6
4 5 10 30 65 78 98
6
6
6
4 5 10 30 65 78 98
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
Bài giải:
Int binary_search(X[], l, r, KH)
{
If(l>r)
Return 0;
Else
{
J=(l+r) % 2;
If (K==X[j]) return j;
Else
If (K<X[j])
return (binary_search(X,l,j-1,K));
Else
return (binary_search(X,j+1,r,K));
}
}
Minh họa tìm phần tử 10 trong dãy sau:
4 5 10 30 65 78 98
Bước
j
Khóa ở giữa
Tìm kiếm với Dãy khóa
Ghi chú
1
4
30
4 5 10 30 65 78 98
K=10<X[4]=30
2
2
5
4 5 10
K>5
3
3
10
10
Tìm kiếm thành công
Câu 30
a. Trình bày dạng giả định giải thuật tìm kiếm tuần tự.
cách 1:
Int timkiemtuantu(X[],n,KH)
{
i=1;
While (X[i] != K&& i<=n)
{
i=i+1;
If (i<=n) return (i);
Else return (0);
}
}
Cách 2:
Int timkiemtuantu(X[],n,KH)
{
Int dem=0,i;
Printf(“
nhap phan tu can tim kiem:”);
Scanf(%d,&x);
For(i=1;i<n;i++)
If (a[i]==X)
Dem=dem+1;
Printf(“so luong ket qua”,dem);
}
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
I
So sánh
1
X[1] ≠ 5
Không tìm thấy
2
X[2] ≠ 5
Ko
3
X[3] ≠ 5
Ko
4
X[4]=5
Tìm thấy
5
X[5] ≠5
Ko
6
X[6] ≠5
Ko
7
X[7] ≠5
Ko
8
X[8] ≠5
Ko
9
X[9] ≠5
Ko
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).
void bubble_sort(int X[], int n)
{
For (i=1;i<=n-1;i++)
For(j=0;j<n-i;j++)
If (X[j]>X[j+1])
{
Tg=X[j];
X[j]=X[j+1];
X[j+1]=tg;
}
}
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
Lần duyệt
X1
10
X2
65
X3
98
X4
5
X5
30
X6
78
X7
4
X8
45
X9
20
Giải thích
I=1
10
65
98
5
30
78
4
45
20
X1<x2
10
65
98
5
30
78
4
45
20
X2<x3
10
65
5
98
30
78
4
45
20
X3>x4=>đổi
10
65
5
30
98
78
4
45
20
X4>x5=>đổi
10
65
5
30
78
98
4
45
20
X5>x6=>đổi
10
65
5
30
78
4
98
45
20
X6>x7=>đổi
10
65
5
30
78
4
45
98
20
X7>x8=>đổi
10
65
5
30
78
4
45
20
98
X8>x9=>đổi
I=2
10
5
30
65
4
45
20
78
98
Tương tự với lần duyệt i=1
I=3
5
10
30
4
45
20
65
78
98
I=4
5
10
4
30
20
45
65
78
98
I=5
5
4
10
20
30
45
65
78
98
I=6
4
5
10
20
30
45
65
78
98
I=8
4
5
10
20
30
45
65
78
98
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).
Sắp xếp thêm dần:
Void sap_xep_tang_dan(int a[])
{
for(i=0;i<n;i++)
{
temp=a[i];
j=i-1;
while ((temp<a[j]) && (j>=0))
{
A[j+1]=A[j];
J=j-1;
}
A[j+1]=temp;
}
}
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
I
J
Temp
Dãy
Giải thích
0
-1
10
10 65 98 5 30 78 4 45 20
Lấy t=65 chèn vào X[1]
1
0
10
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).
void selection_sort(int a[], int n);
{
Int i,j;
Int tam;
For(i=1; i<=n-1;i++)
{
M=i;
For(j=i+1;j<=n;j++)
If(a[j] < a[m])
M=j;
If (m!=i)
{
// đổi chỗ a[i] và a[j]
Tam=a[i];
A[i]=a[j];
A[j]=tam;
}
}
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
Lần duyệt
X1
X2
X3
X4
X5
X6
X7
X8
X9
Giải thích
I=1
4
65
98
5
30
78
10
45
20
Duyệt từ x1=>x9, x7 min Đổi chỗ cho x1
I=2
4
5
98
65
30
78
10
45
20
Duyệt từ x2=>x9, x4 min
Dổi chỗ cho x2
I=3
4
5
10
65
30
78
98
45
20
Duyệt từ x3=>x9, x7 min đổi chỗ cho x3
I=4
4
5
10
20
30
78
98
45
65
Duyệt từ x4=>x9, x4 min không đổi chỗ
I=5
4
5
10
20
30
78
98
45
65
Giống TH i=4
I=6
4
5
10
20
30
45
98
78
65
Duyệt từ x6=>x9, x8 min
Dổi chỗ cho x6
I=7
4
5
10
20
30
45
65
78
98
Duyệt từ x7=>x9, x9 min
Dổi chỗ cho x7
I=8
4
5
10
20
30
45
65
78
98
Giống TH i=4
Bạn đang đọc truyện trên: AzTruyen.Top