Câu hỏi: CSI106 Nhập môn khoa học máy tính – Bộ ôn tập cuối kỳ số 3

Đáp án đúng: "12". Mô hình thác nước cho các pha chạy nối tiếp, pha sau chỉ bắt đầu khi pha trước kết thúc, nên tổng thời gian bằng số pha nhân thời gian mỗi pha. Câu dẫn liệt kê sáu pha gồm phân tích yêu cầu, thiết kế, hiện thực, kiểm thử, lập tài liệu và đánh giá; sáu pha nhân hai tuần cho 12 tuần. Phương án "14" ứng với bảy pha, tức đếm thêm một pha không có trong danh sách. Phương án "8" ứng với bốn pha, bỏ sót hai pha, thường do quên lập tài liệu và đánh giá. Phương án "10" ứng với năm pha, bỏ sót một pha; con số này chỉ đúng nếu các pha được chồng lấn hay gộp lại, nhưng câu dẫn đã nói rõ là không có chồng lấn.

Đáp án đúng: "Requirements specification document". Pha phân tích trong vòng đời phát triển hệ thống đi tìm hiểu hệ thống phải làm gì cho ai, nên kết quả chính của nó là tài liệu đặc tả yêu cầu: bản ghi đầy đủ các yêu cầu chức năng và phi chức năng, trở thành căn cứ ràng buộc cho mọi pha về sau và cho cả việc kiểm thử. Phương án "Source code" là sản phẩm của pha hiện thực, chỉ viết được sau khi đã thiết kế xong. Phương án "User documentation" là tài liệu hướng dẫn cho người dùng cuối, sinh ra ở giai đoạn cuối khi hệ thống đã chạy được. Phương án "Software architecture diagram" thuộc pha thiết kế, vì sơ đồ kiến trúc trả lời câu hỏi hệ thống được tổ chức thế nào, còn phân tích chỉ trả lời hệ thống cần làm gì.

Đáp án đúng: "Procedure-oriented design organizes the system around procedures, while object-oriented design organizes it around objects.". Thiết kế hướng thủ tục chia hệ thống thành các hàm xử lý, dữ liệu được truyền qua lại giữa chúng; thiết kế hướng đối tượng thì gom dữ liệu cùng những hành vi tác động lên chính dữ liệu đó vào một đối tượng, và hệ thống là tập các đối tượng trao đổi thông điệp. Phương án "Procedure-oriented design organizes the system around data, while object-oriented design organizes it around procedures." đảo ngược đúng hai cách tổ chức. Phương án "Procedure-oriented design uses classes, while object-oriented design uses functions." cũng sai chiều, vì lớp là khái niệm của hướng đối tượng. Phương án "Procedure-oriented design is used only in Agile methodologies." lẫn hai thứ khác loại: Agile là quy trình phát triển, không quy định kiểu thiết kế, và lối thiết kế hướng thủ tục có từ rất lâu trước Agile.

Đáp án đúng: "Modularity". Tính mô-đun là nguyên tắc chia hệ thống lớn thành các khối nhỏ, mỗi khối có nhiệm vụ rõ ràng và giao diện xác định, nhờ đó mỗi khối có thể được hiểu, viết, kiểm thử và bảo trì gần như độc lập với phần còn lại. Phương án "Abstraction" là trừu tượng hoá: che chi tiết bên trong và chỉ phơi ra những gì cần biết để dùng, nó làm giảm độ phức tạp khi nhìn một đơn vị chứ không phải việc chia hệ thống thành nhiều đơn vị. Phương án "Encapsulation" là đóng gói dữ liệu cùng phương thức và chặn truy cập trực tiếp vào trạng thái bên trong, đó là tính chất của một đơn vị đã có. Phương án "Inheritance" là kế thừa, cơ chế để lớp con dùng lại và mở rộng lớp cha, phục vụ tái dùng mã chứ không phải phân rã hệ thống.

Đáp án đúng: "Integrity". Bốn tính chất ACID của giao dịch là Atomicity, Consistency, Isolation và Durability; chữ thứ ba là Isolation, nghĩa là các giao dịch chạy đồng thời không thấy trạng thái dở dang của nhau. Phương án "Atomicity" nằm trong ACID: giao dịch thực hiện trọn vẹn hoặc không có gì xảy ra. Phương án "Consistency" cũng nằm trong ACID: giao dịch đưa cơ sở dữ liệu từ một trạng thái hợp lệ sang trạng thái hợp lệ khác. Phương án "Durability" là tính bền: kết quả đã xác nhận không mất dù hệ thống sập ngay sau đó. Còn "Integrity" là tính toàn vẹn dữ liệu nói chung, được bảo đảm bằng các ràng buộc khoá, kiểu và quy tắc nghiệp vụ, nên nó là mục tiêu chung của cơ sở dữ liệu chứ không phải một chữ trong ACID.

