Các vấn đề cơ sở của khoa học máy tính

Các Vấn Đề Cơ Sở Của Khoa Học Máy Tính Th.S GVC Tơ Oai Hùng 1 BÀI TẬP CHƯƠNG 1 1. Viết giải thuật để mơ tả thĩi quen mỗi buổi sáng của bạn, từ lúc nghe chuơng đồng hồ báo thức cho đến lúc bạn rời khỏi nhà để đi làm hay đi học. 2. Viết giải thuật tính để căn bậc hai của một số dương bất kỳ. Áp dụng giải thuật để tính giá trị 2046, lấy đến 2 số lẻ. Khơng sử dụng thiết bị tính tốn. 3. Tại sao nhà khoa học máy tính chú trọng đến cơ sở dữ liệu cũng cần phải biết về mạng máy tính. Các Vấn Đề Cơ Sở Của Khoa Học Máy Tính Th.S GVC Tơ Oai Hùng 1 BÀI TẬP CHƯƠNG 2 1. Viết mã giả cho giải thuật tìm căn bậc 2 của một số dương bất kỳ (phương pháp Newton– Raphson) được thực hiện trong hàm squareRoot(number). 2. Viết mã giả cho hàm mean(listNumbers) để tìm trung bình cộng của tập số bất kỳ. 3. Viết mã giả cho hàm median(listNumbers) để tìm phần tử trung bình của tập cĩ n số bất kỳ. Biết rằng, nếu n lẻ thì phần tử trung bình là phần tử giữa của tập cĩ thứ tự. Ngược lại, phần tử trung bình là trung bình cộng của hai phần tử giữa của tập cĩ thứ tự. 4. Cho biết độ phức tạp của giải thuật tìm phần tử trung bình trong câu 3?. 5. Giả sử giải thuật tìm trung bình cộng (mean) là (n) và giải thuật tìm phần tử trung bình (median) là (nlog2n). Cho biết tỷ lệ về thời gian thực thi giữa hai giải thuật khi số phần tử trong tập số là 1.000.000. 6. Một giải thuật sắp xếp đơn giản nhất là bubble sort (sắp xếp nổi bọt). Giải thuật sẽ quét qua tất cả phần tử nhiều lần. Mỗi lần, giải thuật sẽ so sánh hai phần tử kề nhau để sắp thứ tự. Cho ví dụ, cĩ danh sách sau: 6 7 3 1 4 Bubble sort bắt đầu so sánh 6 với 7. Hai phần tử này đã cĩ thứ tự, vì thế bubble sort sẽ so sánh tiếp 7 với 3, bubble sort hốn đổi hai phần tử này. Tiếp tục so sánh 7 với 1, bubble sort hốn đổi hai phần tử này. Tiếp tục so sánh 7 với 4, bubble sort hốn đổi hai phần tử này. Sau một lần quét, kết quả là: 6 3 1 4 7 Quét từ trái sang phài lần nữa, kết quả là: 3 1 4 6 7 Quét từ trái sang phài lần nữa, kết quả là: 1 3 4 6 7 Đây cũng là kết quả cuối cùng. Hãy viết mã giả cho giải thuật bubble sort trong hàm bubbleSort(listNumbers). 7. Cho biết độ phức tạp của giải thuật bubble sort? 8. Cho biết tỷ lệ về thời gian thực thi giữa giải thuật bubble sort và merge sort khi số phần tử trong danh sách là 1.000.000 và cĩ thứ tự ngẫu nhiên? 9. Tìm giải thuật để giải quyết vấn đề sau: a) Cho một số nguyên dương n, tìm danh sách các số nguyên dương mà tích của nĩ là lớn nhất trong tất cả danh sách của các số nguyên dương mà tổng của nĩ là n. Cho ví dụ: - Nếu n = 4, danh sách kết quả là {2, 2}. Vì 2  2 lớn hơn các danh sách cĩ 1  1  1  1; 2  1  1 và 3  1. Các Vấn Đề Cơ Sở Của Khoa Học Máy Tính Th.S GVC Tơ Oai Hùng 2 - Nếu n = 5, thì danh sách kết quả là {2, 3}. b) Danh sách kết quả như thế nào nếu n = 2001? 10. Những tên nào sau đây được đem ra so sánh trong câu lệnh if list[midpoint] = searchItem của giải thuật tìm kiếm nhị phân khi tên cần tìm là Joe: Alice, Brenda, Carol, Duane, Evelyn, Fred, George, Henry, Irene, Joe, Karl, Larry, Mary, Nancy, Oliver 11. Số lần tìm kiếm nhiều nhất của giải thuật tìm kiếm nhị phân khi số phần tử trong danh sách là: a) 200 b) 100.000 12. Các giá trị nào được in ra màn hình khi thực thi thủ tục đệ qui Exercise(N) nếu giá trị của N lúc đầu được gán là 1? procedure Exercise(N) in giá trị của N if (N < 3) then Exercise(N + 1) in giá trị của N 13. Cho biết những giải thuật nào cĩ thời gian thực thi là: (log2n), (n) và (n2)? 14. Đoạn chương trình sau dùng để tính thương của hai số nguyên dương trong phép chia nguyên bằng cách đếm số lần mà số bị chia trừ cho số chia đến khi số bị chia nhỏ hơn số chia. Cho ví dụ 7/3 = 2, bởi vì 7 - 3 - 3 = 1 (< 3). Hỏi kết quả là quotient của chương trình cĩ đúng khơng? count  0; remainder  dividend; // dividend = số bị chia do remainder  remainder – divisor; count  count + 1 while (remainder >= divisor) // divisor = số chia quotient  count // quotient = thương 15. Đoạn chương trình sau dùng để tính tích của hai số nguyên khơng âm X và Y bằng cách tích lũy (cộng dồn) tổng X lần giá trị Y. Hỏi kết quả là product của chương trình cĩ đúng khơng? product  Y // product = tích count  1 while (count < X) do product  product + Y; count  count + 1 Các Vấn Đề Cơ Sở Của Khoa Học Máy Tính Th.S GVC Tơ Oai Hùng 1 BÀI TẬP CHƯƠNG 3 1. Viết số 6, 13, 11, 18, 27, 4, 229 ở dạng nhị phân (cơ số 2). 2. Giá trị thập phân (cơ số 10) của 0101, 1001, 1011, 0110, 10000, 10010, 11100101 là bao nhiêu? 3. Giá trị thập phân của 11.01, 101.111, 10.1, 110.011, 0.101 là bao nhiêu? 4. Viết các hỗn số sau ở dạng nhị phân: 214 , 432 , 811 , 1650 , 855 . 5. Thực hiện các phép cộng nhị phân sau: 11011 1010.001 11111 111.11 + + + + 1100 1.101 0001 00.01 6. Giá trị nhị phân của số 377 trong hệ bát phân (cơ số 8) là bao nhiêu? 7. Giả sử số nguyên cĩ dấu được biểu diễn bằng 16 bit. a) Cho biết giá trị dương lớn nhất cĩ thể biểu diễn. b) Cho biết giá trị âm nhỏ nhất cĩ thể biểu diễn. c) Biểu diễn 17440. d) Biểu diễn -20. 8. Viết giá trị của các ký tự C, H và R trong bảng mã ASCII dạng thập phân và nhị phân. 9. Tham khảo danh sách các lệnh của CPU Intel x86 ở dạng từ gợi nhớ trong chương này, viết các lệnh để cộng hai giá trị được chứa trong bộ nhớ tại địa chỉ 50 và 51. Kết quả ghi vào địa chỉ 101. 10. Viết các lệnh để lấy giá trị chứa trong bộ nhớ tại địa chỉ 50 trừ cho giá trị tại địa chỉ 51. Kết quả ghi vào địa chỉ 101. 11. Cho biết ưu và khuyết điểm của máy tính cĩ chiều dài từ lớn? 12. Giả sử bộ nhớ cache cĩ thời gian truy cập là 10 ns, bộ nhớ chính cĩ thời gian truy cập là 100 ns. Nếu tỷ lệ "hit rate" của cache là 70. Tính thời gian trung bình truy cập bộ nhớ? Lưu ý: - hit rate – tỷ lệ phần trăm truy cập bộ nhớ được tìm thấy. - miss rate – tỷ lệ phần trăm truy cập bộ nhớ khơng được tìm thấy. - miss rate = 1 – hit rate. 13. Giả sử tốc độ máy tính 1GHz và trung bình cĩ 3 chu kỳ cho mỗi lệnh. Máy tính được kết nối với Internet tốc độ 10 Mbit/s. Cĩ bao nhiêu lệnh được thực thi từ lúc máy tính nhận bit đầu tiên cho đến khi máy tính nhận tồn bộ 1 ký tự (8 bit)? 14. Cho biết giá trị thập phân của các số bù hai sau: 00011, 01111, 11100, 11010, 00000, 10000? 15. Viết các giá trị thập phân sau ở dạng bù 2 sử dụng 8 bit: 6, -6, -17, 13, -1, 0? Các Vấn Đề Cơ Sở Của Khoa Học Máy Tính Th.S GVC Tơ Oai Hùng 1 BÀI TẬP CHƯƠNG 5 1. Viết chương trình Java cĩ khai báo hai biến dividend và divisor với giá tri tương ứng là 74.3 và 12.6, thực hiện phép chia dividend cho divisor. Hiển thị kết quả ra màn hình. 2. Viết chương trình Java để tính diện tích hình trịn cĩ bán kính r = 5 với  = 3.14 và  = Math.PI. Hiển thị kết quả ra màn hình. 3. Viết chương trình Java nhắc người sử dụng nhập vào một số nguyên. Sau đĩ, cho biết số vừa nhập cĩ phải là bội số của 5 hay khơng? 4. Viết chương trình Java nhắc người sử dụng nhập vào 5 chuỗi ký tự. Sau đĩ hiển thị các chuỗi này theo thứ tự ngược với thứ tự đã nhập. 5. Viết chương trình Java phân loại phương tiện dựa trên số bánh xe. Chương trình nhắc người sử dụng nhập số bánh xe và hiển thị loại phương tiện tương ứng: - Xe cĩ 2 hay 3 bánh: Mơ tơ. - Xe cĩ 4 bánh: Ơ tơ hay xe tải nhẹ. - Xe cĩ 6, 8, 10, 12, 14, 16 hay 18 bánh: Xe tải. - Ngược lại, hiển thị thơng báo lỗi. 6. Định nghĩa lớp Java cĩ tên là Vehicle, gồm các thuộc tính và phương thức sau: a) Thuộc tính:  make: hãng sản xuất (String).  model: kiểu xe (String).  color: màu xe (String).  speed: vận tốc (double).  vehicleCount: đếm số xe đã sản xuất (int). b) Phương thức:  Định nghĩa phương thức tạo dựng: thiết lập các giá trị cho make, model, color dựa vào giá trị của người sử dụng truyền đến và tăng số xe đã sản xuất thêm 1. Riêng thuộc tính speed được gán trị 0.  Định nghĩa bốn phương thức get() cho các thuộc tính make, model, color và speed để trả về giá trị tương ứng.  Định nghĩa phương thức changeSpeed() để nhận vào vận tốc mới và trả về hiệu giữa vận tốc mới với vận tốc trước đĩ (speed). Sau đĩ thay đổi trị của speed thành vận tốc mới.  Định nghĩa phương thức main() để thực hiện yêu cầu sau: - Tạo 3 đối tượng lần lượt với các giá trị cho make, model và color là: ("Ford", "Mustang", "red") ("BMW", "328i", "silver") ("Chrysler", "PT Cruiser", "gold" ) Các Vấn Đề Cơ Sở Của Khoa Học Máy Tính Th.S GVC Tơ Oai Hùng 2 - Hiển thị số đối tượng hiện cĩ của lớp Vehicle. - Hiển thị hãng sản xuất của đối tượng 1, kiểu của đối tượng 2 và màu của đối tượng 3. - Thiết lập vận tốc của đối tượng 1 là 70.0 mph và hiển thị vận tốc đĩ. - Ví dụ: Hãng sản xuất v1: Ford Kiểu của v2: 328i Màu của v3: gold Vận tốc của v1 là 70.0 mph. 7. Định nghĩa lớp Skateboard thừa kế từ lớp Vehicle. Nạp chồng phương thức changeSpeed() để thể hiện của lớp Skateboard khơng bao giờ cĩ vận tốc vượt quá 10 mph. Nếu người sử dụng cung cấp giá trị lớn hơn 10 mph, phương thức sẽ gán vận tốc của Skateboard bằng 10 mph. 8. (*) Định nghĩa lớp Bus thừa kế từ lớp Vehicle. Một thể hiện của lớp Bus phải luơn cĩ thuộc tính driver (tài xế) kiểu String. Trong phương thức tạo dựng của lớp Bus phải cĩ mã lệnh lưu tên tài xế. Lớp Bus cĩ phương thức get() và set() để lấy hoặc thay đổi tên của tài xế. Định nghĩa phương thức main() để thực hiện yêu cầu sau: - Tạo 2 đối tượng như sau: Bus firstBus = new Bus( "GM", "Metro", "Silver", "Joe" ); Bus secondBus = new Bus( "Mercedes", "B302", "Black", "Mary"); - Hiển thị kết quả: First bus: GM được Joe lái. Second bus: Mercedes được Mary lái. Các Vấn Đề Cơ Sở Của Khoa Học Máy Tính Th.S GVC Tơ Oai Hùng 1 BÀI TẬP CHƯƠNG 6 Nhắc lại:  Để đạt dạng chuẩn 1, chúng ta dùng phương pháp sau: - Loại bỏ các thuộc tính vi phạm dạng chuẩn 1 và đặt chúng vào một bảng riêng cùng với khố chính của quan hệ ban đầu. - Khố chính của bảng này là một tổ hợp của khố chính của quan hệ ban đầu và thuộc tính đa trị. - Các thuộc tính cịn lại lập thành một quan hệ với khĩa chính là khĩa chính ban đầu.  Để đạt dạng chuẩn 2, chúng ta dùng phương pháp sau: - Loại bỏ các thuộc tính khơng khố phụ thuộc vào một bộ phận khố chính và tách thành ra một bảng riêng. - Khố chính của bảng là bộ phận khố mà chúng phụ thuộc vào. Các thuộc tính cịn lại lập thành một quan hệ, khĩa chính của nĩ là khĩa chính ban đầu.  Để đạt dạng chuẩn 3, chúng ta dùng phương pháp sau: - Loại bỏ các thuộc tính phụ thuộc bắc cầu ra khỏi quan hệ và tách chúng thành một quan hệ riêng cĩ khố chính là thuộc tính bắc cầu. - Các thuộc tính cịn lại lập thành một quan hệ cĩ khĩa chính là quan hệ ban đầu. 1. Giả sử người thiết kế CSDL đưa ra lược đồ cho bảng Sales trong một cửa hàng nào đĩ như sau: Trong đĩ: khơng cĩ khách hàng (Customer_Name) nào cùng tên. a) Lược đồ này ở dạng chuẩn 1 chưa? b) Lược đồ này ở dạng chuẩn 2 chưa? c) Lược đồ này ở dạng chuẩn 3 chưa? d) Nếu lược đồ trên khơng phải dạng chuẩn 3, hãy thiết kế lại để thành dạng chuẩn 3. 2. Cho các lược đồ quan hệ như sau: DonVi MaDV TenDV MaNQL TruSo 5 Nghiên cứu NV002 Nam Định, Hà Nội, Bắc Ninh 4 Hành chính NV014 Hà Nội 1 Lãnh đạo NV061 Tp.HCM Sales Item_ID Description Price Date Customer_Name Addr City St ZIP Phone Các Vấn Đề Cơ Sở Của Khoa Học Máy Tính Th.S GVC Tơ Oai Hùng 2 Trong đĩ: ứng với mỗi nhân viên và mỗi dự án thì số giờ thực hiện dự án sẽ được xác định. a) Lược đồ này ở dạng chuẩn 1 chưa? Nếu chưa thì chuyển thành dạng chuẩn 1. b) Sau khi đưa các lược đồ về dạng chuẩn 1, thì nĩ cĩ ở dạng chuẩn 2 khơng? c) Sau khi đưa các lược đổ về dạng chuẩn 2, thì nĩ cĩ là dạng chuẩn 3 khơng? 3. Cho lược đồ quan hệ như sau: NhanVien_DonVi (MaNV, MaDV, TenDV, HoTenNV, NgaySinh, DiaChi, MaNQL) Lược đồ này ở dạng chuẩn 3 chưa? Nếu chưa thì chuyển thành dạng chuẩn 3. 4. Cho lược đồ của hai bảng Deliveries và Delivery_Services: Viết các lệnh SQL để tạo hai bảng trên. Chỉ định cột nào khơng thể cĩ trị NULL, các ràng buộc khố chính và khố ngoại. Chú ý là cột Delivery_Service trong bảng Deliveries cĩ cùng ý nghĩa như cột Name trong bảng Delivery_Service. 5. Cho một lược đồ cơ sở dữ liệu như sau: Emp(EmpNo, Ename, Job, Mgr, HireDate, Sal, Benefit, DeptNo) Dept(DeptNo, Dname, Loc) SalGrade(Grade, Losal, Hisal) Trong đĩ các quan hệ cĩ ý nghĩa như sau: - Emp: chứa các thơng tin của nhân viên, bao gồm: mã nhân viên (EmpNo), tên nhân viên (Ename), cơng việc (Job), mã người quản lý trực tiếp (Mgr), ngày vào làm (HireDate), NhanVien_DuAn MaNV MaDA HoTenNV TenDA SoGio DiaDiem NV001 1 Nguyễn Văn Nam DA01 20 Hà Nội NV003 2 Lê Thị Thanh DA02 28 TP.HCM NV005 3 Hồ Văn Sơn DA03 25 Đà Nẵng NV010 4 Trần Hồng Sơn DA04 15 Huế Deliveries Date_Time Customer_ID Delivery_Service Cost Invoice_No Driver Delivery_Services Name Phone Addr City St ZIP Contact Các Vấn Đề Cơ Sở Của Khoa Học Máy Tính Th.S GVC Tơ Oai Hùng 3 lương hàng tháng (Sal), phụ cấp hàng tháng (Benefit) và mã phịng ban (DeptNo) mà nhân viên này đang làm việc. - Dept: chứa các thơng tin về phịng ban, bao gồm: mã phịng ban (DeptNo), tên phịng ban (Dname), nơi đặt văn phịng (Loc). - SalGrade: chứa các thơng tin về mức lương, bao gồm: mã mức lương (Grade), lương thấp nhất (Losal), lương cao nhất (Hisal). Viết các lệnh SQL để tạo ba bảng trên. 6. Viết truy vấn SQL cho câu 3 theo các yêu cầu sau: a) Nêu tên phịng ban mà nhân viên “Smith” làm việc. b) Liệt kê tồn bộ thơng tin của những nhân viên cĩ tên bắt đầu bằng chữ “A”. c) Liệt kê tất cả các phịng ban đĩng tại thành phố Hồ Chí Minh. d) Liệt kê mã nhân viên, tên nhân viên, tên phịng ban, lương và mã mức lương của tất cả nhân viên theo thứ tự mã nhân viên tăng dần. e) Liệt kê mã và tên những nhân viên khơng cĩ phụ cấp hàng tháng. Biết rằng những nhân viên cĩ giá trị của cột Benefit bằng 0 hay Null đều được xem là khơng cĩ phụ cấp. f) Liệt kê những nhân viên cĩ chức vụ thấp nhất trong cơng ty: nhân viên khơng làm quản lý cho nhân viên nào cả. g) Liệt kê các nhân viên cĩ lương cao hơn mức lương trung bình của tất cả mọi nhân viên. 7. Cho một số lược đồ sau: Viết truy vấn SQL theo các yêu cầu sau: a) Cho biết tên và phần trăm tiền hoa hồng của tất cả người bán hàng ký gởi ở bang NY theo thứ tự phần trăm tiền hoa hồng tăng dần. b) Cho biết mã hàng và những mơ tả thơng tin của nĩ mà người bán tên là “Parker Smith” và giá bán là NULL. Item Item_ID Type Description Cost Consignment_Seller_ID Price_Sold Sale Invoice_No Customer_ID Date_Sold Line_Item Invocie_No Item_ID Unit_Price Quantity Line_Item_Price (tổng số tiền) Consignment_Seller Seller_ID Name Addr City State ZIP Fee_Percent Các Vấn Đề Cơ Sở Của Khoa Học Máy Tính Th.S GVC Tơ Oai Hùng 4 c) Cho biết tổng số tiền bán được trong tháng 3/2007. d) Cho biết các mã hàng mà “Parker Smith” đã bán (tức giá bán khác NULL) trong tháng 11/2007.