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

Đáp án đúng: "Data is organized as an inverted tree and each entity can have several children". Mô hình phân cấp xếp dữ liệu như một cái cây úp ngược: có một bản ghi gốc trên cùng, từ đó toả xuống các bản ghi con, mỗi thực thể được phép có nhiều con nhưng chỉ có đúng một cha, nên đường từ gốc tới một bản ghi là duy nhất. Mục "Data is organized as a binary tree and each entity can have several children" tự mâu thuẫn, cây nhị phân khống chế mỗi nút tối đa hai con, còn mô hình phân cấp không giới hạn như vậy. Mục "Data is organized as a binary tree and each entity have only one children" sai cả hai chỗ, vừa áp cây nhị phân vừa bó mỗi thực thể một con, lúc đó cấu trúc thành một chuỗi thẳng. Mục "Data is organized as an inverted tree and each entity have only one child" đúng hình dạng nhưng đặt giới hạn sai phía, ràng buộc chỉ một nằm ở phía cha chứ không ở phía con.

Đáp án đúng: "1011". Cách tìm biểu diễn bù hai của một số âm gồm ba bước: viết trị tuyệt đối trên bốn bit được 0101, đảo tất cả các bit được 1010, rồi cộng thêm 1 được 1011. Kiểm lại theo trọng số, bit trái nhất mang trọng số âm 8 nên 1011 bằng âm 8 cộng 2 cộng 1, đúng bằng âm 5; phép kiểm hai chiều này khép kín nên kết quả không còn chỗ nghi ngờ. Mục "1101" bằng âm 8 cộng 4 cộng 1, tức âm 3. Mục "1110" bằng âm 8 cộng 4 cộng 2, tức âm 2. Mục "1100" bằng âm 8 cộng 4, tức âm 4. Cả ba đều có bit dấu bằng 1 nên đều là số âm, nhưng giá trị lệch so với yêu cầu.

Đáp án đúng: "Subtraction". Phép trừ làm việc trên giá trị số của hai toán hạng và trả về một giá trị số, nên nó là phép toán số học; trong máy tính nó thường được thực hiện bằng cách cộng số thứ nhất với bù hai của số thứ hai, vì vậy chỉ cần một mạch cộng là đủ. Mục "The exclusive OR" là phép logic, nó xét từng cặp bit ở cùng vị trí và cho 1 khi hai bit khác nhau, không có nhớ sang vị trí bên cạnh. Mục "The unary NOT" cũng là phép logic, chỉ đảo từng bit của một toán hạng. Mục "The binary AND" là phép logic lấy giao từng bit, thường dùng để xoá bớt bit bằng mặt nạ. Dấu hiệu phân biệt là phép số học có nhớ lan giữa các vị trí bit, còn phép logic xử lý từng vị trí độc lập.

Đáp án đúng: "TCP provides error recovery, congestion control, and flow control, while UDP provides none of these features". Giao thức hướng kết nối của tầng vận tải thiết lập kết nối trước khi truyền, đánh số thứ tự từng byte, chờ báo nhận, truyền lại khi mất, đồng thời điều tiết tốc độ theo sức bên nhận và mức tắc nghẽn của mạng; giao thức còn lại chỉ bọc dữ liệu vào một datagram rồi gửi, không có các cơ chế đó nên nhanh hơn. Mục "UDP is connection-oriented and ensures data reliability, while TCP is connectionless and faster" đảo vai trò của hai giao thức. Mục "Both TCP and UDP are connection-oriented protocols but differ in flow control mechanisms" sai vì giao thức nhẹ không thiết lập kết nối nào. Mục "TCP is primarily used for real-time communication, while UDP is used for file transfers" cũng ngược: truyền tệp cần đúng từng byte nên dùng loại tin cậy, còn thoại và video trực tiếp chịu được mất gói nhưng không chịu được chờ.

Đáp án đúng: "Assembly". Hợp ngữ là ngôn ngữ bậc thấp: mỗi câu lệnh gần như tương ứng một lệnh máy, người viết phải biết thanh ghi và tập lệnh của bộ xử lý, và mã viết cho kiến trúc này không chạy trên kiến trúc khác. Mục "Ruby" là ngôn ngữ bậc cao, cú pháp gần ngôn ngữ tự nhiên và che hết chi tiết phần cứng. Mục ghi tên ngôn ngữ «C» cũng là ngôn ngữ bậc cao, có kiểu dữ liệu, hàm và cấu trúc điều khiển; nó cho phép làm việc sát hệ thống hơn nhiều ngôn ngữ khác nhưng vẫn độc lập với kiến trúc máy và cần trình biên dịch. Mục "Pascal" là ngôn ngữ bậc cao có cấu trúc, lâu nay dùng để dạy lập trình. Dấu hiệu chung của ba mục đó là một câu lệnh sinh ra nhiều lệnh máy.

