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

Đáp án đúng: "[-35, -15, -10, 1, 5, 7, 12, 50]". Tìm kiếm nhị phân chỉ chạy đúng khi danh sách đã được sắp thứ tự, vì mỗi bước nó so khoá với phần tử giữa rồi bỏ hẳn một nửa; danh sách được chọn tăng dần đều từ giá trị nhỏ nhất đến giá trị lớn nhất nên điều kiện được thoả. "[-60, 37, 42, -63, 59, 53, -78, 57]" không sắp thứ tự: ngay sau giá trị 42 đã tụt xuống số âm, nên việc loại nửa danh sách sẽ loại mất cả khoá cần tìm. "[3, 1, 2]" cũng không sắp, phần tử đầu lớn hơn hai phần tử đứng sau. "[1, 2, 3, 4, 5, 6, 7, 9, 0]" tăng dần cho tới 9 rồi đột ngột quay về 0 ở cuối; chỉ một chỗ sai thứ tự là đủ làm thuật toán kết luận sai, chẳng hạn khi tìm giá trị 0 nó sẽ bỏ ngay nửa sau.

Đáp án đúng: "To provide services directly to end-users and applications". Tầng ứng dụng trong mô hình TCP/IP là tầng trên cùng, nơi các giao thức như duyệt web, thư điện tử hay truyền tệp cung cấp dịch vụ trực tiếp cho người dùng và cho chương trình ứng dụng, còn phần việc chuyển dữ liệu đã do các tầng dưới lo. "To establish and maintain logical connections" sai vì thiết lập và duy trì kết nối logic giữa hai đầu cuối là nhiệm vụ của tầng giao vận. "To encrypt data for secure transmission" sai vì mã hoá không phải nhiệm vụ định danh của tầng ứng dụng; mô hình TCP/IP không có tầng riêng cho bảo mật, việc này được cài thêm ở nhiều mức khác nhau. "To manage data packets and frames" sai vì xử lý gói là việc của tầng mạng, còn khung dữ liệu thuộc tầng liên kết dữ liệu.

Đáp án đúng: "1". Phép hoặc loại trừ cho kết quả 1 khi hai bit đầu vào khác nhau và cho 0 khi chúng giống nhau, vì thế nó được dùng để kiểm tra hai mẫu bit có khác nhau không, để đảo bit chọn lọc bằng mặt nạ, hoặc để dò lỗi khi truyền. "0" sai vì giá trị này ứng với trường hợp hai bit bằng nhau, cùng là 0 hoặc cùng là 1. "The operation is not possible." sai vì đây là một phép toán logic cơ bản, mạch thực hiện nó có mặt trong mọi đơn vị số học và logic. "The result is undefined." sai vì bảng chân lý của phép này xác định đầy đủ cả bốn tổ hợp đầu vào, không có trường hợp nào bỏ trống hay nhập nhằng.

Đáp án đúng: "Coaxial cable and Fiber-optic cable". Môi trường có dẫn hướng là môi trường dẫn tín hiệu đi trong một vật dẫn vật lý: cáp đồng trục dẫn tín hiệu điện trong lõi đồng có lưới chắn bọc ngoài, còn cáp quang dẫn tín hiệu ánh sáng trong lõi thuỷ tinh nhờ phản xạ toàn phần. "Radio and Microwaves" sai vì sóng vô tuyến và vi ba lan truyền tự do trong không gian, thuộc nhóm không dẫn hướng và dùng ăng ten thay vì dây. "Infrared wave and twisted-pair cable" sai vì dù cáp xoắn đôi đúng là môi trường có dẫn hướng, hồng ngoại lại là sóng truyền trong không khí, nên cặp này lẫn hai nhóm vào nhau. "Water and air" sai vì nước và không khí chỉ là môi trường tự nhiên, không phải vật dẫn được chế tạo để truyền tín hiệu trong viễn thông.

Đáp án đúng: "Collect the information needed to be stored --> Build an entity-relation model --> Normalization". Thiết kế cơ sở dữ liệu đi từ thực tế vào mô hình: trước hết thu thập xem cần lưu những thông tin gì, rồi dựng mô hình thực thể liên kết để nhận ra các thực thể, thuộc tính và quan hệ, sau đó mới chuẩn hoá những quan hệ sinh ra từ mô hình để bỏ dư thừa. "Collect the information needed to be stored --> Normalization --> Build an entity-relation model" đảo hai bước cuối, mà chuẩn hoá cần có sẵn các bảng để làm việc trên đó nên không thể đứng trước khi dựng mô hình. "Build an entity-relation model --> Normalization --> Collect the information needed to be stored" đặt việc thu thập thông tin xuống cuối, nghĩa là dựng mô hình khi còn chưa biết phải lưu gì. "Not need be done through a step-by-step process" sai vì đây là quy trình có thứ tự rõ ràng; làm tuỳ hứng sẽ dẫn tới lược đồ dư thừa, khó sửa và dễ sinh bất thường khi cập nhật.

