TAILIEUCHUNG - Đáp án đề thi cuối học kỳ II năm học 2019-2020 môn Cấu trúc rời rạc - ĐH Sư phạm Kỹ thuật

Mời các bạn cùng tham khảo đáp án đề thi cuối học kỳ II năm học 2019-2020 môn Cấu trúc rời rạc sau đây để biết được cấu trúc đề thi, cách thức làm bài thi cũng như những dạng bài chính được đưa ra trong đề thi. Từ đó, giúp các bạn sinh viên có kế hoạch học tập và ôn thi hiệu quả. | TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT ĐỀ THI CUỐI KỲ HỌC KỲ II THÀNH PHỐ HỒ CHÍ MINH NĂM HỌC 2019-2020 KHOA ĐÀO TẠO CHẤT LƯỢNG CAO Môn Cấu Trúc Rời Rạc Mã môn học DSCC235864 NGÀNH Công nghệ Kỹ thuật Máy tính Đề thi có 01 trang. ------------------------- Thời gian 75 phút. Được phép sử dụng tài liệu. Câu 1 điểm a. Cho các mệnh đề p q r. Chứng minh p q r q p r . b. Lấy phủ định của mệnh đề sau viết cụ thể bằng lời P Nếu trời mưa và bạn không đến đón thì tôi không đi học. c. Hãy kiểm tra suy luận sau t u r s t p q r s u ______________ p Câu 2 1 điểm a. Vẽ sơ đồ Venn thể hiện sự kết hợp giữa các tập hợp A và B như sau A B B A . Giả định rằng 2 tập hợp A và B giao nhau. b. Cho f là hàm từ R sang R được xác định bởi f x x2. Tìm f 1 x x gt 4 . Câu 3 điểm Cho X ℕ 12 ℎ ℎế ℎ và cho R ℎ ℎế ℎ . a. Chứng minh rằng X R là một tập sắp thứ tự poset . Lý giải cụ thể từng luận điểm. b. Vẽ biểu đồ Hasse. c. Poset trên có phần tử lớn nhất maximum và nhỏ nhất minimum hay không Tại sao d. Poset trên có phải là một Lattice hay không Tại sao Câu 4 điểm Cho A a b c d e và cho R là một quan hệ trên tập A với ma trận quan hệ như sau a b c d e a 0 0 1 0 0 b 0 0 0 1 0 c 1 0 0 0 0 d 0 1 0 0 0 e 0 0 0 1 0 a. Hãy biểu diễn R bằng đồ thị có hướng directed graphs b. Quan hệ R có hoặc không có các tính chất nào trong những tính chất sau phản xạ đối xứng phản đối xứng bắc cầu Tại sao c. Hãy tìm bao đóng closure của R để nó vừa đối xứng vừa phản xạ. d. Hãy tìm bao đóng closure của R để nó vừa phản xạ vừa bắc cầu. Câu 5 a. Viết mã giả pseudocode hoặc chương trình cho thuật toán tìm số nguyên nhỏ nhất trong một mảng gồm n số nguyên bằng cách so sánh mỗi số nguyên với số nhỏ nhất đã tìm được trước đó. b. Tính số phép so sánh phải thực hiện trong trường hợp tốt nhất best-case và xấu nhất worst-case của thuật toán trên. Lý giải cụ thể kết quả đạt được. c. Kết luận về độ phức tạp tính toán time complexity big-O cho các trường hợp tốt và xấu nhất. Ghi chú Cán bộ coi thi không được giải .

Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.