Câu hỏi: CSI106 - Phần 10: Cấu trúc dữ liệu và kiểu dữ liệu trừu tượng

Đá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: "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: "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: "Files where data is stored based on a computed hash value, which determines the location of the data". Trong tệp băm, khoá của bản ghi được đưa qua một hàm băm và kết quả cho ra địa chỉ ô lưu trong tệp, nên việc tìm một bản ghi chỉ cần tính lại hàm băm trên khoá là tới đúng chỗ, không phải tra bảng hay quét tuần tự. Mô tả "Files that store data in a fixed order" ứng với tệp tuần tự được sắp theo khoá, nơi vị trí phụ thuộc thứ tự chứ không phải một phép tính. Mô tả "Files that are encrypted for security purposes" nhầm hàm băm địa chỉ với mã hoá, vì hàm băm ở đây dùng để định vị chứ không nhằm che nội dung. Mô tả "Files that contain only textual information" nói về kiểu nội dung của tệp, không nói gì về cách tổ chức lưu trữ.

Đáp án đúng: "The edges have no direction". Trong đồ thị vô hướng, một cạnh chỉ nói hai đỉnh có liên hệ với nhau mà không chỉ chiều, nên đi được từ đỉnh này sang đỉnh kia và ngược lại. Mục "It has one-way connections between nodes." mô tả đồ thị có hướng, nơi mỗi cung chỉ cho đi một chiều. Mục "The edges have a specific starting and ending point" cũng là đặc trưng của đồ thị có hướng, vì chỉ ở đó cạnh mới có đỉnh đầu và đỉnh cuối phân biệt. Mục "A node only has one parent" dùng khái niệm cha con của cây; đồ thị vô hướng không có gốc nên không có quan hệ cha con, hơn nữa một đỉnh có thể kề với bao nhiêu đỉnh khác cũng được.

Đáp án đúng: "N(N-1)/2". Mỗi cặp đỉnh phân biệt chỉ nối được nhiều nhất một cạnh và cạnh không có hướng, nên số cạnh tối đa đúng bằng số cặp chọn được từ N đỉnh, tức N nhân với N trừ 1 rồi chia 2; đó là trường hợp đồ thị đầy đủ. Thử với bốn đỉnh thì công thức cho 6 cạnh, khớp với hình vẽ. Mục "N" quá nhỏ, bốn đỉnh nối đủ đã có 6 cạnh chứ không phải 4. Mục "N+1" cũng chỉ tăng theo đường thẳng nên không theo kịp mức tăng bình phương của số cặp đỉnh. Mục "2N" với bốn đỉnh cho 8 cạnh, vượt quá số cặp đỉnh thật có nên không thể vẽ được. Mục "None of the others" không dùng được vì công thức đúng đã nằm trong danh sách.

Đáp án đúng: "Each element containing a data part and a link (pointer) to the next element." Danh sách liên kết gồm các nút rời nhau, mỗi nút chứa phần dữ liệu và một con trỏ chỉ tới nút kế tiếp, nhờ vậy thêm hay xoá chỉ cần sửa con trỏ mà không phải dồn dịch cả dãy. Mục "Elements stored in contiguous memory locations" mô tả mảng, nơi các phần tử nằm liền nhau trong bộ nhớ; danh sách liên kết thì các nút có thể nằm rải rác. Mục "Direct access to any element using an integer index" cũng là tính chất của mảng, vì địa chỉ tính được từ chỉ số; muốn đến nút thứ k của danh sách liên kết thì phải đi lần lượt từ nút đầu. Mục "Elements always being of the same data type" đúng với nhiều cấu trúc dữ liệu khác nên không phân biệt được gì, và nó không nói lên cách các nút nối với nhau.

Đáp án đúng: "Stack". Ngăn xếp chỉ cho thêm và lấy ở một đầu gọi là đỉnh, nên phần tử vào sau cùng lại là phần tử ra đầu tiên; đó đúng là nguyên tắc vào sau ra trước, thấy rõ trong việc lưu địa chỉ trở về khi gọi hàm. Mục "Queue" chạy theo nguyên tắc ngược lại là vào trước ra trước, thêm ở một đầu và lấy ở đầu kia. Mục "Linked List" chỉ là cách tổ chức lưu trữ bằng các nút nối bởi con trỏ, nó không áp đặt luật truy cập nào, thậm chí người ta dùng nó để hiện thực cả ngăn xếp lẫn hàng đợi. Mục "Binary Tree" là cấu trúc phân cấp, việc truy cập đi theo đường từ gốc xuống các nút con nên không có khái niệm vào sau ra trước.

Đáp án đúng: "Calculating a key". Tệp băm hoạt động bằng cách đưa giá trị khoá của bản ghi qua một hàm băm để tính ra địa chỉ khối trên đĩa, nhờ vậy tìm một bản ghi chỉ cần một phép tính rồi truy cập trực tiếp, không phải quét cả tệp. Mục "Sorting files by Index" mô tả tệp chỉ mục, nơi người ta giữ một bảng khoá đã sắp xếp kèm địa chỉ rồi tìm trên bảng đó, cơ chế khác hẳn việc tính địa chỉ. Mục "Compress a normal file" nói về nén dữ liệu, mục đích là giảm kích thước chứ không phải định vị bản ghi. Mục "Adding lines to the file" chỉ là một thao tác cập nhật nội dung, nó không nói gì về cách tổ chức và tra cứu tệp.

