Ôn tập

Cấu trúc dữ liệu & giải thuật

Nội dung

• Phần đánh giá cuối khoá • Độ phức tạp của giải thuật • Tìm kiếm & sắp xếp • Danh sách liên kết • Stack & queue • Cấu trúc cây

Đánh giá cuối khoá

• Thực hành: 30% tổng số điểm

– Thực hiện các bài tập 1, 2, 3 và 4

• Lý thuyết: 70% tổng số điểm – 40 câu trắc nghiệm tổng quát

Đánh giá cuối khoá

Nội dung Số câu hỏi

Độ phức tạp 2

Sắp xếp và tìm kiếm 7

Danh sách liên kết đơn 8

Danh sách liên kết vòng, kép 4

Stack & queue 3

Cấu trúc cây 2

Cây nhị phân 3

Cây nhị phân tìm kiếm 5

Cây AVL 3

Cây đa phân tìm kiếm( top-down và BTree) 3

40 Tổng cộng

Độ phức tạp của giải thuật

• Thời gian thực hiện GT

– Giải thuật – Tập chỉ thị của máy tính – Cấu hình của máy tính – Kỹ năng của người lập trình

• Dựa trên sự thực thi • Thời gian thực hiện của chương trình là

hàm theo kích thước dữ liệu vào n.

Độ phức tạp của giải thuật

• Đơn vị của T(n) : theo số lệnh được thực

hiện.

• T(n) = Cn thì CT cần Cn chỉ thị thực thi • Thời gian thực hiện xấu nhất: do tính chất

dữ liệu cũng ảnh hưởng – Chương trình sắp xếp sẽ cho thời gian khác nhau với các bộ DL có thứ tự khác nhau! •  T(n) thường được xem là TG chương trình thực hiện xấu nhất trên DL kích thước n.

Độ phức tạp giải thuật

T2(n) = 5n3

T1(n) = 100n2

• Khi n đủ lớn: n > 20, thì T1(n) < T2(n) • Cách hợp lý nhất là xét tỷ suất tăng của hàm TG thực hiện CT thay vì chính bản thân thời gian thực hiện.

Tỉ suất tăng

• Hàm ko âm T(n) có tỉ xuất tăng f(n) nếu tồn tại các hằng số C và N0 sao cho: – T(n) < Cf(n), với mọi n ≥ N0 – “cho hàm ko âm T(n) bất kỳ, ta luôn tìm được

tỷ suất tăng f(n) của nó”

• Giả sử T(0) =1, T(1) = 4, tổng quát

T(n) = (n+1)2.

– Đặt N0 = 1, và C = 4, thì  n ≥ 1, chứng minh được rằng T(n) = (n+1)2 ≤ 4n2,  n ≥ 1, tỉ suất tăng khi đó n2

Độ phức tạp giải thuật