Đáp án đúng: "Display output". Bộ xử lý trung tâm làm việc theo chu trình máy gồm lấy lệnh, giải mã lệnh rồi thi hành lệnh. Việc hiện kết quả ra màn hình thuộc thiết bị ra cùng bộ điều khiển màn hình trong phân hệ vào ra; bộ xử lý chỉ ghi dữ liệu vào bộ nhớ hoặc cổng tương ứng rồi để thiết bị lo phần trình bày. "Fetch instructions" là chức năng của bộ xử lý, nó đọc lệnh kế tiếp từ bộ nhớ theo địa chỉ trong con trỏ lệnh. "Decode instructions" là chức năng của đơn vị điều khiển, nó dịch mã lệnh thành các tín hiệu điều khiển. "Execute instructions" là chức năng của đơn vị số học và logic cùng các thanh ghi, nơi phép toán thực sự được tiến hành.

Đáp án đúng: "Minus". Phép lấy hiệu hai tập kết quả trong ngôn ngữ của SQL Server được viết bằng từ khoá EXCEPT; từ khoá được hỏi tới ở đây là của Oracle, nên câu lệnh mang nó sẽ báo lỗi cú pháp khi chạy trên SQL Server. "Union" vẫn dùng được vì hợp hai tập kết quả là toán tử chuẩn, có cả dạng giữ lại bản ghi trùng. "Intersection" dùng được dưới dạng toán tử giao, SQL Server hỗ trợ phép lấy phần chung của hai tập kết quả. "Join" dùng được và là phép thông dụng nhất, ghép hai bảng theo điều kiện so khớp với nhiều biến thể trong và ngoài. Điểm cần nhớ là cùng một phép toán quan hệ có thể mang tên từ khoá khác nhau giữa các hệ quản trị.

Đáp án đúng: "Trade secret". Bí mật thương mại bảo hộ thông tin kinh doanh có giá trị nhờ chính việc nó được giữ kín, như công thức sản phẩm, danh sách khách hàng hay quy trình nội bộ; bảo hộ kéo dài chừng nào chủ sở hữu còn áp dụng biện pháp giữ kín hợp lý. "Trademark" sai vì nó bảo hộ dấu hiệu dùng để phân biệt hàng hoá và dịch vụ, mà dấu hiệu thì phải công khai mới làm được việc phân biệt. "Patent" sai vì để lấy độc quyền có thời hạn, người nộp đơn phải bộc lộ đầy đủ giải pháp kỹ thuật cho công chúng, tức đánh đổi chính sự bí mật. "Copyright" sai vì nó bảo hộ hình thức thể hiện của tác phẩm, không bảo hộ thông tin kinh doanh được giữ kín.

Đáp án đúng: "NOT". Phép phủ định là phép một ngôi vì nó chỉ cần một toán hạng: đưa vào một bit hoặc một mẫu bit, kết quả là mẫu bit đã bị đảo từng bit một, 0 thành 1 và 1 thành 0. "AND" là phép hai ngôi, cần hai mẫu bit và cho 1 chỉ khi cả hai bit tương ứng đều là 1. "OR" cũng là phép hai ngôi, cho 1 khi ít nhất một trong hai bit là 1. "XOR" là phép hai ngôi, cho 1 khi hai bit tương ứng khác nhau. Dấu hiệu nhận biết nằm ở số toán hạng mà phép toán đòi hỏi, không nằm ở độ phức tạp của bảng chân lý.

Đáp án đúng: "To synchronize sequence numbers and establish connection parameters". Bắt tay mở kết nối tồn tại để hai bên thống nhất số thứ tự khởi đầu dùng cho việc đánh số byte và thoả thuận các tham số kết nối như kích thước cửa sổ hay kích thước đoạn lớn nhất; đoạn mang đồng thời cờ đồng bộ và cờ báo nhận chính là bước giữa của quá trình đó. "To acknowledge the receipt of data segments" sai vì báo nhận dữ liệu đã tới là việc của cờ báo nhận trong pha truyền, còn bắt tay diễn ra trước khi có byte dữ liệu nào. "To request retransmission of lost segments" sai vì yêu cầu gửi lại đoạn bị mất được kích hoạt bởi hết thời gian chờ hoặc báo nhận trùng lặp, không phải bởi bắt tay. "To terminate the connection" sai vì đóng kết nối dùng cờ kết thúc theo một trình tự riêng.

