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: "Collision". Hàm băm nén miền khoá rất rộng về một dải địa chỉ hẹp nên không thể tránh việc hai khoá khác nhau cho cùng một địa chỉ; hiện tượng đó gọi là collision, và mọi phương pháp băm đều phải kèm cách giải quyết như địa chỉ mở hoặc nối chuỗi. "Duplication" nói về trùng lặp dữ liệu, tức hai bản ghi giống nhau, chứ không phải hai khoá khác nhau cùng rơi vào một ô. "Synonym" là cách một số tài liệu về tổ chức tệp gọi bản thân cặp khoá cùng địa chỉ, trong khi câu dẫn hỏi tên của hiện tượng xảy ra. "Hazard" là thuật ngữ của mạch số và đường ống lệnh, không thuộc chủ đề băm khoá.

Đáp án đúng: "Indexed sequential access". Với tệp có rất nhiều bản ghi, cách tổ chức tuần tự có chỉ mục dựng thêm bảng chỉ mục, thường là nhiều mức, để từ giá trị khoá đi thẳng tới vùng chứa bản ghi; nhờ vậy không phải đọc từ đầu tệp mà vẫn giữ được khả năng đọc tuần tự theo thứ tự khoá. "Sequential access" phải đi qua lần lượt từng bản ghi nên chi phí tăng theo kích thước tệp, đúng chỗ tệp lớn làm nó yếu nhất. "Direct access" cho nhảy tới bản ghi theo vị trí, nhưng muốn dùng thì phải biết trước vị trí ứng với khoá. "Hashing" cũng lấy bản ghi theo khoá và rất nhanh với một khoá đơn lẻ, song phải xử lý xung đột và không giữ thứ tự khoá; câu dẫn nhấn vào tệp có số lượng bản ghi rất lớn, đúng tình huống mà chỉ mục nhiều mức được dựng ra để giải quyết.

Đá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: "Computer networks, where vertices represent nodes/hubs and edges represent routes.". Đồ thị gồm các đỉnh và các cạnh nối chúng, rất tự nhiên để mô hình hoá mạng máy tính: mỗi nút hay bộ tập trung là một đỉnh, mỗi đường truyền là một cạnh, và bài toán tìm đường đi ngắn nhất cho gói tin trở thành bài toán trên đồ thị. "Storing student records in a school." sai vì hồ sơ học sinh là tập các bản ghi đồng dạng, phù hợp với bảng trong cơ sở dữ liệu hoặc với tệp, không cần quan hệ nối từng cặp đối tượng. "Implementing stacks and queues." sai vì ngăn xếp và hàng đợi được cài đặt bằng mảng hoặc danh sách liên kết, chúng là cấu trúc tuyến tính. "Decimal to binary conversion" sai vì đổi số thập phân sang nhị phân là thuật toán chia liên tiếp lấy số dư, không có đối tượng nào đóng vai trò đỉnh hay cạ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: "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: "An array defines a combination of elements, while a record defines the identifiable parts (attributes) of a single element.". Mảng và bản ghi khác nhau ở chỗ gom cái gì: mảng là tập nhiều phần tử cùng kiểu, truy cập bằng chỉ số; bản ghi gom các thuộc tính có thể khác kiểu của cùng một đối tượng, truy cập bằng tên trường. "An array defines attributes of an element, while a record defines a collection of similar elements" sai vì nói ngược hai vai trò, gán việc mô tả thuộc tính cho mảng và việc gom phần tử đồng dạng cho bản ghi. "Arrays store data on disk, while records store data in main memory" sai vì cả hai đều là kiểu dữ liệu trong chương trình, nơi lưu trên đĩa hay trong bộ nhớ chính không phải tiêu chí phân biệt chúng. "Records can only store numerical data, while arrays store all data types." sai vì bản ghi sinh ra chính để chứa nhiều kiểu khác nhau, còn mảng mới là thứ đòi các phần tử phải cùng kiểu.

