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

Ghi chú: đề thi gồm tất cả 7 câu. Sinh viên lớp KSTN làm hết 7 câu, thang điểm 12/12. Sinh viên lớp thường làm 6 câu (từ câu 1 đến câu 6), thang diểm 10/10. Câu 1 (1.5 điểm): Tính toán big-O của các hàm dưới đây và sắp xếp chúng theo thứ tự từ nhỏ đến lớn theo big-O: Đáp áp: a) (1 điểm) Tính big-Oa. 2 = O(2 ) b. n! = O(n!) c. n3.5 = O(n3.5) d. n + n2 + n3 = O(n3) e. 105 = O(1) f. 150,000 = O(1) g. nlog2(n) = O(nlog2(n))n...
Nội dung trích xuất từ tài liệu:
Đề thi giữa kì 1 môn: Cấu trúc dữ liệu và giải thuật ĐÁP ÁNTrường ĐH Bách Khoa Tp.HCM Khoa KH&KT Máy tính Đề thi giữa kỳ HK1/2009 Môn: Cấu trúc dữ liệu và Giải thuật Thời gian: 60 phút (Không sử dụng tài liệu) Ghi chú: đề thi gồm tất cả 7 câu. Sinh viên lớp KSTN làm hết 7 câu, thang điểm 12/12. Sinh viên lớp thường làm 6 câu (từ câu 1 đến câu 6), thang diểm 10/10. Câu 1 (1.5 điểm): Tính toán big-O của các hàm dưới đây và sắp xếp chúng theo thứ tự từ nhỏ đến lớn theo big-O: Đáp áp: a) (1 điểm) Tính big-O n n a. 2 = O(2 ) b. n! = O(n!) c. n3.5 = O(n3.5) d. n + n2 + n3 = O(n3) e. 105 = O(1) f. 150,000 = O(1) g. nlog2(n) = O(nlog2(n)) b) (0.5 điểm) Sắp xếp theo big-O: 105 1. pre = null, tmp = head 2. loop (tmp is not null) 1. if ((tmp->data == x) or (tmp->data == x+1) or (tmp->data == x+2)) 1. if (pre is null) //delete first 1. head = head->link 2. delete tmp 3. tmp = head 2. else //delete the element after pre 1. pre->next = tmp->link 2. delete tmp 3. tmp = pre->link 3. end if 2. else 1. pre = tmp 2. tmp = tmp->link 3. end if 3. end loopend remove_in_rangeCâu 3 (2 điểm): Viết Stack ADT Create()một hàm cục toàn Push (val DataIn ) //Thêm 1 phần tử vào đỉnh stack //Bỏ phần tử trên đỉnh stack Pop ()(global function) bằng Top (ref DataOut ) //Xem phần tử trên đỉnh stack isEmpty ()pseudocode nhận vàomột queue và đảo ngược Queue ADT Create()queue đó. Giả sử rằng EnQueue (val DataIn ) //Thêm 1 phần tử vào cuối queue //Bỏ 1 phần tử đầu queue DeQueue ()các phương thức của QueueFront (ref DataOut ) //Xem phần tử đầu queue QueueRear (ref DataOut ) //Xem phần tử cuối queuequeue và stack được cho isEmpty ()theo đặc tả của hình bêncạnh. Chú ý: không được viết và dùng thêm các hàm phụ trợ nào khác.Đáp áp:algorithm reverse_queue (ref queue ) Post các phần tử trong queue sẽ bị đảo ngược vị trí 1. stack = Create a stack 2. loop (not queue.isEmpty()) 1. queue.QueueFront (x) 2. stack.Push (x) 3. queue.DeQueue() 3. end loop 4. loop (not stack.isEmpty()) 1. stack.Top (x) 2. queue.EnQueue (x) 3. stack.Pop() 5. end loopend reverse_queueCâu 4 (1.5 điểm): Hãy trình bày từng bước quá tr ình tạo một cây nhị phân t ìm kiếm (BST) bằng cách thêmvào trong cây rỗng ban đầu các khóa lần lượt như sau: F,O,R,G,E,T biết rằng giá trị so sánh của các khóa nàylà thứ tự của chúng trong bảng chữ cái.Đáp áp: F F F F F F O E O E O O O G R G R G R R TCâu 5 (1.5 điểm): Trình bày binary_search_1 (val target , ref position )từng bước quá trình tìm kiếm 1. bottom = 0 2. top = size of the listkhóa 31 dùng phương pháp t ìm 3. loop (bottom < top)kiếm nhị phân binary_search_1 1. mid = (bottom + top)/2 2. if (target > datamid)(forgetful version) trên danh 1. bottom = mid + 1 3. elsesách liên kết (DSLK) đơn có ...