Đáp án đúng: "Arithmetic right shift". Dịch phải số học đẩy mọi bit sang phải một vị trí nhưng giữ lại bit dấu bằng cách nhân bản nó vào chỗ trống bên trái, nên số âm vẫn còn âm; mỗi lần dịch tương đương chia cho 2 với phần dư bị bỏ đi. "Logical right shift" sai vì nó chèn bit 0 vào bên trái, biến một số âm dạng bù hai thành số dương rất lớn, tức phá mất dấu. "Logical left shift" sai vì dịch sang trái tương đương nhân với 2, đi ngược yêu cầu chia. "Arithmetic left shift" sai vì nó cũng là phép nhân với 2 chứ không phải chia, và còn có thể làm bit dấu bị đẩy ra ngoài gây tràn số, đổi hẳn dấu của kết quả.

Đáp án đúng: "2*10^4 packets". Tổng số bit truyền được trong 2 giây là 10^7 nhân 2, tức 2 nhân 10^7 bit. Mỗi gói dài 1000 bit nên số gói tối đa bằng 2 nhân 10^7 chia cho 1000, được 2 nhân 10^4 gói. "2*10^5 packets" lớn gấp mười lần kết quả đúng, nó ứng với trường hợp mỗi gói chỉ dài 100 bit. "10^4 packets" chỉ là số gói truyền trong 1 giây, thiếu một lần nhân cho khoảng thời gian 2 giây. "2*10^6 packets" lớn gấp một trăm lần, tương ứng với gói dài 10 bit. Sai số kiểu này thường do nhầm bậc của luỹ thừa, nên cần viết rõ đơn vị bit và giây ở từng bước tính.

Đáp án đúng: "Leftmost node". Trong cây tìm kiếm nhị phân, mọi khoá ở cây con bên trái một nút đều nhỏ hơn khoá của nút đó, nên cứ đi theo liên kết trái từ gốc đến khi gặp nút không còn con trái là tới khoá nhỏ nhất. "Root" sai vì gốc chỉ là điểm bắt đầu, nó lớn hơn toàn bộ cây con bên trái của mình. "Rightmost node" sai vì đi mãi theo liên kết phải sẽ tới khoá lớn nhất, đúng ngược lại. "Complete binary tree" sai vì đây là tên một dạng cây nói về hình dáng, không phải một vị trí trong cây nên không trả lời được câu hỏi về chỗ nằm của khoá. "Any leaf node" sai vì lá nằm bên phía phải của cây có thể mang khoá rất lớn; riêng việc một nút không có con không nói lên điều gì về giá trị khoá.

Đáp án đúng: "Machine language is directly understood by a computer, while high-level languages must be converted". Ngôn ngữ máy là dãy mẫu bit mà mạch điều khiển của bộ xử lý giải mã trực tiếp; chương trình viết bằng ngôn ngữ cấp cao phải qua trình biên dịch hoặc trình thông dịch để thành mã máy mới chạy được. "Machine language uses symbols, while high-level languages use binary patterns" sai vì nói ngược: ngôn ngữ cấp cao mới dùng từ khoá và ký hiệu gần với tiếng người, còn mã máy là mẫu bit. "Machine language is portable, while high-level languages are machine-dependent." sai vì mã máy gắn chặt với tập lệnh của một kiến trúc nên không khả chuyển, trong khi ngôn ngữ cấp cao chính là thứ cho phép mang mã nguồn sang máy khác rồi dịch lại. "High-level languages are tedious to write, while machine language is easier." sai vì viết mã máy khó và dễ sai hơn nhiều, hơn nữa độ tiện tay không phải khác biệt về việc máy hiểu được hay không.

Đáp án đúng: "Monoprogramming dedicates most memory to one program, while multiprogramming allows multiple programs concurrently.". Đơn chương trình dành gần như toàn bộ bộ nhớ chính cho một chương trình, chạy xong mới nạp chương trình kế tiếp; đa chương trình chia bộ nhớ cho nhiều chương trình cùng nằm trong đó và luân phiên dùng bộ xử lý, nhờ vậy lấp được thời gian chờ vào ra. "Monoprogramming uses virtual memory, while multiprogramming does not" sai vì bộ nhớ ảo ra đời để phục vụ đa chương trình. "Multiprogramming loads programs entirely into memory, while monoprogramming uses demand paging" sai vì nói ngược: nạp trọn chương trình vào bộ nhớ là cách của đơn chương trình, còn phân trang theo yêu cầu là kỹ thuật của đa chương trình. "Monoprogramming always stores programs on disk, multiprogramming in RAM" sai vì chương trình nào cũng phải vào bộ nhớ chính mới thi hành được, kể cả trong đơn chương trình.

