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

Đáp án đúng: "EDVAC". EDVAC là máy tính đầu tiên được thiết kế theo nguyên lý chương trình lưu trữ mà von Neumann trình bày trong bản thảo năm 1945, tức lệnh và dữ liệu cùng nằm trong bộ nhớ. "Pascal" không phải máy tính mà là tên một ngôn ngữ lập trình, đặt theo tên nhà toán học Blaise Pascal. "Pascaline" là máy tính cơ khí cộng trừ do Pascal chế tạo ở thế kỷ mười bảy, nó không có bộ nhớ chương trình và chỉ làm được phép tính cố định. "ABC" là máy tính điện tử của Atanasoff cùng Berry, dùng để giải hệ phương trình, nhưng chương trình nằm trong cách đấu nối phần cứng nên nó không thuộc mô hình chương trình lưu trữ.

Đáp án đúng: "Port numbers". Tầng giao vận phải nối đúng tiến trình với tiến trình, nên ngoài việc biết máy nào nó còn cần biết chương trình nào trong máy đó; số hiệu cổng là định danh làm việc ấy, mỗi tiến trình đang chờ hoặc đang gửi được gắn một số cổng, và cặp địa chỉ máy cùng số cổng xác định duy nhất một đầu liên lạc. Loại "MAC addresses" định danh giao diện mạng ở tầng liên kết dữ liệu, chỉ có nghĩa trong phạm vi một đường truyền. Loại "IP addresses" định danh máy hay giao diện trên liên mạng, nó đưa dữ liệu tới đúng máy nhưng không chỉ ra tiến trình nào. Cách dùng "Process names" không khả thi vì tên tiến trình do từng hệ điều hành tự đặt, không có chuẩn chung giữa hai bên liên lạc.

Đáp án đúng: "4". Mô hình von Neumann chia phần cứng máy tính thành bốn hệ con: bộ nhớ, đơn vị số học và logic, đơn vị điều khiển, cùng hệ vào ra; chương trình và dữ liệu đều nằm trong bộ nhớ, còn đơn vị điều khiển lần lượt nạp rồi thi hành từng lệnh. "3" thiếu một hệ con, thường do gộp hệ vào ra vào bộ nhớ hoặc gộp hai đơn vị bên trong bộ xử lý thành một. "5" đếm dư, chẳng hạn tách đường truyền dữ liệu hay nhóm thanh ghi ra thành hệ con riêng, nhưng đó là bộ phận nằm bên trong các hệ con đã kể. "6" càng dư hơn nữa và không khớp với cách phân chia của mô hình này.

Đáp án đúng: "To provide a set of instructions that dictates what to do with data". Trong mô hình Turing, máy tính vạn năng nhận cả dữ liệu lẫn chương trình làm đầu vào, trong đó chương trình là tập lệnh nói cho máy biết phải làm gì với dữ liệu để sinh ra kết quả; chính việc đổi chương trình mà không phải đổi máy làm nên tính vạn năng. Vai trò "To define the hardware architecture." không thuộc chương trình, vì kiến trúc phần cứng do người thiết kế máy quyết định và đã cố định trước khi chương trình chạy. Vai trò "To manage memory allocation." là việc của hệ điều hành, bản thân nó cũng chỉ là một chương trình trong số nhiều chương trình. Vai trò "To establish communication protocols between devices" là việc của các giao thức truyền thông, không phải định nghĩa của chương trình.

Đá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: "Indexed file structure". Tệp có chỉ mục giữ kèm một bảng ánh xạ từ khoá của bản ghi sang vị trí của bản ghi đó trong tệp, nên muốn lấy một bản ghi thì tra bảng để biết chỗ rồi nhảy thẳng tới đó, không phải đọc qua các bản ghi đứng trước. Cấu trúc "Sequential file structure" buộc đọc lần lượt từ đầu tệp cho tới khi gặp bản ghi cần tìm, đúng thứ bị loại trong câu hỏi. Cấu trúc "Text file structure" nói về nội dung tệp là các ký tự đọc được, nó không quy định cách định vị bản ghi. Cấu trúc "Stream file structure" coi tệp là một dòng byte liên tục không chia bản ghi, nên cũng không có cơ chế nhảy tới bản ghi theo khoá.

