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

Đáp án đúng: "Restructuring existing code to improve readability, maintainability, and efficiency". Refactoring là việc sắp xếp lại cấu trúc bên trong của mã đã có — tách hàm, đổi tên định danh, gỡ đoạn trùng lặp — sao cho mã dễ đọc và dễ bảo trì hơn, trong khi hành vi quan sát được từ bên ngoài vẫn y nguyên. "Rewriting code from scratch to improve performance" là viết lại từ đầu, tức bỏ mã cũ chứ không cải tổ nó, và chỉ nhắm vào hiệu năng. "Adding new features to existing software without changing its external behavior" tự mâu thuẫn, bởi thêm tính năng chính là làm đổi hành vi bên ngoài, còn refactoring thì không thêm chức năng nào. "Optimizing code to reduce memory usage" chỉ tối ưu một chỉ số tài nguyên và nhiều khi làm mã khó đọc hơn, nên không phải mục đích của refactoring.

Đáp án đúng: "Waterfall". Mô hình thác nước chạy một chiều: phân tích xong mới sang thiết kế, thiết kế xong mới cài đặt, mỗi pha chỉ bắt đầu khi pha trước đã kết thúc trọn vẹn và không quay lui. "Spiral" lặp lại cả chuỗi pha qua nhiều vòng, mỗi vòng mở rộng sản phẩm và đánh giá rủi ro, nên các pha được làm lại nhiều lần. "Agile" chia việc thành nhiều chu kỳ ngắn, trong một chu kỳ vẫn vừa phân tích vừa viết mã vừa kiểm thử và chấp nhận yêu cầu thay đổi giữa đường. "Prototype" cố ý dựng bản mẫu nhanh cho người dùng xem rồi dựa vào phản hồi mà làm lại, tức quay về pha trước thay vì khoá pha đó lại.

Đáp án đúng: "design". Pha thiết kế là nơi trả lời câu hỏi làm thế nào: hệ thống được chia thành các module, từng thành phần được xác định rõ cùng giao diện giữa chúng và cấu trúc dữ liệu kèm theo, thường diễn đạt bằng sơ đồ cấu trúc và lưu đồ dữ liệu. "analysis" đi trước và chỉ xác định hệ thống phải làm gì — yêu cầu của người dùng, dữ liệu vào và ra — chứ chưa chỉ ra những thành phần nào tạo nên hệ thống. "implementation" nhận bản thiết kế đã có rồi viết mã cho từng thành phần, nên các thành phần buộc phải được định nghĩa từ trước. "testing" chỉ kiểm chứng rằng những thành phần đã dựng hoạt động đúng, không phải nơi khai sinh ra chúng.

Đáp án đúng: "The dependency between different modules, which should be minimized". Coupling đo mức ràng buộc giữa các module với nhau: càng phụ thuộc nhiều thì sửa một chỗ càng dễ làm vỡ chỗ khác, vì vậy thiết kế tốt hướng tới coupling thấp đi kèm cohesion cao. "The internal logical structure of a module" nói về bên trong một module, đó là phạm vi của cohesion chứ không phải quan hệ giữa các module. "The reusability of a module in different projects." là kết quả thu được khi coupling đã thấp, không phải định nghĩa của chính coupling. "The efficiency of a module's execution." thuộc về hiệu năng lúc chạy, một chỉ số hoàn toàn khác với mức lệ thuộc trong thiết kế.

Đáp án đúng: "Rectangle". Trong sơ đồ thực thể - quan hệ, mỗi tập thực thể, tức nhóm đối tượng cùng loại mà ta cần lưu dữ liệu về chúng, được vẽ bằng một hình chữ nhật có tên tập thực thể đặt bên trong. "Ellipse" dành cho thuộc tính của thực thể hoặc của quan hệ, chẳng hạn tên hay ngày sinh. "Diamond" dành cho tập quan hệ, tức mối liên kết giữa các tập thực thể như quan hệ dạy giữa giảng viên và môn học. "Line" không phải khung chứa đối tượng nào mà chỉ là đoạn nối, dùng gắn thuộc tính vào thực thể hoặc gắn thực thể vào quan hệ, kèm ký hiệu ràng buộc lực lượng ở hai đầu.

