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: "7". Trong cây nhị phân, mỗi nút có nhiều nhất hai con, nên mức thứ nhất chứa tối đa một nút, mức thứ hai tối đa hai nút, mức thứ ba tối đa bốn nút; tổng cộng là 1 cộng 2 cộng 4 bằng 7. Tổng quát, cây đầy có n mức chứa tối đa 2 lũy thừa n trừ 1 nút, với n bằng 3 thì ra 8 trừ 1 bằng 7. Phương án "4" chỉ là số nút tối đa của riêng mức thứ ba, bỏ quên gốc và mức giữa. Phương án "8" là 2 lũy thừa 3, tức số nút tối đa của mức thứ tư nếu cây có thêm một mức, hoặc do dùng công thức mà quên trừ một. Phương án "10" không ứng với tổng nào trong cây nhị phân ba mức, nó chỉ là một số lớn hơn giới hạn thật.

Đáp án đúng: "Each node has at most two subtrees, called left and right.". Theo định nghĩa kiểu dữ liệu trừu tượng, cây nhị phân là cây mà mỗi nút có nhiều nhất hai cây con, và hai cây con đó được phân biệt rõ thành cây con trái và cây con phải; chính việc phân biệt trái phải làm cây nhị phân khác với cây tổng quát có hai con. Phương án "Every node must have exactly two children and each must be a prime number." sai hai chỗ: nút được phép có không, một hoặc hai con, và giá trị chứa trong nút không hề bị buộc phải là số nguyên tố. Phương án "A binary tree is only used in graphical user interfaces for drawing." sai về công dụng, vì cây nhị phân là cấu trúc dữ liệu dùng cho tìm kiếm, sắp xếp, biểu diễn biểu thức, mã nén. Phương án "Every leaf connects to every other node via hidden arcs." mô tả một đồ thị dày cung, trong khi cây chỉ có đúng một đường đi từ gốc tới mỗi nút và không có cung ẩn nào.

Đáp án đúng: "link". Mỗi phần tử của danh sách liên kết gồm hai phần: phần dữ liệu giữ giá trị, và phần liên kết giữ địa chỉ của phần tử kế tiếp; nhờ phần liên kết này mà các phần tử nằm rải rác trong bộ nhớ vẫn xâu được thành một chuỗi theo thứ tự logic. Phương án "node" là nút, tức cả gói gồm dữ liệu cộng liên kết, nên nó là vật chứa con trỏ chứ không phải bản thân con trỏ. Phương án "array" là mảng, cấu trúc lưu các phần tử liền kề nhau và định vị bằng chỉ số, chính là lựa chọn đối lập với danh sách liên kết nên không thể là thành phần của nó. Phương án "data" là phần dữ liệu trong nút, nơi giữ nội dung của phần tử, hoàn toàn không mang thông tin về vị trí phần tử sau.

Đáp án đúng: "In-order traversal". Duyệt giữa đi cây con trái trước, rồi xử lý gốc, rồi đi cây con phải. Trên cây tìm kiếm nhị phân, mọi khoá ở cây con trái nhỏ hơn khoá ở gốc và mọi khoá ở cây con phải lớn hơn, nên trình tự này lấy ra các khoá theo đúng thứ tự tăng dần. Phương án "Pre-order traversal" xử lý gốc trước khi xuống con, nên dãy thu được bám theo hình dạng cây và dùng để sao chép hay lưu lại cấu trúc, không hề được sắp. Phương án "Post-order traversal" để gốc sau cùng, phù hợp khi cần xong việc với các con trước, như giải phóng bộ nhớ hoặc tính cây biểu thức. Phương án "Level-order traversal" đi theo từng mức bằng hàng đợi, cho thứ tự theo độ sâu của nút chứ không theo quan hệ lớn nhỏ giữa các khoá.

Đáp án đúng: "2". Giới hạn hai con là chính điều làm nên tên gọi cây nhị phân: mỗi nút được phép có không con, một con hoặc nhiều nhất hai con, và nếu có hai thì phân biệt thành con trái và con phải. Phương án "1" là một trường hợp được phép xảy ra chứ không phải mức tối đa; cây mà mọi nút chỉ có một con thì suy biến thành một chuỗi giống danh sách liên kết. Phương án "3" ứng với cây tam phân, một dạng cây nhiều nhánh khác, không còn là cây nhị phân. Phương án "Any number of children" mô tả cây tổng quát, nơi số con của mỗi nút không bị chặn; cây nhị phân chính là trường hợp riêng được đặt thêm ràng buộc để các giải thuật duyệt và tìm kiếm trở nên đơn giản và hiệu quả.

Đáp án đúng: "Data is stored in the order in which it is entered and can only be accessed sequentially". Tệp tuần tự ghi các bản ghi nối tiếp theo đúng thứ tự đưa vào và không có cấu trúc tra cứu nào kèm theo, nên muốn tới bản ghi thứ n thì phải đi qua các bản ghi trước nó. Phương án "Data is stored in random order within the file, and access to specific records is achieved using a key or index" mô tả truy cập trực tiếp theo khoá, đặc điểm của tệp băm hoặc tệp chỉ mục. Phương án "Data is stored using a linked list structure, where each record contains a pointer to the location of the next record in the sequence" nói về cấu trúc liên kết bằng con trỏ, không phải cách tổ chức tệp tuần tự vốn dựa vào vị trí liền kề. Phương án "Data is organized with an index that allows for quick searching and retrieval of records based on specific keys or identifiers" chính là định nghĩa tệp chỉ mục.

Đáp án đúng: "Hashed files". Tệp băm dùng một hàm băm biến khoá của bản ghi thành địa chỉ lưu trữ, nên từ khoá có thể tính ra ngay chỗ cần đọc mà không phải dò tìm, đổi lại phải có cách xử lý khi hai khoá rơi vào cùng địa chỉ. Phương án "Sequential files" ghi bản ghi theo thứ tự nhập và chỉ truy cập lần lượt, hoàn toàn không có cơ chế tính địa chỉ. Phương án "Indexed files" cũng truy cập trực tiếp được, nhưng dựa vào một bảng chỉ mục lưu cặp khoá và địa chỉ rồi tìm kiếm trên bảng đó, tức tra cứu chứ không tính bằng hàm băm. Phương án "Binary files" chỉ nói nội dung tệp được lưu ở dạng nhị phân thô thay vì văn bản; đó là cách mã hoá nội dung, không phải cách tổ chức để tìm kiếm bản ghi.

Đáp án đúng: "When two different data items are assigned the same hash value, leading to the same storage location". Hàm băm nén một miền khoá rất rộng về một miền địa chỉ hẹp, nên không thể tránh được việc hai khoá khác nhau cho cùng một kết quả băm và cùng trỏ vào một ô lưu trữ; đó là xung đột địa chỉ, và tệp băm phải có phương pháp giải quyết như dò tuyến tính hay vùng tràn. Phương án "When data cannot be accessed due to file corruption" nói về tệp bị hỏng, một sự cố vật lý hoặc logic ở mức lưu trữ, không liên quan tới cách tính địa chỉ. Phương án "When a file grows beyond its maximum size" là tình trạng tệp vượt dung lượng cấp cho nó, một vấn đề về sức chứa. Phương án "When an index points to a non-existent location in a file" mô tả chỉ mục trỏ sai, lỗi riêng của tệp chỉ mục, trong khi xung đột là chuyện của hàm băm.