Đáp án đúng: "325.6". Phần nguyên đổi bằng cách chia liên tiếp cho 8 và lấy số dư từ dưới lên: 213 chia 8 bằng 26 dư 5, 26 chia 8 bằng 3 dư 2, 3 chia 8 bằng 0 dư 3, đọc ngược được 325. Phần lẻ đổi bằng cách nhân liên tiếp với 8 và lấy phần nguyên: 0,75 nhân 8 bằng 6,0 nên được chữ số 6 và dừng. Kiểm lại 3 nhân 64 cộng 2 nhân 8 cộng 5 bằng 213, còn 6 chia 8 bằng 0,75. Mục "225.7" cho 2 nhân 64 cộng 2 nhân 8 cộng 5 bằng 181 và phần lẻ 0,875. Mục "235.6" cho 2 nhân 64 cộng 3 nhân 8 cộng 5 bằng 157. Mục "322.5" cho 3 nhân 64 cộng 2 nhân 8 cộng 2 bằng 210 và phần lẻ 0,625.

Đáp án đúng: "ext4". Đây là hệ tệp mặc định của hầu hết bản phân phối Linux hiện nay, phát triển tiếp từ hai thế hệ trước, có ghi nhật ký để phục hồi nhanh sau sự cố và quản lý vùng dữ liệu theo khoảng liên tục nên ít phân mảnh. Mục "NTFS" là hệ tệp của Windows; Linux đọc ghi được nó nhưng không dùng làm hệ tệp gốc. Mục "FAT32" là hệ tệp cũ, nay chủ yếu dùng cho thẻ nhớ và ổ USB vì nhiều thiết bị hiểu được, nó không ghi nhật ký và giới hạn mỗi tệp dưới 4 GB. Mục "HFS+" là hệ tệp của máy Mac, về sau được thay bằng một hệ tệp mới hơn của chính hãng đó. Mỗi hệ điều hành gắn với hệ tệp riêng, và lựa chọn đúng là hệ tệp sinh ra cùng dòng Linux.

Đáp án đúng: "To store data as character sequences". Tệp văn bản chỉ chứa các ký tự được mã hoá theo một bảng mã như ASCII hay Unicode, nên một số thực đang nằm trong bộ nhớ dưới dạng dấu phẩy động nhị phân phải được dịch thành dãy ký tự chữ số, dấu phân cách và dấu, nếu không thì mở tệp ra chỉ thấy rác. Mục "To reduce the file size for storage efficiency" ngược thực tế, dạng ký tự thường tốn nhiều byte hơn bản nhị phân gọn của cùng con số đó. Mục "To enable random access to the data" không đúng, truy cập ngẫu nhiên dựa vào việc các bản ghi dài bằng nhau, còn chuỗi ký tự dài ngắn khác nhau lại làm việc này khó hơn. Mục "To prevent collisions during retrieval" nói về đụng độ khi băm khoá thành địa chỉ, chuyện của tệp băm chứ không phải của việc ghi văn bản.

Đáp án đúng: "White-box testing". Kỹ thuật kiểm thử này mở mã nguồn ra để xem, dựa vào cấu trúc bên trong và luồng điều khiển để chọn ca kiểm thử, mục tiêu là đi qua hết câu lệnh, hết nhánh rẽ và hết các đường thực thi đáng kể. Mục "Black-box testing" làm ngược lại, nó chỉ dựa vào đặc tả và quan sát cặp dữ liệu vào ra, coi phần bên trong là kín. Mục "Integration testing" là một mức kiểm thử, lo việc ghép các mô-đun lại xem giao diện giữa chúng có khớp không, và mức này có thể thực hiện theo cả hai kỹ thuật nói trên. Mục "User acceptance testing" do người dùng tiến hành để nghiệm thu theo yêu cầu nghiệp vụ, càng không nhìn vào mã.

Đáp án đúng: "Transport layer". Tầng vận tải chịu trách nhiệm giao dữ liệu tin cậy giữa hai tiến trình ở hai đầu, nhờ giao thức đánh số thứ tự, chờ báo nhận, truyền lại phần bị mất, sắp lại đúng thứ tự và kiểm soát luồng. Mục "Physical layer" chỉ lo biến bit thành tín hiệu trên môi trường truyền, nó không biết gói nào mất. Mục "Data link layer" có kiểm soát lỗi nhưng chỉ trên từng chặng giữa hai thiết bị kề nhau, qua chặng sau là trách nhiệm hết, nên không bảo đảm được đường đi xuyên nhiều mạng. Mục "Application layer" lo nội dung và định dạng của dịch vụ như thư hay web, nó dựa vào tầng dưới để có dữ liệu đủ và đúng chứ không tự bảo đảm.

