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

Đáp án đúng: "Dividing a project into small parts that are easier to manage." Module hoá là nguyên tắc chia một hệ thống lớn thành nhiều phần nhỏ, mỗi phần đảm nhiệm một nhiệm vụ rõ ràng và giao tiếp với nhau qua giao diện hẹp, nhờ đó lượng chi tiết người lập trình phải nắm cùng lúc giảm xuống, công việc chia được cho nhiều người và mỗi phần sửa hay thay thế riêng được. Cách hiểu "Writing code without documentation as whole but focus on documentation of small parts of the project." lẫn sang chính sách viết tài liệu, trong khi module hoá nói về cấu trúc chương trình, và bỏ tài liệu mức tổng thể còn làm mất bức tranh kiến trúc. "Testing the whole system at once." đi ngược tinh thần module hoá, vì module hoá cho phép kiểm thử từng đơn vị trước khi ghép. "Combining all code into one large file." chính là thứ module hoá tránh: một khối mã khổng lồ không tách được trách nhiệm và rất khó bảo trì.

Đáp án đúng: "Flexibility". Khả năng vận hành của phần mềm được đo bằng những thuộc tính nhìn thấy khi chương trình đang chạy, còn tính linh hoạt là khả năng sửa đổi chương trình cho mục đích mới nên nó thuộc nhóm khả năng bảo trì chứ không thuộc nhóm vận hành. Tiêu chí "Accuracy" thuộc nhóm vận hành vì nó đo mức kết quả chương trình trả về đúng với yêu cầu. Tiêu chí "Efficiency" cũng là tiêu chí vận hành, đo lượng tài nguyên như thời gian xử lý và bộ nhớ mà chương trình tiêu tốn khi chạy. Tiêu chí "Reliability" là tiêu chí vận hành đo mức chương trình chạy ổn định, không sụp và không cho kết quả sai trong suốt thời gian sử dụng.

Đáp án đúng: "Testing". Vòng đời phần mềm theo lối thác nước gồm bốn pha nối tiếp là phân tích, thiết kế, hiện thực và kiểm thử; kiểm thử đứng cuối vì chỉ khi đã có mã chạy được người ta mới kiểm được rằng sản phẩm đúng với yêu cầu đã phân tích và đúng với thiết kế. Pha "Design" là pha thứ hai, nơi hệ thống được chia thành module và định rõ giao diện giữa chúng, nhưng lúc đó chưa có gì chạy được để kiểm. Pha "Analysis" là pha mở đầu, làm rõ bài toán và yêu cầu của người dùng. Pha "Implementation" là pha thứ ba, viết mã theo thiết kế, và nó sinh ra chính thứ mà pha cuối sẽ đem kiểm.

Đáp án đúng: "4". Các ngôn ngữ máy tính được xếp vào bốn mô thức: thủ tục, hướng đối tượng, hướng hàm và khai báo theo logic. Mỗi mô thức là một cách nhìn khác nhau về việc chương trình là gì: dãy lệnh tác động lên dữ liệu, tập đối tượng tương tác với nhau, phép hợp của các hàm, hay tập sự kiện cùng luật suy diễn. Con số "2" chỉ phản ánh cách gộp thô thành nhóm ra lệnh và nhóm khai báo, không phải cách phân loại đang được hỏi. Con số "3" là đếm thiếu, bỏ sót một trong bốn nhóm kể trên. Con số "5" là đếm dư, vì các ngôn ngữ chuyên dụng như ngôn ngữ đánh dấu hay ngôn ngữ truy vấn được xét riêng chứ không được coi là một mô thức độc lập.

Đáp án đúng: "20". Một quan hệ trong mô hình dữ liệu quan hệ là một bảng chữ nhật: mỗi dòng là một bản ghi, mỗi cột là một thuộc tính, và mỗi ô giao giữa một dòng với một cột chứa đúng một giá trị. Vậy số giá trị được lưu bằng số dòng nhân số cột, tức 5 nhân 4 bằng 20. Con số "25" là kết quả của 5 nhân 5, tức đã lấy số dòng thay cho số cột. Con số "15" ứng với 5 nhân 3, tức đếm thiếu một cột. Con số "9" là 5 cộng 4, tức đã cộng hai chiều của bảng thay vì nhân; phép cộng không đếm được số ô vì mỗi dòng đều trải hết bốn cột.