Đáp án đúng: "When a new record's key maps to an occupied address.". Trong tệp băm, hàm băm biến khoá của bản ghi thành địa chỉ lưu trữ. Xung đột là tình huống hai khoá khác nhau cùng cho ra một địa chỉ, nên khi ghi bản ghi mới thì chỗ đó đã bị bản ghi khác chiếm và phải xử lý bằng vùng tràn, dò tuyến tính hay băm kép. "The process of converting a key into an address." sai vì đó là mô tả của chính hàm băm, công việc bình thường diễn ra ở mọi lần truy nhập chứ không phải một sự cố. "The method of sorting records alphabetically." sai vì sắp xếp bản ghi theo thứ tự chữ cái là cách tổ chức tệp tuần tự, không liên quan tới cơ chế băm. "The use of an index file to find records." sai vì dùng tệp chỉ mục để tìm bản ghi là một tổ chức tệp khác, nó tránh được chuyện trùng địa chỉ chứ không phải định nghĩa của chuyện đó.

Đáp án đúng: "Data and a link". Nút của danh sách liên kết đơn gồm hai phần: phần dữ liệu chứa giá trị cần lưu, và phần liên kết chứa địa chỉ của nút kế tiếp; nút cuối mang liên kết rỗng để đánh dấu hết danh sách. Nhờ phần liên kết mà danh sách lớn lên hay co lại không cần vùng nhớ liền mạch. "Data and an index code" sai vì chỉ số là cách định vị phần tử của mảng, mà mảng không lưu đường tới phần tử sau. "Data and a hash code" sai vì mã băm thuộc bảng băm hay tệp băm, nơi địa chỉ được tính ra từ khoá. "Data and a value" sai vì giá trị chính là phần dữ liệu đã nói, nhắc lại nó không cho ta thành phần dẫn tới nút tiếp theo nên các nút sẽ không nối được với nhau.

Đáp án đúng: "O(n)". Muốn biết chiều cao thì phải so chiều cao của hai cây con tại mỗi nút, nghĩa là thăm mọi nút đúng một lần và làm một lượng việc hằng số ở mỗi nút, cho chi phí tỉ lệ với số nút. "O(log n)" sai vì đây là chiều cao của một cây nhị phân cân bằng, tức là giá trị kết quả có thể nhỏ, chứ không phải chi phí tìm ra nó; hơn nữa cây có thể suy biến thành một chuỗi dài. "O(n^2)" sai vì phép duyệt không có vòng lặp lồng nhau nào, mỗi nút không bị thăm lại nhiều lần. "O(n log n)" sai vì đây là chi phí đặc trưng của các thuật toán sắp xếp dựa trên so sánh, không phát sinh khi chỉ đi một lượt qua cây.

Đáp án đúng: "Indexed sequential access". Truy nhập tuần tự có chỉ mục dựng thêm một tệp chỉ mục gồm các cặp khoá và địa chỉ, sắp theo khoá; muốn tìm bản ghi thì tra chỉ mục rồi nhảy thẳng tới chỗ cần, nhanh hơn đọc lần lượt, đổi lại phải tốn chỗ lưu chỉ mục và phải cập nhật chỉ mục mỗi khi tệp thay đổi. "Sequential access" sai vì cách này không dùng cấu trúc phụ nào, nó đọc từ đầu nên không thể nhanh hơn chính nó. "Direct access" sai vì truy nhập trực tiếp tính địa chỉ ngay từ khoá, không cần nuôi một tệp chỉ mục bên cạnh. "Hashing" sai vì hàm băm cũng tính địa chỉ từ khoá nên không tốn chỗ cho chỉ mục; cái giá nó trả là phải xử lý xung đột khi hai khoá cho cùng một địa chỉ.

Đáp án đúng: "Linked List". Danh sách liên kết lớn lên và co lại trong lúc chương trình chạy: mỗi lần thêm phần tử thì xin cấp một nút mới, mỗi lần bớt thì trả nút đó về, và các nút nối với nhau bằng liên kết nên không cần một vùng nhớ liền mạch có sẵn. "Array" sai vì mảng được định kích thước ngay từ lúc khai báo và chiếm một vùng liền mạch, muốn đổi cỡ phải cấp vùng mới rồi chép dữ liệu sang. "Record" sai vì bản ghi là tập các trường đã định trước về số lượng và kiểu, nó không thêm bớt trường trong lúc chạy. "Variable" sai vì một biến chỉ là một ô giữ một giá trị, nó không phải cấu trúc dữ liệu có thể nở ra hay thu lại.