Đáp án đúng: "Efficient utilization of system resources". Phải nói thẳng rằng đây là một câu hỏng của đề gốc: lựa chọn này chỉ chốt được bằng loại trừ, chứ bản thân nó không đúng với đơn chương. Cả ba lựa chọn sai đều là đặc trưng của đa chương nên bị loại chắc chắn: "Concurrent execution of multiple processes" đòi nhiều tiến trình chạy đồng hành, điều đơn chương không làm được vì bộ nhớ chỉ giữ một chương trình người dùng; "Dynamic allocation of memory" là cấp phát động để nhiều chương trình chia nhau bộ nhớ; "Shared memory space among processes" cũng đòi nhiều tiến trình cùng tồn tại mới có gì để chia sẻ. Cần biết thêm rằng đơn chương thực ra dùng tài nguyên kém hiệu quả, bộ xử lý ngồi không mỗi lần chương trình chờ vào ra, và chính nhược điểm đó mới là lý do đa chương ra đời.

Đáp án đúng: "Analysis". Pha phân tích là nơi người làm hệ thống đi hiểu miền bài toán: nghiệp vụ hiện tại diễn ra thế nào, ai tham gia, dữ liệu nào xuất hiện, hệ thống mới phải làm được những gì; kết quả là mô hình mô tả yêu cầu, chưa chứa quyết định kỹ thuật nào. Phương án "Design" đi sau, lấy mô hình yêu cầu đó làm đầu vào để quyết cấu trúc module, cấu trúc dữ liệu và thuật toán, tức chuyển từ bài toán sang giải pháp. Phương án "Testing" là pha kiểm thử, đối chiếu sản phẩm đã có với yêu cầu đã chốt nên không thể là nơi lần đầu phân tích miền bài toán. Phương án "Implementation" là pha viết mã, chỉ hiện thực những gì đã phân tích và thiết kế xong trước đó.

Đáp án đúng: "The user’s interaction with the system". Lược đồ ca sử dụng vẽ các tác nhân bên ngoài cùng những ca sử dụng mà họ thực hiện, nên nó trả lời ai dùng hệ thống và dùng để làm gì, tức mô tả ranh giới hệ thống và các cách người dùng tương tác với nó, chưa nói gì về cấu trúc hay thuật toán bên trong. Phương án "The movement of data within the system" là việc của lược đồ luồng dữ liệu bên lối phân tích hướng thủ tục. Phương án "The relationships between entities in a database" thuộc lược đồ thực thể liên kết dùng khi thiết kế cơ sở dữ liệu. Phương án "The sequence of events in a process" gần với lược đồ tuần tự hay lược đồ hoạt động, những lược đồ mô tả diễn biến theo thời gian, khác mục đích của lược đồ ca sử dụng.

Đáp án đúng: "A hardware address for the network interface.". Địa chỉ MAC là địa chỉ vật lý dài 48 bit được ghi sẵn trong card giao tiếp mạng, gắn với thiết bị và dùng để phân phát frame giữa các máy trên cùng một liên kết Ethernet. "A logical network address." sai vì địa chỉ logic chính là địa chỉ IP do tầng mạng cấp, nó thay đổi khi máy chuyển sang mạng khác, còn MAC thì không. "A temporary address assigned by a server." sai vì thứ do server cấp tạm theo thời hạn là địa chỉ IP qua giao thức DHCP; MAC nằm trong phần sụn của card, không ai cấp phát cho nó khi máy khởi động. "An private address used for internet routing purposes." sai vì khái niệm địa chỉ riêng chỉ tồn tại trong không gian IP, hơn nữa định tuyến trên Internet dựa hoàn toàn vào IP; frame mang địa chỉ MAC không đi qua được router mà bị thay địa chỉ ở từng chặng.