Đáp án đúng: "If data is inserted into a stack and then removed, the order of the data is reversed". Ngăn xếp chỉ cho thêm và lấy ở một đầu gọi là đỉnh, nên thứ vào sau cùng lại ra đầu tiên; hệ quả thấy ngay là nếu đưa một dãy vào rồi lấy hết ra thì dãy nhận được là dãy ban đầu đảo ngược. Mục "Elements are retrieved based on their priority" mô tả hàng đợi ưu tiên, nơi thứ tự ra phụ thuộc mức ưu tiên gắn cho từng phần tử chứ không phụ thuộc lúc vào. Mục "Elements can be accessed directly by their memory address" là tính chất của mảng và của bộ nhớ nói chung; ngăn xếp cố ý chỉ cho chạm vào đỉnh. Mục "The oldest element is always removed first." đúng là nguyên tắc vào trước ra trước của hàng đợi, trái hẳn với ngăn xếp.

Đá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: "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: "A restricted linear list; Last In, First Out (LIFO)." Ngăn xếp là danh sách tuyến tính bị hạn chế: mọi phép thêm và lấy chỉ diễn ra ở một đầu duy nhất gọi là đỉnh, vì thế phần tử vào sau cùng lại là phần tử ra trước tiên. "A linear list; First In, First Out (FIFO)." mô tả hàng đợi, nơi thêm ở một đầu và lấy ở đầu kia. "A collection of related elements of different types." là mô tả bản ghi gồm nhiều trường khác kiểu, không nói gì tới thứ tự vào ra. "A sorted collection of elements accessed by index." mô tả mảng đã sắp thứ tự và truy cập theo chỉ số, trong khi ngăn xếp không cho với tay vào phần tử nằm giữa.

Đáp án đúng: "20, 10, 15, 5". Dãy đẩy vào theo thứ tự 5, 15, 10, 20 và ngăn xếp chỉ cho lấy ở đỉnh, nên trình tự lấy ra là nghịch đảo trình tự đẩy vào: 20 ra trước, kế đó 10, rồi 15, cuối cùng là 5. "5, 10, 15, 20" là thứ tự tăng dần, mà ngăn xếp không sắp xếp gì và cũng không trả phần tử theo thứ tự đẩy vào. "10, 15, 20, 5" đòi lấy một phần tử nằm giữa trước khi lấy phần tử đang ở đỉnh, điều mà cấu trúc này không cho phép. "15, 10, 5, 20" bỏ qua phần tử đang ở đỉnh để lấy phần tử bên dưới trước rồi mới lấy đỉnh ở bước cuối, vi phạm đúng luật chỉ thao tác ở đỉnh.

Đáp án đúng: "Data and a pointer to the next node". Mỗi nút của danh sách liên kết gồm hai phần: phần dữ liệu mang nội dung cần lưu, và phần liên kết chứa địa chỉ của nút kế tiếp; chính chuỗi địa chỉ này nối các nút nằm rải rác trong bộ nhớ thành một danh sách, nút cuối mang liên kết rỗng. "Data and an index of the current node" gán cho nút một chỉ số như phần tử mảng, nhưng danh sách liên kết không nằm liền khối nên chỉ số chẳng dẫn tới đâu. "Data and the next node's value" chỉ sao lại giá trị của nút sau: biết giá trị mà không biết địa chỉ thì không đi tiếp được, lại còn nhân đôi dữ liệu. "Data and the size of the list" nhồi một thuộc tính của toàn danh sách vào từng nút, vừa trùng lặp vừa không giúp tìm nút kế tiếp.

Đáp án đúng: "Keep the same order". Hàng đợi chỉ cho thêm ở cuối và lấy ở đầu, nên phần tử nào vào trước sẽ ra trước; nhờ tính chất vào trước ra trước đó mà hàng đợi được dùng để giữ nguyên trật tự của dòng dữ liệu hoặc dòng yêu cầu đang chờ xử lý. "Reverse the order of elements" là việc của ngăn xếp, nơi phần tử vào sau lại ra trước nên trật tự bị đảo. "Random elements" trái với cấu trúc hàng đợi, vì không có phép lấy ở vị trí tuỳ ý, mọi phần tử phải chờ tới lượt mình. "Sort the elements" cũng không đúng: hàng đợi không so sánh giá trị, muốn phần tử ra theo độ ưu tiên thì phải dùng hàng đợi ưu tiên, một cấu trúc khác.

Đáp án đúng: "Data value and the address of the next element". Một phần tử của danh sách liên kết luôn có hai phần, giá trị dữ liệu và trường liên kết giữ địa chỉ của phần tử đứng sau, bởi các phần tử nằm rời rạc trong bộ nhớ nên chỉ có địa chỉ mới cho biết đi tiếp đến đâu. "Data value and the index of the element" dùng chỉ số kiểu mảng, thứ chỉ có nghĩa khi các phần tử nằm liên tiếp nhau. "Index of the previous and next element" bỏ mất chính giá trị dữ liệu, mà thiếu dữ liệu thì phần tử không lưu được gì. "Only the data value" thiếu trường liên kết nên các phần tử rời nhau, không tạo thành danh sách. "None of the others" không dùng được vì mô tả gồm giá trị dữ liệu kèm địa chỉ phần tử kế tiếp đã hoàn toàn đúng.