Đáp án đúng: "A column or combination of columns that uniquely identify each row in the table". Khoá chính là thuộc tính hoặc tổ hợp thuộc tính mà giá trị của nó không trùng ở hai dòng nào, nhờ đó mỗi bản ghi được chỉ đích danh duy nhất; kéo theo là nó không được để rỗng. "A column that can store null values" trái hẳn với yêu cầu đó, vì giá trị rỗng nghĩa là không nhận dạng được dòng. "A column used for indexing" lẫn khoá với chỉ mục: chỉ mục chỉ là cơ chế tăng tốc tìm kiếm và có thể dựng trên cột có giá trị trùng nhau. "A foreign key reference in another table" mô tả khoá ngoại nằm ở bảng khác, thứ dùng để liên kết hai bảng chứ không phải khoá nhận dạng của bảng này.

Đáp án đúng: "Relational model". Mô hình quan hệ nhìn dữ liệu như một tập các bảng hai chiều: mỗi dòng là một bản ghi, mỗi cột là một thuộc tính, và liên hệ giữa các bảng thể hiện qua giá trị chung của cột chứ không qua con trỏ. "Hierarchical model" tổ chức dữ liệu thành cây lộn ngược, bản ghi con treo dưới bản ghi cha. "Network model" cho một bản ghi nối tới nhiều bản ghi khác thành đồ thị, các liên kết hiện thực bằng con trỏ. "Distributed model" nói về chỗ đặt dữ liệu, tức chia nhau trên nhiều máy, chứ không quy định dữ liệu được cấu trúc theo hình thức nào.

Đáp án đúng: "project". Phép chiếu là phép toán một ngôi: nó nhận đúng một quan hệ làm đầu vào và sinh ra quan hệ mới chỉ gồm những cột được chọn, số dòng không đổi. "union" cần hai quan hệ có cùng cấu trúc để gộp các dòng của chúng lại, nên là phép hai ngôi. "join" cũng lấy hai quan hệ rồi ghép từng cặp dòng theo điều kiện trên thuộc tính chung, tức hai ngôi. "all of these above" chỉ đúng nếu mọi phép được liệt kê đều một ngôi, nhưng phép gộp và phép ghép vừa nêu đều đòi hai bảng đầu vào.

Đáp án đúng: "Hierarchical database model". Mô hình phân cấp xếp dữ liệu thành cây lộn ngược: một bản ghi gốc ở trên, mỗi bản ghi cha có thể có nhiều con nhưng mỗi con chỉ thuộc một cha, nên đường truy cập luôn đi từ gốc xuống. "Relational database model" dựng dữ liệu thành các bảng hai chiều, không có quan hệ cha con cố định nào. "Object-oriented database model" lưu dữ liệu dưới dạng đối tượng mang theo cả phương thức, tổ chức theo lớp và kế thừa. "Network database model" cũng nối bản ghi bằng con trỏ nhưng cho phép một bản ghi có nhiều cha, vì thế hình dạng của nó là đồ thị chứ không còn là cây.

Đáp án đúng: "When the data is unsorted". Tìm nhị phân sống nhờ một tiền đề: dữ liệu đã sắp thứ tự, nhờ đó một phép so sánh với phần tử giữa đủ để biết nên bỏ nửa trước hay nửa sau. Dữ liệu chưa sắp xếp thì phép loại nửa đó mất căn cứ, thuật toán có thể bỏ qua đúng phần tử cần tìm. "When the data is sorted" lại chính là điều kiện để thuật toán chạy được. "When the data is in an array" là hoàn cảnh thuận lợi nhất, vì mảng cho nhảy thẳng tới chỉ số giữa trong một bước. "When the data is in a linked list" làm thuật toán chậm đi do phải đi tuần tự mới tới được phần tử giữa, nhưng nếu danh sách đã sắp thứ tự thì kết quả vẫn đúng.