Đáp án đúng: "A stack is LIFO, and a queue is FIFO". Ngăn xếp chỉ cho thêm và lấy ở cùng một đầu nên phần tử vào sau ra trước, giống chồng đĩa; hàng đợi thêm ở một đầu và lấy ở đầu kia nên phần tử vào trước ra trước, giống dòng người xếp hàng. Phương án "A stack follows FIFO, and a queue follows LIFO" đảo ngược đúng hai quy tắc đó, nên sai hoàn toàn. Phương án "A stack is a hierarchical data structure, and a queue is not" gán sai bản chất: cả hai đều là cấu trúc tuyến tính, phần tử nối nhau thành dãy; cấu trúc phân cấp là cây, nơi một nút có nhiều nút con. Phương án "There is no difference between a stack and a queue" bỏ qua đúng điểm phân biệt cốt lõi, trong khi thứ tự lấy phần tử ra là lý do người ta chọn cấu trúc này thay cho cấu trúc kia.

Đáp án đúng: "Shift elements after the insertion point to create space". Mảng chiếm một dải ô nhớ liền kề nên không có chỗ trống sẵn ở giữa; muốn chèn mà vẫn giữ thứ tự, ta tìm vị trí đúng rồi dịch mọi phần tử từ vị trí đó về sau sang phải một ô, bắt đầu dịch từ phần tử cuối để không ghi đè, sau đó đặt giá trị mới vào ô vừa trống. Phương án "Shift all elements to the left to create space at the beginning" không tạo được chỗ trống mà còn ghi đè phần tử đầu làm mất dữ liệu, và chỉ phục vụ việc chèn vào đầu. Phương án "Replace the last element with the new element" vừa xoá mất phần tử cuối vừa phá vỡ thứ tự nếu giá trị mới không phải lớn nhất. Phương án "Reorganize the array into a linked list structure" đổi hẳn kiểu cấu trúc dữ liệu, không phải việc cần làm để chèn.

Đá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: "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: "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: "Field". Bản ghi là tập hợp các thành phần có thể khác kiểu, và mỗi thành phần ấy được gọi là một trường; trường có tên riêng nên ta truy cập nó bằng tên thay vì bằng chỉ số như với mảng. Phương án "Cell" là thuật ngữ của bảng tính hay của bảng trong cơ sở dữ liệu, chỉ giao của một hàng và một cột, không phải tên gọi thành phần của bản ghi. Phương án "Word" là từ máy, đơn vị nhóm bit mà bộ xử lý xử lý một lần, thuộc tầng tổ chức bộ nhớ chứ không thuộc tầng cấu trúc dữ liệu. Phương án "Item" là từ chung chung để chỉ một phần tử bất kỳ của một tập dữ liệu, không phải tên gọi chuẩn cho thành phần của bản ghi.

Đáp án đúng: "Social relationships among users". Khi mô hình hoá một mạng xã hội bằng đồ thị, mỗi đỉnh là một người dùng và mỗi cạnh là một quan hệ giữa hai người, chẳng hạn kết bạn hay theo dõi; nhờ cách biểu diễn này, các bài toán như gợi ý người quen hay đo khoảng cách giữa hai người trở thành bài toán trên đồ thị. Phương án "Connections between computers" là một ứng dụng khác của đồ thị, nơi đỉnh là máy và cạnh là đường truyền, không phải ngữ cảnh mạng xã hội mà câu dẫn nêu. Phương án "Sorting the list of friends on social media" nói về việc sắp xếp, vốn là nhiệm vụ của thuật toán chứ không phải thứ mà đồ thị biểu diễn. Phương án "Displaying data structures" nhầm vai trò: đồ thị tự nó là một cấu trúc dữ liệu, không phải công cụ để trình bày cấu trúc dữ liệu.

Đáp án đúng: "Process Left subtree → Right subtree → Root". Trong ba cách duyệt theo chiều sâu, tên gọi được đặt theo vị trí của gốc: duyệt sau nghĩa là gốc được xử lý sau cùng, nên trình tự là đi hết cây con trái, rồi cây con phải, cuối cùng mới tới gốc. Cách này hữu ích khi phải xử lý các con trước cha, chẳng hạn giải phóng cây hoặc tính giá trị một cây biểu thức. Phương án "Process Root → Left subtree → Right subtree" là duyệt trước, vì gốc được xử lý đầu tiên. Phương án "Process Root → Right subtree → Left subtree" là duyệt trước theo chiều đảo, gốc vẫn đi đầu nên không phải duyệt sau. Phương án "Process Right subtree → Root → Left subtree" đặt gốc ở giữa, đó là duyệt giữa theo chiều đảo, cho dãy giảm dần trên cây tìm kiếm nhị phân.