Cấu trúc dữ liệu và giải thuật

Mối quan hệ giữa cấu trúc dữ liệu và giải thuật có thể minh họa bằng đẳng thức:

• Cấu trúc dữ liệu + Giải thuật = Chương trình

• Cấu trúc dữ liệu + Chương trình = Giải thuật

• Chương trình + Giải thuật = Cấu trúc dữ liệu

• Cấu trúc dữ liệu = Chương trình

Các tiêu chuẩn đánh giá cấu trúc dữ liệu. Để đánh giá một cấu trúc dữ liệu chúng ta thường dựa vào một số tiêu chí:

• A. Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong)

• B. Cấu trúc dữ liệu phải phản ảnh đúng thực tế của bài toán

• C. Cấu trúc dữ liệu phải dễ dàng trong việc thao tác dữ liệu

• D. Cả a, b, c đều đúng

Chọn câu đúng nhất để mô tả thuật toán sắp xếp nổi bọt (Bubble Sort) trên mảng M có N phần tử:

• A. Đi từ cuối mảng về đầu mảng, trong quá trình đi nếu phần tử ở dưới (đứng phía sau) nhỏ hơn phần tử đứng ngay trên (trước) nó thì hai phần tử này sẽ được đổi chỗ cho nhau. Sau mỗi lần đi chúng ta đưa được một phần tử trồi lên đúng chỗ. Sau N–1 lần đi thì tất cả các phần tử trong mảng M sẽ có thứ tự tăng

• B. Đi từ đầu mảng về cuối mảng, trong quá trình đi nếu phần tử ở dưới (đứng phía sau) nhỏ hơn phần tử đứng ngay trên (trước) nó thì hai phần tử này sẽ được đổi chỗ cho nhau. Sau mỗi lần đi chúng ta đưa được một phần tử trồi lên đúng chỗ. Sau N lần đi thì tất cả các phần tử trong mảng M sẽ có thứ tự tăng.

• C. Đi từ cuối mảng về đầu mảng, trong quá trình đi nếu phần tử ở dưới (đứng phía sau) nhỏ hơn phần tử đứng ngay trên (trước) nó thì hai phần tử này sẽ được đổi chỗ cho nhau. Sau mỗi lần đi chúng ta đưa được một phần tử trồi lên đúng chỗ. Sau N lần đi thì tất cả các phần tử trong mảng M sẽ có thứ tự tăng

• D. Cả a, b, c đều sai

Đối với thuật toán sắp xếp chọn trực tiếp cho dãy các phần tử sau (10 pt) 16 60 2 25 15 45 5 30 33 20 Cần thực hiện ..................... chọn lựa phần tử nhỏ nhất để sắp xếp mảng M có thứ tự tăng dần.

• A. 7 lần

• B. 8 lần

• C. 9 lần

• D. 10 lần

Lựa chọn định nghĩa về danh sách đúng nhất?

• A. Danh sách là tập hợp các phần tử có kiểu dữ liệu xác định và giữa chúng có một mối liên hệ nào đó

• B. Số phần tử của danh sách gọi là chiều dài của danh sách

• C. Một danh sách có chiều dài bằng 0 là một danh sách rỗng

• D. Cả a, b, c đều đúng

Cấu trúc dữ liệu mảng có các ưu điểm nào?

• A. Việc thêm, bớt các phần tử trong danh sách đặc có nhiều khó khăn do phải di dời các phần tử khác đi qua chỗ khác

• B. Việc truy xuất và tìm kiếm các phần tử của mảng là dễ dàng vì các phần tử đứng liền nhau nên chúng ta chỉ cần sử dụng chỉ số để định vị vị trí các phần tử trong danh sách (định vị địa chỉ các phần tử)

• C. Mật độ sử dụng bộ nhớ của mảng là tối ưu tuyệt đối

• D. Câu a, b, c đúng

Định nghĩa nào là đúng với danh sách liên kết?

• A. Danh sách liên kết là cấu trúc dữ liệu dạng cây

• B. Danh sách liên kết là cấu trúc dữ liệu tự định nghĩa

• C. Danh sách liên kết là tập hợp các phần tử mà giữa chúng có một sự nối kết với nhau thông qua vùng liên kết của chúng

• D. Danh sách liên kết là tập hợp các phần tử mà đặt kề cận với nhau trong vùng nhớ

Cấu trúc dữ liệu nào tương ứng với LIFO:

• A. Queue

• B. Linked List

• C. Tree

• D. Stack

Lựa chọn câu đúng nhất về danh sách liên kết đôi (Doubly Linked List):

• A. Vùng liên kết của một phần tử trong danh sách liên đôi có 02 mối liên kết với 01 phần tử khác trong danh sách

• B. Vùng liên kết của một phần tử trong danh sách liên đôi có 01 mối liên kết với 02 phần tử khác trong danh sách

• C. Vùng liên kết của một phần tử trong danh sách liên đôi có 02 mối liên kết với 02 trước và sau nó trong danh sách

• D. Vùng liên kết của một phần tử trong danh sách liên đôi có 02 mối liên kết với phần tử đầu và cuối của danh sách

Chọn định nghĩa đúng nhất về hàng đợi (Queue):

• A. Hàng đợi còn được gọi là danh sách FILO và cấu trúc dữ liệu này còn được gọi cấu trúc FILO (First In Last Out)

• B. Hàng đợi là một danh sách mà trong đó thao tác thêm 1 phần tử vào trong danh sách được thực hiện 1 đầu này và lấy 1 phần tử trong danh sách lại thực hiện bởi đầu kia

• C. Hàng đợi là một danh sách mà trong đó thao tác thêm 1 phần tử hay hủy một phần tử trong danh sách được thực hiện 1 đầu

• D. Hàng đợi phải là một danh sách liên kết đơn