Đáp án đúng: "To ensure each tuple can be uniquely identified". Khoá chính là thuộc tính hoặc tập thuộc tính mà giá trị của nó không trùng nhau và không rỗng, nên mỗi bộ trong quan hệ được chỉ đích danh bằng đúng một giá trị khoá; đây cũng là điều kiện để các quan hệ khác tham chiếu tới nó qua khoá ngoại. Phương án "To allow multiple tuples to have identical values for all attributes" ngược hẳn mục đích: khoá chính tồn tại để chặn hai bộ trùng nhau. Phương án "To reduce the number of attributes in a relation" không đúng vì số thuộc tính do thiết kế lược đồ quyết định, đặt khoá không bỏ đi thuộc tính nào. Phương án "To link the relation to the conceptual schema" lẫn sang kiến trúc nhiều mức: việc ánh xạ giữa các mức lược đồ do hệ quản trị đảm nhiệm, còn nối các quan hệ với nhau là việc của khoá ngoại.

Đáp án đúng: "SQL". SQL là ngôn ngữ truy vấn có cấu trúc dành riêng cho cơ sở dữ liệu quan hệ, được ANSI và ISO chuẩn hoá, nên các hệ quản trị khác nhau vẫn hiểu một tập lệnh nền chung để định nghĩa lược đồ và thao tác dữ liệu. Phương án "Java" là ngôn ngữ lập trình đa dụng chạy trên máy ảo; nó nói chuyện với cơ sở dữ liệu bằng cách gửi câu lệnh SQL qua thư viện kết nối, chứ bản thân không phải ngôn ngữ truy vấn. Phương án "Python" cũng vậy: một ngôn ngữ lập trình thông dịch, truy cập dữ liệu thông qua thư viện. Phương án "C++" là ngôn ngữ hệ thống có chuẩn ISO, nhưng chuẩn đó dành cho ngôn ngữ lập trình, không liên quan tới việc mô tả và truy vấn dữ liệu quan hệ.

Đáp án đúng: "Network". Một hệ quản trị cơ sở dữ liệu được mô tả gồm phần cứng, phần mềm, dữ liệu, người dùng và các thủ tục vận hành; mạng chỉ là hạ tầng truyền tải khi muốn truy cập từ xa, và một hệ quản trị chạy trên đúng một máy vẫn đầy đủ chức năng mà không cần mạng. Phương án "Hardware" là thành phần thật: máy và thiết bị lưu trữ nơi dữ liệu nằm và được xử lý. Phương án "Software" cũng là thành phần: bản thân hệ quản trị cùng các tiện ích định nghĩa lược đồ, truy vấn, sao lưu. Phương án "Data" là thành phần trung tâm, gồm cả dữ liệu nghiệp vụ và siêu dữ liệu mô tả lược đồ, vì chính nó là thứ mà cả hệ thống được dựng lên để quản lý.

Đáp án đúng: "3". Kiến trúc ANSI/SPARC chia cách nhìn cơ sở dữ liệu thành ba mức: mức trong mô tả dữ liệu được lưu trữ vật lý thế nào, mức khái niệm mô tả toàn bộ lược đồ logic của tổ chức, mức ngoài là các khung nhìn riêng của từng nhóm người dùng. Ba mức này tạo ra tính độc lập dữ liệu: đổi cách lưu ở mức trong không buộc phải sửa ứng dụng ở mức ngoài. Phương án "2" thiếu mức khái niệm, tức bỏ mất lớp đệm làm nên tính độc lập dữ liệu. Phương án "4" thêm một mức không có trong mô hình này. Phương án "5" càng xa, vì không có mức thứ tư hay thứ năm nào được định nghĩa trong kiến trúc ba mức.

Đáp án đúng: "An algorithm". Định nghĩa của giải thuật gồm đúng những điều kiện nêu trong câu: một dãy hữu hạn các bước có thứ tự, mỗi bước rõ ràng không gây hiểu hai nghĩa, cho ra kết quả và kết thúc sau thời gian hữu hạn. Phương án "A construct" chỉ là cấu trúc điều khiển như tuần tự, rẽ nhánh, lặp; đó là viên gạch để xây giải thuật chứ không phải cả lời giải. Phương án "A recursion" là đệ quy, một cách định nghĩa lời giải bằng cách gọi lại chính nó; nó là kỹ thuật, và nếu thiếu điều kiện dừng thì còn chẳng kết thúc. Phương án "An iteration" là một vòng lặp hoặc một lần lặp, bản thân nó không bảo đảm sinh ra kết quả và dừng, nên không thể là định nghĩa của giải thuật.

