Đang chuẩn bị liên kết để tải về 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
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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) | Đại học Quốc Gia TP. Hồ Chí Minh Trường đại học Bách Khoa Khoa Khoa học Kỹ thuật Máy tính Bộ môn Khoa học Máy tính ĐỀ KIỂM TRA GIỮA HỌC KỲ 1 Năm học 2010 - 2011 Môn Cấu trúc dữ liệu Giải thuật 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 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 2 a i void ExB int n int a for int i 0 0 i n n i a i void ExC int n int a for int i 0 for int j 0 i n i 0 j i j a i void ExD int n int a for int i 0 i n for int j 0 j i n i i j a i void ExE int n int a for int i 0 i n i for int j 0 j n - i j a i void ExF int n int a for int i 1 i n i 2 a i 1 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ường hợ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. Giải a. ExA O n ExB O n2 ExC O n2 ExD O n4 ExE O n2 ExF O log2n b. void f1 int n int m int a if n m a n else for int i 0 i n n i a i void f2 int n int m int a for int i 0 i n i a i 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 fact class Node public int data Node next interface part class List private int count Node pHead public List void add int data int index void display List Hình 1 2 Method 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. Giải a. Không đệ quy void List add int data int index if index 0 index count Node pCur pNew pNew new Node pNew - data data if index 1 pNew - next pHead pHead pNew