Câu hỏi: PRF192 - Phần 7: Mảng và kiểu cấu trúc (struct)

Đáp án đúng: "1 2 3 0 0". Khi danh sách khởi tạo có ít phần tử hơn kích thước mảng, C điền ba giá trị đã cho vào a[0], a[1], a[2] rồi khởi tạo toàn bộ phần còn lại bằng 0, đúng theo quy tắc khởi tạo thiếu của ngôn ngữ, nên a[3] và a[4] đều bằng 0 chứ không phải rác. "1 2 3 4 5" sai vì ngôn ngữ không suy diễn quy luật tăng dần từ ba số đầu, nó chỉ biết điền 0. "1 2 3 a[3] a[4]" sai vì printf với %d in giá trị của biểu thức, không bao giờ in lại tên phần tử; tên chỉ tồn tại trong mã nguồn, sau khi dịch không còn. "An error will be raised." sai vì khởi tạo thiếu phần tử là hợp lệ hoàn toàn, trình biên dịch không báo lỗi.

Đáp án đúng: "Calculates the sum of the absolute value of all odd elements in the array a of size n." Chìa khoá là biểu thức (a[i] % 2)*a[i]: với số chẵn phần dư là 0 nên hạng tử bằng 0; với số lẻ dương phần dư là 1 nên hạng tử bằng chính a[i]; với số lẻ âm, phép lấy dư trong C giữ dấu của toán hạng bên trái nên -3 % 2 cho -1, hạng tử thành -1 nhân -3 là 3, tức trị tuyệt đối. "Calculates the sum of all odd elements in the array a of size n." chỉ trùng kết quả khi mảng không có số lẻ âm, nên sai trong trường hợp tổng quát: gặp -3 thì hàm cộng 3 chứ không cộng -3. "Calculates the sum of all even elements in the array a of size n." sai vì số chẵn cho phần dư 0 nên không góp gì vào tổng. "Calculates the sum of squares of all elements in the array a of size n." sai vì bình phương phải là a[i] nhân a[i], còn ở đây một thừa số chỉ nhận 0, 1 hoặc -1.

Đáp án đúng: "The number of elements in arr". Toán tử sizeof cho số byte mà toán hạng chiếm; với một mảng thật thì sizeof(arr) là tổng số byte của cả mảng và sizeof(arr[0]) là số byte của một phần tử, nên phép chia cho ra số phần tử mà không cần biết kiểu. Mẹo này chỉ đúng ở nơi arr còn là mảng: truyền mảng vào hàm thì nó suy biến thành con trỏ và phép chia cho ra số vô nghĩa. "The size of arr in bytes" sai vì đó là giá trị của riêng sizeof(arr), chưa chia. "The number of bytes occupied by each element in arr" sai vì đó là giá trị của riêng sizeof(arr[0]), tức số chia chứ không phải thương. "The total size of arr in bytes" cũng chỉ là tử số; phép chia đã triệt tiêu đơn vị byte nên thương là một số đếm, không còn là dung lượng.

Đáp án đúng: "Because elements can be accessed directly by unique index". Mảng nằm liền khối trong bộ nhớ và mọi phần tử cùng kích thước, nên địa chỉ phần tử thứ i tính được ngay bằng địa chỉ đầu cộng i nhân kích thước một phần tử; phép tính đó tốn thời gian như nhau với mọi i, không phải dò tuần tự. "Because arrays allow fast insertion/deletion of elements" sai vì chèn hay xoá giữa mảng buộc phải dịch chuyển mọi phần tử phía sau. "Because elements in an array are allocated in scattered memory locations" sai ngược hẳn: chính tính liền khối mới cho phép tính địa chỉ, còn nằm rải rác là đặc điểm của danh sách liên kết. "Because arrays automatically expand in size when new elements are added" sai vì mảng trong C có kích thước cố định, muốn lớn hơn phải tự cấp phát vùng mới rồi chép sang.

Đáp án đúng: "Bubble sort". Thuật toán nổi bọt đi qua danh sách nhiều lượt, mỗi lượt so từng cặp phần tử kề nhau và đổi chỗ nếu sai thứ tự, nhờ vậy sau mỗi lượt phần tử lớn nhất trong phần chưa sắp nổi về cuối; nó dừng khi một lượt không còn phép đổi chỗ nào. "Selection sort" làm khác: mỗi lượt tìm phần tử nhỏ nhất của phần chưa sắp rồi đổi chỗ đúng một lần, phép so sánh không giới hạn ở các cặp kề nhau. "Binary sort" không phải tên thuật toán sắp xếp trong chương trình môn học; chữ nhị phân gắn với tìm kiếm nhị phân, một phép tìm trên dãy đã sắp. "None of the others" sai vì danh sách đã có đúng tên thuật toán nổi bọt.