Đáp án đúng: "Pseudocode". Đoạn đã cho viết bằng chữ theo khuôn mẫu giải thuật quen thuộc: có tên, mục đích, điều kiện trước, điều kiện sau, giá trị trả về, rồi thân chứa cấu trúc rẽ nhánh if và else với phép gán bằng mũi tên. Đó chính là mã giả: diễn đạt giải thuật bằng ngôn ngữ gần tiếng người nhưng có cấu trúc như mã, không ràng buộc cú pháp của ngôn ngữ lập trình nào. Phương án "Flowchart" là lưu đồ, biểu diễn bằng các khối hình học nối bằng mũi tên, trong đoạn trên không có hình vẽ nào. Phương án "Decision Table" là bảng quyết định, liệt kê các tổ hợp điều kiện theo cột và hành động tương ứng theo dòng. Phương án "Data Structure Diagram" mô tả tổ chức của dữ liệu và quan hệ giữa các thành phần dữ liệu, không mô tả trình tự xử lý.

Đáp án đúng: "To deliver data end-to-end and provide error control". Tầng vận chuyển trong mô hình TCP/IP làm việc giữa hai tiến trình ở hai đầu: nó gắn số hiệu cổng để giao đúng ứng dụng, chia và ghép dữ liệu, và với TCP thì bảo đảm tin cậy bằng đánh số thứ tự, báo nhận, phát lại khi mất và kiểm soát luồng. Phương án "To encode and decode data" nói về chuyển đổi cách biểu diễn dữ liệu, việc này do ứng dụng lo, tương ứng tầng trình diễn trong mô hình OSI. Phương án "To assign IP addresses" thuộc tầng Internet về mặt đánh địa chỉ, còn việc cấp phát địa chỉ là nhiệm vụ của dịch vụ cấu hình như DHCP. Phương án "To handle physical transmission media" là chuyện đường truyền và tín hiệu, thuộc tầng truy nhập mạng ở dưới cùng.

Đáp án đúng: "WHILE loop". Vòng lặp while kiểm tra một điều kiện trước mỗi lần lặp và còn lặp lại thân của nó chừng nào điều kiện còn thoả, nên nó là cấu trúc dành cho trường hợp không biết trước số lần lặp mà chỉ biết khi nào thì phải dừng. Phương án "FOR loop" cũng lặp, nhưng được dùng khi số lần lặp xác định được qua một biến đếm chạy trên khoảng đã biết, chứ không phải lặp cho tới khi một điều kiện xảy ra. Phương án "IF statement" chỉ rẽ nhánh một lần, chọn chạy khối này hay khối kia, hoàn toàn không quay lại. Phương án "SWITCH statement" chọn một trong nhiều nhánh theo giá trị của một biểu thức, cũng là cấu trúc rẽ nhánh nên không tạo ra sự lặp lại nào.

Đáp án đúng: "Process Left subtree → Right subtree → Root". Trong ba cách duyệt theo chiều sâu, tên gọi được đặt theo vị trí của gốc: duyệt sau nghĩa là gốc được xử lý sau cùng, nên trình tự là đi hết cây con trái, rồi cây con phải, cuối cùng mới tới gốc. Cách này hữu ích khi phải xử lý các con trước cha, chẳng hạn giải phóng cây hoặc tính giá trị một cây biểu thức. Phương án "Process Root → Left subtree → Right subtree" là duyệt trước, vì gốc được xử lý đầu tiên. Phương án "Process Root → Right subtree → Left subtree" là duyệt trước theo chiều đảo, gốc vẫn đi đầu nên không phải duyệt sau. Phương án "Process Right subtree → Root → Left subtree" đặt gốc ở giữa, đó là duyệt giữa theo chiều đảo, cho dãy giảm dần trên cây tìm kiếm nhị phân.

Đáp án đúng: "7". Trong cây nhị phân, mỗi nút có nhiều nhất hai con, nên mức thứ nhất chứa tối đa một nút, mức thứ hai tối đa hai nút, mức thứ ba tối đa bốn nút; tổng cộng là 1 cộng 2 cộng 4 bằng 7. Tổng quát, cây đầy có n mức chứa tối đa 2 lũy thừa n trừ 1 nút, với n bằng 3 thì ra 8 trừ 1 bằng 7. Phương án "4" chỉ là số nút tối đa của riêng mức thứ ba, bỏ quên gốc và mức giữa. Phương án "8" là 2 lũy thừa 3, tức số nút tối đa của mức thứ tư nếu cây có thêm một mức, hoặc do dùng công thức mà quên trừ một. Phương án "10" không ứng với tổng nào trong cây nhị phân ba mức, nó chỉ là một số lớn hơn giới hạn thật.