Đáp án đúng: "0111 0111 . 0000 1010 . 0000 0010 . 0000 1000". Địa chỉ dạng này gồm bốn byte, mỗi byte viết bằng đúng tám bit: 119 bằng 64 cộng 32 cộng 16 cộng 4 cộng 2 cộng 1 nên là 0111 0111; 10 bằng 8 cộng 2 nên là 0000 1010; 2 là 0000 0010; 8 là 0000 1000. Phương án "0111 0110 . 0000 1010 . 0000 0010 . 0000 1000" sai byte đầu, vì mẫu bit đó ứng với 118 chứ không phải 119. Phương án "0111 0111 . 0000 1010 . 0000 0010 . 0000 0100" sai byte cuối, vì mẫu bit đó ứng với 4. Phương án "0111 0111 . 10 . 0000 0010 . 0000 1000" viết byte thứ hai chỉ bằng hai bit; cách viết nhị phân của địa chỉ buộc giữ đủ tám bit mỗi byte kể cả các bit 0 ở đầu.

Đáp án đúng: "Punctuation, blank, newline, and tab". Bảng mã ký tự không chỉ chứa chữ và số: nó còn phải mã hoá các dấu câu, ký tự dấu cách và những ký tự điều khiển như xuống dòng hay tab, bởi văn bản thật cần cả cách ngắt từ và ngắt dòng mới đọc được. Phương án "Only mathematical operators." bó hẹp sai ở chữ chỉ, vì các dấu phép toán chỉ là một phần nhỏ và bỏ sót toàn bộ nhóm dấu câu cùng ký tự điều khiển. Phương án "Only programming language keywords" nhầm tầng khái niệm: từ khoá là các chuỗi ghép từ chữ cái đã có sẵn, không phải một nhóm ký hiệu riêng trong bảng mã. Phương án "Only special graphical symbols." cũng chỉ nêu một nhóm hẹp và bỏ qua dấu cách lẫn ký tự xuống dòng, hai thứ xuất hiện trong gần như mọi tệp văn bản.

Đáp án đúng: "As a collection of data meaningful only if properly interpreted by the program (e.g., two bytes as one integer)". Tệp nhị phân chỉ là một dãy byte thô, không mang kèm quy ước chia tách hay ý nghĩa, nên chính chương trình đọc nó mới quyết định gộp mấy byte thành một số nguyên, một số thực hay một trường của bản ghi; đọc sai quy ước thì dữ liệu thành vô nghĩa. "Always as individual characters." áp đặt một cách diễn giải duy nhất, trong khi phần lớn tệp nhị phân chứa số và cấu trúc chứ không chứa ký tự. "As plain, human-readable text." là mô tả tệp văn bản, nơi mỗi byte ứng với một ký tự theo bảng mã. "As a sorted list of alphanumeric symbols" thêm cả giả thiết đã sắp thứ tự lẫn giả thiết chỉ chứa chữ và số, hai điều mà định dạng nhị phân không hề bảo đảm.

Đáp án đúng: "110 0110". Mã của chữ in thường và chữ in hoa cùng tên lệch nhau đúng 32 đơn vị, tức bit thứ sáu tính từ phải đổi từ 0 thành 1, nên từ 100 0110 của chữ hoa ta được 110 0110; kiểm lại bằng cách tính giá trị của mẫu bit này là 64 cộng 32 cộng 4 cộng 2, đúng bằng 102 như đề cho. Mẫu "110 0101" có giá trị 101 nên nó là mã của chữ e, nhỏ hơn mẫu cần tìm một đơn vị. Mẫu "110 0111" có giá trị 103 nên nó là mã của chữ g. Mẫu "110 1000" có giá trị 104 nên nó là mã của chữ h, lệch hai đơn vị so với giá trị mà đề yêu cầu.

Đáp án đúng: "Record". Bản ghi là cấu trúc gom nhiều trường có thể khác kiểu vào một đơn vị dữ liệu, chẳng hạn một bản ghi sinh viên gồm chuỗi tên, số nguyên tuổi và số thực điểm; các trường được truy cập bằng tên nên kiểu của chúng không cần giống nhau. Phương án "Array" đòi mọi phần tử cùng một kiểu và cùng kích thước, vì nhờ vậy máy mới tính được địa chỉ phần tử theo chỉ số. Phương án "Linked List" là dãy các nút cùng kiểu nối nhau bằng con trỏ, điểm khác biệt của nó nằm ở cách lưu rời rạc trong bộ nhớ chứ không phải việc trộn nhiều kiểu. Phương án "Queue" là cấu trúc quy định thứ tự vào trước ra trước, phần tử trong nó thường vẫn cùng một kiểu.

