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

Ô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 Tổng cộng 40 Độ 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 • 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. T1(n) = 100n2 T2(n) = 5n3 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 – (1) for(i = 0; i < n-1; i++) – (2) for(j=n-1; j >i; j--) – (3) if (a[j-1] > a[j]){ – (4) temp = a[j-1]; – (5) a[j-1] = a[j]; – (6) a[j] = temp; – (7) } VD tính độ phức tạp • VD hàm tìm kiếm tuần tự – (1) i=0; – (2) found = false; – (3) while ( i<n && !found) – (4) if (a[i] == x) – (5) found = true; – (6) else – (7) i++; – (8) return found; Câu hỏi 1. 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à A. nlogn B. logn C. n D. n2 2. 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 A. Trường hợp tốt nhất B. Trường hợp trung bình C. Trường hợp xấu nhất D. Không xác định 3. 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à A. logn B. nlogn C. N2 D. n 4. 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à A. nlogn B. logn C. n2 C.n 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 1. Selection Sort 2. Insertion Sort 3. Bubble Sort 4. Interchange Sort 5. Shell sort 6. Quick sort 7. Radix... Câu hỏi 1. 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 C. 4 D. 5 2. 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 B. 10 8 6 C. 10 8 D. 10 6 8 3. 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 B. 11 C. 10 D. 14 4. 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 đủ 1. void InsertionSort(int a[], int n) { 2. int pos, i, x; 3. for(i=1; i < n; i++) { 4. x = a[i]; pos = i-1; 5. while ((pos ≥ 0) && (a[pos] > x)) { 6. a[pos+1] = a[pos]; 7. pos--; 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 B. a[pos+1] = x C. a[i] = 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 5. Hoàn thành thao tác xóa nút sau p 1. void DeleteAfter(NodePtr &p) 2. { 3. NodePtr q; 4. if (p->next ==NULL) 5. printf(“Cannot delete node!”); 6. else 7. { 8. q = p->next; 9. 10. FreeNode(q); 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 8. Thao tác chèn vào đầu DSLK vòng 1. void InsertFirst(NodePtr &pList, int x) { 2. NodePtr newNode; 3. newNode = NewNode(); 4. newNode->Info = x; 5. if ( (*) == NULL){ 6. pList = newNode; 7. pList->next = (*); 8. } 9. else { 10. newNode->next = pList->next; 11. pList->next = (**); 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 9.Thao tác chèn vào cuối 1. void InsertLast(NodePtr &pList, int x) { 2. NodePtr newNode; 3. newNode = NewNode(); 4. newNode->Info = x; 5. if (pList == NULL){ 6. pList = newNode; 7. (1) = pList; 8. } 9. else { 10. newNode->next = pList->next; 11. (1) = newNode; 12. pList = newNode; 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) B. (2) (1) (3) C. (1) (3) (2) D. (2) (3) (1)