Đáp án đúng: "Hardware, Software, Data, Users, and Procedures". Một hệ quản trị cơ sở dữ liệu không chỉ là phần mềm mà là một hệ thống gồm thiết bị lưu trữ và xử lý, phần mềm quản trị, bản thân dữ liệu, con người khai thác hoặc quản trị, cùng các thủ tục quy định cách dùng và cách sao lưu. Nhóm "CPU, Memory, I/O devices, Network, Operating System" chỉ kể chi tiết bên trong thành phần thiết bị và hệ thống, bỏ hẳn dữ liệu, con người và thủ tục. Nhóm "Application programs, End users, Database administrators, Data analysts, and System architects" chỉ chia nhỏ phần con người và chương trình ứng dụng. Nhóm "Tables, Rows, Columns, Keys, and Indexes" là các khái niệm cấu trúc bên trong một cơ sở dữ liệu quan hệ, tức chỉ nằm trong thành phần dữ liệu.

Đáp án đúng: "It has a complex structure that makes it difficult to query." Trong mô hình mạng, mỗi bản ghi nối với nhiều bản ghi khác bằng con trỏ nên toàn bộ cơ sở dữ liệu thành một đồ thị dày; muốn lấy dữ liệu, người dùng phải biết trước đường đi qua các mối nối, và chính sự rối rắm đó là hạn chế khiến mô hình này bị mô hình quan hệ thay thế. Nhận định "It does not support relationships between records." trái với bản chất mô hình, vì nó ra đời chính để biểu diễn quan hệ nhiều-nhiều. Nhận định "It does not allow more than one parent for a record." là hạn chế của mô hình phân cấp, còn mô hình mạng thì cho phép một bản ghi có nhiều cha. Nhận định "It only works for relational data." nhầm lẫn hai mô hình khác nhau, vì dữ liệu quan hệ thuộc mô hình quan hệ ra sau.

Đáp án đúng: "To eliminate repeating groups of data in a relation". Dạng chuẩn một đòi mỗi ô của quan hệ chỉ chứa một giá trị nguyên tử, nên bước này nhằm phá các nhóm lặp và thuộc tính đa trị, chẳng hạn việc nhét nhiều số điện thoại vào cùng một ô; khi còn nhóm lặp thì không thể tìm, sắp hay cập nhật từng giá trị một cách tin cậy. Mục tiêu "To ensure that all attributes depend on a composite key" là chuyện của dạng chuẩn hai, vốn xử lý phụ thuộc bộ phận vào khoá phức. Mục tiêu "To reduce the need for complex SQL queries" đi ngược thực tế, vì chuẩn hoá tách bảng nên truy vấn thường phải nối nhiều bảng hơn. Mục tiêu "To establish relationships between multiple relations" do khoá ngoại đảm nhiệm, không phải việc của dạng chuẩn một.

Đáp án đúng: "Encrype". Ba phép thao tác quen thuộc trên quan hệ là chọn dòng, chọn cột và nối hai quan hệ; mã hoá dữ liệu thuộc lĩnh vực bảo mật, nó biến đổi cách lưu trữ chứ không sinh ra một quan hệ mới từ các quan hệ có sẵn, nên không nằm trong nhóm phép toán này, và chữ trong lựa chọn còn bị viết sai chính tả. Phép "Select" lấy ra những dòng thoả một điều kiện và giữ nguyên toàn bộ các cột. Phép "Project" lấy ra một số cột được chỉ định và giữ mọi dòng. Phép "Join" ghép hai quan hệ theo giá trị trùng nhau của thuộc tính chung để tạo ra một quan hệ rộng hơn.

Đáp án đúng: "Sorting". Sắp xếp là quá trình xếp lại dữ liệu theo giá trị của chúng, theo chiều tăng hay giảm, và nó phổ biến vì nhiều việc khác như tìm nhị phân, phát hiện trùng lặp hay trình bày báo cáo đều dựa trên dữ liệu đã có thứ tự. Việc "Classifying" là gán dữ liệu vào các nhóm theo tiêu chí, kết quả là các lớp chứ không phải một dãy có thứ tự theo giá trị. Việc "Re-structuring" đổi cách tổ chức hay định dạng dữ liệu, không nói gì tới việc so sánh giá trị để xếp chỗ. Việc "Searching" là dò tìm một phần tử theo khoá rồi trả về vị trí của nó, và nó không hề làm thay đổi thứ tự của dữ liệu.

