Đề kiểm tra giữa học kì 1, môn : Cấu trúc dữ liệu và giải thuật

Lưu ý: Đề kiểm tra gồm 4 câu với thang điểm 11/10. Sinh viên làm đúng trên 10 điểm sẽ được làm tròn thành 10. Câu 1: (2.5 điểm) a. (1.5 điểm) Hãy cho biết độ phức tạp của các hàm sau (theo Big-O Notation) trong trường hợp xấu nhất (chỉ ghi kết quả, không cần giải thích)void ExA(int n) { int a; for (int i = 0; i
Nội dung trích xuất từ tài liệu:
Đề kiểm tra giữa học kì 1, môn : Cấu trúc dữ liệu và giải thuật Đại học Quốc Gia TP. Hồ Chí Minh ĐỀ KIỂM TRA GIỮA HỌC KỲ 1 Trường đại học Bách Khoa Năm học: 2010 – 2011Khoa: Khoa học & Kỹ thuật Máy tính Môn: Cấu trúc dữ liệu & Giải thuật Bộ môn: Khoa học Máy tính MSMH: 503001 Ngày thi: 31/10/2010 - Thời gian: 60 phút (Được sử dụng tài liệu)Lưu ý: Đề kiểm tra gồm 4 câu với thang điểm 11/10. Sinh viên làm đúng trên 10 điểm sẽđược làm tròn thành 10.Câu 1: (2.5 điểm)a. (1.5 điểm) Hãy cho biết độ phức tạp của các hàm sau (theo Big-O Notation) trongtrường hợp xấu nhất (chỉ ghi kết quả, không cần giải thích) void ExA(int n) { int a; for (int i = 0; i < n; i += 2) a = i; O(n/2) } void ExB(int n) { int a; for (int i = 0; i < n * n; i++) a = i; O(n^2) } void ExC(int n) { int a; for (int i = 0; i < n; i++) O(n^2/2) for (int j = 0; j b. (1 điểm) Cho ví dụ về hai hàm f1 và f2, trong đó f1 sẽ thực thi nhanh hơn f2 trong trườnghợp tốt nhất và f1 sẽ thực thi chậm hơn f2 trong trường hợp xấu nhất.Câu 2: (4 điểm)Cho một cấu trúc danh sách liên kết được mô tả trong Hình 1.//just an entry in the list, a “struct++” in factclass Node {public: int data; Node* next;}; Node * pTemp = pHead;//interface part if(pHead->next=NULL)class List { while(countnext; int count; } Node* pHead; ptem->data+=data;public: List(); void add(int data, int index); if(count ==index) this.da return void display(); ~List();}; Hình 1Method add sẽ thêm data vào vị trí thứ index trong danh sách liên kết. Giả sử phần tử bắtđầu của danh sách có chỉ số là 1 và số phần tử của danh sách luôn lớn hơn index khi addđược gọi.Ví dụ : Giả sử danh sách list đang là (4,5,7,9). Sau khi gọi list.add(6,2) thì list sẽ trởthành (4,6,5,7,9).Hãy hiện thực method add theo hai cách: (i) không đệ quy và (ii) đệ quy.Câu 3: (3 điểm)Giả sử chúng ta đã có một cấu trúc dữ liệu stack đã được hiện thực cùng với các hàm sau:boolean isEmpty(stack s) // kiểm tra xem s có rỗng hay khôngint peek(stack s) // trả về giá trị trên đỉnh của svoid push(int x, stack s) // đẩy x vào sint pop(stack s) // lấy phần tử đầu tiên ra khỏi s và trả về giá trị của phần tử nàyHãy hiện thực hàm sau: sort(stack s1, stack s2)Trong đó s1 sẽ được dùng như dữ liệu nhập, s2 dùng như dữ liệu xuất. Sau khi sort thựcthi, s2 sẽ chứa các phần tử của s1 nhưng được sắp xếp từ nhỏ đến lớn (khi đó thao tácpeek(s2) sẽ trả về phần tử lớn nhất trong s2). Sinh viên lớp thường có thể khai báo các 2biến tạm tuỳ ý khi hiện thực hàm sort, sinh viên lớp KSTN chỉ được phép khai báothêm các biến tạm thuộc kiểu stack.Câu 4: (1.5 điểm)a. (1 điểm) Cho một danh sách các số nguyên như sau:{60, 71, 1, 19, 59, 17, 4, 13, 72, 91, 67, 21, 33}Giả sử các số nguyên này được chèn lần lượt vào một cây nhị phân tìm kiếm (BinarySearch Tree – BST) rỗng theo đúng thứ tự trong danh sách. Hãy vẽ cây nhị phân t ìmkiếm sau khi các số nguyên trong danh sách được chèn xong.b. (0.5 điểm) Vẽ lại cây nhị phân t ìm kiếm sau khi xóa node 60 từ cây nhị phân ở câu a. -- Hết -- 3