Đáp án đúng: "1". Khi danh sách khởi tạo có ít giá trị hơn số phần tử, C lấp lần lượt từ đầu mảng rồi tự đặt 0 cho những phần tử còn lại, nên a giữ các giá trị 1, 2, 3, 0, 0. Chỉ số trong C đếm từ 0, vì vậy a[0] là phần tử đầu tiên và bằng 1, đúng cái mà printf in ra. Ý "3" sai vì 3 nằm ở a[2], tức là phần tử thứ ba của mảng. Ý "2" sai vì 2 nằm ở a[1]; nhầm lẫn này bắt nguồn từ việc tưởng chỉ số bắt đầu từ 1. Ý "An error will be raised." sai vì khởi tạo thiếu giá trị là hợp lệ và được chuẩn quy định rõ ràng; trình biên dịch không báo lỗi, cũng không để các phần tử còn lại mang giá trị rác.

Đáp án đúng: "Arrays provide constant-time access to elements.". Mảng chiếm một dải ô nhớ liên tục và mọi phần tử cùng một kiểu nên cùng kích thước; nhờ vậy địa chỉ phần tử thứ i tính ra ngay bằng địa chỉ đầu cộng i nhân kích thước một phần tử, một phép tính không phụ thuộc vào i, tức là thời gian truy xuất là hằng số. Ý "Arrays allow for dynamic resizing during runtime." sai vì mảng khai báo tĩnh có kích thước cố định từ lúc dịch, muốn thay đổi dung lượng thì phải tự cấp vùng nhớ động rồi gọi realloc, và đó không còn là mảng ban đầu nữa. Ý "Arrays can store elements of different data types." sai vì mảng đòi hỏi các phần tử đồng kiểu, chính điều đó mới cho phép tính địa chỉ bằng một bước nhảy cố định. Ý "Arrays automatically adjust their size based on the number of elements." sai vì số phần tử ghi trong khai báo là bất biến; khởi tạo thiếu giá trị thì phần còn lại nhận 0 chứ mảng không tự co lại hay nở ra.

Đáp án đúng: "0". Khi một mảng có danh sách khởi tạo, những phần tử không được nêu giá trị đều bị đặt về 0 theo đúng quy định của chuẩn; vì thế cách viết với một số 0 duy nhất trong cặp ngoặc nhọn là lối quen dùng để xoá trắng cả mảng. Phần tử ở chỉ số 3 nằm trong nhóm được lấp 0 nên printf in ra 0. Ý "Garbage value" sai vì giá trị rác chỉ xuất hiện khi một mảng cục bộ không có bất kỳ danh sách khởi tạo nào; ở đây đã có danh sách nên toàn bộ mảng được xác định. Ý "3" sai vì 3 là chỉ số, không phải nội dung của ô; vị trí và nội dung là hai chuyện khác nhau. Ý "Error" sai vì khởi tạo thiếu giá trị là hợp lệ, và chỉ số 3 vẫn nằm trong phạm vi mảng 5 phần tử.

Đáp án đúng: "DataType ArrayName[NumberOfElements];". Khai báo mảng tĩnh đi theo đúng lối đọc khai báo của C: tên kiểu đứng trước cho biết mỗi phần tử trông thế nào, rồi tên biến, rồi số phần tử đặt trong cặp ngoặc vuông ngay sau tên; từ hai thông tin đó trình biên dịch tính ra tổng số byte phải dành và bước nhảy giữa các phần tử. Ý "ArrayName DataType[NumberOfElements];" sai vì tên biến bị đặt lên trước tên kiểu, trật tự này trình biên dịch không hiểu. Ý "DataType[NumberOfElements] ArrayName;" sai vì cặp ngoặc vuông phải gắn vào tên biến chứ không gắn vào tên kiểu, đó là cú pháp của một số ngôn ngữ khác. Ý "[NumberOfElements] DataType ArrayName;" sai vì không có khai báo nào trong C được mở đầu bằng cặp ngoặc vuông.

Đáp án đúng: "int a[5] = {0};". Danh sách khởi tạo của mảng trong C đặt trong cặp ngoặc nhọn, và chuẩn quy định nếu số giá trị ít hơn số phần tử thì phần còn lại được khởi tạo về 0, nên viết đúng một số 0 là đủ để cả năm phần tử bằng 0. Cách viết "int a[5] = [0, 0, 0, 0, 0];" dùng ngoặc vuông làm danh sách, nhưng ngoặc vuông trong C chỉ dành cho khai kích thước và truy cập phần tử, nên đây là lỗi cú pháp. Cách viết "int a[5] = (0, 0, 0, 0, 0);" dùng ngoặc tròn nên vế phải thành một biểu thức với toán tử phẩy, giá trị của nó là một số 0 đơn lẻ và không thể gán cho cả mảng. Cách viết "int a[5];" không có phần khởi tạo: mảng cục bộ như vậy chứa đúng những byte rác còn lại trong bộ nhớ, chỉ mảng toàn cục hoặc static mới tự về 0, nên không bảo đảm được điều đề bài đòi.

