CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
1.
K[]={18,12,6,13,9,14,7,15,8,18,9,25,5,11,13,17} 16 phần tử.
a. Trình bầy Bubble Sort sắp xếp dãy khoá K[] theo thứ tự tăng dần?
b. Áp dụng,ghi kết quả mỗi bước.
2.
Cho đồ thị vô hướng G=<V,E> thực hiện
a. Biến đổi đồ thị G dưới dạng ma trận kề.
b. Biến đổi đồ thị G dưới dạng danh sách cạnh.
c. Biến đổi đồ thị dưới dạng danh sách kề.
3.
a. Định nghiã hàng đợi. Các thao tác trên hàng đợi.
b. Xây dựng thuật toán duyệt các đỉnh cuả đồ thị vào hàng đợi.
c. Kiểm nghiệm thuật toán bắt đầu tại đỉnh u=5 và u=10 cho đồ thị được biểu diễn dưới dạng
ma trận kề, chỉ rõ kả các bước thực hiện cuả thuật toán.
0100110000000
1000110000000
0001001000100
0010101100100
1101010000000
1100100000000
0011000100000
0001001000100
0000000001011
0000000010011
0011000100010
1
2
7
8
11
13
10
6
3
4
5
9
12
1
0000000011101
0000000011010
G=<V,E>
2
4.
a. Định nghĩa ngăn xếp; các thao tác ngăn xếp.
b. Xây dựng thuật toán duyệt các đỉnh cuả đồ thị dựa vào ngăn xếp.
c. Kiểm nghiệm thuật toán bắt đầu tại đỉnh u=4 và u=13 cho đồ thị được biểu diễn dưới dạng
ma trận kề ở hình. Chỉ rõ jết quả trung gian mỗi bước thực hiện cuả thuật toán.
0100110000000
1000110000000
0001001000100
0010101100100
1101010000000
1100100000000
0011000100000
0001001000100
0000000001011
0000000010011
0011000100010
0000000011101
0000000011010
G=<V,E>
3
KỸ THUẬT LẬP TRÌNH
1. Cho đoạn chương trình sau:
4
#include <stdio.h>
#include <conio.h>
int X[10], chuaxet[10], n, count;
void Int(void)
{
n=4;
count=0;
for (int i=1;i<=n;i++)chuaxet[i]=1;
}
void Result(void)
{
printf("\n Ket qua buoc %d: ",++count);
for (i=1;i<=n;i++)
printf("%3d",X[i]);
}
void Try(int i)
{
for (int j=1;j<=n;j++)
{
if(chuaxet[j])
{
X[i]=j;
chuaxet[j]=0;
if(i==n) Result();
else Try(i+1);
chuaxet[j]=1;
}
}
}
void main(void)
{
Int();
Try(1);
}
- Cho biết kết quả thực hiện đoạn chương trình.
5