Đáp án đúng: "Network". Bộ định tuyến đọc địa chỉ logic trong gói tin, tra bảng định tuyến rồi chuyển gói sang mạng kế tiếp, nghĩa là nó làm việc đúng ở tầng mạng; cũng vì thế nó nối được những mạng dùng công nghệ liên kết khác nhau. "Transport" cao hơn một bậc, làm việc với số cổng và cơ chế tin cậy giữa hai tiến trình, thiết bị hoạt động tới mức đó là cổng dịch vụ hay tường lửa trạng thái. "Data link" là tầng của bộ chuyển mạch và cầu nối, chúng chuyển khung theo địa chỉ vật lý trong phạm vi một mạng. "Physical" là tầng của bộ lặp và bộ tập trung, chỉ khuếch đại hoặc phát lại tín hiệu mà không đọc địa chỉ nào.

Đáp án đúng: "An entire row of an array is stored before the next row". Bộ nhớ là một dãy ô địa chỉ liên tiếp, nên mảng hai chiều phải được dàn phẳng thành một chiều; cách lưu theo hàng xếp hết các phần tử của hàng thứ nhất, rồi mới tới hàng thứ hai, nhờ vậy địa chỉ một phần tử tính được bằng địa chỉ đầu cộng số hàng đã qua nhân số cột rồi cộng chỉ số cột. Phương án "An entire column of an array is stored before the next column" mô tả cách lưu theo cột, cách mà một số ngôn ngữ khác dùng, nên không phải nghĩa của lưu theo hàng. Phương án "Elements are stored randomly" không thể đúng, vì khi đó máy không còn công thức nào để tính địa chỉ từ chỉ số. Phương án "Rows and columns are stored simultaneously" bất khả thi với bộ nhớ tuyến tính một chiều.

Đá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: "Left, Root, Right". Duyệt giữa đi xuống cây con bên trái cho tới hết, thăm gốc, rồi mới sang cây con bên phải. Trên cây tìm kiếm nhị phân, mọi khoá bên trái một nút đều nhỏ hơn nút đó và mọi khoá bên phải đều lớn hơn, nên đúng thứ tự này cho ra dãy khoá tăng dần, đó là lý do người ta dùng nó để lấy dữ liệu đã sắp xếp. Phương án "Root, Left, Right" là duyệt trước. Phương án "Left, Right, Root" là duyệt sau, dùng khi cần xử lý con trước cha như khi giải phóng cây. Phương án "Right, Root, Left" là bản phản chiếu của duyệt giữa, cho dãy khoá giảm dần. Phương án "Right, Left, Root" là bản phản chiếu của duyệt sau. Phương án "Root, Right, Left" là bản phản chiếu của duyệt trước; cả ba bản phản chiếu đều không phải định nghĩa của duyệt giữa.

Đáp án đúng: "(1001001100)2". Mỗi chữ số hệ mười sáu ứng với đúng bốn bit, nên ta đổi riêng từng chữ số: chữ số 2 thành 0010, chữ số 4 thành 0100, chữ số cuối mang giá trị 12 thành 1100; ghép theo đúng thứ tự được 0010 0100 1100, bỏ hai bit 0 không mang giá trị ở đầu thì còn 1001001100. Phương án "(1100010010)2" tách từ phải thành các nhóm 0010, 0001 và 11, tức ứng với 312 trong hệ mười sáu, không phải số đã cho. Phương án "(0100101010)2" tách ra các nhóm 1010, 0010 và 01, ứng với 12A, cũng lệch. Phương án "(1000101100)2" chỉ sai ở nhóm giữa, nơi nó cho 0010 thay vì 0100, nên ứng với 22C; đây là lỗi dễ mắc khi đổi nhầm một chữ số trong lúc nhẩm.