Đáp án đúng: "It represents the two characters 'a' and 'c'". Chuỗi 16 bit chia thành hai byte: 01100001 và 01100011, đổi sang thập phân là 97 và 99, tra bảng mã ASCII thì đó là hai chữ cái thường. Mục "It represents the two characters 'A' and 'C'" sai vì chữ hoa có mã 65 và 67, viết nhị phân là 01000001 và 01000011, bit thứ ba từ trái bằng 0 chứ không bằng 1 như chuỗi đã cho. Mục "It represents the two characters 'A' and 'b'" trộn một chữ hoa với một chữ thường, cho mã 65 và 98, tức 01000001 và 01100010, cả hai byte đều lệch. Mục "It represents the decimal number 24903" cũng không khớp: đọc cả 16 bit như một số nguyên không dấu thì giá trị là 24931. Khoảng cách 32 giữa mã chữ hoa và chữ thường chính là bit thứ ba từ trái trong mỗi byte.

Đáp án đúng: "172.16.254.1". Địa chỉ IPv4 gồm bốn byte viết cách nhau bằng dấu chấm, nên mỗi nhóm chỉ nhận giá trị từ 0 đến 255; lựa chọn đúng có cả bốn nhóm nằm trong khoảng đó nên là địa chỉ hợp lệ. Mục "300.168.0.1" có nhóm đầu bằng 300, vượt mức tối đa 255 mà một byte biểu diễn được. Mục "192.168.1.256" sai ở nhóm cuối, 256 cần tới chín bit nên không nằm trong một byte, giá trị lớn nhất chỉ là 255. Mục "123.456.78.90" có nhóm thứ hai bằng 456, càng vượt xa giới hạn. Lưu ý là giá trị nằm trong khoảng cho phép chỉ bảo đảm địa chỉ viết đúng dạng, còn việc địa chỉ đó thuộc mạng riêng hay mạng công cộng lại là chuyện khác.

Đáp án đúng: "Repeatedly comparing adjacent elements and swapping them if they are in the wrong order." Thuật toán này đi dọc danh sách, so sánh từng cặp phần tử đứng cạnh nhau và đổi chỗ chúng nếu thứ tự sai; sau mỗi lượt phần tử lớn nhất trong phần chưa sắp sẽ nổi về cuối, lặp đủ số lượt thì cả danh sách có thứ tự. Mục "Dividing the list into two parts and inserting elements from unsorted to sorted" là cơ chế của sắp xếp chèn, nó lấy một phần tử rồi tìm chỗ đặt vào phần đã sắp. Mục "Finding the smallest element and swapping it to the correct position" là cơ chế của sắp xếp chọn, mỗi lượt chỉ có một phép đổi chỗ sau khi đã tìm ra phần tử nhỏ nhất. Mục "Dividing the list in half and searching" không phải thuật toán sắp xếp, đó là tìm nhị phân, nó còn đòi danh sách phải sắp xếp sẵn.

Đáp án đúng: "531". Đổi sang hệ tám bằng cách chia liên tiếp cho 8 rồi đọc các số dư từ dưới lên: 345 chia 8 bằng 43 dư 1, 43 chia 8 bằng 5 dư 3, 5 chia 8 bằng 0 dư 5, ghép lại được 531. Kiểm ngược theo trọng số: 5 nhân 64 cộng 3 nhân 8 cộng 1 bằng 320 cộng 24 cộng 1, đúng bằng 345, nên kết quả này khép kín về số học. Mục "521" cho 5 nhân 64 cộng 2 nhân 8 cộng 1 bằng 337, thiếu 8 so với yêu cầu. Mục "505" cho 5 nhân 64 cộng 0 cộng 5 bằng 325. Mục "515" cho 5 nhân 64 cộng 1 nhân 8 cộng 5 bằng 333. Cách kiểm nhanh là nhân ngược lại theo trọng số 64, 8 và 1 rồi so với số thập phân ban đầu.

Đáp án đúng: "UDP packets". Môi trường truyền ở tầng vật lý là vật chất dẫn được tín hiệu, gồm loại có dây và loại không dây; còn datagram của giao thức nhẹ ở tầng vận tải là dữ liệu chạy trên môi trường đó chứ không phải bản thân môi trường, nên nó là thứ bị loại. Mục "Fiber optic cables" là môi trường có dây, dẫn tín hiệu ánh sáng trong lõi thuỷ tinh, băng thông lớn và không bị nhiễu điện từ. Mục "Coaxial cables" cũng là môi trường có dây, dẫn tín hiệu điện trên lõi đồng có lớp chắn bọc ngoài. Mục "Wi-Fi signals" là môi trường không dây, dùng sóng vô tuyến lan trong không khí. Ba thứ đó đều ở tầng dưới cùng, nơi người ta chỉ quan tâm tới bit và tín hiệu.