• Cho hàm T(n), T(n) có độ phức tạp f(n) nếu tồn tại các hằng C, N0 sao cho: – T(n) ≤ Cf(n) với mọi n ≥ N0 (tức là T(n) có tỉ suất tăng là f(n) và ký hiệu T(n) là O(f(n)) – VD: T(n) = (n+1)2 có tỷ suất tăng là n2 nên

T(n) = (n+1)2 là O(n2).

– Lưu ý: O(Cf(n)) = O(f(n)) với C là hằng số.

O(C) = O(1).

• Nói cách khác độ phức tạp tính toán giải thuật là hàm chặn trên của hàm thời gian

Qui tắc tính độ phức tạp

• Thời gian thực hiện lệnh gán, đọc/ghi dữ liệu là

O(1).

• Thời gian thực hiện một chuỗi tuần tự các lệnh

được xác định bằng quy tắc cộng.

• Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện sau THEN hoặc ELSE và thời gian điều kiện. Thường thời gian điều kiện là O(1).

Qui tắc tính độ phức tạp

• Thời gian thực hiện vòng lặp là tổng thời

gian thực hiện thân vòng lặp. – Tích số lần lặp với thời gian thực hiện vòng

lặp

• Qui tắc cộng

– T1(n) và T2(n) là thời gian thực hiện của hai

đoạn chương trình P1 và P2, và T1(n)= O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện của hai đoạn chương trình đó nối tiếp nhau là T(n)= O(max(f(n), g(n)))

Qui tắc tính độ phức tạp

• Qui tắc nhân:

– Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn chương trình P1và P2 và T1(n) = O(f(n)), T2(n) = O(g(n))

– Thời gian thực hiện của đoạn hai đoạn chương

trình đó lồng nhau là T(n) = O(f(n).g(n))

VD tính độ phức tạp

• VD giải thuật sắp xếp nổi bọt

if (a[j-1] > a[j]){

temp = a[j-1]; a[j-1] = a[j]; a[j] = temp;

– (1) for(i = 0; i < n-1; i++) for(j=n-1; j >i; j--) – (2) – (3) – (4) – (5) – (6) – (7)

}

VD tính độ phức tạp

• VD hàm tìm kiếm tuần tự

i=0; found = false; while ( i

found = true;

else

i++;

– (1) – (2) – (3) – (4) – (5) – (6) – (7) – (8)

return found;

Câu hỏi

1.

A.

nlogn

B. logn

C. n

D. n2

Giải thuật tìm kiếm nhị phân trên một mảng dữ liệu số nguyên với kích thước là n có độ phức tạp là

2.

A. B. C. D.

Trường hợp tốt nhất Trường hợp trung bình Trường hợp xấu nhất Không xác định

Khi tính thời gian thực hiện của một giải thuật, người ta thường dùng trường hợp nào để so sánh

3.

A.

logn

B. nlogn

C. N2

D. n

Có 3 lệnh thực thi tuần tự I1, I2 và I3, độ phức tạp O(I1) = 1, O(I2) = logn và O(l3) = n2. Độ phức tạp của khi 3 lệnh thực thi tuần tự là

4.

A.

nlogn

B. logn

C. n2

C.n

Có 2 nhóm lệnh I1 và I2, độ phức tạp O(l1) = logn và O(l2) = O(1). Lệnh l1 thực thi n lần, mỗi lần gọi thực thi l2. Độ phức tạp là

Tìm kiếm

• Tìm kiếm tuyến tính

– Trên tập dữ liệu bất kỳ, vét cạn – Kết thúc khi tìm thấy hoặc ko tìm thấy (đến

cuối mảng)

• Tìm kiếm nhị phân

– Trên mảng được sắp – Độ phức tạp là logn

Sắp xếp

Interchange Sort

1. Selection Sort Insertion Sort 2. 3. Bubble Sort 4. 5. Shell sort 6. Quick sort 7. Radix...

Câu hỏi

1.

C. 4

D. 5

2.

B. 10 8 6 C. 10 8

D. 10 6 8

3.

D. 14

C. 10

B. 11

4.

Cho một mảng n = 8 số nguyên được sắp: 2 5 9 12 21 33 50 66, áp dụng giải thuật tìm kiếm nhị phân để tìm phần tử có giá trị 33 thì cần bao nhiêu lần so sánh khóa A. 2 B. 3 Cho một mảng n = 10 số nguyên được sắp: 4 6 8 9 10 14 18 22 25 30, áp dụng giải thuật tìm kiếm nhị phân để tìm phần tử có khóa là 8 thì các giá trị lần lượt được so sánh là A. 10 9 8 Cho mảng số nguyên n = 10 phần tử sắp tăng: 3 7 10 11 14 17 20 25 28 34, sử dụng thuật giải tìm kiếm nhị phân để tìm phần tử có khoá là 9 thì giải thuật kết thúc không tìm thấy khi so sánh với phần tử nào trong mảng A. 7 Cho mảng số nguyên n = 8 phần tử thứ tự như sau: 12 2 8 5 1 6 4 15, sử dụng giải thuật chọn để sắp xếp thì tại lượt thứ 3 thì trạng thái sắp xếp của mảng là: A. 2 12 8 5 1 6 4 15 B. 1 2 8 5 12 6 4 15 C. 1 2 5 8 12 6 4 15 D. 1 2 4 5 12 6 8 15

Câu hỏi

5. Cho mảng n = 8 phần tử: 10 3 7 6 2 5 4 16, áp dụng phương pháp chèn trực tiếp, ở lượt thứ 3 thì trạng thái của mảng là: A. 2 3 5 4 10 7 6 16 B. 2 3 4 10 7 6 5 16 C. 2 3 4 7 10 6 5 16 D. 2 3 4 7 10 5 6 16

Câu hỏi

6. Cho mảng n = 8 phần tử: 10 3 7 6 2 5 4 16, sử dụng

phương pháp shellsort, với h=3, kết quả sau khi áp dụng trạng thái mảng là

A. 2 3 4 7 6 5 10 16

B. 2 5 3 4 7 6 10 16 C. 4 2 5 6 3 7 10 16 D. 4 2 6 5 3 7 10 16

7. Cho mảng n = 9, 493 812 715 710 195 437 582 340 385, sử dụng RadixSort, kết quả sau khi phân lô hàng chục là

A. 710 340 812 582 493 715 195 385 437 B. 710 812 715 437 340 582 385 493 195 C. 195 812 715 437 340 582 385 493 710 D. 437 812 710 195 340 582 385 493 715

8. Phương pháp sắp xếp nào không cần so sánh giá trị

khóa của các phần tử A. Quicksort B. Shellsort C. InterchangeSort D. RadixSort

9. Cho hàm InsertionSort không đầy đủ

x = a[i]; pos = i-1; while ((pos ≥ 0) && (a[pos] > x)) {

pos--;

}

}

B. a[pos+1] = x C. a[i] = x

1. void InsertionSort(int a[], int n) { 2. int pos, i, x; 3. for(i=1; i < n; i++) { 4. 5. 6. a[pos+1] = a[pos]; 7. 8. 9. … // lệnh bị thiếu 10. 11.} Dòng lệnh (9) bị thiếu, hãy chọn lệnh đúng A. a[pos] = x D. a[pos-1] = x

Linked list

1. Phát biểu nào của danh sách liên kết dùng cấp phát

động là đúng

A. Thao tác thêm và xóa đơn giản B. Kích thước của danh sách phải cố định C. Có thể áp dụng tìm kiếm nhị phân D. Các phần tử nằm liên tục trong bộ nhớ

Linked list

2. Cho 4 lệnh sau

(1) node = NewNode();

(2) node->next = p->next; (3) node->info = x; (4) p->next = node; Hãy sắp thứ tự để chèn nút có khóa x vào sau nút p

Linked list

3. Có các lệnh sau

(1) pHead = node; (2) node->info = x; (3) node->next = pHead; (4) node = NewNode();

Sắp thứ tự sau cho thao tác là chèn nút có khóa x vào trước pHead

Linked list

4. Cho hàm xóa nút đầu danh sách void DeleteFirst(NodePtr &pHead) { 1. NodePtr p; 2. if (IsEmpty(pHead)) 3. printf(“List is empty!”); 4. else { 5. p = pHead; 6. … 7. FreeNode(p);

}

Hãy bổ sung vào dòng lệnh (6) để hoàn chỉnh thao tác

}

Linked list

void DeleteAfter(NodePtr &p) {

NodePtr q; if (p->next ==NULL)

printf(“Cannot delete node!”);

else {

q = p->next; … FreeNode(q);

}

5. Hoàn thành thao tác xóa nút sau p 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. } Hãy bổ sung lệnh (9) để hoàn tất thao tác

Linked list

6. Cho đoạn chương trình không đầy đủ sau: NodePtr Search(NodePtr pHead, int x)

{ NodePtr p; p = (1); while ( p != NULL && (2) != x)

p = (3);

return p;

} Hãy điền giá trị thích hợp cho (1) (2) và (3)

Linked list

7. Điểm nổi bật của danh sách liên kết vòng

A. duyệt nhanh hơn dslk đơn B. cho phép duyệt hai chiều C. chỉ cần biết một phần tử là có thể duyệt hết danh sách D.

Linked list

NodePtr newNode; newNode = NewNode(); newNode->Info = x; if ( (*) == NULL){

pList = newNode; pList->next = (*);

} else {

newNode->next = pList->next; pList->next = (**);

}

8. Thao tác chèn vào đầu DSLK vòng 1. void InsertFirst(NodePtr &pList, int x) { 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. } Xác định chính xác giá trị của (*) và (**) A. (*) là pList và (**) là newNode->next B. (*) là pList và (**) là newNode C. (*) là newNode và (**) là pList->next

Linked list

NodePtr newNode; newNode = NewNode(); newNode->Info = x; if (pList == NULL){

pList = newNode; (1) = pList;

} else {

newNode->next = pList->next; (1) = newNode; pList = newNode;

}

9.Thao tác chèn vào cuối 1. void InsertLast(NodePtr &pList, int x) { 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.} Xác định giá trị thích hợp cho (1) A. newNode B. pList C.pList->next D. newNode->next

Linked list

10.

Cho 3 lệnh như sau:

(1): pList->next = p->next; (2): p = pList->next; (3): FreeNode(p); Xóa phần tử đầu của danh sách LK vòng có nhiều hơn 1 phần tử A. (1) (2) (3) C. (1) (3) (2)

B. (2) (1) (3) D. (2) (3) (1)