Đáp án đúng: "decision". Cấu trúc quyết định đánh giá một biểu thức điều kiện rồi dựa vào kết quả đúng hoặc sai mà chọn một trong hai nhánh lệnh để thi hành, nên nó đúng là cấu trúc dùng để kiểm tra một điều kiện. Cấu trúc "sequence" chỉ thi hành các lệnh lần lượt từ trên xuống, không có chỗ nào rẽ nhánh. Cấu trúc "repetition" có dùng điều kiện, nhưng điều kiện ở đó dùng để quyết định còn lặp lại khối lệnh nữa hay dừng, khác với việc chọn giữa hai nhánh, và bản chất được định nghĩa của nó là sự lặp lại. Từ "flow" chỉ nói chung về dòng điều khiển của chương trình và không phải một trong ba cấu trúc cơ bản.

Đáp án đúng: "Bubble Sort". Sắp xếp nổi bọt đi dọc dãy, so sánh từng cặp phần tử nằm kề nhau và đổi chỗ chúng nếu sai thứ tự; sau mỗi lượt quét, phần tử lớn nhất trong phần chưa sắp nổi về cuối, đúng như tên gọi. Thuật toán "Quick Sort" chia dãy quanh một phần tử chốt, các phần tử bị đổi chỗ thường nằm xa nhau ở hai phía chốt chứ không kề nhau. Thuật toán "Merge Sort" chia dãy thành nửa, sắp từng nửa rồi trộn hai dãy đã sắp, nó sao chép phần tử sang vùng kết quả thay vì đổi chỗ hai phần tử kề nhau. Thuật toán "Selection Sort" mỗi lượt tìm phần tử nhỏ nhất trong phần còn lại rồi đưa nó về đầu, chỉ một lần đổi chỗ giữa hai vị trí có thể rất xa nhau.

Đáp án đúng: "They all require the same amount of additional memory". Ba thuật toán được nêu đều sắp xếp ngay trên dãy gốc và chỉ cần thêm vài biến phụ để so sánh và đổi chỗ, nên bộ nhớ phụ của cả ba đều là một lượng hằng số không phụ thuộc số phần tử; vì thế không thuật toán nào trong số đó tiết kiệm bộ nhớ hơn hai thuật toán kia. Chọn "Bubble Sort" là sai vì nó chỉ cần một biến tạm để đổi chỗ, đúng bằng mức của hai thuật toán còn lại. Chọn "Selection Sort" cũng sai vì nó chỉ giữ thêm chỉ số của phần tử nhỏ nhất, vẫn là lượng hằng số. Chọn "Insertion Sort" sai tương tự, vì biến giữ phần tử đang được chèn cũng chỉ chiếm một ô nhớ.

Đáp án đúng: "A data structure that stores a list of data items in contiguous memory locations". Mảng là một dãy phần tử cùng kiểu nằm liên tiếp trong bộ nhớ, và nhờ tính liên tiếp đó địa chỉ của phần tử thứ i tính được ngay từ địa chỉ đầu, nên truy cập theo chỉ số mất thời gian như nhau với mọi phần tử. Mô tả "A collection of functions" ứng với thư viện hay lớp chứa các hàm, không phải nơi chứa dữ liệu theo chỉ số. Mô tả "A sequence of characters" là định nghĩa của chuỗi ký tự, một trường hợp riêng chứ không phải khái niệm mảng nói chung. Mô tả "A method for sorting data" nói về một thuật toán, trong khi mảng là một cấu trúc lưu trữ dữ liệu.

Đáp án đúng: "an operation that is applied to all elements of the array". Duyệt mảng nghĩa là đi qua lần lượt từng phần tử từ đầu đến cuối và áp dụng cùng một xử lý lên mọi phần tử, chẳng hạn in ra, cộng dồn hay tăng giá trị; đặc trưng của nó là không bỏ sót phần tử nào và không nhằm vào một phần tử cụ thể. Mô tả "an operation that search a specific element of the array" là phép tìm kiếm, nó dừng ngay khi gặp phần tử cần tìm. Mô tả "an operation that search and edit a specific element of the array" là phép cập nhật một phần tử đã xác định. Mô tả "an operation that search and delete a specific element of the array" là phép xoá; cả hai phép sau chỉ tác động lên một phần tử chứ không lên toàn mảng.