Đáp án đúng: "Each node has at most two subtrees, called left and right.". Theo định nghĩa kiểu dữ liệu trừu tượng, cây nhị phân là cây mà mỗi nút có nhiều nhất hai cây con, và hai cây con đó được phân biệt rõ thành cây con trái và cây con phải; chính việc phân biệt trái phải làm cây nhị phân khác với cây tổng quát có hai con. Phương án "Every node must have exactly two children and each must be a prime number." sai hai chỗ: nút được phép có không, một hoặc hai con, và giá trị chứa trong nút không hề bị buộc phải là số nguyên tố. Phương án "A binary tree is only used in graphical user interfaces for drawing." sai về công dụng, vì cây nhị phân là cấu trúc dữ liệu dùng cho tìm kiếm, sắp xếp, biểu diễn biểu thức, mã nén. Phương án "Every leaf connects to every other node via hidden arcs." mô tả một đồ thị dày cung, trong khi cây chỉ có đúng một đường đi từ gốc tới mỗi nút và không có cung ẩn nào.

Đáp án đúng: "link". Mỗi phần tử của danh sách liên kết gồm hai phần: phần dữ liệu giữ giá trị, và phần liên kết giữ địa chỉ của phần tử kế tiếp; nhờ phần liên kết này mà các phần tử nằm rải rác trong bộ nhớ vẫn xâu được thành một chuỗi theo thứ tự logic. Phương án "node" là nút, tức cả gói gồm dữ liệu cộng liên kết, nên nó là vật chứa con trỏ chứ không phải bản thân con trỏ. Phương án "array" là mảng, cấu trúc lưu các phần tử liền kề nhau và định vị bằng chỉ số, chính là lựa chọn đối lập với danh sách liên kết nên không thể là thành phần của nó. Phương án "data" là phần dữ liệu trong nút, nơi giữ nội dung của phần tử, hoàn toàn không mang thông tin về vị trí phần tử sau.

Đáp án đúng: "In-order traversal". Duyệt giữa đi cây con trái trước, rồi xử lý gốc, rồi đi cây con phải. Trên cây tìm kiếm nhị phân, mọi khoá ở cây con trái nhỏ hơn khoá ở gốc và mọi khoá ở cây con phải lớn hơn, nên trình tự này lấy ra các khoá theo đúng thứ tự tăng dần. Phương án "Pre-order traversal" xử lý gốc trước khi xuống con, nên dãy thu được bám theo hình dạng cây và dùng để sao chép hay lưu lại cấu trúc, không hề được sắp. Phương án "Post-order traversal" để gốc sau cùng, phù hợp khi cần xong việc với các con trước, như giải phóng bộ nhớ hoặc tính cây biểu thức. Phương án "Level-order traversal" đi theo từng mức bằng hàng đợi, cho thứ tự theo độ sâu của nút chứ không theo quan hệ lớn nhỏ giữa các khoá.

Đáp án đúng: "2". Giới hạn hai con là chính điều làm nên tên gọi cây nhị phân: mỗi nút được phép có không con, một con hoặc nhiều nhất hai con, và nếu có hai thì phân biệt thành con trái và con phải. Phương án "1" là một trường hợp được phép xảy ra chứ không phải mức tối đa; cây mà mọi nút chỉ có một con thì suy biến thành một chuỗi giống danh sách liên kết. Phương án "3" ứng với cây tam phân, một dạng cây nhiều nhánh khác, không còn là cây nhị phân. Phương án "Any number of children" mô tả cây tổng quát, nơi số con của mỗi nút không bị chặn; cây nhị phân chính là trường hợp riêng được đặt thêm ràng buộc để các giải thuật duyệt và tìm kiếm trở nên đơn giản và hiệu quả.

Đáp án đúng: "As binary patterns: sequences of 0s and 1s corresponding to the binary representation of the integer". Bộ nhớ máy tính chỉ chứa các bit, nên một số nguyên được lưu bằng chính mẫu bit biểu diễn giá trị của nó trong hệ hai, thường trên một số bit cố định và dùng cách biểu diễn bù hai nếu cần dấu; nhờ vậy mạch số học cộng trừ trực tiếp trên mẫu bit đó. Phương án "As text strings: sequences of characters representing the numerical value" là cách lưu văn bản, mỗi chữ số chiếm một mã ký tự riêng và không tính toán số học được ngay. Phương án "Using ASCII codes: numerical representations of characters, not the integers themselves" tự nói ra điểm sai của nó: mã ASCII là mã của ký tự, không phải giá trị số. Phương án "As hexadecimal values: a compact representation of binary patterns using base-16 notation" chỉ là cách con người viết gọn mẫu bit cho dễ đọc, bên trong máy vẫn là các bit không và một.