Đáp án đúng: "random file structure". Cấu trúc tệp truy nhập ngẫu nhiên cho phép tính ra vị trí của bản ghi từ khoá của nó, bằng hàm băm hoặc qua tệp chỉ mục, nên đọc được đúng bản ghi cần mà không phải đi qua những bản ghi đứng trước. "sequential file structure" sai vì tệp tuần tự lưu bản ghi nối tiếp theo thứ tự và chỉ đọc được lần lượt từ đầu, muốn tới bản ghi thứ một nghìn thì phải vượt qua chín trăm chín mươi chín bản ghi trước nó. "Both a and b are correct" sai vì không thể cùng đúng khi một trong hai cấu trúc được nêu không có khả năng truy nhập trực tiếp. "Both a and b are incorrect" sai vì đã có một cấu trúc đáp ứng đúng yêu cầu nêu trong câu hỏi nên không thể phủ định cả hai.

Đáp án đúng: "Ready state". Job còn chờ bên ngoài bộ nhớ nằm ở trạng thái giữ; khi hệ điều hành cấp đủ bộ nhớ và nạp nó vào, nó trở thành tiến trình ở trạng thái sẵn sàng, tức đã đủ điều kiện chạy và chỉ còn chờ bộ định thời cấp bộ xử lý. "Hold state" sai vì đó là trạng thái trước khi được nạp, lúc job còn xếp hàng chờ tài nguyên. "Running state" sai vì tiến trình chỉ bước vào trạng thái đang chạy khi thực sự được cấp bộ xử lý, mà nhiều tiến trình cùng sẵn sàng thì mỗi thời điểm trên một lõi chỉ một tiến trình được chạy. "Terminated state" sai vì đó là trạng thái cuối, khi tiến trình đã chạy xong hoặc bị huỷ và tài nguyên được thu hồi.

Đáp án đúng: "Relationships between tables are established using pointers.". Mô hình quan hệ nối các bảng bằng giá trị chứ không bằng con trỏ: bảng con chứa cột khoá ngoại mang đúng giá trị khoá chính của bảng cha, và hệ quản trị dựa vào sự trùng giá trị đó khi ghép bảng. Dùng con trỏ địa chỉ là cách của mô hình mạng và mô hình phân cấp trước đó. "Data is stored in tables with rows and columns." đúng là đặc điểm của mô hình quan hệ, dữ liệu nằm trong bảng hai chiều gồm các hàng và các cột. "Each table has a primary key to uniquely identify each row." đúng là đặc điểm, khoá chính bảo đảm mỗi hàng được phân biệt duy nhất. "Data integrity is enforced using constraints such as foreign keys." cũng đúng, các ràng buộc như khoá ngoại giữ cho dữ liệu không mâu thuẫn giữa các bảng.

Đáp án đúng: "An algorithm that calls itself". Thuật toán đệ quy là thuật toán được định nghĩa bằng chính nó: trong lời giải có lời gọi lại chính thuật toán trên dữ liệu nhỏ hơn, cộng thêm một trường hợp cơ sở để dãy lời gọi dừng lại. Tính giai thừa hay duyệt cây là ví dụ quen thuộc. "An algorithm that runs only once" sai vì chạy đúng một lần là mô tả chung của hầu hết lời gọi hàm thông thường, không liên quan tới cách định nghĩa đệ quy. "An algorithm that sorts data" sai vì sắp xếp là một bài toán cụ thể; có thuật toán sắp xếp viết theo lối đệ quy nhưng cũng có thuật toán sắp xếp viết theo lối lặp. "An algorithm that stores data" sai vì lưu dữ liệu là việc của cấu trúc dữ liệu, không phải đặc điểm của một thuật toán.

Đáp án đúng: "(01001100)2". Mỗi chữ số hệ mười sáu đổi thành đúng bốn bit và giữ nguyên thứ tự: chữ số 4 cho 0100, chữ C có giá trị 12 nên cho 1100, ghép lại được 0100 1100. "(11000100)2" sai vì đảo vị trí hai nhóm, đặt nhóm của 12 lên trước nhóm của 4. "(01001010)2" sai ở nhóm sau, vì 1010 có giá trị 10 chứ không phải 12. "(00101100)2" sai ở nhóm đầu, vì 0010 có giá trị 2 chứ không phải 4. Cách kiểm tra nhanh là đổi cả hai vế sang hệ mười: giá trị đã cho bằng 4 nhân 16 cộng 12, tức 76, và chỉ mẫu bit được chọn mới có giá trị 76.