Đáp án đúng: "Inserts an item at the rear of the queue, making it the last item". Hàng đợi hoạt động theo nguyên tắc vào trước ra trước, nên phần tử mới luôn được thêm vào đuôi và trở thành phần tử cuối cùng sẽ được lấy ra; phép thêm vào đuôi đó chính là enqueue. Mô tả "Removes the item at the front of the queue." là phép dequeue, phép lấy phần tử ở đầu hàng đợi ra. Mô tả "Checks if the queue is empty" là phép kiểm tra hàng đợi rỗng, nó chỉ trả về đúng hoặc sai và không làm thay đổi nội dung. Mô tả "Creates a new empty queue" là phép khởi tạo, chỉ chạy một lần lúc dựng cấu trúc chứ không phải phép thêm phần tử.

Đáp án đúng: "ROM". Bộ nhớ không khả biến là loại giữ được nội dung khi mất điện, và bộ nhớ chỉ đọc đúng như vậy: nội dung được ghi lúc chế tạo hoặc nạp sẵn, dùng để lưu chương trình khởi động nên máy mới có thứ để chạy ngay khi vừa bật. Loại "RAM" là bộ nhớ khả biến, các ô nhớ cần được nuôi điện liên tục nên nội dung mất sạch khi tắt máy. Loại "Cache" được xây bằng bộ nhớ bán dẫn tốc độ cao và cũng khả biến, nó chỉ giữ bản sao tạm của dữ liệu đang được dùng nhiều. Loại "Register" nằm ngay trong bộ xử lý, giữ toán hạng và kết quả trung gian trong lúc thi hành lệnh, và cũng mất nội dung khi ngắt điện.

Đáp án đúng: "More efficient insertions and deletions." Danh sách liên kết cấp phát từng nút rời rạc và nối chúng bằng con trỏ, nên thêm hay bớt một phần tử chỉ cần sửa vài con trỏ tại chỗ đó mà không phải dồn toàn bộ phần tử phía sau như mảng; bộ nhớ cũng được xin thêm hoặc trả lại theo từng nút thay vì phải định trước một vùng liên tiếp đủ lớn. Lợi thế "Faster searching." không có, vì muốn tới phần tử nào cũng phải đi lần theo con trỏ từ đầu, còn mảng đã sắp thì tìm nhị phân được. Lợi thế "Easier random access to elements." thuộc về mảng, nơi địa chỉ phần tử tính trực tiếp từ chỉ số. Lợi thế "More efficient memory usage per node." cũng không đúng, vì mỗi nút phải mang thêm con trỏ nên tốn hơn một ô mảng cùng kiểu dữ liệu.

Đáp án đúng: "When the number of deletions and insertions is small, but a lot of searching and retrieval activities are expected." Mảng mạnh ở chỗ các phần tử nằm liên tiếp nên lấy phần tử theo chỉ số rất nhanh, nhưng yếu ở chỗ chèn hay xoá buộc phải dồn phần tử và kích thước thường phải định trước; vậy nó thích hợp đúng với tình huống ít thay đổi cấu trúc mà tra cứu nhiều. Tình huống "When a large number of insertions and deletions are expected after creation" là lúc nên dùng danh sách liên kết. Tình huống "When data items are completely unrelated" không hợp, vì mảng dành cho tập phần tử cùng kiểu và cùng thuộc về một danh sách. Tình huống "When elements need to be accessed non-sequentially only" nêu một điểm mạnh của mảng nhưng không phải điều kiện chọn mảng, vì mảng dùng tốt cả cho truy cập tuần tự và mô tả này bỏ qua yếu tố quyết định là số lần chèn xoá.

Đáp án đúng: "Simplifies addition and subtraction." Trong biểu diễn bù hai, phép trừ được đưa về phép cộng bằng cách cộng với bù hai của số bị trừ, và phép cộng thì làm giống nhau bất kể hai toán hạng âm hay dương, nên phần cứng chỉ cần một mạch cộng duy nhất và không phải so dấu hay so độ lớn trước khi tính. Nhận định "There are two representations for zero." là nhược điểm của biểu diễn dấu và độ lớn cùng biểu diễn bù một, còn bù hai chỉ có duy nhất một mẫu bit cho số không. Nhận định "It uses floating-point numbers." lẫn sang cách biểu diễn số thực, trong khi bù hai dùng cho số nguyên có dấu. Nhận định "It uses more bits for the sign." sai vì bù hai không thêm bit nào, dấu nằm sẵn trong bit trái cùng.