Đáp án đúng: "int binarySearch(int x, int a[], int n)". Tìm nhị phân cần đủ ba thứ: khoá cần tìm, mảng đã sắp xếp và số phần tử; mỗi bước nó so khoá với phần tử giữa rồi bỏ hẳn nửa không thể chứa khoá, nên nguyên mẫu phải có tham số cho khoá và kiểu trả về nguyên để đưa về chỉ số tìm được. Nguyên mẫu "int linearSearch(int a[], int n)" thiếu hẳn tham số khoá nên không có gì để so, và cái tên cũng chỉ ra lối tìm tuần tự. Nguyên mẫu "int firstLinearSearch(double x, double a[], int n)" đủ tham số nhưng tên nói rõ đây là tìm tuần tự từ đầu mảng, cách làm không đòi mảng phải sắp xếp trước. Nguyên mẫu "void sort(int a[], int n)" là hàm sắp xếp: nó trả về void nên không báo lại được vị trí nào, việc của nó là chuẩn bị dữ liệu cho tìm nhị phân chứ không phải tìm kiếm.

Đáp án đúng: "It moved to the beginning of the sorted part". Sắp xếp nổi bọt tăng dần so từng cặp kề nhau và đổi chỗ khi cặp đó nghịch, nên sau một lượt quét phần chưa sắp, phần tử lớn nhất của phần đó bị đẩy dần tới ô cuối cùng của phần chưa sắp. Ô ấy nằm sát ngay vùng đã sắp ở đuôi mảng và từ lúc này thuộc vùng đã sắp, tức nó đứng ở vị trí đầu tiên của phần đã sắp xếp, còn ranh giới giữa hai phần lùi lại một ô. Mô tả "It moved to the end of the sorted part" chỉ đúng cho lượt đầu tiên, khi phần đã sắp còn rỗng nên ô cuối mảng vừa là đầu vừa là cuối; từ lượt thứ hai, cuối phần đã sắp luôn là ô cuối mảng đã có chủ từ trước. Mô tả "It stays in its position" trái với cơ chế đổi chỗ, phần tử lớn nhất bị mang đi sau mỗi lần so. Mô tả "It removed from the array" sai về bản chất, thuật toán chỉ đổi chỗ trong cùng một mảng và không xoá phần tử nào.

Đáp án đúng: "2". Mảng x được khởi tạo với năm giá trị và chỉ số đếm từ 0, nên x[0] là 1, x[1] là 2, x[2] là 3 rồi tiếp tục như thế; biến y bằng 1 nên x[y] chính là x[1], tức giá trị 2, và đặc tả %d in ra số nguyên đó. Bản chất của phép truy cập mảng là cộng địa chỉ: tên mảng cho địa chỉ ô đầu, chỉ số được nhân với kích thước một phần tử rồi cộng vào, vì vậy chỉ số 1 trỏ tới ô thứ hai. Giá trị "3" là x[2], tức cách đọc theo kiểu đếm từ 1 mà C không dùng. Giá trị "4" là x[3], lệch hai ô so với chỉ số đang dùng. Kết luận "An error will be raised." không đúng: mảng có năm ô nên chỉ số 1 nằm gọn trong dải hợp lệ; mà ngay cả khi chỉ số vượt biên thật, C cũng không báo lỗi mà lặng lẽ đọc vùng nhớ bên cạnh.

Đáp án đúng: "A collection of elements of the same data type stored in contiguous memory locations.". Mảng trong C là một dãy phần tử cùng kiểu nằm liền kề trong bộ nhớ; chính tính liền kề và cùng kiểu cho phép tính địa chỉ phần tử thứ i chỉ bằng địa chỉ đầu cộng i lần kích thước kiểu, nhờ vậy truy cập theo chỉ số nhanh như nhau ở mọi vị trí và số học con trỏ trên mảng mới chạy được. Lựa chọn "A single variable that holds multiple values of different data types." mô tả kiểu cấu trúc, nơi các thành phần được phép khác kiểu. Lựa chọn "A pointer to a single element in memory" lẫn mảng với con trỏ: tên mảng tự suy biến thành địa chỉ phần tử đầu khi dùng trong biểu thức, nhưng bản thân mảng là vùng dữ liệu chứa nhiều phần tử chứ không phải một biến con trỏ. Lựa chọn "A function that performs mathematical calculations." nói về hàm, không phải cấu trúc dữ liệu.