Đáp án đúng: "Only for small lists, or lists that are not searched often, and are not ordered." Tìm tuần tự duyệt lần lượt từng phần tử cho tới khi gặp giá trị cần tìm hoặc hết danh sách, trung bình phải so sánh khoảng một nửa số phần tử, nên nó chỉ đáng dùng khi danh sách nhỏ, ít phải tìm, hoặc chưa được sắp xếp, vì lúc đó cách nhanh hơn không áp dụng được. Mục "For very large, sorted lists." là trường hợp nên dùng tìm nhị phân, thứ chỉ cần số phép so sánh theo logarit. Mục "When the list is organized hierarchically" ứng với dữ liệu dạng cây, ở đó người ta đi theo đường từ gốc xuống. Mục "When the exact position of the target is known" tự loại mình, biết sẵn vị trí thì truy cập trực tiếp vào chỗ đó, không phải tìm kiếm gì nữa.

Đáp án đúng: "They must have the same attributes (columns)." Phép hợp ghép các dòng của hai quan hệ thành một quan hệ mới, nên hai quan hệ đầu vào phải tương thích về cấu trúc: cùng số cột, các cột tương ứng cùng tên và cùng miền giá trị, nếu không thì không rõ dòng kết quả có những thuộc tính nào. Mục "They must have different primary keys" đặt ra điều kiện không liên quan, khoá chính chỉ ràng buộc trong từng bảng. Mục "They must be sorted in the same order" quên rằng quan hệ là một tập hợp các dòng, thứ tự dòng không mang nghĩa và phép hợp không phụ thuộc thứ tự. Mục "They must contain unique data" lẫn điều kiện với kết quả, các dòng trùng nhau được loại bỏ trong quan hệ kết quả chứ không bị cấm ở đầu vào.

Đáp án đúng: "Data structure and operations". Kiểu dữ liệu trừu tượng đóng gói hai thứ vào một khối: cách tổ chức dữ liệu bên trong, và tập các phép toán hợp lệ được công bố ra ngoài. Người dùng chỉ gọi các phép toán đó mà không cần và không được phụ thuộc vào cách hiện thực, nhờ vậy đổi cách lưu bên trong không làm vỡ chương trình đang dùng. Mục "Hardware and software" không thuộc phạm vi của mô hình dữ liệu này. Mục "Database and operations" đưa vào cơ sở dữ liệu, vốn là một hệ lưu trữ lớn chứ không phải thành phần bên trong một kiểu dữ liệu. Mục "Data structure and algorithms" gần đúng nhưng lệch một bước: thuật toán là cách hiện thực các phép toán và thuộc phần bị che đi, còn thứ được công bố cho người dùng chính là tập phép toán.

Đáp án đúng: "Segmentation". Phân đoạn chia không gian địa chỉ của chương trình theo đơn vị logic do chính chương trình gợi ra, chẳng hạn đoạn mã, đoạn dữ liệu, đoạn ngăn xếp hay từng hàm, và những phần này dài ngắn khác nhau nên các đoạn có kích thước thay đổi, mỗi đoạn được ghi địa chỉ đầu cùng độ dài trong bảng đoạn. Mục "Paging" chia bộ nhớ thành các trang bằng nhau và cố định, chính sự bằng nhau đó làm việc cấp phát đơn giản nhưng không theo cấu trúc logic của chương trình. Mục "Virtual memory" là kỹ thuật cho chương trình lớn hơn bộ nhớ thật vẫn chạy được, nó dựa trên phân trang hoặc phân đoạn theo yêu cầu chứ không tự quy định cỡ khối. Mục "Swapping" chuyển cả tiến trình giữa bộ nhớ và đĩa, không phải cách chia bộ nhớ.

Đáp án đúng: "Selection sort". Thuật toán này coi danh sách gồm hai phần, phần đầu đã có thứ tự và phần sau chưa; mỗi lượt nó quét phần chưa sắp để tìm phần tử nhỏ nhất rồi đổi chỗ phần tử đó với phần tử đứng đầu phần chưa sắp, nhờ vậy ranh giới giữa hai phần dịch sang một ô và mỗi lượt chỉ cần đúng một phép đổi chỗ. Mục "Bubble sort" không tìm phần tử nhỏ nhất, nó đổi chỗ liên tục các cặp kề nhau nên một lượt có thể sinh rất nhiều phép đổi. Mục "Insertion sort" cũng chia hai phần nhưng làm ngược chiều: lấy phần tử đầu của phần chưa sắp rồi chèn vào đúng vị trí trong phần đã sắp, phải dịch các phần tử lớn hơn sang chỗ khác. Mục "Binary sort" không phải tên của một thuật toán sắp xếp, cách chia đôi vốn thuộc về tìm kiếm.