đề cương CTDL-GT-01 tin(full đáp án)
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->phép tích cực thực hiện 2 lần
.
.
i=n->phép tích cực thực hiện n lầ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;
Giải:
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->phép tích cực lặp n lần
.
.
i=n->phép tích cực lặp n lầ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;
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
Khi i=1->phép tích cực thực hiện n-1 lần
i=2->phép tích cực thực hiện n-2 lần
.
.
i=n-1->phép tích cực thực hiện 1 lần
=>tống : 1+2 + 3+…+(n-3) + (n-2) + (n-1) = n(n-1)/2
Vậy 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 đó.
Giải:
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;
}
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,n-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(1,1))
= A(0,A(0,A(1,0) ) )
= A(0,A(0,A(0,1) ) )
= A(0,A(0,2) )
= A(0,3)
= 4
Thủ tục đệ quy
Int A(m,n)
{
If (m=0)
Return n+1;
Else
If (n=0)
Return A(m-1,n);
Else
Return A(m-1,A(m,n-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.
giải:
a.
s(10) = 10 + S(9)
= 10 + 9 + S(8)
= 10 + 9 + 8 + S(7)
= 10 + 9 + 8 + 7 + S(6)
= 10 + 9 + 8 + 7 + 6 + S(5)
= 10 + 9 + 8 + 7 + 6 + 5 + S(4)
= 10 + 9 + 8 + 7 + 6 + 5 + 4 + S(3)
= 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + S(2)
= 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + S(1)
= 55
b.
int S(n)
{
If (n=1)
Return 1;
Else
Reurn (n+S(n-1));
}
C.
Int S(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.
giải.
a.
f(2,3) = f(1,3) + f(2,2)
= f(0,3) + f(1,2) + f(1,2) + f(2,1)
Ta có
f(1,2) = f(0,2) + f(1,1)
= 2 + f(1,1) + f(0,1) + f(1,0)
= 2 + f(0,1) + f(1,0) + 1 + f(1,0) + 6
= 2 + 1 + f(1,0) + 6 + 1 + 6 + 6
= 2 + 1 + 6 + 6 + 1 + 6 + 6
= 28
f(0,3) = 3 + f(1,2)
= 3 + 28
= 31
f(2,1) = f(1,1) + f(2,0)
= f(0,1) + f(1,0) + 7
= 1 + f(1,0) + 6 + 7
= 1 + 6 + 6 + 7
= 20
ðf(2,3) = 31+ 28 + 28 + 20
= 107
b.
int f(m,n)
{
If(n<=0)
Return (m+50);
Else
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.
Giải:
-Khái niệm:
Hàng đợi là kiểu danh sách tuyến tính trong đó phép bổ sung một phần tử vào hàng đợi được thực hiện ở 1 đầu, gọi là lối sau (rear) và phép loại bỏ 1 phần tử được thực hiện ở đầu kia, gọi là lối trước (front)
-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.
//khai báo
#define max N
Struct queue
{
int dem;
Int front,rear;
Item e[max];
}
// bổ sung
Void addQ(struct queun *Q, item e[max])
{
if (q->dem==max)
printf(“hàng đầy”);
else
{
if (q->rear==max)
q->rear=1;
else q->rear=q->rear+1;
q->e[q->rear]=1;
q->dem=q->dem+1;
} }
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
Giải:
a.
b.
c.
d.
e.
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:
a.
b.
v[1] v[2]v[3 ] v[4] …………………………………………………………………………………………………………………………..v[31]
c.
duyệt theo thứ tự trước
+ / A + B C - * D * A – C D
Duyệt theo thứ tự giữa
A / B + C / + D * E - A * C - D
Duyệt theo thứ tự sau
A B C + / D E * A C D - * - +
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
giải
a.
duyệt theo thứ tự trước
ABDHCFGEI
Duyệt theo thứ tự giữa
HDBAFCEGI
Duyệt theo thứ tự sau
HDBFEIGCA
b.
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.
Giải:
a.
chen (nodep M, unyotype X)
{
N = (nodep malloc (sizeof (struct node))
N -> next := null;
If L := null;
L := N;
}
Else
{
N -> next := N;
}
b.
xoa (nodep L, node M)
{
nodep N
if L = null
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:
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.
Giải:
a.
Q(2,3) = 0
Q(14,3) = Q(11,3) + 1
= Q(8,3) + 1 + 1
= Q(5,3) + 1 + 1 + 1
= Q(2,3) + 1 + 1 + 1 + 1
= 4
b.
int Q(a,b)
{
If(a<b)
Return 0;
Else
If (a>=b)
Return (Q(a-b,b)+1);
}
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)?
Giải:
a.
giải thuật trên là giải thuật đệ quy
vì
trong thân chương trình nó có lời gọi ra chính nó. Fib = Fib(n-2) + Fib(n-1)
kích thước chương trình giảm F(n-1), F(n-2)
có trường hợp suy biến n<=2
b.
định nghĩa đệ quy:
Fib(n) =1 nếu n>=2
Fib(n-2) + Fib(n-2) nếu n<=2
c.
F(8) = F(7) + F(6)
= 2F(6) + F(5)
= 3F(5) + 2F(4)
= 5F(4) + 3F(3)
= 8F(3) + 5F(2)
= 13F(2) + 8F(1)
= 21
=> khi gọi Fib(8) 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. Vẽ hình minh họa biểu diễn cây bằng danh sách móc nối.
Giải:
a.
b.
duyệt theo thứ tự trước
+ / a + b c - * d e * a c
Duyệt theo thứ tự sau
A b c + / d e * a c * - +
C
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ố.
Giải:
b.
- Duyệt theo thứ tự trước
+ / 8 + 1 3 - * 6 5 * 4 2
- Duyệt theo thứ tự sau
8 1 3 + / 6 5 * 4 2 * - +
c.
X
S
E
8
∅
8
/
/
8
(
/ (
8
1
/ (
8 1
+
/ ( +
8 1
3
/ ( +
8 1 3
)
/
8 1 3 +
+
+
8 1 3 + /
6
+
8 1 3 + / 6
*
+ *
8 1 3 + / 6
5
+ *
8 1 3 + / 6 5
-
+ -
8 1 3 + / 6 5 *
4
+ -
8 1 3 + / 6 5 * 4
*
+ - *
8 1 3 + / 6 5 * 4
2
+ - *
8 1 3 + / 6 5 * 4 2
∅
∅
8 1 3 + / 6 5 * 4 2 - +
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ố.
giải:
a.
b.
duyệt theo thứ tự trước
- * - 5 2 + 4 3 / * 7 2 – 6 4
Duyệt theo thứ tự sau
5 2 – 4 3 + * 7 2 * 6 4 - / -
c.
X
S
5
5
2
5, 2
-
3
4
3,4
3
3,4,3
+
3,7
*
21
7
21,7
2
21,7,2
*
21,14
6
21,14,6
4
21,14,6,4
-
21,14,2
/
21,7
-
14
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.
Giải:
a.
biểu diễn bằng vecto liên tiếp
A
B
C
D
E
F
G
H
∅
I
∅
∅
∅
∅
∅
V[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] v[9] v[10] v[11] v[12] v[13] v[14] v[15]
Biểu diễn bằng danh sách móc nối
b.
Duyệt theo thứ tự trước
A B D H E I C F G
Duyệt theo thứ tự giữa
H D B I E A F C G
Duyệt theo thứ tự sau
H D I E B F G C A
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.
Giải:
a.
void A (nodep L)
{
Nodep P;
P = L;
If (L = null)
Printf (“ khong co giai tri ”);
Else
While (P!= null)
{
Printf (“%d”,P->info);
P = P-> next;
}
}
b.
int chen (node L,K,X)
if(L = null)
{
Nodep P; P = L;
Int i:=0;
While (i!=K)
{
P = P-> next;
i := i + 1;
}
Nodep N;
N = nodep;
{
Malloc (sizecf (structnode));
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.
Giải:
Int demnut(node L)
Nodep P;
Int i;
If(L=null)
Reurn();
Else
{
P=L;
I=0;
While (p!=null)
{
If(p->data>0)
{ i=i+1;}
P=P->next;
}
}return(D);
}
}
b.void tach(node L,node M)
{
Node P;
If(L==nulll)
Return();
Else
{
P=L;
While (P->next!=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 đó.
Giải:
a.
void cong (node L, nodep P, int A)
{
If(L = null)
Return -1;
{
P = L;
While (P!= null)
P-> data = P-> data + A;
P = P-> next;
}
}
b.
void dem nut (ndep P, nodep L, int i)
{
If(L = null)
Return (0);
}
Else
{
P = L;
I = 1;
While (P-> next != null)
P = P-> P-> next;
i := i + 1;
return (i);
}
}
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.
Giải:
a.
int dem(L)
{
Int K=0;
If(L==null)
Return(0);
Else
{
P=L;
While(P!=null)
}
If(P->data>0)
{
P=P->next;
K=K+1;
}
Return(K);
}
}
b.void Tb(L)
{
Float T=0 , D=0 ,Tb=0;
If(L==null)
Return(0);
Else
{
P=L;
While(P!=null)
{
P=p-> next;
T=T+P->data
D=D+1;
}Return(T/D);
}
}
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.
Giải
a, 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).
1, đếm số lần duyệt
For (i=1;i<=n-1;i++)
2.Duyệt dãy và chọn phần tử nhỏ nhất
Đặt m=i;// giải định Xi là phần tử nhỏ nhất
For (j=i+1;j<=n;j++)
If (Xj <Xi) m=j;
3.đổi chỗ Xm và Xi
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.
void find min (nodep L)
{
Nodep*;
P=L
Int VT,I;
If(L==null)
Return(0);
Else
{
P=L;
While (P!=null)
{
I=i+1;
If(p->data<min)
{VT=I;min=p->data;)
P=P->next
}
Printf(“phan tu min”);
Printf(“vit tri:%d,gia tri:%d”,VT,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.
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.
giải:
a.
void in(nodep L,infotype K)
{
Nodep;
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.
void sap xep (nodep L)
{
Nodep P;
Int tg,I,n=0;
If(L==null)
Return();
Else
{
P=L;
While(P!=null)
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.
Giải:
a.
phép toán tích cực nhất: i:=j
với i = 1-> phép tích cực lặp n lần
i = 2-> phép tích cực lặp n lần
.
.
i = n-> phép tích cực lặp n lần
=> tổng số lần lặp là n.n = n2
=> Tn = O(n2)
b.
S := 0;
For i :=1 to n do
S := S + A[i,i]
Độ phức tạp của thuật toán Tn = O(n)
Vì chỉ còn 1 vòng lặp for
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
GIẢI:
Mô tả thuật toán:
+ so sánh 2 khóa nhỏ nhất của 2 dãy X và Y, chon khóa nhỏ hơn đặt vào vị trí thích hợp trong dãy z, rồi lại khóa được chọn khỏi dãy chứa nó
+ quá trình như vậy cứ tiếp tục cho đến khi một trong 2 dãy đã hết khi đó chuyển hết phần đuôi của dãy còn lại vào dãy Z là xong
Giải thuật:
Void merging(X[],m,Y[],n,Z)
// KHỞI tạo các chỉ số
I=1, j=1, k=1
// chuyển các phần tử của dãy x,y vào dãy z
While (j<=m && j<=m)
{
If (x[i] < x[j])
{
Z[k]=x[i], i++,k++;
}
Else
{
Z[k]=y[i], j++,k++;
}
}
//một trong 2 mạch đã hết, chuyển đuôi của dãy còn lại và z
While(i<=m)
{
Z[k]=x[i], i++,k++;
}
While(j<=n)
{
Z[k]=y[i], j++,k++;
}
}
b,
A: 2 4 21 39 43 58 72 99 175
B: 1 6 41 59 65 80 172
I
J
K
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 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
Giải
Chọn khóa chốt là khóa trung tâm trong dãy đang xét
Giả sử cần sắp xếp 1 đoạn từ X left => X right trên dãy.
Để xđ vị trí các khóa cần đổi chỗ cho nhau, dùng 2 biến i và j để duyệt từ 2 đầu của dãy khóa
(1)Nếu left<right
I=left, j=right;
K=(left+right)/2
T=x[k];
(2)
Nếu Xi<t tăng i lên 1 và lặp lại quá trình đó
Nếu Xj>t giảm j đi 1 và ……
(3)Nếu i<=j thì đổi chỗ Xi và Xj
(4)quay lại bước 2 cho đến khi i>j thì dãy X được chia thành 3 dãy nếu vị trí chốt không thay đổi, ngược lại thành 2 dãy và kthúc lượt sxếp
Từ Xl => Xj là dãy gồm các phần tử < chốt
Từ Xi => Xr là dãy gồm các phần tử > chốt
Lượt
I
j
t
X1
X2
X3
X4
X5
X6
X7
GiảiThích
10
65
98
5
30
78
4
1
1
7
4
4
65
98
5
30
78
10
X1>x7->đổi chỗ x1 và x7
1
7
4
4
65
98
5
30
78
10
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
X2>x4 đổi chỗ x2 và x4
2
3
7
5
4
5
10
65
30
78
98
X3>x7 đổi chỗ x3 và x7
4
6
5
4
5
10
65
30
78
98
4
5
5
4
5
10
30
65
78
98
X4>x5->đổi chỗ x4 và x5
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
Giải:
Int tim kiem nhi phan (int a[ ], int n, int x)
{
Int left := 0;
Int right := n-1;
Int mid;
Do {
Mid := (left + right)/2;
If (x = a[mid])
Return mid;
Else
If (x < a[mid])
Right := mid -1;
Else left := mid + 1;
}
While (left = right)
}
Ví dụ
Root=30;
X=10<root => tkiem các phần tử bên trái của X
=>chọn root=10=X => là phần tử cần tìm kiếm
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
Giải:
a.
Int timkiemtuantu(X[],n,KH)
{
//khởi tạo
I=0;
//tìm khóa trong dãy
While (X[i] != KH && i<=m)
I=i+1;
//kiểm tra và trả về kết quả tìm kiếm
If (i<=n) return (i);
Else return (0);
}
b
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
Giải:
a, Ta dùng 2 biến i (chạy từ 1 =>n-1) và biến j (chạy từ 0=> n-i)
tức là thực hiện n-1 lần duyệt từ trái sang phải
Mỗi lần duyệt lần lượt so sánh các cặp phần tử liên tiếp
Nếu x[j]>x[j+1] thì đổi chỗ
b,
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).
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
Giải:
A, Sắp xếp thêm dần:
Để sx tăng dần dãy X có n phần tử X1,X2…Xn ta thực hiện n-1 lần chia dãy đích và dãy nguồn
-dãy đích gồm các phần tử X1=>Xi (với i=1 =>n-1);
-dãy nguồn gồm các phần tử Xi+1 => Xn
Mỗi lần chia lấy phần tử đầu dãy nguồn (là Xi+1 ) chèn vào vị trí thích hợp trong dãy đích
Void sxchen(int X,int n)
{
For (i=0;i<n;i++)
{
I=X[i+1];
J=i;
While (X[j] >0 && j>-1)
{X[j+1]=X[j];
j=j-1;
}
}
}
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
Giải:
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
Giải:
a, 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).
1, đếm số lần duyệt
For (i=1;i<=n-1;i++)
2.Duyệt dãy và chọn phần tử nhỏ nhất
Đặt m=i;// giải định Xi là phần tử nhỏ nhất
For (j=i+1;j<=n;j++)
If (Xj <Xi) m=j;
3.đổi chỗ Xm và Xi
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: truyentop.pro