BÀI GIẢNG CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT DATA STRUCTURE AND ALGORITHMS

Chia sẻ: Nguyen Thi Thu Thuy | Ngày: | Loại File: PDF | Số trang:33

Thêm vào BST

Báo xấu

56
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mảng 1 chiều Khai báo mảng Các phép toán trên mảng 11 void function(char *s1, char *s2){ while (*(s1++)=*(s2++)); } void main(){ char s2[100]; char s1[]="Giao Trinh Ngon Ngu C++"; function(s2,s1); cout

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: BÀI GIẢNG CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT DATA STRUCTURE AND ALGORITHMS

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT DATA STRUCTURE AND ALGORITHMS GV: Phạm Tuấn Hiệp Email: hiep0109@yahoo.com Nội dung ôn tập 2 Chương 1: Ôn tập Kỹ thuật lập trình Chương 2: Tìm kiếm, Sắp xếp Chương 3: Danh sách liên kết Chương 4: Cây Ôn tập tốt nghiệp
Tài liệu học tập 3 Giáo trình: C & Data Structures, P. S. Deshpande, O. G. Kakde - CHARLES RIVER MEDIA, INC. Hingham, Massachusetts. Tham khảo: Giáo trình Cấu trúc dữ liệu 1, Trần Hạnh Nhi – Dương Anh Đức, Trường ĐHKHTN – ĐHQG TP.HCM. Phần mềm lập trình: C-Free 4.0 Borland C++ … Ôn tập tốt nghiệp 4 Chương 1: Ôn tập Kỹ thuật lập trình
Nội dung 5 Con trỏ Mảng 1 chiều Đệ quy Ôn tập tốt nghiệp Con trỏ 6 Cách khai báo con trỏ Các phép toán trên con trỏ void main(){ x = 10 int x=10, y=20; y = 10 int *p, *q; p = 10 p=&x; q = 10 q=&y; cout
Con trỏ 7 void main(){ int x=10, y=20; int *p, *q; p=&x; x = 50 q=&y; y = 90 *p=50; p = 50 *q=90; q = 90 cout
Con trỏ 9 Cho biết kết quả của chương trình sau: int Test(int &a, int b, int &c) { a--; a+=b; ++c=a+b; return a+b+c; A. 16 6 2 2011 } B. 16 5 2 8 int x=5, y=2, z=2011; C. 16 5 2 2011 void main(){ D. 16 6 2 8 cout
Mảng 1 chiều 11 Khai báo mảng Các phép toán trên mảng void function(char *s1, char *s2){ while (*(s1++)=*(s2++)); } void main(){ char s2[100]; char s1[]="Giao Trinh Ngon Ngu C++"; function(s2,s1); cout
Mảng 1 chiều 13 Cho biết kết quả của chương trình sau: void main(){ int a[]={5,1,12,11,8,20,14,12,7}; for(int i=4;i
Đệ quy 15 Đệ quy là sự gọi lại chính nó khi thực hiện Thường được dùng cho các bài toán truy hồi Cho hàm đệ quy sau: A. 50 int Func(int n){ B. 2 if(n == 5) return 5; C. 5 else D. 40 return 2 * Func(n+1); } Giá trị của Func(2) là? Ôn tập tốt nghiệp Đệ quy 16 void Foo(int x){ if(x>0) Foo(x-3); cout
17 Chương 2: Tìm kiếm, Sắp xếp Nội dung 18 Tìm kiếm tuyến tính, nhị phân Các thuật toán sắp xếp Đổi chỗ trực tiếp (Interchange sort) Nổi bọt (Bubble sort) Chèn trực tiếp (Insertion sort) Chọn trực tiếp (Selection sort) Dựa trên phân hoạch (Quick sort) Ôn tập tốt nghiệp
Tìm kiếm tuyến tính (tuần tự) 19 Ý tưởng: Bắt đầu từ phần tử đầu tiên của danh sách, so sánh lần lượt từng phần tử của danh sách với giá trị X cần tìm Nếu có phần tử bằng X thì trả về vị trí tìm thấy, thuật toán dừng lại (thành công) Nếu đến cuối danh sách mà không có phần tử nào bằng X, thuật toán dừng lại (không thành công) Ôn tập tốt nghiệp Tìm kiếm tuyến tính (tuần tự) 20 1 2 n 3 5 10 13 6 9 A[0] A[n-1] i i=0 i=1 i=2 i=3 i=4 i=5 3 -1 thấy tại Tìm 13 19 vị trí 4 Tìm Ko thấy Ôn tập tốt nghiệp
Tìm kiếm nhị phân 21 Điều kiện: Danh sách phải được sắp xếp trước Ý tưởng: So sánh giá trị muốn tìm X với phần tử nằm ở vị trí giữa của danh sách: Nếu bằng, tìm kiếm dừng lại (thành công) Nếu X lớn hơn thì tiếp tục tìm kiếm ở phần danh sách bên phải phần tử giữa Nếu X nhỏ hơn thì tiếp tục tìm kiếm ở phần danh sách bên trái phần tử giữa Ôn tập tốt nghiệp Tìm kiếm nhị phân 22 0 1 2 3 4 5 6 7 8 9 10 11 Left Right A[m] A[m] A[m] m Tìm thấy tại 36 vị trí 11 m=(Left + Right)/2 m=(Left + Right)/2 m=(Left + Right)/2 = (0+11)/2 = (6+11)/2 = (9+11)/2 =5 =8 = 10 Ôn tập tốt nghiệp
Tìm kiếm nhị phân 23 0 1 2 3 4 5 6 7 8 9 10 11 Left Right A[m] A[m] A[m] A[m] -1 Tìm ko thấy 24 m=(Left + m=(Left Right)/2 m=(Left +m=(Left + Right)/2 Right)/2 + Right)/2 = (0+11)/2 = (6+7)/2 = (6+11)/2 = (7+7)/2 =5 =6=7 =8 Ôn tập tốt nghiệp Tìm kiếm 24 int TimKiem(int M[],int N,int X){ int k=0; M[N]=X; while(M[k]!=X) k++; if(k
Tìm kiếm 25 Cho thuật toán (được thể hiện bằng mã giả): B1: k = 1 B2: IF(M[k] == X && k != N) B2.1: k++ B2.2: Lặp lại B2 B3: IF (k < N) Thông báo tìm thấy tại vị trí k B4: ELSE Không tìm thấy B5: Kết thúc Đoạn mã trên mô tả thuật toán gì? A. Tìm nhị phân phần tử có giá trị X B. Tìm phần tử nhỏ nhất trong mảng M bao gồm N phần tử C. Tìm tuyến tính phần tử có giá trị X D. Tìm phần tử lớn nhất trong mảng N bao gồm M phần tử Ôn tập tốt nghiệp Tìm kiếm 26 int TimKiem(int M[],int First, int Last,int X){ if(First > Last) return -1; int Mid = (First+Last)/2; if(M[Mid] == X) return Mid; if(X < M[Mid]) return TimKiem(M,First,Mid-1,X); else return TimKiem(M,Mid+1,Last,X); } Chọn câu đúng nhất miêu tả hàm trên: A. Hàm tìm kiếm phần tử có giá trị X trên mảng các phần tử từ chỉ số First đến chỉ số Last B. Hàm tìm kiếm đệ quy phần tử có giá trị X trên mảng các phần tử từ chỉ số First đến chỉ số Last C. Hàm tìm kiếm đệ quy phần tử có giá trị X trên mảng các phần tử từ chỉ số Last đến chỉ số First D. Hàm tìm kiếm không đệ quy phần tử có giá trị X trên mảng các phần tử từ chỉ số Last đến chỉ số First Ôn tập tốt nghiệp
Nội dung 27 Tìm kiếm tuyến tính, nhị phân Các thuật toán sắp xếp Đổi chỗ trực tiếp (Interchange sort) Nổi bọt (Bubble sort) Chèn trực tiếp (Insertion sort) Chọn trực tiếp (Selection sort) Dựa trên phân hoạch (Quick sort) Ôn tập tốt nghiệp Sắp xếp 28 void T(int A[], int n){ int i, j, tmp; for(i=1; i0 && A[j-1] > A[j]){ tmp = A[j]; A[j] = A[j-1]; A[j-1] = tmp; j--; } A. Bubble sort } B. Selection sort } C. Insertion sort Thuật toán trên là: D. Quick sort Ôn tập tốt nghiệp
Sắp xếp 29 Cho mảng A[]={11, 16, 12, 75, 51, 54, 73, 36, 52, 98}; Cần thực hiện bao nhiêu lần để mảng A có thứ tự tăng dần theo phương pháp sắp xếp Chèn trực tiếp (Insertion Sort)? A. 7 B. 8 C. 9 D. 10 Ôn tập tốt nghiệp Sắp xếp 30 Cho mảng A[]={16, 60, 2, 25, 15, 45, 5, 30, 33, 20}; Cần thực hiện bao nhiêu lần để mảng A có thứ tự tăng dần theo phương pháp sắp xếp Chọn trực tiếp (Selection Sort)? A. 7 B. 8 C. 9 D. 10 Ôn tập tốt nghiệp
Sắp xếp 31 void T(int A[], int n){ int i, j, minIndex, tmp; for(i=0; i
Sắp xếp 33 Cho mảng A[]={12, 2, 8, 5, 1, 6, 4, 15}. Các giá trị của mảng A được sắp xếp tăng dần theo từng bước như sau: 4 2 8 5 1 6 12 15 4 2 1 5 8 6 12 15 1 2 4 5 8 6 12 15 1 2 4 5 6 8 12 15 Mảng A được sắp xếp theo thuật toán nào? A. Selection Sort B. Quick Sort C. Insertion Sort D. Bubble Sort Ôn tập tốt nghiệp Sắp xếp 34 Cho mảng A[]={12, 2, 8, 5, 1, 6, 4, 15}. Dùng phương pháp sắp xếp nhanh (Quick Sort) để sắp mảng tăng dần, sau bước thứ 2, ba vị trí đầu trong mảng là những số nào? A. 4 2 8 B. 4 2 1 C. 1 2 4 D. 2 1 4 Ôn tập tốt nghiệp
Sắp xếp 35 Cho mảng A[]={8, 22, 7, 9, 31, 19, 5, 13}. Dùng phương pháp sắp xếp nổi bọt (Bubble Sort) để sắp mảng tăng dần. Cho biết số lần hoán vị các phần tử trong mảng? A. 11 B. 12 C. 13 D. 14 Ôn tập tốt nghiệp 36 Chương 3: Danh sách liên kết
Nội dung 37 Danh sách liên kết Ngăn xếp (Stack), Hàng đợi (Queue) Ôn tập tốt nghiệp Danh sách liên kết 38 Định nghĩa cấu trúc Node trong dslk Các phép toán trên trên dslk Thêm đầu Thêm cuối Thêm sau phần tử q Xóa đầu Xóa cuối Xóa sau phần tử q Xóa với giá trị X cho trước Duyệt danh sách Ôn tập tốt nghiệp
Danh sách liên kết 39 Định nghĩa cấu trúc dữ liệu của danh sách liên kết đơn được mô tả như sau: typedef struct Node{ int Key; Node *pNext; }; Trong đó khai báo Node *pNext dùng để mô tả: A. Con trỏ trỏ tới phần dữ liệu B. Vùng liên kết quản lý địa chỉ phần tử kế tiếp C. Con trỏ trỏ tới địa chỉ vùng nhớ của phần tử trước đó D. Con trỏ trỏ tới địa chỉ vùng nhớ của phần tử đầu tiên Ôn tập tốt nghiệp Danh sách liên kết 40 Cho danh sách liên kết đơn L gồm các phần tử sau: 5 6 -3 7 8 0 2 Cho biết kết quả của hàm sau: int Dem(List L){ int t=0; Node *p=L.pHead; while(p != L.pTail){ if(p->Info > 0) t++; p=p->pNext; A. 5 } B. 6 return t; C. 7 } D. 8 Ôn tập tốt nghiệp