NEW
Font size
WorksheetsCâu hỏi về Giải thuật và Cấu trúc dữ liệu
Total questions: 54
Worksheet time: 27mins
Nhân tố nào là nhân tố chính ảnh hưởng đến thời gian thực hiện của một giải thuật
Kích thước dữ liệu đầu vào
Máy tính
Thuật toán
Chương trình dịch
Theo cách tiếp cận của lập trình có cấu trúc, NiklausWirth đưa ra công thức thể hiện được mối liên hệ giữa cấu trúc dữ liệu và giải thuật như sau:
Thuật toán + dữ liệu đầu vào = chương trình
Thuật toán + cấu trúc dữ liệu = chương trình
Kỹ thuật lập trình + cấu trúc dữ liệu = Kết quả đầu ra.
Tất cả đều đúng
Giải thuật là … câu lênh chặt chẽ, rõ ràng và xác định các thao tác trên các đối tượng dữ liệu
Một
Hai
Nhiều
Dãy
Kiểu dữ liệu trừu tượng là…...
Kiểu dữ liệu mà người lập trình phải tự xây dựng dựa trên các kiểu dữ liệu cơ bản được cung cấp từ ngôn ngữ này.
Kiểu dữ liệu mà người lập trình phải tự xây dựng dựa trên kiểu dữ liệu không cơ bản được cung cấp từ ngôn ngữ lập trình
Kiểu dữ liệu mà người lập trình phải tự xây dựng trên các kiểu dữ liệu cơ bản được cung cấp từ ngôn ngữ lập trình
Kiểu dữ liệu mà người lập trình tự xây dựng không dựa trên kiểu dữ liệu cơ bản được cung cấp từ ngôn ngữ lập trình
Hàm đệ quy sau thực hiện công việc gì? int F(int n){if(n==0) return 1;return F(n-1) + F(n-1) + F(n-1);}
3n
n^3
3^n
3n^2
Cho hàm đê quy sau:int F(int n){if(n==0) return 1;return F(n-1) + F(n-1);}Vậy
F(5) = 32
F(5) = 10
F(5) = 25
F(5) = 5
Chọn phát biểu đúng nhất
Một chương trình gọi là đệ quy nếu trong chương trình có lời gọi đến một chương trình đệ quy khác.
Một chương trình đệ quy là chương trình lặp đi lặp lại với số lần lặp không biết trước.
Một đối tượng được gọi là đệ quy nếu nó hoặc một phần của nó được định nghĩa thông qua khái
niệm về chính nó.
Một chương trình đề quy là chương trình có chưa hàm main.
Đánh giá độ phức tạp của giải thuật là việc xác định ……và…… mà giải thuật cần để thưc hiện giải một bài toán
Khoảng thời gian, độ khó
Khoảng thời gian, độ phức tạp
Khoảng thời gian, dung lượng bộ nhớ máy tính
Độ khó, dung lượng bộ nhớ máy tính
Các kiểu dữ liệu cơ bản là……
Các kiểu dữ liệu mà người lập trình được cung cấp sẵn từ máy tính
Các kiểu dữ liệu mà người lập trình được cung cấp sẵn từ ngôn ngữ tự nhiên
Các kiểu dữ liệu mà người lập trình được cung cấp sẵn từ ngôn ngữ lập trình
Các kiểu dữ liệu mà người lập trìn được cung cấp sẵn từ ngôn ngữ này
Chỉ ra kiểu dữ liệu cơ bản:
Sinh viên
float
Hoten
Ngày sinh
Cài đặt danh sách bằng mảng có nghiã là
Dùng bản ghi có hai thành phần để lưu trữ các phần tử của danh sách
Dùng biến con trỏ lưu trữ các phần tử của danh sách.
Tất cả đều đúng.
Dùng một mảng (array) để lưu trữ liên tiếp các phần tử của danh sách bắt đầu từ vị trí đầu tiên của mảng.
Tư tưởng của giải thuật tìm kiếm nhị phân:
So sánh X lần lượt với các phần tử thứ nhất, thứ hai,… của dãy cho đến khi gặp phần tử có khoá cần tìm.
Lần lượt chia dãy thành hai dãy con dựa vào phần tử khoá, sau đó thực hiện việc tìm kiếm trên hai đoạn đã chia.
Tại mỗi bước tiến hành so sánh X với phần tử ở giữa của dãy, dựa vào bước so sánh này quyết định giới hạn dãy tìm kiếm nằm ở nửa trên, hay nửa dưới của dãy hiện hành.
Tìm kiếm dựa vào cây nhị tìm kiếm.
Tư tưởng của giải thuật tìm kiếm tuần tự
So sánh X lần lượt với các phần tử thứ nhất, thứ hai,... của dãy cho đến khi gặp phần tử có khoá cần tìm.
Tìm kiếm dựa vào cây nhị tìm kiếm: Nếu giá trị cần tìm nhỏ hơn gốc thì thực hiện tìm kiếm trên cây con trái, ngược lại ta việc tìm kiếm được thực hiện trên cây con phải.
Tại mỗi bước tiến hành so sánh X với phần tử ở giữa của dãy, Dựa vào bước so sánh này quyết định giới hạn dãy tìm kiếm nằm ở nửa trên, hay nửa dưới của dãy hiện hành.
Lần lượt chia dãy thành hai dãy con dựa vào phần tử khoá, sau đó thực hiện việc tìm kiếm trên hai đoạn đã chia.
Danh sách Đặc là:
Một tập hợp mà không cần khai báo trước số lượng phần tử khi sử dụng
Một tập hợp có thứ tự gồm một số xác định n phần tử cùng kiểu dữ liệu liên tục trong bộ nhớ và có cùng một tên (với n được gọi là độ dài hay kích thước của mảng).
Một các phần từ được xác định trước, có cùng kiểu dữ liệu và nằm rài rác trong vùng nhớ
Một tập các hợp phần tử có cùng kiểu dữ liệu và được sắp xếp theo thứ tự tăng dần.
Ý tưởng phương pháp sắp xếp nổi bọt (bubble sort) là:
Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.
Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất với phần tử thứ nhấ; Tương tự đối với phần tử nhỏ thứ hai, ba...
Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy bằng cách đẩy các phần tử lớn hơn xuống.
Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần tử nào nhỏ hơn
được đứng vị trí trên.
Ý tưởng phương pháp sắp xếp nhanh (Quick sort) là:
Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khoá (dãy con trước khoá gồm các phần tử nhỏ hơn khoá và dãy còn lại gồm các phần tử lớn hơn khoá).
Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất với phần tử thứ nhất; Tương tự đối với phần tử nhỏ thứ hai, ba...
Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.
Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu phần tử nào nhỏ hơn được đứng vị trí trên.
Trong các giải thuật sắp xếp, giải thuật nào áp dụng phương pháp "Chia để trị"?
Quick sort, Bubble sort
Qucick sort, Insert sort
Quick sort, Merge sort
Quick sort, Heap sort
Cho dãy số {6 1 3 0 5 7 9 2 8 4}. Áp dụng phương pháp sắp xếp lựa chọn (Select sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}. Dãy số thu được sau lần lặp thứ năm là:
{0 1 2 3 5 7 9 4 8 6}
{0 1 2 3 6 5 7 9 8 4}
{0 1 2 3 4 7 9 6 8 5}
{0 1 2 3 4 5 6 7 8 9}
Trong thuật toán sắp xếp nổi bọt kết thúc khi nào?
Khi các phần tử đã nằm đúng thứ tự mong muốn.
Không còn bất kì cặp liền kề trái thứ tự mong muốn
Không còn xảy ra đổi chỗ lần nào nữa
Cả A, B và C đều đúng
Định nghĩa đúng nhất về danh sách liên kết
Danh sách liên kết là tập hợp các phần từ mà giữa chúng có sự nối kết với nhau thông qua vùng liên kết của chúng
Danh sách liên kế là cấu trúc dữ liệu dạng cây
Danh sách liên kết là cấu trúc dữ liệu tự định nghĩa
Danh sách liên kết là tập hợp các phần từ liên tục trong vùng nhớ
Dấu hiệu nào dưới đây cho biết danh sách liên kết đơn rỗng:
(p->right==NULL);
(p->info==NULL);
(p==NULL);
(p->next==NULL);
Chọn câu nói đúng nhất về danh sách liên kết đôi
Vùng liên kết của 1 phần từ trong danh sách liên kết có 2 mối liên kết với 2 phần tử trước và sau nó trong danh sách
Vùng liên kết của 1 phần từ trong danh sách liên kết có 2 mối liên kết với 1 phần tử khác
Vùng liên kết của 1 phần từ trong danh sách liên kết có 1 mối liên kết với 2 phần tử khác
Vùng liên kết của 1 phần từ trong danh sách liên kết có 2 mối liên kết với 2 phần tử khác trong danh sách
Định nghĩa cấu trúc dữ liệu dạng danh sách(LIST)
danh sách là kiểu con trỏ
danh sách là tập hợp các phần tử khác kiểu
danh sách là kiểu dữ liệu mảng
danh sách là một tập hợp các phần tử có cùng một kiểu mà ta gọi là kiểu phần tử (ElementType).
Dấu hiệu nào dưới đây cho biết node p của một danh sách liên kết đơn là node cuối cùng bên phải:
(p->info!=NULL);
(p->info==NULL);
(p->next!=NULL);
(p->next==NULL);
Cho p trỏ vào nút giữa của một DSLK đôi trỏ bởi con trỏ đầu pHead và con trỏ cuối pTail, danh
sách chỉ gồm 3 nút. Để tách p ra khỏi danh sách mà danh sách vẫn nối đúng. Thực thiện những câu
lệnh nào sau đây.
p->Next->Pre=p->Next; p->Pre->Next=p->Pre.
p->Pre->Next=p->Pre; p->Next->Pre=p->Next
pHead->Next=pTail; pTail->Pre=pHead;
Tất cả đều đúng.
Để xóa con trỏ p đang trỏ vào một nút không phải là vị trí đầu trong danh sách liên kết đơn có nhiều hơn một nút. Ta cần xác định con trỏ q trỏ vào vị trí nào sau đây:
Trỏ vào vị trí đầu danh sách.
Trỏ vào vị trí cuối danh sách.
Trỏ vào nút bên trái của p và gần p nhất.
Trỏ vào nút bên phải của p và gần p nhất.
Để nối 1 node vào danh sách liên kết đơn thì các câu lệnh cần thực hiện là gì?
q = (listnode) malloc(sizeof(struct node)); q->item = x; q->next=*p;
q->next=*p; q = (listnode) malloc(sizeof(struct node)); q->item = x;
q = (listnode) malloc(sizeof(struct node)); q->next=*p; q->item = x;
q->item = x;
Phát biểu nào sau đây là đúng
Mỗi nút trong DSLK đơn chứa thành phần kết nối và một số nguyên hoặc dữ liệu của nút đó
Thành phần kết nối của một nút trong DSLK đơn luôn chứa địa chỉ của nút kết tiếp.
Trong DSLK đơn nối vòng thành phần kết nối của mỗi nút luôn trỏ vào nó.
Mỗi nút trong DSLK đôi chứa hai thành phần kết nối và thành phần dữ liệu.
Cơ chế nào dưới đây được cài đặt cho Stack:
LIFO
Tuần tự
Round Robin
FIFO
Định nghĩa cấu trúc dữ liệu Stack:
Stack là danh sách kết nối.
Stack là một danh sách đặc biệt mà phép thêm vào được thực hiện ở một đầu, và phép loại bỏ được thực hiện ở phần kia của stack.
Stack là một danh sách đặc biệt mà phép thêm vào hoặc loại bỏ một phần tử chỉ thực hiện tại một đầu gọi là đỉnh (Top) của Stack.
Stack là cấu trúc dữ liệu được cài đặt bằng con trỏ.
Trong việc xây dựng các hàm cho danh sách hạn chế hàm sau viết ra để làm gì bool FunctionEmpty(Queue pHead){return (pHead==NULL);}
Khởi tạo hàng đợi rỗng
Khởi tạo ngăn xếp rỗng
Kiểm tra ngăn xếp hoặc hàng đợi đầy
Kiểm tra hàng đợi hoặc ngăn xếp rỗng.
Cơ chế nào dưới đây được cài đặt cho hàng đợi:
FIFO
Round Robin
Tuần tự
FILO
Cho biểu thức sau: A + B - C * D + F thì biểu thức hậu tố là:
AB+CD*-F+
AB+CD-*F+
ABCD+*-F+
AB+CDF*-+
Cho biểu thức trung tố sau P=a*(b+c), biểu thức nào sau đây là biểu thức hậu tố P
ab+c*
a*bc+
ab*c+
abc+*
Để cài đặt Stack ta có thể dùng phương pháp nào sau đây:
Bằng con trỏ
Bằng mảng
Bằng con trỏ và bằng mảng
Các phương án khác đều sai
Tính chất của hàng đợi
Vào trước - ra trước" - FIFO: First In First Out.
Vào sau - ra trước" - LIFO: Last In Fist Out.
Vào trước - ra sau" - FILO: First In last Out.
Các phương án khác đều sai
Chọn định nghĩa đúng nhât về hàng đợi (Queue)
Hàng đợi là 1 danh sách, trong đó việc thêm và bớt phần tử được thực hiện ở 2 đầu khác nhau
Hàng đợi là 1 danh sách, trong đó việc thêm và bớt phần tử được thực hiện ở cùng 1 đầu
Hàng đợi là 1 danh sách liên kết đơn
Hàng đợi là 1 danh sách họat động theo cơ chế FILO(First In Last Out)
Cho biểu thức tiền tố sau P=(a+b)^2+c, biểu thức hậu tố (Q) nào sau đây là kết quả của biểu thức P.
ab+2^c+
ab2+^c+
ab+2^+c
ab+2c^+
biểu thức tiền tố sau P=(a+b)^2+c, biểu thức hậu tố (Q) nào sau đây là kết quả của biểu thức P.
ab+2^c+
ab2+^c+
ab+2^+c
ab+2c^+
Một cây nhị phân được gọi là đúng nếu:
Node gốc và tất cả các node trung gian đều có 2 node con
Giá trị khóa của node gốc bao giờ cũng lớn hơn giá trị các khóa của nhánh cây con bên phải
Giá trị khóa của node gốc bao giờ cũng lớn hơn giá trị các khóa của nhánh cây con bên trái
Node gốc và các node trung gian đều có 2 node con và các node lá đều có mức giống nhau
Chọn định nghĩa đúng nhất về cây nhị phân tìm kiếm (BST: Binary Search Tree)
BST là cây mà với mọi nút không phải là Lá có giá trị lớn hơn mọi giá trị của các nút trên cây con trái và nhỏ hơn mọi giá trị của các nút trên cây con phải
BST là cây mà với mọi nút không phải là Lá có giá trị lớn hơn giá trị của nút trên cây con trái và nhỏ hơn giá trị của nút con phải
BST là cây mà với mọi nút không phải là Lá có giá trị lớn hơn mọi giá trị của các nút trên cây con phải và nhỏ hơn mọi giá trị của các nút trên cây con trái
BST là cây nhị phân mà giá trị các nút trên cây khác nhau từng đôi một
Chọn phát biểu đúng
Cây nhị phân là cây phải có hai nhánh con
Cây nhị phân là cây mà các cây con của nó phải có hai nút
C.Cây nhị phân là cây mà mọi nút trên cây chỉ có tối đa hai nhánh con
Tất cả đều đúng
Một cây nhị phân được gọi là đúng nếu:
Node gốc và các node trung gian đều có 2 node con và các node lá đều có mức giống nhau
Giá trị khóa của node gốc bao giờ cũng lớn hơn giá trị các khóa của nhánh cây con bên trái
Giá trị khóa của node gốc bao giờ cũng lớn hơn giá trị các khóa của nhánh cây con bên phải
Node gốc và tất cả các node trung gian đều có tối đa 2 node con
Chiều cao của cây là gì?
Cấp lớn nhất của nút
Mức lớn nhất của cây
Số cây con của cây
Số lượng nút của cây
Cây nhị phân đầy đủ là?
Là cây nhị phân mà nút gốc và các nút con có tối đa hai cây con.
Là cây nhị phân mà nút gốc và tất cả các node trung gian có đúng hai node con.
Là cây nhị phân mà nút gốc có đúng hai cây con.
Là cây nhị phân mà tất cả các nút trung gian có đúng hai node con.
Cây nhị phân tìm kiếm là:
Cây rỗng.
Cây có một nút gốc
Với mọi Node: Node có tối đa hai cây con. Nội dung node cha lớn hơn nội dung node con bên trái và nhỏ hơn nội dung node con bên phải.
Tất cả đêu đúng
Chọn phát biểu đúng
Cây nhị phân là cây phải có hai nhánh con
Cây nhị phân là cây mà các cây con của nó phải có hai nút
Cây nhị phân là cây mà mọi nút trên cây chỉ có tối đa hai nhánh con
Tất cả đều đúng
Cây nhị phân cân bằng (AVL Tree) là:
Là cây nhị phân có số node thuộc nhánh cây con trái và số node thuộc nhánh cây con phải cân bằng nhau
Cây nhị phân có số node thuộc nhánh cây con trái và số node thuộc nhánh cây con phải chênh lệch nhau không quá 1.
Cây nhị phân có số node thuộc nhánh cây con trái và số node thuộc nhánh cây con phải không được chênh lệch nhau.
Là cây nhị phân mà nút gốc và tất cả các node trung gian có đúng hai node con
Cho cây bên dưới, cho biết kết quả duyệt cây theo thứ tự trước (NLR)
A. 40, 30, 25, 20, 28, 35, 32, 38, 60, 50, 70, 65, 90
B. 20, 25, 28, 30, 32, 35, 38, 40, 50, 60, 65, 70, 90
C. 20, 28, 25, 32, 38, 35, 30, 50, 65, 90, 70, 60, 40
D. 40, 30, 25, 20, 28, 35, 32, 38, 60, 90, 65, 70, 50
Cho cây bên dưới. Nếu ta muốn xóa nút mang số 30 thì giá trị của nút nào có chọn thế mạng là…
A. 20 hoặc số 28
B. 35 hoặc 25
C. 28 hoặc 32
D. 20 hoặc 38
Cho cây bên dưới. Nếu ta muốn xóa nút mang số 40 thì giá trị của nút nào có chọn thế mạng
A. 20
B. 35
C. 38
D. 65
Cho cây biểu thức sau. Duyệt cây theo thứ tự trước (NLR) ta được biểu thức nào sau đây:
A. - * + a b c /d e
B. a b + c * d e / -
C. - * a+ b c d/ e
D. + a b - * c /d e
Cho cây biểu thức sau. Duyệt cây theo thứ tự giữa (LNR) ta được biểu thức nào sau đây:
A. (a + b)* c – d/e
B. a b + c * d e / -
C. (a + b) * d – c/e
D. + a b - * c /d e
Cho cây biểu thức sau. Duyệt cây theo thứ tự sau (LRN) ta được biểu thức nào sau đây:
A. a b + c * d e / -
B. a b + dc * e- /
C. (a + b) * d – c/e
D. + a b - * c /d e