Đáp án đúng: "The sum of squares of all elements in the array a.". Biến s bắt đầu từ 0, vòng lặp đi qua mọi chỉ số từ 0 tới n trừ 1, và mỗi lượt cộng vào s tích của phần tử với chính nó, tức bình phương của nó. Vì không có câu điều kiện nào lọc bớt nên mọi phần tử đều góp phần, và vì bình phương không bao giờ âm nên s luôn không âm dù mảng có chứa số âm. Lựa chọn "The sum of all even elements in the array a." đòi một phép kiểm tra chia hết cho 2 trước khi cộng, điều mã không có. Lựa chọn "The sum of all odd elements in the array a." cũng đòi phép lọc theo tính chẵn lẻ tương tự. Lựa chọn "The sum of all elements in the array a." ứng với dòng cộng thẳng phần tử vào s, không có phép nhân phần tử với chính nó.

Đáp án đúng: "0". Khi danh sách khởi tạo có ít giá trị hơn số phần tử khai báo, chuẩn C bắt phần còn lại phải được khởi tạo như đối tượng tĩnh, nghĩa là bằng 0 với kiểu số. Mảng này có năm ô, ba ô đầu nhận 1, 2, 3 còn hai ô cuối được điền 0, nên phần tử ở chỉ số 4 là 0 và lệnh in cho ra 0. Chính quy tắc đó là lý do người ta hay viết cặp ngoặc với một số 0 duy nhất để xoá trắng cả mảng. Lựa chọn "3" là giá trị ở chỉ số 2, tức giá trị khởi tạo cuối cùng được viết ra. Lựa chọn "Runtime error" sai vì chỉ số 4 vẫn nằm trong năm phần tử đã khai báo, không có truy cập ngoài biên. Lựa chọn "Compilation error" sai vì viết thiếu giá trị khởi tạo là hợp lệ; chỉ viết nhiều hơn số phần tử mới bị báo lỗi.

Đáp án đúng: "{1, 8, 2, 7, 9}". Sắp xếp chọn làm việc theo lượt: lượt đầu dò toàn mảng tìm phần tử nhỏ nhất rồi đổi chỗ nó với vị trí đầu tiên. Phần tử nhỏ nhất là 1, đang nằm ở vị trí thứ hai, nên nó đổi chỗ với 8 ở vị trí đầu; các phần tử còn lại không bị xê dịch vì thuật toán chỉ thực hiện đúng một phép đổi chỗ mỗi lượt, khác hẳn sắp xếp nổi bọt đổi chỗ liên tục. Lựa chọn "{8, 1, 2, 7, 9}" là mảng ban đầu, tức giả định lượt đầu không đổi chỗ gì, chỉ đúng nếu phần tử đầu vốn đã nhỏ nhất. Lựa chọn "{1, 2, 8, 7, 9}" là trạng thái sau hai lượt, khi 2 cũng đã được đưa về vị trí thứ hai. Lựa chọn "{1, 2, 7, 8, 9}" là mảng đã sắp xong, kết quả của cả bốn lượt chứ không phải một lượt.

Đáp án đúng: "5 10 15". Khai báo arr[] = {5, 10, 15} tạo mảng ba phần tử theo đúng thứ tự liệt kê, chỉ số chạy từ 0 tới 2. Vòng for đặt i bằng 0, còn chạy khi i nhỏ hơn 3 và tăng i sau mỗi nhịp; thân vòng không có ngoặc nhọn nên chỉ ôm đúng một lệnh printf, lệnh đó in arr[i] theo %d kèm một dấu cách, cho ba lần in lần lượt 5, 10 rồi 15. Dòng "15 10 5" là thứ tự ngược, muốn có nó phải cho i đi từ 2 giảm về 0. Dòng "0 1 2" là dãy chỉ số i, sẽ ra nếu in i thay vì arr[i]. Dòng "10 15 20" là dãy đã cộng thêm 5 vào từng phần tử, không có phép tính nào trong mã làm việc đó.

Đáp án đúng: "The program compiles and runs without any errors, but the behavior is undefined". C đổi an toàn lấy tốc độ: chỉ số mảng chỉ là phép cộng địa chỉ rồi lấy giá trị, không kèm mã kiểm biên nào, nên chương trình vẫn dịch xong và vẫn chạy, chỉ là nó đọc ghi vào vùng không thuộc mảng. Chuẩn gọi đó là hành vi không xác định: có thể ra số rác, có thể phá biến khác, có thể gây lỗi truy cập, và kết quả đổi theo máy lẫn trình dịch. Câu "The program compiles and runs without any errors, and the 11th element is accessed" sai vì phần tử thứ mười một không tồn tại, thứ bị chạm tới là ô nhớ kế bên. Câu "The program fails to compile due to a compilation error" sai vì chỉ số thường chỉ biết lúc chạy. Câu "The program compiles and runs without any errors, and the 11th element is automatically added to the array" sai vì mảng trong C có kích thước cố định lúc khai báo.