Đáp án đúng: "Using a for loop to iterate over a list". Cấu trúc lặp nghĩa là một nhóm lệnh được thực hiện lại nhiều lần dưới sự kiểm soát của một điều kiện hoặc một dãy giá trị; vòng for đi qua từng phần tử của danh sách đúng là hình ảnh đó. "Assigning a value to a variable" là một lệnh đơn chạy một lần, thuộc cấu trúc tuần tự. "Evaluating a condition once" là cấu trúc quyết định: xét điều kiện rồi rẽ nhánh, không có chuyện quay lại thực hiện tiếp. "Breaking out of a loop" là lệnh thoát khỏi vòng lặp, nó rút bớt số lần lặp đang có chứ bản thân không sinh ra sự lặp nào.

Đáp án đúng: "When stack overflow is a concern". Mỗi lời gọi đệ quy đều đẩy một khung vào ngăn xếp lời gọi để giữ tham số và chỗ quay về; độ sâu lớn làm ngăn xếp cạn và chương trình chết, trong khi bản lặp chỉ giữ trạng thái trong vài biến nên không tốn ngăn xếp. "When solving problems that require backtracking" là chỗ đệ quy có lợi, vì việc quay lui khớp tự nhiên với việc trả về khung gọi trước đó. "When the problem involves tree traversal" cũng vậy: cây vốn được định nghĩa đệ quy nên duyệt bằng đệ quy ngắn và rõ hơn. "When solving problems with divide-and-conquer techniques" chia bài toán thành bài toán con cùng dạng, đúng khuôn mẫu mà đệ quy diễn đạt gọn nhất.

Đáp án đúng: "Binary search divides the search space into halves, while sequential search checks elements one by one". Khác biệt gốc nằm ở cách thu hẹp vùng tìm: mỗi bước của tìm nhị phân loại bỏ một nửa số phần tử còn lại nên số phép so sánh tỉ lệ với logarit kích thước dữ liệu, còn tìm tuần tự xét lần lượt từng phần tử nên chi phí tỉ lệ với số phần tử. Khẳng định "Sequential search requires the data to be sorted in ascending order" nói ngược vấn đề, bởi chính tìm nhị phân mới đòi dữ liệu đã sắp thứ tự, còn tìm tuần tự chạy trên dữ liệu bất kỳ. Khẳng định "Sequential search exhibits greater efficiency and speed compared to binary search" sai vì dữ liệu càng lớn thì lợi thế càng nghiêng về phía chia nửa. Còn "sequential search is specifically designed to work only with arrays" cũng sai: tìm tuần tự dùng được cho cả danh sách liên kết, trong khi tìm nhị phân mới là thuật toán cần truy cập ngẫu nhiên.

Đáp án đúng: "for". Lệnh for là cấu trúc lặp với số lần xác định: nó lần lượt lấy từng phần tử hoặc từng chỉ số của mảng rồi chạy lại thân lệnh cho tới khi đi hết mảng. "if else" chỉ xét một điều kiện rồi chọn một trong hai nhánh và chạy đúng một lần, nên không đi qua được toàn bộ mảng. "switch case" cũng là cấu trúc rẽ nhánh, chỉ chọn nhánh khớp với giá trị của biểu thức rồi kết thúc. "return" kết thúc hàm hiện tại và trả giá trị về nơi gọi, thậm chí làm vòng lặp dừng sớm, chứ không tạo ra sự lặp.

Đáp án đúng: "A restricted linear list; Last In, First Out (LIFO)." Ngăn xếp là danh sách tuyến tính bị hạn chế: mọi phép thêm và lấy chỉ diễn ra ở một đầu duy nhất gọi là đỉnh, vì thế phần tử vào sau cùng lại là phần tử ra trước tiên. "A linear list; First In, First Out (FIFO)." mô tả hàng đợi, nơi thêm ở một đầu và lấy ở đầu kia. "A collection of related elements of different types." là mô tả bản ghi gồm nhiều trường khác kiểu, không nói gì tới thứ tự vào ra. "A sorted collection of elements accessed by index." mô tả mảng đã sắp thứ tự và truy cập theo chỉ số, trong khi ngăn xếp không cho với tay vào phần tử nằm giữa.

