TAILIEUCHUNG - Đề 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: ( điểm) a. ( đ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 | Đạ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 điểm a. đ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 a i 0 i n i 2 O n 2 void ExB int n int a for int i a i 0 i n n i O nA2 void ExC int n int a for int i for int a i 0 i n i j 0 j i j O nA2 2 void ExD int n int a for int i for int a i 0 i n n i j 0 j i j O nA4 2 void ExE int n int a for int i for int a i 0 i n i j 0 j n - i j o nA2 2 void ExF int n int a for int i a i 1 i n i 2 log2 n 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. 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 void display List Node pTemp pHead if pHead- next NULL while count index pTemp ptemp- next ptem- data data int index if count index return Hình 1 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 6 2 thì list sẽ trở thành 4 6 5 7 9 . Ị j 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ông int peek stack s trả về giá

• Phần cứng
• cấu trúc dữ liệu
• đề kiểm tra cấu trúc dữ liệu
• cấu trúc máy tính
• ôn tập cấu trúc dữ liệu
• ôn tập giải thuật
• ôn thi cấu trúc và giải thuật
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp