15 trang 35 lượt tải

Đề Thi Kết Thúc Học Phần - Cấu Trúc Dữ Liệu & Giải Thuật | Đại học Kinh tế kỹ thuật công nghiệp

69

Viết giải thuật sắp xếp Bubble Sort để sắp xếp một dãy số nguyên theo thứ tự tăng dần. Cho một danh sách nối đơn lưu trữ các số nguyên, giả sử đầu của danh sách  được trỏ bởi con trỏ p. Hãy tìm một dãy con (không nhất thiết phải liên tiếp nhau) dài nhất có tổng các số chia hết cho số k = 3 (k nguyên dương). Tài liệu giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời đọc đón xem!

Môn: Cấu trúc dữ liệu và giải thuật (KTKTCN) 20 tài liệu

Trường: Đại học Kinh tế kỹ thuật công nghiệp 1.6 K tài liệu

Tác giả:

Profile

Mỹ Châu

2 tuần trước
Danh sách Quiz
/15
lOMoARcPSD| 40551442
TRƯỜNG ĐẠI HỌC ĐỀ THI KẾT THÚC HỌC PHẦN
KINH TẾ - KỸ THUẬT CÔNG NGHIỆP CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Hệ đào tạo: ĐẠI HỌC
KHOA CÔNG NGHỆ THÔNG TIN Thời gian làm bài: 90 phút, không kể thời gian phát đề
ĐỀ SỐ 1
Câu 1 (3 điểm)
a. Viết giải thuật sắp xếp Bubble Sort để sắp xếp một dãy số nguyên theo thứ
tựtăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau:
42, 27, 15, 29, 21, 68, 34, 18
42 27 15 29 21 68 34 18
42 27 15 29 21 68 18 34
42 27 15 29 21 18 68 34
42 27 15 29 18 21 68 34
42 27 15 18 29 21 68 34
42 15 27 18 29 21 68 34
15 42 27 18 29 21 68 34
15 42 27 18 29 21 34 68
15 42 27 18 21 29 34 68
15 42 18 27 21 29 34 68
15 18 42 27 21 29 34 68
15 18 42 21 27 29 34 68
15 18 21 42 27 29 34 68
15 18 21 27 42 29 34 68
15 18 21 27 29 42 34 68
15 18 21 27 29 34 42 68
20 37 25 39 11 5 14 15
20 37 25 39 5 11 14 15
20 37 25 5 39 11 14 15
20 37 5 25 39 11 14 15
20 5 37 25 39 11 14 15
5 20 37 25 39 11 14 15
lOMoARcPSD| 40551442
5 20 37 25 11 39 14 15
5 20 37 25 11 14 39 15
5 20 37 25 11 14 15 39
5 20 37 11 25 14 15 39
5 20 37 11 14 25 15 39
5 20 37 11 14 15 25 39
5 20 11 37 14 15 25 39
5 20 11 14 37 15 25 39
5 20 11 14 15 37 25 39
5 20 11 14 15 25 37 39
5 11 20 14 15 25 37 39
5 11 14 20 15 25 37 39
5 11 14 15 20 25 37 39
34 25 7 12 8 16 30 28
34 25 7 12 8 16 28 30
34 25 7 8 12 16 28 30
34 7 25 8 12 16 28 30
7 34 25 8 12 16 28 30
7 34 8 25 12 16 28 30
7 8 34 25 12 16 28 30
7 8 34 12 25 16 28 30
7 8 34 12 16 25 28 30
7 8 12 34 16 25 28 30
7 8 12 16 34 25 28 30
7 8 12 16 25 34 28 30
7 8 12 16 25 28 34 30
7 8 12 16 25 28 30 34
Câu 2 (3 điểm) Cho một danh sách nối đơn lưu trữ các số nguyên, giả sử đầu của danh
sách được trỏ bởi con trỏ p. Hãy viết thủ tục thực hiện các công việc sau:
a. Tạo nút cho danh sáchNodePtr node ; node = new NODE ; node->info
= x ;
b. Bổ sung một nút mới vào giữa danh sách.
lOMoARcPSD| 40551442
c. Tìm phần tử X trong danh sách.
Câu 3 (3 điểm) Cho một dãy A gồm các số nguyên như sau
6 11 5 10 15 20 2 7
Hãy tìm một dãy con (không nhất thiết phải liên tiếp nhau) dài nhất có tổng các số chia
hết cho số k = 3 (k nguyên dương).
a. Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng
phương án).
lOMoARcPSD| 40551442
8 1 2|7 0|8 1|7
c.
Câu 4 (1 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự giữa.
NLR :40,30,25,20,28,35,32,38,60,50,70,65,80
LNR :20,25,28,30,32,35,38,40,50,60,65,70,90
LRN :20,28,25,32,38,35,30,50,65,90,70,60,40
lOMoARcPSD| 40551442
N
TRƯỜNG ĐẠI HỌC ĐỀ THI KẾT THÚC HỌC PHẦN
KINH TẾ - KỸ THUẬT CÔNG NGHIỆP CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Hệ đào tạo: ĐẠI HỌC
KHOA CÔNG NGHỆ THÔNG TIN Thời gian làm bài: 90 phút, không kể thời gian phát đề
ĐỀ SỐ 2
Câu 1 (3 điểm)
a. Viết giải thuật sắp xếp Selection Sort để sắp xếp một dãy số nguyên theo thứtự
tăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau:
30, 47, 35, 49, 41, 31, 24, 28
Đẩy nhỏ nhất về đầu lần lượt
Đẩy vị trí cho nhau
30 47 35 49 41 31 24 28 24 47 35 49 41 31 30
28 24 28 35 49 41 31 30 47 24 28 30 49 41 31
35 47 24 28 30 31 41 49 35 47 24 28 30 31 35
49 41 47 24 28 30 31 35 41 49 47 24 28 30 31
35 41 47 49
5 37 26 15 8 14 22 5 8 26 15 37 14 22 5 8 14
15 37 26 22 5 8 14 15 22 26 37
Câu 2 (3 điểm) Cho một danh sách nối đơn lưu trữ các số nguyên, giả sử đầu của danh
sách được trỏ bởi con trỏ p. Hãy viết thủ tục thực hiện các công việc sau:
a. Tạo nút cho danh sách
NodePtr node ;
Node = new NODE ;
Node->info = x ;
b. Bổ sung một nút mới vào đầu danh sách.
c. Xóa nút cuối của danh sách.
lOMoARcPSD| 40551442
Câu 3 (3 điểm) Cho một dãy A gồm các số nguyên như sau
2 3 5 7 9 6 12 7
Hãy tìm một dãy con (không nhất thiết phải liên tiếp nhau) dài nhất có tổng các số chia
hết cho số k = 5 (k nguyên dương).
a. Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng
phương án, Truy vết).
b. Viết giải thuật truy vết của bài toán trên.
Câu 4 (1 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự sau.
TRƯỜNG ĐẠI HỌC ĐỀ THI KẾT THÚC HỌC PHẦN
KINH TẾ - KỸ THUẬT CÔNG NGHIỆP CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Hệ đào tạo: ĐẠI HỌC
KHOA CÔNG NGHỆ THÔNG TIN Thời gian làm bài: 90 phút, không kể thời gian phát đề
ĐỀ SỐ 3
Câu 1 (3 điểm)
a. Viết giải thuật sắp xếp Insertion Sort để sắp xếp một dãy số nguyên theo thứtự
tăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau:
30, 47, 35, 49, 21, 22, 24, 15
Đưa số nhỏ nhất rồi đẩy các số sau
30 47 35 49 21 22 24 15
30 35 47 49 21 22 24 15
21 30 35 47 49 22 24 15
lOMoARcPSD| 40551442
21 22 30 35 47 49 24 15
21 22 24 30 35 47 49 15
15 21 22 24 30 35 47 49
25 16 9 37 12 18 4 22
16 25 9 37 12 18 4 22
9 16 25 37 12 18 4 22
9 12 16 25 37 18 4 22
9 12 16 18 25 37 4 22
4 9 12 16 18 25 37 22
4 9 12 16 18 22 25 37
Câu 2 (3 điểm) Cho một danh sách nối vòng có nút cuối được trỏ bởi pList lưu trữ các
số nguyên.
a. Cài đặt danh sách trên.
Void Init ( NodePtr &pList)
{
*pList = NULL;
}
a. Hãy bổ sung một nút mới với thông tin X vào cuối danh sách.
b.
lOMoARcPSD| 40551442
Hiển thị danh sách sau khi thêm nút X.
lOMoARcPSD| 40551442
c. Hãy bổ sung một nút mới với thông tin X vào cuối danh sách.
d. Hiển thị danh sách sau khi thêm nút X.
Câu 3 (3 điểm) Cho một balo khối lượng W=9. Có 5 đồ vật lần lượt như sau: Giá trị
C[i] = {3, 5, 6, 4, 1}; khối lượng A[i] = {3, 4, 5, 2, 1}. Hãy chọn các đồ vật để cho vào
ba lô sao cho các đồ vật được chọn có giá trị lớn nhất và khối lượng không vượt quá
khối lượng balo. Mỗi đồ vật có thể được chọn nhiều lần.
a. Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng
phương án, Truy vết).
b. Viết giải thuật truy vết của bài toán trên.
Câu 4 (1 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự sau.
TRƯỜNG ĐẠI HỌC ĐỀ THI KẾT THÚC HỌC PHẦN
KINH TẾ - KỸ THUẬT CÔNG NGHIỆP CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Hệ đào tạo: ĐẠI HỌC
KHOA CÔNG NGHỆ THÔNG TIN Thời gian làm bài: 90 phút, không kể thời gian phát đề
ĐỀ SỐ 4
Câu 1 (3 điểm)
a. Viết giải thuật sắp xếp Bubble Sort để sắp xếp một dãy số nguyên theo thứ tự
tăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau:
20, 37, 25, 39, 11, 5, 14, 15
lOMoARcPSD| 40551442
Câu 2 (3 điểm) Cho một danh sách nối vòng có nút cuối được trỏ bởi pList lưu trữ các
số nguyên.
a. Cài đặt danh sách trên.
b. Hãy bổ sung một nút mới với thông tin X vào cuối danh sách.
c. Xóa nút đầu danh sách.
Câu 3 (3 điểm) Cho một balo khối lượng W=15. Có 5 đồ vật lần lượt như sau: Giá trị
C[i] = {4, 2, 1, 2, 10}; khối lượng A[i] = {12, 2, 1, 1, 4}. Hãy chọn các đồ vật để cho
vào ba lô sao cho các đồ vật được chọn có giá trị lớn nhất và khối lượng không vượt quá
khối lượng balo. Mỗi vật chỉ được chọn một lần
Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng phương
án, Truy vết).
c. Viết giải thuật truy vết của bài toán trên.
Câu 4 (1 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự giữa.
lOMoARcPSD| 40551442
TRƯỜNG ĐẠI HỌC ĐỀ THI KẾT THÚC HỌC PHẦN
KINH TẾ - KỸ THUẬT CÔNG NGHIỆP CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Hệ đào tạo: ĐẠI HỌC
KHOA CÔNG NGHỆ THÔNG TIN Thời gian làm bài: 90 phút, không kể thời gian phát đề
ĐỀ SỐ 5
Câu 1 (3 điểm)
a. Viết giải thuật sắp xếp Heap Sort để sắp xếp một dãy số nguyên theo thứ tự tăngdần.
b. Minh họa giải thuật trên với dãy số đã cho sau:
40 30 50 22 60 55 77 65
Câu 2 (3 điểm) Cho một danh sách nối vòng có nút cuối được trỏ bởi pList lưu trữ các
số nguyên.
a. Cài đặt danh sách trên.
Void Init ( NodePtr &pList )
{
}
b. Hãy bổ sung một nút mới với thông tin X vào đầu danh sách.
c. Xóa nút ở vị trí giữa của danh sách.
Câu 3 (2 điểm) Cho một balo khối lượng W=13. Có 5 đồ vật lần lượt như sau: Giá trị
C[i] = {4, 5, 6, 3, 1}; khối lượng A[i] = {3, 4, 5, 2, 1}. Hãy chọn các đồ vật để cho vào
ba lô sao cho các đồ vật được chọn có giá trị lớn nhất và khối lượng không vượt quá
khối lượng balo. Mỗi vật chỉ được chọn một lần
lOMoARcPSD| 40551442
Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng phương
án, Truy vết).
Câu 4 (2 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự giữa.
Ptree
( 1 đ )
Quicksort
0 1 2 3 4 5 6 7 (j)
12 2 8 5 1 6 4 15
0 1 2 3 4 5 6 7 (i)
lOMoARcPSD| 40551442
I = left , j = right k = ( left +
right) / 2 = 0+7=3 ak =
a[3] = 5
i=0 , j = 7 => a[0] = 12 > 5 , a[7]=15 > 5
=>I = 0 , j-- = 6
I=0 , j = 6=> a[0] = 12 > 5
, a[6] = 4 < 5 ( a[i] > x ,
a[j] < x ) đổi chỗ đổi
chỗ a[0] , a[6]
I = 1 , j = 5 => A[1] = 2 < 5 ,
a[5] = 6 > 5 i++ , j—
I =2 , j = 4 => A[2] = 8 > 5 ,
a[4] = 1 < 5 =>đổi chỗ a[2] ,
a[4]
I=3,j=3 => dừng
Dãy cũ : 12 2 8 5 1 6 4 15
lOMoARcPSD| 40551442
Dãy mới : 4 2 1 5 8 6 12 15
4 2 1 : dãy 1 , 8 6 12 15 : dãy 2
Quy hoạch dãy 1 : 4 2 1
0 1 2
K1= ( left+right)/2 = 1
A[k1] = a[1] = 2
I = 0 , j = 2 =>
A[0] = 4 > 2, a[2] = 1 < 2
đổi chỗ a[0] với a[2] dãy
mới : 1 2 4
Quy hoạch dãy 2 : 8 6 12 15
0 1 2 3
K2 = …. = 1
A[k2] = a[1] = 6
I = 0 , j =3 => A[0] = 8 > 6 ,
a[3] = 15 > 6 I = 0 ; j—
I = 0 , j = 2 => A[0] = 8 > 6,
a[2] = 12 >6 I = 0 ; j—
lOMoARcPSD| 40551442
I = 0 , j = 1=> A[0] = 8 > 6 ,
a[1] = 6 = 6 =>đổi chỗ a[0]
và a[1]
Dãy mới : 6 8 12 15
Vậy dãy là 1 2 4 5 6 8 12 15

Tài liệu khác của Đại học Kinh tế kỹ thuật công nghiệp

Preview text:

lOMoAR cPSD| 40551442 TRƯỜNG ĐẠI HỌC
ĐỀ THI KẾT THÚC HỌC PHẦN
KINH TẾ - KỸ THUẬT CÔNG NGHIỆP
CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Hệ đào tạo: ĐẠI HỌC
KHOA CÔNG NGHỆ THÔNG TIN
Thời gian làm bài: 90 phút, không kể thời gian phát đề ĐỀ SỐ 1 Câu 1 (3 điểm)
a. Viết giải thuật sắp xếp Bubble Sort để sắp xếp một dãy số nguyên theo thứ tựtăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau:
42, 27, 15, 29, 21, 68, 34, 18 42 27 15 29 21 68 34 18 42 27 15 29 21 68 18 34 42 27 15 29 21 18 68 34 42 27 15 29 18 21 68 34 42 27 15 18 29 21 68 34 42 15 27 18 29 21 68 34 15 42 27 18 29 21 68 34 15 42 27 18 29 21 34 68 15 42 27 18 21 29 34 68 15 42 18 27 21 29 34 68 15 18 42 27 21 29 34 68 15 18 42 21 27 29 34 68 15 18 21 42 27 29 34 68 15 18 21 27 42 29 34 68 15 18 21 27 29 42 34 68 15 18 21 27 29 34 42 68 20 37 25 39 11 5 14 15 20 37 25 39 5 11 14 15 20 37 25 5 39 11 14 15 20 37 5 25 39 11 14 15 20 5 37 25 39 11 14 15 5 20 37 25 39 11 14 15 lOMoAR cPSD| 40551442 5 20 37 25 11 39 14 15 5 20 37 25 11 14 39 15 5 20 37 25 11 14 15 39 5 20 37 11 25 14 15 39 5 20 37 11 14 25 15 39 5 20 37 11 14 15 25 39 5 20 11 37 14 15 25 39 5 20 11 14 37 15 25 39 5 20 11 14 15 37 25 39 5 20 11 14 15 25 37 39 5 11 20 14 15 25 37 39 5 11 14 20 15 25 37 39 5 11 14 15 20 25 37 39 34 25 7 12 8 16 30 28 34 25 7 12 8 16 28 30 34 25 7 8 12 16 28 30 34 7 25 8 12 16 28 30 7 34 25 8 12 16 28 30 7 34 8 25 12 16 28 30 7 8 34 25 12 16 28 30 7 8 34 12 25 16 28 30 7 8 34 12 16 25 28 30 7 8 12 34 16 25 28 30 7 8 12 16 34 25 28 30 7 8 12 16 25 34 28 30 7 8 12 16 25 28 34 30 7 8 12 16 25 28 30 34
Câu 2 (3 điểm) Cho một danh sách nối đơn lưu trữ các số nguyên, giả sử đầu của danh
sách được trỏ bởi con trỏ p. Hãy viết thủ tục thực hiện các công việc sau:
a. Tạo nút cho danh sáchNodePtr node ; node = new NODE ; node->info = x ;
b. Bổ sung một nút mới vào giữa danh sách. lOMoAR cPSD| 40551442
c. Tìm phần tử X trong danh sách.
Câu 3 (3 điểm) Cho một dãy A gồm các số nguyên như sau 6 11 5 10 15 20 2 7
Hãy tìm một dãy con (không nhất thiết phải liên tiếp nhau) dài nhất có tổng các số chia
hết cho số k = 3 (k nguyên dương).
a. Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng phương án). lOMoAR cPSD| 40551442 8 1 2|7 0|8 1|7 c.
Câu 4 (1 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự giữa.
NLR :40,30,25,20,28,35,32,38,60,50,70,65,80
LNR :20,25,28,30,32,35,38,40,50,60,65,70,90
LRN :20,28,25,32,38,35,30,50,65,90,70,60,40 lOMoAR cPSD| 40551442 N TRƯỜNG ĐẠI HỌC
ĐỀ THI KẾT THÚC HỌC PHẦN
KINH TẾ - KỸ THUẬT CÔNG NGHIỆP
CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Hệ đào tạo: ĐẠI HỌC
KHOA CÔNG NGHỆ THÔNG TIN
Thời gian làm bài: 90 phút, không kể thời gian phát đề ĐỀ SỐ 2 Câu 1 (3 điểm)
a. Viết giải thuật sắp xếp Selection Sort để sắp xếp một dãy số nguyên theo thứtự tăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau:
30, 47, 35, 49, 41, 31, 24, 28
Đẩy nhỏ nhất về đầu lần lượt Đẩy vị trí cho nhau
30 47 35 49 41 31 24 28 24 47 35 49 41 31 30
28 24 28 35 49 41 31 30 47 24 28 30 49 41 31
35 47 24 28 30 31 41 49 35 47 24 28 30 31 35
49 41 47 24 28 30 31 35 41 49 47 24 28 30 31 35 41 47 49
5 37 26 15 8 14 22 5 8 26 15 37 14 22 5 8 14
15 37 26 22 5 8 14 15 22 26 37
Câu 2 (3 điểm) Cho một danh sách nối đơn lưu trữ các số nguyên, giả sử đầu của danh
sách được trỏ bởi con trỏ p. Hãy viết thủ tục thực hiện các công việc sau: a. Tạo nút cho danh sách NodePtr node ; Node = new NODE ; Node->info = x ;
b. Bổ sung một nút mới vào đầu danh sách.
c. Xóa nút cuối của danh sách. lOMoAR cPSD| 40551442
Câu 3 (3 điểm) Cho một dãy A gồm các số nguyên như sau 2 3 5 7 9 6 12 7
Hãy tìm một dãy con (không nhất thiết phải liên tiếp nhau) dài nhất có tổng các số chia
hết cho số k = 5 (k nguyên dương).
a. Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng phương án, Truy vết).
b. Viết giải thuật truy vết của bài toán trên.
Câu 4 (1 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự sau. TRƯỜNG ĐẠI HỌC
ĐỀ THI KẾT THÚC HỌC PHẦN
KINH TẾ - KỸ THUẬT CÔNG NGHIỆP
CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Hệ đào tạo: ĐẠI HỌC
KHOA CÔNG NGHỆ THÔNG TIN
Thời gian làm bài: 90 phút, không kể thời gian phát đề ĐỀ SỐ 3 Câu 1 (3 điểm)
a. Viết giải thuật sắp xếp Insertion Sort để sắp xếp một dãy số nguyên theo thứtự tăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau:
30, 47, 35, 49, 21, 22, 24, 15
Đưa số nhỏ nhất rồi đẩy các số sau 30 47 35 49 21 22 24 15 30 35 47 49 21 22 24 15 21 30 35 47 49 22 24 15 lOMoAR cPSD| 40551442 21 22 30 35 47 49 24 15 21 22 24 30 35 47 49 15 15 21 22 24 30 35 47 49 25 16 9 37 12 18 4 22 16 25 9 37 12 18 4 22 9 16 25 37 12 18 4 22 9 12 16 25 37 18 4 22 9 12 16 18 25 37 4 22 4 9 12 16 18 25 37 22 4 9 12 16 18 22 25 37
Câu 2 (3 điểm) Cho một danh sách nối vòng có nút cuối được trỏ bởi pList lưu trữ các số nguyên.
a. Cài đặt danh sách trên.
Void Init ( NodePtr &pList) { *pList = NULL; }
a. Hãy bổ sung một nút mới với thông tin X vào cuối danh sách. b. lOMoAR cPSD| 40551442
Hiển thị danh sách sau khi thêm nút X. lOMoAR cPSD| 40551442
c. Hãy bổ sung một nút mới với thông tin X vào cuối danh sách.
d. Hiển thị danh sách sau khi thêm nút X.
Câu 3 (3 điểm) Cho một balo khối lượng W=9. Có 5 đồ vật lần lượt như sau: Giá trị
C[i] = {3, 5, 6, 4, 1}; khối lượng A[i] = {3, 4, 5, 2, 1}. Hãy chọn các đồ vật để cho vào
ba lô sao cho các đồ vật được chọn có giá trị lớn nhất và khối lượng không vượt quá
khối lượng balo. Mỗi đồ vật có thể được chọn nhiều lần.
a. Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng phương án, Truy vết).
b. Viết giải thuật truy vết của bài toán trên.
Câu 4 (1 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự sau. TRƯỜNG ĐẠI HỌC
ĐỀ THI KẾT THÚC HỌC PHẦN
KINH TẾ - KỸ THUẬT CÔNG NGHIỆP
CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Hệ đào tạo: ĐẠI HỌC
KHOA CÔNG NGHỆ THÔNG TIN
Thời gian làm bài: 90 phút, không kể thời gian phát đề ĐỀ SỐ 4 Câu 1 (3 điểm)
a. Viết giải thuật sắp xếp Bubble Sort để sắp xếp một dãy số nguyên theo thứ tự tăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau: 20, 37, 25, 39, 11, 5, 14, 15 lOMoAR cPSD| 40551442
Câu 2 (3 điểm) Cho một danh sách nối vòng có nút cuối được trỏ bởi pList lưu trữ các số nguyên.
a. Cài đặt danh sách trên.
b. Hãy bổ sung một nút mới với thông tin X vào cuối danh sách.
c. Xóa nút đầu danh sách.
Câu 3 (3 điểm) Cho một balo khối lượng W=15. Có 5 đồ vật lần lượt như sau: Giá trị
C[i] = {4, 2, 1, 2, 10}; khối lượng A[i] = {12, 2, 1, 1, 4}. Hãy chọn các đồ vật để cho
vào ba lô sao cho các đồ vật được chọn có giá trị lớn nhất và khối lượng không vượt quá
khối lượng balo. Mỗi vật chỉ được chọn một lần
Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng phương án, Truy vết).
c. Viết giải thuật truy vết của bài toán trên.
Câu 4 (1 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự giữa. lOMoAR cPSD| 40551442 TRƯỜNG ĐẠI HỌC
ĐỀ THI KẾT THÚC HỌC PHẦN
KINH TẾ - KỸ THUẬT CÔNG NGHIỆP
CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Hệ đào tạo: ĐẠI HỌC
KHOA CÔNG NGHỆ THÔNG TIN
Thời gian làm bài: 90 phút, không kể thời gian phát đề ĐỀ SỐ 5 Câu 1 (3 điểm)
a. Viết giải thuật sắp xếp Heap Sort để sắp xếp một dãy số nguyên theo thứ tự tăngdần.
b. Minh họa giải thuật trên với dãy số đã cho sau: 40 30 50 22 60 55 77 65
Câu 2 (3 điểm) Cho một danh sách nối vòng có nút cuối được trỏ bởi pList lưu trữ các số nguyên.
a. Cài đặt danh sách trên.
Void Init ( NodePtr &pList ) { }
b. Hãy bổ sung một nút mới với thông tin X vào đầu danh sách.
c. Xóa nút ở vị trí giữa của danh sách.
Câu 3 (2 điểm) Cho một balo khối lượng W=13. Có 5 đồ vật lần lượt như sau: Giá trị
C[i] = {4, 5, 6, 3, 1}; khối lượng A[i] = {3, 4, 5, 2, 1}. Hãy chọn các đồ vật để cho vào
ba lô sao cho các đồ vật được chọn có giá trị lớn nhất và khối lượng không vượt quá
khối lượng balo. Mỗi vật chỉ được chọn một lần lOMoAR cPSD| 40551442
Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng phương án, Truy vết).
Câu 4 (2 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự giữa. Ptree ( 1 đ ) Quicksort 0 1 2 3 4 5 6 7 (j) 12 2 8 5 1 6 4 15 0 1 2 3 4 5 6 7 (i) lOMoAR cPSD| 40551442
I = left , j = right k = ( left + right) / 2 = 0+7=3 ak = a[3] = 5
i=0 , j = 7 => a[0] = 12 > 5 , a[7]=15 > 5 =>I = 0 , j-- = 6
I=0 , j = 6=> a[0] = 12 > 5
, a[6] = 4 < 5 ( a[i] > x ,
a[j] < x ) đổi chỗ đổi chỗ a[0] , a[6]
I = 1 , j = 5 => A[1] = 2 < 5 , a[5] = 6 > 5 i++ , j—
I =2 , j = 4 => A[2] = 8 > 5 ,
a[4] = 1 < 5 =>đổi chỗ a[2] , a[4] I=3,j=3 => dừng Dãy cũ : 12 2 8 5 1 6 4 15 lOMoAR cPSD| 40551442
Dãy mới : 4 2 1 5 8 6 12 15
4 2 1 : dãy 1 , 8 6 12 15 : dãy 2 Quy hoạch dãy 1 : 4 2 1 0 1 2 K1= ( left+right)/2 = 1 A[k1] = a[1] = 2 I = 0 , j = 2 =>
A[0] = 4 > 2, a[2] = 1 < 2
đổi chỗ a[0] với a[2] dãy mới : 1 2 4
Quy hoạch dãy 2 : 8 6 12 15 0 1 2 3 K2 = …. = 1 A[k2] = a[1] = 6
I = 0 , j =3 => A[0] = 8 > 6 , a[3] = 15 > 6 I = 0 ; j—
I = 0 , j = 2 => A[0] = 8 > 6, a[2] = 12 >6 I = 0 ; j— lOMoAR cPSD| 40551442
I = 0 , j = 1=> A[0] = 8 > 6 ,
a[1] = 6 = 6 =>đổi chỗ a[0] và a[1] Dãy mới : 6 8 12 15
Vậy dãy là 1 2 4 5 6 8 12 15

Tài liệu liên quan: