Câu hỏi trắc nghiệm ôn tập môn Cấu trúc dữ liệu và giải thuật | Trường đại học kinh doanh và công nghệ Hà Nội

lOMoAR cPSD| 48704538
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Tổng số Nội dung câu 122 Phần 1: Cấu trúc dữ liệu cơ bản và cấu trúc dữ liệu trừu 22 tượng (STACK, QUEUE) Phần 2: Thuật toán và đánh giá độ phức 15 tạp của thuật toán
Phần 3: Giải thuật đệ quy, giải thuật sắp 55 xếp và tìm kiếm. Phần 4: Cây và cây nhị phân tìm kiếm 30
Phần 1. Cấu trúc dữ liệu cơ bản và cấu trúc dữ liệu trừu tượng (STACK, QUEUE) (22câu)
Câu 1. Các thuộc tính của một kiểu dữ liệu a. Tên kiểu dữ liệu b. Miền giá trị
c. Kích thước lưu trữ, Tập các toán tử tác động lên kiểu dữ liệu
Tất cả các thuộc tính đưa ra Đáp án: d
Câu 2. Miền giá trị của Kiểu số nguyên là: -32767 ... 32768 a. 0..32768 b. -32768 ... 32767 c. 0..32767 Đáp án: a
Câu 3. Kích thước lưu trữ kiểu số nguyên là 2 byte a. 4 byte. lOMoAR cPSD| 48704538 b. 1 byte c. 6 byte. Đáp án: a
Câu 4. Tập các toán tử kiểu số nguyên là
a. +, -, *, /, %, các phép so sánh
+, -, *, /, %, các phép so sánh, div, mod b. +, -, *, /, %
c. +, -, *, /, %, true, false Đáp án: b
Câu 5. Tên kiểu nguyên trong hệ kiểu pascal là: Integer a. Byte b. Real
c. Boolean Đáp án: a Câu 6. Khi khai báo: type T = min ...max
Trong đó min và max là cận dưới và cận trên của khoảng
T là kiểu gì? Kiểu đoạn con a. Kiểu liệt kê b. Kiểu integer
c. Không có kiểu này Đáp án: a
Câu 7. Khi khai báo trong hệ kiểu pascal
type T = (obj1, obj2, ..., objn) obj1, obj2, ...,
objn là các đối tượng nào đó T là kiểu gì? Kiểu liệt kê a. Kiểu đoạn con b. Kiểu integer c. Kiểu liệt kê
d. Không có kiểu này Đáp án: a
Câu 8. Đâu là kiểu dữ liệu có cấu trúc trong hệ kiểu pascal a. Kiểu array (mảng) b. Kiểu record (bản ghi) c.
Kiểu con trỏ Tất cả các kiểu đưa ra Đáp án: d
Câu 9. Dấu hiệu nào dưới đây cho biết danh sách liên kết đơn L là rỗng: lOMoAR cPSD| 48704538 A. (L->left == NULL) B. (L->infor == NULL) C. (L->next == NULL) D. (L == NULL) Đáp án: d
Câu 10. Để truy nhập vào từng phần tử trong danh sách móc nối đơn ta phải bắt đầu từ:
a. Phần tử đầu tiên của danh sách
b. Truy nhập trực tiếp vào phần tử đó giống mảng 1 chiều
c. Thực hiện tìm kiếm nhị phân trên danh sách móc nối đơn
d. Thực hiện tìm kiếm tuần tự từ phần tử cuối dãy Đáp án: a
Câu 11. Để tiện cho việc quản lý một danh sách móc nối đơn, ta cần phải quản lý a.
Địa chỉ phần tử đầu danh sách
b. Địa chỉ phần tử cuối danh sách
c. Thành phần thông tin của nút đầu danh sách. d. Cả a và b Đáp án: d
Câu 12. Trong danh sách móc nối đơn, để tìm kiếm một phần tử có khoá X, ta phải thực hiện tìm kiếm:
a. Tìm kiếm tuyến tính
b. Tìm kiếm nhị phân
c. Tìm kiếm trên cây nhị phân
d. Có thể bắt đầu tìm trên một thành phần bất kỳ. Đáp án: a
Câu 13. Giả sử pHead và pTail là hai con trỏ để trỏ đến phần tử đầu và cuối trong danh
sách móc nối đơn. Ban đầu danh sách rỗng. Để tạo danh sách móc nối đơn ta có thể sử
dụng cách nào trong các cách sau:
a. Chèn liên tiếp phần từ mới vào sau phần tử đang trỏ bởi pTail (chèn liên tiếp vào cuối danh sách)
b. Chèn liên tiếp phần tử mới vào đầu danh sách sau nút đang trỏ bởi pHead
c. Chèn liên tiếp phần tử mới vào giữa danh sách
d. Chèn liên tiếp phần tử mới vào trước nút trỏ bởi bởi pTail Đáp án: a
Câu14. Với cấu trúc dữ liệu của danh sách liên kết đơn lưu trữ thông tin về phòng máy
typedef struct PM { int maPM; int tongsoMay; } PHONGMAY; typedef struct Node { PHONGMAY Info; Node * PNext; } OneNode; typedef OneNode * SLLPointer;
Để quản lý danh sách liên kết đơn bằng phần tử đầu và phần tử cuối, cần định nghĩa kiểu dữ liệu: a. SLLPointer DanhSach; lOMoAR cPSD| 48704538 b. typedef struct SSLLIST { SLLPointer Phead; SLLPointer Ptail; } LIST;
c. typedef struct SSLLIST { SLLPointer Phead; SLLPointer Ptail; int total; } LIST; d.typedef struct SSLLIST { SLLPointer Phead; int total; } LIST; Đáp án: c Câu 15. Trong khai báo sau: Typedef struct SinhVien { char Ten[30]; int MaSV; }; Typedef struct SinhVienNODE { Sinhvien Info; SinhvienNODE *PNext; }SV;
Thành phần con trỏ dùng để trỏ lưu địa chỉ của phần tử kế tiếp trong danh sách móc nối đơn là: a. PNext b. Ten c. MaSV
d. Cả Ten, MaSV và Next. Đáp án: a Câu 16. Trong khai báo Typedef struct NODE { int INFO; struct NODE *Next; } NODE p; Thì biến p là:
a. Con trỏ dùng để trỏ đến địa chỉ của biến động mà mỗi biến động này gồm 2 thành
phần: Thành phần INFO có giá trị nguyên và thành phần con trỏ Next b. Là địa chỉ
của 1 nút (phần tử) trong danh sách móc nối
c. Một nút (phần tử) trong danh sách móc nối lOMoAR cPSD| 48704538
d. Một biến thuộc kiểu cấu trúc không được cấp phát vùng. Đáp án: a
Câu 17. Giải thuật Chèn phần tử có trường thông tin là X vào đầu danh sách thì thứ tự các thao tác sẽ là: Ở đây:
Getnode(P) là thủ tục xin cấp phát một biến động và cho con trỏ P trở tới
Info: Thành phần thông tin (trường thông tin hay dữ liệu) của nút một nút trong danh
sách pnext: Thành phần con trỏ dùng để móc nối đến biến động đứng sau trong danh sách l: danh sách
a. p= Getnode(X); p->pnext = l.Head→pnext; l.Head = p;
b. l.Head→pnext=p; p→pnext=l.head→pnext; p=Getnode(X);
c. p = Getnode(X); p→pnext=l.head→pnext; l.head→pnext=p;
d. p→pnext =l.head→pnext; l.head→pnext=p; p=getnode(X); Đáp án: a
Câu 18. Giải thuật Chèn phần tử có trường thông tin là X vào Cuối danh sách thì thứ tự các thao tác sẽ là:
Ở đây: Thủ tục cấp phát một biến động và cho con trỏ p trỏ tới: Getnode(x)
pnext: Thành phần con trỏ dùng để móc nối đến biến động đứng sau trong danh sách l: danh sách
a. p=Getnode(X); l.PTail->pnext = new_ele; l.Tail = new_ele ;
b. l.PTail->pnext = new_ele; l.Tail = new_ele ; p=Getnode(X);
c. l.Tail = new_ele; l.PTail->pnext = new_ele ; p=Getnode(X);
d. l.PTail->pnext = new_ele ; p=Getnode(X); l.Tail = new_ele; Đáp án: a Câu 19.
Thao tác nào dưới đây thực hiện trên ngăn xếp (stack):
A. Thêm và loại bỏ phần tử luôn B. Thêm và loại bỏ phần tử có thể thực hiện
tại vị trí đỉnh (top) thực hiện tại vị trí bất kỳ lOMoAR cPSD| 48704538
C. Thêm phần tử vào vị trí bất kỳ D. Loại bỏ phần tử tại vị trí bất kỳ Đáp án: A Câu 20.
Thao tác nào dưới đây thực hiện trên hàng đợi (queue):
A. Thêm phần tử vào lối sau B. Loại bỏ phần tử ở lối sau
C. Thêm phần tử vào lối trước D. Thêm và loại bỏ phần tử tại vị trí bất kỳ Đáp án: A
Câu 21. Kiểu cấu trúc dữ liệu Queue hoạt động theo cơ chế nào a.FIFO. b.LIFO. c.LOFI. d.FOFI. Đáp án: A
Câu 22. Cấu trúc dữ liệu nào tương ứng với LIFO a.Queue b.Linked List c.Tree d. Stack Đáp án: D
Phần 2. Thuật toán và đánh giá độ phức tạp của thuật toán (15 câu)
Câu1. Chọn câu trả lời đúng nhất về thuật toán
Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán
hoặc hành động cần thực hiện để giải quyết vấn đề đặt ra
a. Thuật toán cần có một hoặc nhiều dữ liệu ra (output), dữ liệu vào (input).
b. Thuật toán là một dãy hữu hạn các bước, tất cả các phép toán có mặt trong các bước
của thuật toán phải đủ đơn giản.
c. Thuật toán là nòng cốt của chương trình Đáp án A
Câu 2. Đặc trưng của thuật toán:
a. Mỗi thuật toán có bộ dữ liệu vào, ra tương ứng
b. Mỗi bước của thuật toán cần phải được mô tả một các chính xác
c. Tất cả các phép toán có mặt trong các bước của thuật toán phải đủ đơn giản Tất cả ý nêu ra
d. thuật toán phải dừng lại sau một số hữu hạn các bước cần thực hiện Đáp án: D
Câu 3. Đặc trưng nào của thuật toán thể hiện: Tất cả các phép toán có mặt trong các bước
của thuật toán phải đủ đơn giản Tính xác định a. Tính dừng b. Tính khả thi c. Tính đúng đắn Đáp án: a
Câu 4. sắp xếp theo thứ tự tăng dần của cấp thời gian thực hiện chương trình lOMoAR cPSD| 48704538
O(1),O(log2n),O(n),O(nlog2n)
a. O(nlog2n),O(n),O(log2n),O(1)
b. O(log2n),O(n),O(nlog2n),O(1)
c. O(n),O(nlog2n),O(1),O(log2n) Đáp án: A
Câu 5. Qui tắc tổng xác định độ phức tạp tính toán
Giả sử T1(n) và T2(n) là thời gian thực hiện của hai giai đoạn chương trình P1 và P2 mà
T1(n) = O(f(n)); T2(n) = O(g(n)) thì thời gian thực hiện đoạn P1 rồi P2 tiếp theo sẽ là
T1(n) + T2(n) = O(max(f(n), g(n))).
a. T1(n) + T2(n) = O(Min(f(n), g(n))).
b. T1(n) + T2(n) = O((f(n)+g(n))).
c. T1(n) + T2(n) = O((f(n) or g(n))). Đáp án: a
Câu 6. Trong một chương trình có 3 bước thực hiện mà thời gian thực hiện tưng bước lần
lượt là O(n2), O(n3) và O(nlog2n). thời gian thực hiện chương trình sẽ là O(n3) a. O(n2) + O(n3) + O(nlog2n) b. O(n2) c. O(nlog2n) Đáp án: a
Câu 7. Xác định độ phức tạp tính toán
Nếu tương ứng với P1 và P2 là T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện P1
và P2 lồng nhau sẽ là T1(n)T2(n) = O(f(n)g(n)) a. T1(n)T2(n) = O(f(n)+g(n))
b. T1(n)T2(n) = O(f(n)and g(n))
c. T1(n)T2(n) = O(f(n)/g(n)) Đáp án: a
Câu 8. Thời gian thực hiện các lệnh đơn: gán, đọc, viết là O(1) a. O(2) b. O(log2(n))
c. O(n) Đáp án: a Câu 9. Thời gian thực hiện lệnh hợp thành (Begin... end) được xác
định bởi quy tắc tổng a. Quy tắc nhân b. O(log2(n) c. Hằng số Đáp án: a
Câu 10. Nếu S1 và S2 là các câu lệnh và E là biểu thức logic thì if E then S1 else S2
Giả sử thời gian thực hiện các lệnh S1, S2 là O(f(n)) và O(g(n)) tương ứng. Khi đó thời
gian thực hiện lệnh if là O(max (f()n), g(n))) a. O(Min (f()n), g(n))) b. O(or( (f()n), g(n))) lOMoAR cPSD| 48704538
c. O(And (f()n), g(n))) Đáp án: a
Câu 11. Nếu S là câu lệnh và E là biểu thức logic thì while E do S
Giả sử thời gian thực hiện lệnh S (thân của while) là O(f(n)). Giả sử g(n) là số tối đa các
lần thực hiện lệnh while. Khi đó thời gian thực hiện lệnh while O(f(n)g(n)). a. O(max (f()n), g(n))) b. O(And (f()n), g(n)))
c. Quy tắc tổng Đáp án: a
Câu 12. Tính thời gian thực hiện của Hàm sau:
function Euclid (m, n: integer): integer; var r: integer ; begin r := m mod n; (1) while r<> 0 do (2) begin m := n; (3) n :=r; (4) r := m mod n; (5) end; Euclid := n; (6) end; O(log2n) a. 2log2n + 1 b. O(1) c. O(n) Đáp án: a Câu 13. Cho Hàm sau:
function Euclid (m, n: integer) :integer; var r : integer ; begin r := m mod n; (1)
while r<> 0 do (2) begin m := n; (3) n :=r; (4) r := m mod n; (5) end; Euclid := n; (6) end;
lệnh (1) có thời gian thực hiện là O(1) a. O(n) b. O(2) lOMoAR cPSD| 48704538 c. O(m) Đáp án: a Câu 14. Cho Hàm sau:
function Euclid (m, n : integer) :integer; var r : integer ; begin r := m mod n; (1)
while r<> 0 do (2) begin m := n; (3) n :=r; (4) r := m mod n; (5) end; Euclid := n; (6) end;
lệnh (6) có thời gian thực hiện là O(1) d. O(n) e. O(2) f. O(m) Đáp án: a
Câu 15. Thời gian thực hiện lệnh đơn được xác định bởi a. Hằng số d. Quy tắc nhân e. O(log2(n)
f. Quy tắc tổng Đáp án: a
Phần 3. Giải thuật đệ quy, giải thuật sắp xếp và tìm kiếm (55 câu) Câu
1. Câu nào đúng nhất trong các câu sau:
Thuật toán tìm kiếm tuyến tính là thuật toán tiến hành so sánh phần tử cần tìm(x)
lần lượt với phần tử thứ nhất, thứ hai…đến phần tử cuối cùng của mảng cho đến
khi gặp được phần tử có khoá cần tìm hoặc đến hết mảng mà không thấy x. a.
Thuật toán tìm kiếm tuyến tính là thuật toán rất đơn giản và cổ điển.
b. Thuật toán tìm kiếm tuyến tính là thuật toán tiến hành so sánh phần tử cần tìm(x) với
các phần tử của mảng cho đến khi gặp phần tử có khoá cần tìm hoặc đến hết mảng mà không thấy x. Đáp án: a
Câu 2. Nhận xét sau đây, nhận xét nào đúng:
Giải thuật tìm kiếm tuyến tính không phụ thuộc vào thứ tự các phần tử của mảng,
do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy số bất kỳ. a.
Thuật toán tìm kiếm tuyến tính dựa vào quan hệ của các phần tử mảng để định
hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được cho những dãy đã có thứ tự. lOMoAR cPSD| 48704538 b.
Giải thuật tìm kiếm tuyến tính phụ thuộc vào thứ tự các phần tử của mảng, do
vậy đây là phương pháp tìm kiếm tổng quát nhất. Đáp án: a
Câu 3. Giả sử cho dãy số như sau: 4 6 6 7 3 8 7 2 8 7
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] Phần tử cần tìm x=7
Kết thúc giải thuật, phần tử X tìm thấy nằm ở vị trí Vị trí 4 a. Ví trí 7 b. Ví trí 12 c.
Vị trí 4, 7, và 12 Đáp án: a
Câu 4. Xét mảng các số nguyên có nội dung sau:
-9 -9 -9 -9 10 15 0 3 7 7
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
Cần tìm phần tử X= -9 bằng giải thuật tìm kiếm nhị phân. Phần tử -9 ở vị trí thứ mấy
được tìm thấy (vị trí 1, 2 3 hay 4): Vị trí 2 a. Vị trí 1 b. Vị trí 3 c. Vị trí 4 Đáp án: a Câu 5.
Cho hàm tìm kiếm tuyến tính như sau int
TimKiem (int M[], int N, int X) { int k = 0; M[N] = X; while (M[k] != X) k++; if (k < N) return (k); return (-1); } Chọn câu đúng nhất:
a. Hàm sẽ trả về 0 nếu không tìm thấy phần tử có giá trị là X
b. Hàm sẽ trả về 1 nếu tìm thấy phần tử có giá trị lả X Hàm
sẽ trả về -1 nếu không tìm thấy phần tử có giá trị là X c.
Hàm sẽ trả về 1 nếu không tìm thấy phần tử có giá trị lả X Đáp án: c Câu 6. Xét thủ tục sau: lOMoAR cPSD| 48704538
int TimKiemNP (int M[], int First, int Last, int X) { if (First > Last) return (-1); int Mid = (First + Last)/2; if (X == M[Mid]) return (Mid); if (X < M[Mid])
return(TimKiemNP (M, First, Mid – 1, X)); else
return(TimKiemNP (M, Mid + 1, Last, X)); }
Lựa chọn câu đúng nhất để mô tả thủ tục trên a.
Thủ tục hỗ trợ tìm kiếm phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ First đến chỉ số Last
Thủ tục hỗ trợ tìm kiếm đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ
số từ First đến chỉ số Last b.
Thủ tục hỗ trợ tìm kiếm đệ quy phần tử có giá trị là X trên mảng các phần tử từ
chỉ số từ Last đến chỉ số First c.
Thủ tục hỗ trợ tìm kiếm không đệ quy phần tử có giá trị là X trên mảng các phần
tử từ chỉ số từ Last đến chỉ số First Đáp án: b
Câu 7: A và B chơi trò chơi đoán số, thể lệ như sau:
A nghĩ trong đầu 1 số nguyên dương X nằm trong khoảng từ 0 đến 100.
B phải đoán xem A đang nghĩ số bao nhiêu bằng cách đặt câu hỏi bạn cho A
A phải trả lời trung thực bằng 1 trong các đáp án: Lớn hơn, nhỏ hơn, bằng
Hỏi B phải hỏi ít nhất là mấy lần và dùng phương pháp tìm kiếm gì mà B có thể đoán đúng số A đang nghĩ:
7 lần hỏi và dùng tìm kiếm nhị phân a.
X lần hỏi và dùng phương pháp tìm kiếm tuần tự b.
Không thể đoán được A đang nghĩ trong đầu số gì c.
Mất 100 lần hỏi. Đáp án: a Câu 8
Cho đoạn chương trình sau:
Int timkiem(int a[], int N, int x) { Int i=0;
While ((iIf (i= =N) return -1; Else return i; }
Với mảng a= {5,10,20,40,68, 86}; N=6; x=20. Đoạn chương trình trên cho lại giá trị là: a. -1 b. 1 c. 3 d. 6 Đáp án: c Câu 9.
Cho đoạn chương trình sau:
Int timkiemtuantu(int a[], int N, int x) lOMoAR cPSD| 48704538 { Int i=0; a[N]=x; while (a[i]!=x) i++; if (i= = N ) return -1; else return i ; }
Với tham số thực như sau a={4,4,6,7,8,9}; N=6; x= 4. Chương trình trên sẽ cho lại giá trị là: a. -1 b. 1 c. 4 d. 2 Đáp án: b Câu 10.
Cho đoạn chương trình như sau:
Int timkiem_NP(int a[], int N, int x) { Int left=0, right=N-1, mid; Do { mid = (eft+right)/2; if(x=a[mid]) return mid; else if(x else left= mid+1; } while (left<=right); Return -1 }
Với tham số thực truyền vào hàm trên như sau: a={20,85, 90, 68, 78, 90}; x= 90 đoạn
chương trình trên sẽ trả lại giá trị mid bằng bao nhiêu? a. -1 b. 2 c. 5 d. 6 Đáp án: b Câu 11.
Kết quả nào đúng khi thực hiện giải thuật sau với a[]= {-3, -3, 15, -3}; n= 4; x= -3:
int FindX(int a[], int n, int x) A. 1 {int i; B. 2
for (i= n; i>= 1; i--) if (a[i]==x) return C. 3 (i); D. 4 return (-1); } Đáp án: d
Câu 12. Tư tưởng chính của giải thuật chọn trực tiếp là: a.
Ở lượt thứ i ta sẽ chọn trong dãy a[i], a[i+1], …, a[n] phần tử nhỏ nhất và
đổi chỗ nó với a[i]. Như vậy sau j đợt, j khoá nhỏ hơn đã lần lượt ở các vị trí thứ
nhất, thứ 2, …, thứ j theo đúng thứ tự sắp xếp. lOMoAR cPSD| 48704538 b.
Giả sử có dãy A[1], A[2],…, A[n], trong đó i phần tử đầu A[1], …, A[i-1] đã
được sắp xếp. Tìm vị trí để đưa phần tử A[i] vào vị trí thích hợp của đoạn đã được sắp
xếp để được dãy A[1], A[2],…, A[i] có thứ tự. c.
Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kề cận để đưa phần tử nhỏ hơn
trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành, sau đó không xét đến nó ở bước
tiếp theo. Do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i (phần tử ở vị trí i ở đúng vị trí). d.
Tại bước thứ i, xét phần tử thứ a[i]. Với mỗi phần tử a[i], xét các phần tử a[j]
nằm sau nó (j=i+1…n). Nếu a[i]>a[j] thì đổi chỗ a[i] cho a[j] Đáp án: a
Câu 13. Tư tưởng của 1 giải thuật sắp xếp như sau:
Giả sử có dãy A[1], A[2],…, A[n], trong đó i phần tử đầu A[1], …, A[i-1] đã được sắp
xếp. Tìm vị trí để đưa phần tử A[i] vào vị trí thích hợp của đoạn đã được sắp xếp để được
dãy A[1], A[2],…, A[i] có thứ tự. Hỏi giải thuật trên có tên gọi là gì:
a. Chèn trực tiếp (Insertion Sort)
b. Chọn trực tiếp (Selection Sort)
c. Nổi bọt (Bubble Sort)
d. Sắp xếp nhanh (Quick Sort) Đáp án: a
Câu 14. Đố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 Đáp án: c
Câu 15. Giả sử cần sắp xếp mảng M có N phần tử sau theo phương pháp sắp xếp chèn trực tiếp 11 16 12 75 51 54 5 73 36 52 98
Cần thực hiện ..................... chèn các phần tử vào dãy con đã có thứ tự tăng đứng đầu dãy
M để sắp xếp mảng M có thứ tự tăng dần. a. 9 lần b. 10 lần c. 8 lần d. 7 lần Đáp án: d
Câu 16. 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. lOMoAR cPSD| 48704538 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 Đáp án: a
Câu 17. Hàm mô tả sắp xếp nổi bọt (Bubble Sort) trên mảng M có N phần tử
void BubbleSort(int M[], int N) [1] { [2] int Temp; [3]
for (int I = 0; I < N-1; I++) [4]
………………………………….. [5] if (M[J] < M[J-1]) [6] { [7] Temp = M[J]; [8] M[J] = M[J-1]; [9] M[J-1] = Temp; [10] } [11] return; [12] } [13]
Lệnh nào sau đây sẽ được đưa vào dòng lệnh thứ [5] của thủ tục a.
for (int J = N-1; J > I; J++) b.
for (int J = N; J < I; J--) c.
for (int J = N-1; J > I; J--) d.
Không có dòng lệnh nào phù hợp, không cần thêm vào thuật toán vẫn chạy đúng Đáp án: c
Câu 18. Cho 1 dãy gồm các phần tử như sau: 9 6 8 2 5 3 4 7 1 10
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
Sử dụng giải thuật Quick sort để sắp xếp dãy số trên. Giả sử chọn phần tử ở giữa làm khoá
(phần tử chốt) a[5] thì sau khi phân hoạch thành 2 dãy con, ta được dãy nào sau đây?
a. 1, 4, 3, 2, 5, 8, 6, 7, 9, 10
b. 9, 6, 8, 2, 5, 3, 4, 7, 1, 10
c. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
d. 1, 6, 8, 2, 5, 3, 4, 7, 9, 10 Đáp án: a
Câu 19. Cho 1 dãy gồm các phần tử như sau: 6 8 2 7 5 3 4 1 10 14
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] lOMoAR cPSD| 48704538
Sử dụng giải thuật Quick sort để sắp xếp dãy số trên. Giả sử chọn phần tử ở giữa làm khoá
(phần tử chốt) a[5] thì ở lần đổi chỗ đầu tiên ta phải đổi chỗ như thế nào? a. Đổi chỗ A[1] cho A[8]
b. Đổi chỗ A[1] cho A[10] c. Đổi chỗ A[4] và A[6]
d. Đổi chỗ A[2] cho A[7] Đáp án: a
Câu 20. Hiệu quả của giải thuật sắp xếp Quick sort phụ thuộc vào việc chọn phần tử mốc
(khoá). Trường hợp tốt nhất xảy ra nếu mỗi lần phân hoạch đều chọn được phần tử
Median (phần tử trung vị làm khoá). Phần tử Meadian là phần tử:
a. Phần tử lớn hơn (hay bằng) một nửa số phần tử và nhỏ hơn (hay bằng) nửa số
phần tử còn lại
b. Phần tử nằm ở giữa dãy
c. Phần tử nằm ở đầu dãy
d. Phần tử nằm ở cuối dãy Đáp án: a
Câu 21. Trong các giải thuật sau, thì nhóm các giải thuật nào có cùng độ phức tạp tính toán trung bình là O(n2)
a. Quick Sort, Heap Sort và Merge Sort
b. Quick Sort, Heap Sort và Bubble Sort
c. Selection Sort, Heap Sort và Merge Sort
d. Insertion Sort, Bubble Sort và Selection Sort Đáp án: d
Câu 22. ý tưởng phương pháp sắp xếp chọn tăng dần (select sort)
a. 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. 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 bé hơn được cho lên vị trí trên.
c. 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.
d. 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... Đáp án: d
Câu 23. ý tưởng phương pháp sắp xếp nổi bọt (bubble sort) là: a.
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.
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... c.
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. d.
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. Đáp án: c
Câu 24. Ý tưởng phương pháp sắp xếp chèn (insertion sort) là: a.
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. lOMoAR cPSD| 48704538 b.
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... c.
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. d.
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. Đáp án: c
Câu 25. ý tưởng phương pháp sắp xếp nhanh (Quick sort) là: a.
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á). b.
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. c.
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... d.
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. Đáp án: a
Câu 26. Phương pháp sắp xếp nhanh (Quick sort) chính là phương pháp: a. Phân đoạn b. Trộn c. Chèn d. Vun đống Đáp án: a
Câu 27. ý tưởng phương pháp sắp xếp Trộn (Merge sort) là: a.
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.
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. c.
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... d.
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á). Đáp án: d
Câu 28. ý tưởng phương pháp sắp xếp vun đống (Heap sort) là:
a. Lần lượt tạo đống cho cây nhị phân (phần tử gốc có giá trị lớn nhất) và loại
phần tử gốc ra khỏi cây đưa vào dãy sắp xếp.
b. Tạo đống cho cây nhị phân (cây nhị phân đã được sắp xếp giảm dần).
c. 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.
d. 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 Đáp án: a lOMoAR cPSD| 48704538
Câu 29. Cây nhị phân tìm kiếm là:
a. Cây nhị phân mà mỗi nút trong cây đều thoả tính chất: giá trị của nút cha nhỏ
hơn mọi nút trên cây con trái và lớn hơn mọi nút trên cây con phảI của nó.
b. Cây nhị phân mà mỗi nút trong cây đều thoả tính chất: giá trị của nút cha lớn hơn giá trị của hai nút con.
c. Cây nhị phân thoả tính chất heap
d. Là cây nhị phân đầy đủ. Đáp án: a
Câu 30. 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ị? a.
Quick sort, Merge sort b. Quick sort, Heap sort c. Quick sort, Bubble sort
d. Qucick sort, Insert sort Đáp án: a
Câu 31. Thủ tục sau áp dụng giải thuật sắp xếp nào? Procedure F Begin For i:=1 to (n-1) do For j:=n downto (i+1) do if a[j] < a[j-1] then
begin tg:=a[j]; a[j]:=a[j-1]; a[j-1]:=tg; end; End; a. Bubble sort b. Select sort c. insert sort
d. Merge sort Đáp án: a
Câu 32. Thủ tục sau áp dụng giải thuật sắp xếp nào? Procedure F
Begin a[0]:=- ∞; for i:=2 to n do begin x:=a[i]; j:=i-1; while x
begin a[j+1]:=a[j]; j:=j-1; end; a[j+1]:=x; end; End; a. Insert sort b. Select sort c. Bubble sort d. Merge sort Đáp án: a
Câu 33. Thủ tục sau áp dụng giải thuật sắp xếp nào? lOMoAR cPSD| 48704538 Procedure F(X,b,m,n,Z) Begin i:=k; i:=b; j:=m+1; while i<=m and j<=n do
if x[i] <=x[j] then begin z[k]:=x[i]; i:=i+1; end
else begin z[k]:=x[j]; j:=j+1; end; k:=k+1;
if i>m then (zk,…,zn):= (xj,…,xn)
else (zk,…,zn):= (xi,…,xn) End; a. Merge sort b. Select sort c. Bubble sort
d. Insert sort Đáp án: a
Câu34. Thủ tục sau áp dụng giải thuật sắp xếp nào? Procedure F(a, t, s);
Begin B:= true; if tkey:=a[t]; while b do begin
i:=i+1; while a[i]<=key do i:=i+1;
j:=j -1; while a[j]>=key do j:=j-1;
if i begin tg:=a[i]; a[i]:=a[j]; a[j]:=tg; end else b:=false; end;
tg:=a[t]; a[t]:=a[j]; a[j]:=tg; call F(a, t,j- 1); cal F(a, j+1,s); end; End; a. Quick sort b. Merge sort c. Bubble sort d. Insert sort Đáp án: a
Câu 35. 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ứ hai là:
a. {0 1 2 6 5 7 9 3 8 4}
b. {0 1 2 6 5 7 9 3 4 8}
c. {0 1 2 3 4 5 6 7 8 9}
d. {0 1 3 6 5 7 9 2 8 4} Đáp án: a lOMoAR cPSD| 48704538
Câu 36. 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ứ ba là:
a. {0 1 2 3 6 5 7 9 8 4}
b. {0 1 2 6 5 7 9 3 4 8}
c. {0 1 2 3 4 5 6 7 8 9}
d. {0 1 2 6 5 7 9 3 8 4} Đáp án: a
Câu 37. 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ứ tư là:
a. {0 1 2 3 5 7 9 6 8 4}
b. {0 1 2 3 6 5 7 9 8 4}
c. {0 1 2 3 5 7 9 4 8 6}
d. {0 1 2 3 4 5 6 7 8 9} Đáp án: a
Câu 38. 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à:
a. {0 1 2 3 4 7 9 6 8 5}
b. {0 1 2 3 6 5 7 9 8 4}
c. {0 1 2 3 5 7 9 4 8 6}
d. {0 1 2 3 4 5 6 7 8 9} Đáp án: a
Câu 39. 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ứ sáu là:
a. {0 1 2 3 4 5 9 6 8 7}
b. {0 1 2 3 4 7 9 6 8 5}
c. {0 1 2 3 4 5 6 9 8 7}
d. {0 1 2 3 4 5 6 7 8 9} Đáp án: a
Câu 40. 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ứ bảy là:
a. {0 1 2 3 4 5 6 9 8 7}
b. {0 1 2 3 4 5 9 6 8 7}
c. {0 1 2 3 4 5 9 6 8 7}
d. {0 1 2 3 4 5 6 7 8 9} Đáp án: a
Câu 41. 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) tăng dần, 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ứ tám là: lOMoAR cPSD| 48704538
a. {0 1 2 3 4 5 6 7 8 9} b. {0 1 2 3 4 5 9 6 8 7} c. {0 1 2 3 4 5 9 6 8 7}
d. {0 1 2 3 4 5 6 9 8 7} Đáp án: a
Câu 42. Cho dãy số {4 7 0 9 2 5 3 1 8 6}. áp dụng phương pháp sắp xếp nổi bọt
(Bubble sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 4 7 1 9 2 5 3 6 8}.
Dãy số thu được sau lần lặp thứ hai là:
a. {0 1 4 7 2 9 3 5 6 8}
b. {0 4 7 1 9 2 5 3 6 8}
c. {0 1 2 4 7 3 9 5 6 8}
d. {0 1 2 3 4 7 5 9 6 8} Đáp án: a
Câu 43. Cho dãy số {4 7 0 9 2 5 3 1 8 6}. áp dụng phương pháp sắp xếp nổi bọt
(Bubble sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 4 7 1 9 2 5 3 6 8}.
Dãy số thu được sau lần lặp thứ ba là:
a. {0 1 2 4 7 3 9 5 6 8}
b. {0 4 7 1 9 2 5 3 6 8}
c. {0 1 4 7 2 9 3 5 6 8}
d. {0 1 2 3 4 7 5 9 6 8} Đáp án: a
Câu 44. Cho dãy số {4 7 0 9 2 5 3 1 8 6}. áp dụng phương pháp sắp xếp nổi bọt
(Bubble sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 4 7 1 9 2 5 3 6 8}.
Dãy số thu được sau lần lặp thứ bốn là:
a. {0 1 2 3 4 7 5 9 6 8}
b. {0 1 2 4 7 3 9 5 6 8}
c. {0 1 4 7 2 9 3 5 6 8}
d. {0 1 2 3 4 7 9 5 6 8} Đáp án: a
Câu 45. Cho dãy số {4 7 0 9 2 5 3 1 8 6}. áp dụng phương pháp sắp xếp nổi bọt
(Bubble sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 4 7 1 9 2 5 3 6 8}.
Dãy số thu được sau lần lặp thứ năm là:
a. {0 1 2 3 4 5 7 6 9 8}
b. {0 1 2 4 7 3 9 5 6 8}
c. {0 1 4 7 2 9 3 5 6 8}
d. {0 1 2 3 4 7 9 5 6 8} Đáp án: a
Câu 46. Cho dãy số {4 0 2 8 5 9 6 1 3 7}. áp dụng phương pháp sắp xếp chèn (Insert
sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 4 2 8 5 9 6 1 3 7}. Dãy số
thu được sau lần lặp thứ hai là:
a. {0 2 4 8 5 9 6 1 3 7}
b. {0 4 2 8 5 9 6 1 3 7}
c. {0 1 2 8 5 9 6 4 3 7}
d. {0 1 4 8 5 9 6 1 3 7} Đáp án: a