Đáp án đúng: "20, 10, 15, 5". Dãy đẩy vào theo thứ tự 5, 15, 10, 20 và ngăn xếp chỉ cho lấy ở đỉnh, nên trình tự lấy ra là nghịch đảo trình tự đẩy vào: 20 ra trước, kế đó 10, rồi 15, cuối cùng là 5. "5, 10, 15, 20" là thứ tự tăng dần, mà ngăn xếp không sắp xếp gì và cũng không trả phần tử theo thứ tự đẩy vào. "10, 15, 20, 5" đòi lấy một phần tử nằm giữa trước khi lấy phần tử đang ở đỉnh, điều mà cấu trúc này không cho phép. "15, 10, 5, 20" bỏ qua phần tử đang ở đỉnh để lấy phần tử bên dưới trước rồi mới lấy đỉnh ở bước cuối, vi phạm đúng luật chỉ thao tác ở đỉnh.

Đáp án đúng: "Data and a pointer to the next node". Mỗi nút của danh sách liên kết gồm hai phần: phần dữ liệu mang nội dung cần lưu, và phần liên kết chứa địa chỉ của nút kế tiếp; chính chuỗi địa chỉ này nối các nút nằm rải rác trong bộ nhớ thành một danh sách, nút cuối mang liên kết rỗng. "Data and an index of the current node" gán cho nút một chỉ số như phần tử mảng, nhưng danh sách liên kết không nằm liền khối nên chỉ số chẳng dẫn tới đâu. "Data and the next node's value" chỉ sao lại giá trị của nút sau: biết giá trị mà không biết địa chỉ thì không đi tiếp được, lại còn nhân đôi dữ liệu. "Data and the size of the list" nhồi một thuộc tính của toàn danh sách vào từng nút, vừa trùng lặp vừa không giúp tìm nút kế tiếp.

Đáp án đúng: "Keep the same order". Hàng đợi chỉ cho thêm ở cuối và lấy ở đầu, nên phần tử nào vào trước sẽ ra trước; nhờ tính chất vào trước ra trước đó mà hàng đợi được dùng để giữ nguyên trật tự của dòng dữ liệu hoặc dòng yêu cầu đang chờ xử lý. "Reverse the order of elements" là việc của ngăn xếp, nơi phần tử vào sau lại ra trước nên trật tự bị đảo. "Random elements" trái với cấu trúc hàng đợi, vì không có phép lấy ở vị trí tuỳ ý, mọi phần tử phải chờ tới lượt mình. "Sort the elements" cũng không đúng: hàng đợi không so sánh giá trị, muốn phần tử ra theo độ ưu tiên thì phải dùng hàng đợi ưu tiên, một cấu trúc khác.

Đáp án đúng: "Data value and the address of the next element". Một phần tử của danh sách liên kết luôn có hai phần, giá trị dữ liệu và trường liên kết giữ địa chỉ của phần tử đứng sau, bởi các phần tử nằm rời rạc trong bộ nhớ nên chỉ có địa chỉ mới cho biết đi tiếp đến đâu. "Data value and the index of the element" dùng chỉ số kiểu mảng, thứ chỉ có nghĩa khi các phần tử nằm liên tiếp nhau. "Index of the previous and next element" bỏ mất chính giá trị dữ liệu, mà thiếu dữ liệu thì phần tử không lưu được gì. "Only the data value" thiếu trường liên kết nên các phần tử rời nhau, không tạo thành danh sách. "None of the others" không dùng được vì mô tả gồm giá trị dữ liệu kèm địa chỉ phần tử kế tiếp đã hoàn toàn đúng.

Đáp án đúng: "Both a and b are correct". Mặt nạ toàn 0 đem AND với mẫu bit cho kết quả toàn 0, vì bit nào AND với 0 cũng ra 0; còn lấy mặt nạ y hệt mẫu bit rồi XOR thì mỗi cặp bit giống nhau cho 0, nên kết quả cũng toàn 0. Hai cách đều xoá sạch mọi bit, đó là lý do phương án gộp mới là đáp án thật chứ không phải phỏng đoán. "make a mask of all 0s and then AND the bit pattern and the mask." tự nó là một cách làm đúng, nhưng chọn riêng nó thì bỏ sót cách còn lại cũng cho kết quả như vậy. "make a mask exactly the same as the bit pattern and then XOR the bit pattern and the mask." cũng đúng và cũng không đầy đủ nếu chọn một mình. "Both a and b are incorrect" trái hẳn với hai phép tính vừa kiểm chứng ở trên.